閱讀158 返回首頁    go 技術社區[雲棲]

雙向鏈表的C實現

雙向鏈表需要定義一個結構體，結構體有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語言實現代碼如下：

  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

最後更新：2017-04-03 05:39:11

  上一篇：go HTML 基礎
  下一篇：go Binder in Java