AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

双向链表的C实现

2014-07-12 1495
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介：

双向链表需要定义一个结构体，结构体有3个属性

typedef struct __Node{
    int data;    数据
    struct __Node *pre;    指向前一个结点指针
    struct __Node *next;    指向下一个结点指针
}Node;

其中 pre和next指针是嵌套定义。

 

一般链表定义一个头指针

Node *head；

指向链表第一个结点，如果链表为空的话，那么head == NULL。

 

双向链表一般分为init，insert, delete, search, destroy等几种操作

1、init

初始化：将头指针head置为NULL即可

 

2、insert

插入：这里我只实现了在表头位置插入新元素。在表头位置插入元素的话，需要注意区别处理空表和非空表的情况。

1）空表的话，因为有init过程，所以head为NULL，新元素的next指针指向head（NULL），同时设置新元素的pre指针为NULL即可。

2）非空表的话，需要设置以前的头结点元素的pre指针，因为头结点的pre指针都是NULL。其他和空表一样操作。

 

如果要实现在链表的指定位置插入的话，需要先遍历链表找到那个位置，然后再插入。

 

3、delete

删除：这里我实现了删除第一个元素和删除指定的元素。其中删除指定的元素需要查找。

 

4、search

查找：遍历链表进行查找即可

 

5、destroy

销毁：将每个结点开辟的内存分别释放，最后将头结点指针head置为NULL即可。

 

在以上操作过程中，要注意当链表非空时，一定要保证尾结点的next域为NULL，头结点的pre域为NULL，否则容易导致错误！

 

C语言实现代码如下：

[cpp]  view plain copy
  1. #include <stdio.h>  
  2. #include <stdlib.h>  
  3. //定义结点  
  4. typedef struct __Node{  
  5.     int data;  
  6.     struct __Node *pre;  
  7.     struct __Node *next;  
  8. }Node;  
  9. //定义带头结点的双向链表  
  10. typedef struct __doublyLinkedList{  
  11.     Node * head;  
  12. }dLinkedList;  
  13. //初始化：头结点置空  
  14. void init(dLinkedList *L){  
  15.     if(L == NULL){  
  16.         printf("链表异常/n");  
  17.         return;  
  18.     }  
  19.     L->head = NULL;  
  20. }  
  21. //  
  22. void insert(dLinkedList *L, int data){  
  23.     Node *p = NULL;  
  24.     if(L == NULL){  
  25.         printf("双向链表不存在/n");  
  26.         return;  
  27.     }  
  28.       
  29.     p = (Node*)malloc(sizeof(Node));  
  30.     if(p == NULL){  
  31.         printf("内存分配失败!/n");  
  32.         return;  
  33.     }  
  34.     p->data = data;  
  35.     p->next = L->head;  
  36.     if(L->head != NULL){  
  37.         L->head->pre = p;  
  38.     }  
  39.     p->pre = NULL;  
  40.     L->head = p;  
  41. }  
  42. Node *search(dLinkedList L, int data){  
  43.     Node *p = NULL;  
  44.     if(L.head == NULL){  
  45.         printf("链表为空/n");  
  46.         return NULL;  
  47.     }  
  48.     p = L.head;  
  49.       
  50.     while(p != NULL && p->data != data){  
  51.         p = p->next;  
  52.     }  
  53.     if(p != NULL){  
  54.         printf("查找值为 %d的元素成功/n", data);  
  55.         return p;  
  56.     }  
  57.     else{  
  58.         printf("查找值为 %d的元素失败/n", data);  
  59.         return NULL;  
  60.     }  
  61. }  
  62. void deleteFirstData(dLinkedList *L){  
  63.     Node *p = NULL;  
  64.     if(L == NULL){  
  65.         printf("双向链表异常!/n");  
  66.         return;  
  67.     }  
  68.     if(L->head == NULL){  
  69.         printf("双向链表为空!/n");  
  70.         return;  
  71.     }  
  72.       
  73.     p = L->head;  
  74.     //only one element  
  75.     if(p->next == NULL){  
  76.         L->head = NULL;  
  77.         free(p);  
  78.         p = NULL;  
  79.         printf("成功删除第一个元素!/n");  
  80.         return;  
  81.     }  
  82.     else{  
  83.         L->head = p->next;  
  84.         L->head->pre = NULL;  
  85.         free(p);  
  86.         p = NULL;  
  87.         printf("成功删除第一个元素!/n");  
  88.         return;  
  89.     }  
  90.       
  91. }  
  92. void deleteData(dLinkedList *L, int data){  
  93.     Node *p = NULL;  
  94.     Node *pre = NULL;  
  95.     printf("删除查找中.../n");  
  96.     if((p = search(*L, data)) == NULL){  
  97.         printf("删除值为 %d的元素失败/n", data);  
  98.         return;  
  99.     }  
  100.     else{  
  101.         //first element  
  102.         if(p == L->head){  
  103.             deleteFirstData(L, data);  
  104.             return;  
  105.         }  
  106.         //last element  
  107.         else if(p->next == NULL){  
  108.             pre = p->pre;  
  109.             pre->next = NULL;  
  110.             free(p);  
  111.             p = NULL;  
  112.             printf("删除最后一个元素成功/n/n");  
  113.             return;  
  114.         }  
  115.         else{  
  116.             pre = p->pre;  
  117.             pre->next = p->next;  
  118.             p->next->pre = pre;  
  119.             free(p);  
  120.             p = NULL;  
  121.             printf("删除值为 %d的元素成功/n/n", data);  
  122.             return;  
  123.         }  
  124.     }  
  125. }  
  126. void traversal(dLinkedList L){  
  127.     Node *p = NULL;  
  128.     if(L.head == NULL){  
  129.         printf("双向链表为空!/n");  
  130.         return;  
  131.     }  
  132.     p = L.head;  
  133.     while(p != NULL){  
  134.         printf("%d ", p->data);  
  135.         p = p->next;  
  136.     }  
  137.     printf("/n遍历成功/n/n");  
  138. }  
  139. void destroy(dLinkedList *L){  
  140.     Node *p = NULL;  
  141.     Node *temp = NULL;  
  142.     if(L == NULL){  
  143.         printf("链表异常/n");  
  144.         return;  
  145.     }  
  146.     printf("开始销毁链表.../n");  
  147.     p = L->head;  
  148.     while(p != NULL){  
  149.         temp = p;  
  150.         p = p->next;  
  151.         free(temp);  
  152.         temp = NULL;  
  153.     }  
  154.     L->head = NULL;  
  155.     printf("销毁成功!/n");  
  156. }  
  157. int main(int argc, char **args){  
  158.     dLinkedList L;  
  159.     int i;  
  160.     memset(&L, 0, sizeof(dLinkedList));  
  161.     init(&L);  
  162.     traversal(L);  
  163.     for(i=0;i<20;++i){  
  164.         insert(&L, i);  
  165.     }  
  166.     traversal(L);  
  167.     deleteFirstData(&L);  
  168.     deleteFirstData(&L);  
  169.     traversal(L);  
  170.       
  171.     deleteFirstData(&L);  
  172.     deleteData(&L, 10);  
  173.     deleteData(&L, 16);  
  174.     deleteData(&L, 0);  
  175.     traversal(L);  
  176.       
  177.     insert(&L, 100);  
  178.     insert(&L, 99);  
  179.     insert(&L, 98);  
  180.     insert(&L, 97);  
  181.     traversal(L);  
  182.     deleteData(&L, 99);  
  183.     deleteData(&L, 97);  
  184.     deleteData(&L, 96);  
  185.     traversal(L);  
  186.     destroy(&L);  
  187.     return 0;  
  188. }  

 

