日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時(shí)間：8:30-17:00
你可能遇到了下面的問(wèn)題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷解決方案
【數(shù)據(jù)結(jié)構(gòu)之鏈表】詳細(xì)圖文教你花樣玩鏈表

0. 提要鉤玄

 前面在文章【數(shù)據(jù)結(jié)構(gòu)之鏈表】看完這篇文章我終于搞懂鏈表了中已經(jīng)介紹了鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，介紹了鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的最基本(簡(jiǎn)單)實(shí)現(xiàn)——單向鏈表。

單向鏈表，顧名思義，它是單向的。

因?yàn)閱捂湵淼拿總€(gè)結(jié)點(diǎn)只有一個(gè)數(shù)據(jù)域和一個(gè)指針域，而該指針域只存儲(chǔ)了下一個(gè)結(jié)點(diǎn)的地址，所以我們只能通過(guò)某結(jié)點(diǎn)找到其直接后繼結(jié)點(diǎn)，卻不能通過(guò)某節(jié)點(diǎn)找到其直接前驅(qū)結(jié)點(diǎn)。

此外，由于單鏈表到尾結(jié)點(diǎn)(鏈表的最后一個(gè)結(jié)點(diǎn))結(jié)束，所以尾結(jié)點(diǎn)的指針域是 NULL，以此來(lái)表示鏈表的終止，這就導(dǎo)致我們遍歷到尾結(jié)點(diǎn)的時(shí)候，如果想再次遍歷，只能手動(dòng)回到頭結(jié)點(diǎn)再開(kāi)始遍歷。

為了彌補(bǔ)單鏈表的上面兩個(gè)缺點(diǎn)，下面介紹兩種鏈表，它們都是單鏈表的變形，如果你理解了單鏈表，那么會(huì)很容易理解這兩種變形。

目錄

1. 單向循環(huán)鏈表

1.1. 結(jié)構(gòu)

單鏈表的尾結(jié)點(diǎn)的指針域是 NULL，所以單鏈表到此終止。如果我們使用單鏈表的尾結(jié)點(diǎn)的指針域存儲(chǔ)頭結(jié)點(diǎn)的地址，即尾結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)為頭結(jié)點(diǎn)，如此一來(lái)，單鏈表就構(gòu)成了一個(gè)環(huán)(循環(huán))，稱之為單項(xiàng)循環(huán)鏈表。

1.2. 實(shí)現(xiàn)思路

單向循環(huán)鏈表是由單鏈表進(jìn)化而來(lái)的，算是單鏈表的“兒子”，所以單鏈表的那一套結(jié)構(gòu)對(duì)于單向循環(huán)鏈表來(lái)說(shuō)完全適用，從上圖你也可以看出，結(jié)構(gòu)并無(wú)較大改變，二者所不同只在尾結(jié)點(diǎn)，所以我們只需要在尾結(jié)點(diǎn)和與尾結(jié)點(diǎn)相關(guān)的操作上下功夫就行了。

因此，單向循環(huán)鏈表的結(jié)構(gòu)體和單鏈表的結(jié)構(gòu)體相同。

 
 
 
 
    
  
  
  
  
  1. /*單向循環(huán)鏈表的結(jié)點(diǎn)的結(jié)構(gòu)體*/
    2. 
  
  
  
  
  2. typedef struct _Node {
    3. 
  
  
  
  
  3.     int data; //數(shù)據(jù)域：存儲(chǔ)數(shù)據(jù)
    4. 
  
  
  
  
  4.     struct _Node *next; //指針域：存儲(chǔ)直接后繼結(jié)點(diǎn)的地址
    5. 
  
  
  
  
  5. } Node;
    6.

為了統(tǒng)一對(duì)空鏈表和非空鏈表的操作，我們使用帶頭結(jié)點(diǎn)的鏈表來(lái)實(shí)現(xiàn)它。

1.3. 空鏈表及初始化

一個(gè)空鏈表如圖所示，只有一個(gè)頭指針和頭結(jié)點(diǎn)：

空鏈表

