数据结构—线性结构—(特殊链表)

红太狼 2023-07-19 10:45 17阅读 0赞

### 目录 ###

*   *  双链表：
     *   *  插入操作
         *  删除操作：
     *  循环链表：
     *   *  循环单链表
         *  循环双链表：
         *  判空条件：
     *  静态链表：

## 双链表： ##

由于单链表在插入删除某元素操作时时间复杂度过高  
所以在单链表的基础上拓展为双链表  
![在这里插入图片描述][20200330160807664.png]  
![在这里插入图片描述][20200330161248989.png]

typedef struct DNode{ 
    	ElemType data;
    	struct DNode *prior *next;
    }DNode, *DLinklist;

### 插入操作 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][20200330171720330.png]

### 删除操作： ###

![在这里插入图片描述][20200330171932917.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][20200330172023801.png]

## 循环链表： ##

如果在单链表中，我们只知道单链表的尾指针，不知道单链表的头指针

那么我们无法通过尾指针来获取头指针

（所以我们引入循环链表）

### 循环单链表 ###

![在这里插入图片描述][20200330172501993.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 3]

### 循环双链表： ###

![在这里插入图片描述][20200330172710324.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 4]

### 判空条件： ###

> 循环单链表：当 L -> next == L; 时为空  
> 循环双链表：当L -> next == L&&L -> prior == L 时为空

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 5]

## 静态链表： ##

用数组存储元素，用数组下标当作地址

最后一个元素所连接的地址为-1

一般用于没有指针的高级语言当中

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 6]

[20200330160807664.png]: /images/20230528/c06be6374e184a79acd7c5bcbf4f60a3.png
[20200330161248989.png]: /images/20230528/5a20944fa02b4b1d8cbf02cfce05e632.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70]: /images/20230528/1602cfa9f6a14bb9843498dc14c18f4d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 1]: /images/20230528/0b485feb04df4466a925678742c231e3.png
[20200330171720330.png]: /images/20230528/ea18b8aa64234dbbbf1bed4f44ebbbce.png
[20200330171932917.png]: /images/20230528/ad899c0e65e54f46aa538f28ec1e5301.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 2]: /images/20230528/72385ff4fd68439fa7c22e50a3ecbfbc.png
[20200330172023801.png]: /images/20230528/6cac5f4cb31449de9eac4c0fab8db0e4.png
[20200330172501993.png]: /images/20230528/3ccea44a56484c20830b278d45ac6609.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 3]: /images/20230528/c7e37179f8f54f62bad7602c199e19ca.png
[20200330172710324.png]: /images/20230528/48608946ea7e4cc3a337d3c6019a239b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 4]: /images/20230528/870ef3449079412e91fda7832304c56f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 5]: /images/20230528/c3b0f96eb57d4878adc7a45bc30ab802.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNjUyMzI3_size_16_color_FFFFFF_t_70 6]: /images/20230528/5781cd50a29848f0becd50b6402c7611.png