输出如下

 

双向链表为空!
19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
遍历成功

成功删除第一个元素!
成功删除第一个元素!
17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
遍历成功

成功删除第一个元素!
删除查找中...
查找值为 10的元素成功
删除值为 10的元素成功

删除查找中...
查找值为 16的元素成功
成功删除第一个元素!
删除查找中...
查找值为 0的元素成功
删除最后一个元素成功

15 14 13 12 11 9 8 7 6 5 4 3 2 1
遍历成功

97 98 99 100 15 14 13 12 11 9 8 7 6 5 4 3 2 1
遍历成功

删除查找中...
查找值为 99的元素成功
删除值为 99的元素成功

删除查找中...
查找值为 97的元素成功
成功删除第一个元素!
删除查找中...
查找值为 96的元素失败
删除值为 96的元素失败
98 100 15 14 13 12 11 9 8 7 6 5 4 3 2 1
遍历成功

开始销毁链表...
销毁成功!
Press any key to continue

文章标签：
机器学习/深度学习
C++
C语言
this_is_bill
目录
相关文章
爱吃香蕉的猫
|
8天前
|
存储
双向链表
单链表每个结点有一个指针域和一个数据域，要访问任何结点都需知道头结点，不能逆着进行。双向链表则添加了一个指针域，通过两个指针域分别指向结点的前一个结点和后一个结点。这样的话，可以通过双链表的任何结点访问到它的前一个结点和后一个结点。 两个指针域一个存储直接后继结点的地址，一般称为右链域，另一个存储直接前驱结点，一般称为左链域。
爱吃香蕉的猫
18 4
禁默
|
1月前
|
存储
双向链表（详解）
双向链表（详解）
禁默
25 1
waves浪游
|
5月前
|
存储
双向链表专题
双向链表专题
waves浪游
43 6
风掣长空
|
5月前
双向链表的实现
双向链表的实现
风掣长空
21 0
过。
|
6月前
秒懂双向链表
秒懂双向链表
过。
28 0
pearlthriving
|
6月前
|
存储
双向链表介绍
带头链表⾥的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这⾥“放哨的”。哨兵位存在的意义：避免链表出现死循环。
pearlthriving
37 0
码哥字节
|
6月前
|
Java
7.双向链表最佳实现
7.双向链表最佳实现
码哥字节
57 1
起飞的风筝
|
6月前
|
存储
【双向链表】数据结构双向链表的实现
【双向链表】数据结构双向链表的实现
起飞的风筝
53 0
算精通
|
存储 算法 搜索推荐
双向链表
双向链表是一种链式存储结构，每个节点包含两个指针，分别指向其前驱和后继。相比于单向链表，双向链表可以在常数时间内向前或向后遍历整个链表。因此，双向链表在需要频繁遍历链表的场景中具有优势。
算精通
56 7
无聊看看天T
|
6月前
|
存储
双向链表的操作
双向链表的操作
无聊看看天T
51 0