頭結(jié)點(diǎn)的指針域指向其本身構(gòu)成一個(gè)循環(huán)，我們可以借此來(lái)判斷鏈表是否為空。

 
 
 
 
    
  
  
  
  
  1. if (head->next == head) {
    2. 
  
  
  
  
  2.     printf("空鏈表。\n");
    3. 
  
  
  
  
  3. }
    4.

想要初始化一個(gè)空鏈表很簡(jiǎn)單，創(chuàng)造頭結(jié)點(diǎn)，使頭結(jié)點(diǎn)的 next 指針指向其自身即可：

 
 
 
 
    
  
  
  
  
  1. Node *create_node(int elem)
    2. 
  
  
  
  
  2. {
    3. 
  
  
  
  
  3.     Node *new = (Node *) malloc(sizeof(Node));
    4. 
  
  
  
  
  4.     new->data = elem;
    5. 
  
  
  
  
  5.     new->next = NULL;
    6. 
  
  
  
  
  6.     return new;
    7. 
  
  
  
  
  7. }
    8. 
  
  
  
  
  8. 
  
  
  
  
  9. /**
    10. 
  
  
  
  
  10.  * 初始化鏈表
    11. 
  
  
  
  
  11.  * p_head: 指向頭指針的指針
    12. 
  
  
  
  
  12.  */
    13. 
  
  
  
  
  13. void init(Node **p_head)
    14. 
  
  
  
  
  14. {
    15. 
  
  
  
  
  15.     //創(chuàng)建頭結(jié)點(diǎn)
    16. 
  
  
  
  
  16.     Node *head_node = create_node(0);
    17. 
  
  
  
  
  17.     //頭指針指向頭結(jié)點(diǎn)
    18. 
  
  
  
  
  18.     *p_head = head_node;
    19. 
  
  
  
  
  19.     //頭結(jié)點(diǎn)的next指針指向其本身，構(gòu)成環(huán)
    20. 
  
  
  
  
  20.     head_node->next = head_node;
    21. 
  
  
  
  
  21. }
    22.

1.4. 插入操作

這里只演示頭插法和尾插法

【頭插法】

因?yàn)閹ь^結(jié)點(diǎn)，所以不需要考慮是否為空鏈表。下圖是向空鏈表中頭插兩個(gè)元素的過(guò)程：

單向循環(huán)鏈表頭插法過(guò)程

 
 
 
 
    
  
  
  
  
  1. /**
    2. 
  
  
  
  
  2.  * 頭插法，新結(jié)點(diǎn)為頭結(jié)點(diǎn)的直接后繼
    3. 
  
  
  
  
  3.  * p_head: 指向頭指針的指針
    4. 
  
  
  
  
  4.  * elem: 新結(jié)點(diǎn)的數(shù)據(jù)
    5. 
  
  
  
  
  5.  */
    6. 
  
  
  
  
  6. void insert_at_head(Node **p_head, int elem)
    7. 
  
  
  
  
  7. {
    8. 
  
  
  
  
  8.     Node *new = create_node(elem);
    9. 
  
  
  
  
  9.     Node *head_node = *p_head; //頭結(jié)點(diǎn)
    10. 
  
  
  
  
  10.     //新結(jié)點(diǎn)插入頭結(jié)點(diǎn)之后
    11. 
  
  
  
  
  11.     new->next = head_node->next;
    12. 
  
  
  
  
  12.     head_node->next = new;
    13. 
  
  
  
  
  13. }
    14.

【尾插法】

因?yàn)闉榱吮M量簡(jiǎn)單，所以我們并沒(méi)有設(shè)置指向尾結(jié)點(diǎn)的尾指針，所以在尾插之前，需要先借助某個(gè)指針，遍歷至尾結(jié)點(diǎn)，然后再插入。

 
 
 
 
    
  
  
  
  
  1. /**
    2. 
  
  
  
  
  2.  * 尾插法：新插入的結(jié)點(diǎn)始終在鏈表尾
    3. 
  
  
  
  
  3.  * p_head: 指向頭指針的指針
    4. 
  
  
  
  
  4.  * elem: 新結(jié)點(diǎn)的數(shù)據(jù)
    5. 
  
  
  
  
  5.  */
    6. 
  
  
  
  
  6. void insert_at_tail(Node **p_head, int elem)
    7. 
  
  
  
  
  7. {
    8. 
  
  
  
  
  8.     Node *new = create_node(elem);
    9. 
  
  
  
  
  9.     Node *head_node = *p_head; //頭結(jié)點(diǎn)
    10. 
  
  
  
  
  10.     Node *tail = head_node; //tail指針指向頭結(jié)點(diǎn)
    11. 
  
  
  
  
  11.     while (tail->next != head_node) { //tail遍歷至鏈表尾
    12. 
  
  
  
  
  12.         tail = tail->next;
    13. 
  
  
  
  
  13.     }
    14. 
  
  
  
  
  14.     //尾插
    15. 
  
  
  
  
  15.     new->next = tail->next;
    16. 
  
  
  
  
  16.     tail->next = new;
    17. 
  
  
  
  
  17. }
    18.

1.5. 刪除操作

刪除的本質(zhì)是“跳過(guò)”待刪除的結(jié)點(diǎn)，所以我們要找到待刪除結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，然后讓其直接前驅(qū)結(jié)點(diǎn)的 next 指針指向其直接后繼結(jié)點(diǎn)，以此來(lái)“跳過(guò)”待刪除結(jié)點(diǎn)，最后保存其數(shù)據(jù)域，釋放結(jié)點(diǎn)，即完成刪除。

這里只演示頭刪法。

因?yàn)閯h除的是頭結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)，所以我們不必再費(fèi)力尋找待刪除結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)了。

單向循環(huán)鏈表頭刪法過(guò)程

 
 
 
 
    
  
  
  
  
  1. /**
    2. 
  
  
  
  
  2.  * 頭刪法：刪除頭結(jié)點(diǎn)之后的結(jié)點(diǎn)
    3. 
  
  
  
  
  3.  * p_head: 指向頭指針的指針
    4. 
  
  
  
  
  4.  * elem: 指向保存數(shù)據(jù)變量的指針
    5. 
  
  
  
  
  5.  */
    6. 
  
  
  
  
  6. void delete_from_head(Node **p_head, int *elem)
    7. 
  
  
  
  
  7. {
    8. 
  
  
  
  
  8.     Node *head_node = *p_head; //頭結(jié)點(diǎn)
    9. 
  
  
  
  
  9.     if (head_node->next == head_node) {
    10. 
  
  
  
  
  10.         printf("空鏈表，無(wú)元素可刪。\n");
    11. 
  
  
  
  
  11.         return;
    12. 
  
  
  
  
  12.     }
    13. 
  
  
  
  
  13.     Node *first_node = head_node->next; //首結(jié)點(diǎn)：頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
    14. 
  
  
  
  
  14.     *elem = first_node->data; //保存被刪除結(jié)點(diǎn)的數(shù)據(jù)
    15. 
  
  
  
  
  15.     head_node->next = first_node->next; //刪除結(jié)點(diǎn)
    16. 
  
  
  
  
  16.     free(first_node); //釋放
    17. 
  
  
  
  
  17. }
    18.

1.6. 遍歷操作

我們可以一圈又一圈地循環(huán)遍歷鏈表，下面是循環(huán)打印 20 次結(jié)點(diǎn)地代碼：

 
 
 
 
    
  
  
  
  
  1. /**
    2. 
  
  
  
  
  2.  * 循環(huán)打印20次結(jié)點(diǎn)
    3. 
  
  
  
  
  3.  */
    4. 
  
  
  
  
  4. void output_20(Node *head)
    5. 
  
  
  
  
  5. {
    6. 
  
  
  
  
  6.     if (head->next == head) {
    7. 
  
  
  
  
  7.         printf("空鏈表。\n");
    8. 
  
  
  
  
  8.         return;
    9. 
  
  
  
  
  9.     }
    10. 
  
  
  
  
  10.     Node *p = head->next;
    11. 
  
  
  
  
  11.     for (int i = 0; i <= 20; i++) {
    12. 
  
  
  
  
  12.         if (p != head) { //不打印頭結(jié)點(diǎn)
    13. 
  
  
  
  
  13.             printf("%d ", p->data);
    14. 
  
  
  
  
  14.         }
    15. 
  
  
  
  
  15.         p = p->next;
    16. 
  
  
  
  
  16.     }
    17. 
  
  
  
  
  17.     printf("\n");
    18. 
  
  
  
  
  18. }
    19.

2. 雙向鏈表

2.1. 結(jié)構(gòu)

顧名思義，雙向鏈表，就是有兩個(gè)方向，一個(gè)指向前，一個(gè)指向后。這樣我們就彌補(bǔ)了單鏈表的某個(gè)結(jié)點(diǎn)只能找到其直接后繼的缺陷。如圖所示：

雙向鏈表

2.2. 實(shí)現(xiàn)思路

為了實(shí)現(xiàn)能指前和指后的效果，只靠 next 指針肯定是不夠的，所以我們需要再添加一個(gè)指針 —— prev，該指針指向某結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)。

 
 
 
 
    
  
  
  
  
  1. /*雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)體*/
    2. 
  
  
  
  
  2. typedef struct _Node {
    3. 
  
  
  
  
  3.     int data; //數(shù)據(jù)域
    4. 
  
  
  
  
  4.     struct _Node *prev; //指向直接前驅(qū)結(jié)點(diǎn)的指針
    5. 
  
  
  
  
  5.     struct _Node *next; //指向直接后繼結(jié)點(diǎn)的指針
    6. 
  
  
  
  
  6. } Node;
    7.

2.3. 空鏈表及初始化

雙向鏈表的空鏈表如圖所示：

雙向空鏈表

要初始化一個(gè)這樣的空鏈表，需要?jiǎng)?chuàng)造出頭結(jié)點(diǎn)，然后將兩個(gè)指針域置空即可：

 
 
 
 
    
  
  
  
  
  1. Node *create_node(int elem)
    2. 
  
  
  
  
  2. {
    3. 
  
  
  
  
  3.     Node *new = (Node *)malloc(sizeof(Node));
    4. 
  
  
  
  
  4.     new->data = elem;
    5. 
  
  
  
  
  5.     new->prev = NULL;
    6. 
  
  
  
  
  6.     new->next = NULL;
    7. 
  
  
  
  
  7.     return new;
    8. 
  
  
  
  
  8. }
    9. 
  
  
  
  
  9. 
  
  
  
  
  10. void init(Node **p_head)
    11. 
  
  
  
  
  11. {
    12. 
  
  
  
  
  12.     //創(chuàng)建頭結(jié)點(diǎn)
    13. 
  
  
  
  
  13.     Node *head_node = create_node(0);
    14. 
  
  
  
  
  14.     //頭指針指向頭結(jié)點(diǎn)
    15. 
  
  
  
  
  15.     *p_head = head_node;
    16. 
  
  
  
  
  16. }
    17.

2.4. 插入操作

這里只演示頭插法，過(guò)程如下：

雙向鏈表頭插法過(guò)程

代碼如下：

 
 
 
 
    
  
  
  
  
  1. /**
    2. 
  
  
  
  
  2.  * 頭插法，新結(jié)點(diǎn)為頭結(jié)點(diǎn)的直接后繼
    3. 
  
  
  
  
  3.  * p_head: 指向頭指針的指針
    4. 
  
  
  
  
  4.  * elem: 新結(jié)點(diǎn)的數(shù)據(jù)
    5. 
  
  
  
  
  5.  */
    6. 
  
  
  
  
  6. void insert_at_head(Node **p_head, int elem)
    7. 
  
  
  
  
  7. {
    8. 
  
  
  
  
  8.     Node *new = create_node(elem);
    9. 
  
  
  
  
  9.     Node *head_node = *p_head; //頭結(jié)點(diǎn)
    10. 
  
  
  
  
  10.     if (head_node->next != NULL) { //不為空鏈表
    11. 
  
  
  
  
  11.         Node *first_node = head_node->next; //首結(jié)點(diǎn)：頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
    12. 
  
  
  
  
  12.         //首結(jié)點(diǎn)的prev指針指向new結(jié)點(diǎn)
    13. 
  
  
  
  
  13.         first_node->prev = new;
    14. 
  
  
  
  
  14.         //new結(jié)點(diǎn)的next指針指向首結(jié)點(diǎn)
    15. 
  
  
  
  
  15.         new->next = first_node;
    16. 
  
  
  
  
  16.     }
    17. 
  
  
  
  
  17.     //new結(jié)點(diǎn)的prev指針指向頭結(jié)點(diǎn)
    18. 
  
  
  
  
  18.     new->prev = head_node;
    19. 
  
  
  
  
  19.     //頭結(jié)點(diǎn)的next指針指向new結(jié)點(diǎn)
    20. 
  
  
  
  
  20.     head_node->next = new;
    21. 
  
  
  
  
  21. }
    22.

2.5. 刪除操作

這里只演示頭刪法。下圖是將一個(gè)有兩個(gè)元素結(jié)點(diǎn)的雙向鏈表頭刪為空鏈表的過(guò)程：

雙向鏈表頭刪法過(guò)程

代碼如下：

 
 
 
 
    
  
  
  
  
  1. /**
    2. 
  
  
  
  
  2.  * 頭刪法
    3. 
  
  
  
  
  3.  * p_head: 指向頭指針的指針
    4. 
  
  
  
  
  4.  * elem: 指向保存變量的指針
    5. 
  
  
  
  
  5.  */
    6. 
  
  
  
  
  6. void delete_from_head(Node **p_head, int *elem)
    7. 
  
  
  
  
  7. {
    8. 
  
  
  
  
  8.     Node *head_node = *p_head; //頭結(jié)點(diǎn)
    9. 
  
  
  
  
  9.     Node *first_node = head_node->next; //待刪除的首結(jié)點(diǎn)：頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
    10. 
  
  
  
  
  10.     if (head_node->next == NULL) { //判空
    11. 
  
  
  
  
  11.         printf("空鏈表，無(wú)元素可刪。\n");
    12. 
  
  
  
  
  12.         return;
    13. 
  
  
  
  
  13.     }
    14. 
  
  
  
  
  14.     *elem = first_node->data; //保存數(shù)據(jù)
    15. 
  
  
  
  
  15.     
    16. 
  
  
  
  
  16.     if (first_node->next != NULL) {
    17. 
  
  
  
  
  17.         first_node->next->prev = first_node->prev;
    18. 
  
  
  
  
  18.     }
    19. 
  
  
  
  
  19.     first_node->prev->next = first_node->next;
    20. 
  
  
  
  
  20.     free(first_node);
    21. 
  
  
  
  
  21. }
    22.

2.6. 遍歷操作

有了 next 指針域，我們可以一路向后遍歷;有了 prev 指針域，我們可以一路向前遍歷。

這里不再展示代碼了。

3. 總結(jié)

了解了單向循環(huán)鏈表和雙向鏈表，就像拿搭積木一樣，我們還可以創(chuàng)造出來(lái)雙向循環(huán)鏈表。這里就不再演示了，讀者可以自行嘗試。只要你搞懂上面三種鏈表，這絕非難事。

以上就是鏈表的花樣玩法部分內(nèi)容，以后還會(huì)繼續(xù)更新。

參考資料

[1]GitHub: https://github.com/xingrenguanxue/Simple-DS-and-Easy-Algo

[2]Gitee: https://gitee.com/xingrenguanxue/Simple-DS-and-Easy-Algo


文章題目：【數(shù)據(jù)結(jié)構(gòu)之鏈表】詳細(xì)圖文教你花樣玩鏈表
文章地址：http://www.5511xx.com/article/ccichjp.html