（C語言版）鏈表（四）——實現雙向循環鏈表創建、插入、刪除、釋放內存等簡單操作

http://blog.csdn.net/fisherwan/article/details/19801993

雙向循環鏈表是基于雙向鏈表的基礎上實現的，和雙向鏈表的操作差不多，唯一的區別就是它是個循環的鏈表，通過每個節點的兩個指針把它們扣在一起組成一個環狀。所以呢，每個節點都有前驅節點和后繼節點（包括頭節點和尾節點）這是和雙向鏈表不同的地方。我們看下雙向循環鏈表的示意圖（我在網上找了張圖片，自己畫的實在難看，有時間真的要去學下怎么畫圖了，然后可以寫出更好的博客）：

在程序的編寫方面呢，雙向循環鏈表有點向前面知識的組合，雙向循環鏈表在“雙向”方面和雙向鏈表一樣，在“循環方面”和單向循環鏈表一樣。以前的知識消化了呢，這個雙向循環鏈表也就簡單了。上面這個圖比較形象的體現出了雙向循環鏈表的含義：簡單說呢，就是當前節點的一個指針指向前置節點一個指針指向后繼節點，每個節點都重復這樣，就形成了一個環了。

DbCcLinkList.h 頭文件——包含了節點結構的定義和鏈表相關操作函數的聲明

[cpp]?view plain?copy
  1. #ifndef?DOUBLE_CIRCULAR_LINKED_LIST_H??
  2. #define?DOUBLE_CIRCULAR_LINKED_LIST_H??
  3. ??
  4. typedef?struct?Node??
  5. {??
  6. ????int?data;??
  7. ????struct?Node?*pNext;??
  8. ????struct?Node?*pPre;??
  9. }NODE,?*pNODE;??
  10. ??
  11. //創建雙向循環鏈表??
  12. pNODE?CreateDbCcLinkList(void);??
  13. ??
  14. //打印鏈表??
  15. void?TraverseDbCcLinkList(pNODE?pHead);??
  16. ??
  17. //判斷鏈表是否為空??
  18. int?IsEmptyDbCcLinkList(pNODE?pHead);??
  19. ??
  20. //計算鏈表的長度??
  21. int?GetLengthDbCcLinkList(pNODE?pHead);??
  22. ??
  23. //向鏈表中插入節點??
  24. int?InsertEleDbCcLinkList(pNODE?pHead,?int?pos,?int?data);??
  25. ??
  26. //從鏈表中刪除節點??
  27. int?DeleteEleDbCcLinkList(pNODE?pHead,?int?pos);??
  28. ??
  29. //刪除整個鏈表，釋放內存??
  30. void?FreeMemory(pNODE?*ppHead);??
  31. ??
  32. #endif??


DbCcLinkList.cpp 雙向循環鏈表的源文件——包含了鏈表相關操作函數的定義

（1）這部分是用來創建鏈表的，雙向循環鏈表每插入一個節點就要控制4個指針，第一，插入位置的上一個節點有一個指針，它要指向插入節點；第二，插入的節點有兩個指針，一個指向上一個節點，一個指向下一個節點；第三，插入位置的下一個節點有一個指針，它是指著插入節點的。寫程序的關鍵也就是控制好這四個指針，不要弄錯了，要不然會有奇怪的結果（程序出不來結果，無線循環等）

[cpp]?view plain?copy
  1. #include?<stdio.h>??
  2. #include?<stdlib.h>??
  3. #include?"DbCcLinkList.h"??
  4. ??
  5. //創建雙向循環鏈表??
  6. pNODE?CreateDbCcLinkList(void)??
  7. {??
  8. ????int?i,?length?=?0,?data?=?0;??
  9. ????pNODE?p_new?=?NULL,?pTail?=?NULL;??
  10. ????pNODE?pHead?=?(pNODE)malloc(sizeof(NODE));??
  11. ??
  12. ????if?(NULL?==?pHead)??
  13. ????{??
  14. ????????printf("內存分配失敗！\n");??
  15. ????????exit(EXIT_FAILURE);??
  16. ????}??
  17. ????pHead->data?=?0;??
  18. ????pHead->pNext?=?pHead;??
  19. ????pHead->pPre?=?pHead;??
  20. ????pTail?=?pHead;??
  21. ??
  22. ????printf("請輸入想要創建鏈表的長度：");??
  23. ????scanf("%d",?&length);??
  24. ??
  25. ????for?(i=1;?i<length+1;?i++)??
  26. ????{??
  27. ????????p_new?=?(pNODE)malloc(sizeof(NODE));??
  28. ??
  29. ????????if?(NULL?==?p_new)??
  30. ????????{??
  31. ????????????printf("內存分配失敗！\n");??
  32. ????????????exit(EXIT_FAILURE);??
  33. ????????}??
  34. ??
  35. ????????printf("請輸入第%d個節點元素值：",?i);??
  36. ????????scanf("%d",?&data);??
  37. ??
  38. ????????p_new->data?=?data;??
  39. ????????p_new->pPre?=?pTail;??
  40. ????????p_new->pNext?=?pHead;??
  41. ????????pTail->pNext?=?p_new;??
  42. ????????pHead->pPre?=?p_new;??
  43. ????????pTail?=?p_new;??
  44. ????}??
  45. ????return?pHead;??
  46. }??
（2）這部分是獲得雙向鏈表的信息，和單向循環鏈表一樣，鏈表結束的限制條件是判斷是否等于頭結點。意思就是從頭節點的下一個節點開始如果又到了頭節點說明已經遍歷一圈了。

[cpp]?view plain?copy
  1. //打印鏈表??
  2. void?TraverseDbCcLinkList(pNODE?pHead)??
  3. {??
  4. ????pNODE?pt?=?pHead->pNext;??
  5. ??
  6. ????printf("鏈表打印如：");??
  7. ????while?(pt?!=?pHead)??
  8. ????{??
  9. ????????printf("%d?",?pt->data);??
  10. ????????pt?=?pt->pNext;??
  11. ????}??
  12. ????putchar('\n');??
  13. }??
  14. ??
  15. //判斷鏈表是否為空??
  16. int?IsEmptyDbCcLinkList(pNODE?pHead)??
  17. {??
  18. ????pNODE?pt?=?pHead->pNext;??
  19. ??
  20. ????if?(pt?==?pHead)??
  21. ????????return?1;??
  22. ????else??
  23. ????????return?0;??
  24. }??
  25. ??
  26. //計算鏈表的長度??
  27. int?GetLengthDbCcLinkList(pNODE?pHead)??
  28. {??
  29. ????int?length?=?0;??
  30. ????pNODE?pt?=?pHead->pNext;??
  31. ??
  32. ????while?(pt?!=?pHead)??
  33. ????{??
  34. ????????length++;??
  35. ????????pt?=?pt->pNext;??
  36. ????}??
  37. ????return?length;??
  38. }??

（3）這部分是雙向鏈表的插入、刪除節點操作， 但是它不需要和雙向鏈表一樣判斷最后一個節點是否為空（因為此時要用到節點的指針），雙向循環鏈表不存在這樣的情況，這是由于它不光是雙向的，而且是循環的，所以每個節點都不可能為空。

[cpp]?view plain?copy
  1. //向鏈表中插入節點??
  2. int?InsertEleDbCcLinkList(pNODE?pHead,?int?pos,?int?data)??
  3. {??
  4. ????pNODE?p_new?=?NULL,?pt?=?NULL;??
  5. ????if?(pos?>?0?&&?pos?<?GetLengthDbCcLinkList(pHead)?+?2)??
  6. ????{??
  7. ????????p_new?=?(pNODE)malloc(sizeof(NODE));??
  8. ??
  9. ????????if?(NULL?==?p_new)??
  10. ????????{??
  11. ????????????printf("內存分配失敗！\n");??
  12. ????????????exit(EXIT_FAILURE);??
  13. ????????}??
  14. ??
  15. ????????while?(1)??
  16. ????????{??
  17. ????????????pos--;??
  18. ????????????if?(0?==?pos)??
  19. ????????????????break;??
  20. ????????????pHead?=?pHead->pNext;??
  21. ????????}??
  22. ??????????
  23. ????????p_new->data?=?data;??
  24. ????????pt?=?pHead->pNext;??
  25. ????????p_new->pNext?=?pt;??
  26. ????????p_new->pPre?=?pHead;??
  27. ????????pHead->pNext?=?p_new;??
  28. ????????pt->pPre?=?p_new;??
  29. ??????????
  30. ????????return?1;??
  31. ????}??
  32. ????else??
  33. ????????return?0;??
  34. }??
  35. ??
  36. //從鏈表中刪除節點??
  37. int?DeleteEleDbCcLinkList(pNODE?pHead,?int?pos)??
  38. {??
  39. ????pNODE?pt?=?NULL;??
  40. ????if?(pos?>?0?&&?pos?<?GetLengthDbCcLinkList(pHead)?+?1)??
  41. ????{??
  42. ????????while?(1)??
  43. ????????{??
  44. ????????????pos--;??
  45. ????????????if?(0?==?pos)??
  46. ????????????????break;??
  47. ????????????pHead?=?pHead->pNext;??
  48. ????????}??
  49. ????????pt?=?pHead->pNext->pNext;??
  50. ????????free(pHead->pNext);??
  51. ????????pHead->pNext?=?pt;??
  52. ????????pt->pPre?=?pHead;??
  53. ??
  54. ????????return?1;??
  55. ????}??
  56. ????else??
  57. ????????return?0;?????
  58. }??

（4）這是釋放內存操作，和上面講的一樣，不需要判斷最后一個節點是否為空，每次釋放一個節點的內存的以后它還是保持環狀的結構，所以沒有節點為空。

[cpp]?view plain?copy
  1. //刪除整個鏈表，釋放內存空間??
  2. void?FreeMemory(pNODE?*ppHead)??
  3. {??
  4. ????pNODE?pt?=?NULL;??
  5. ????while?(*ppHead?!=?NULL)??
  6. ????{??
  7. ????????pt?=?(*ppHead)->pNext->pNext;??
  8. ??
  9. ??
  10. ????????if?((*ppHead)->pNext?==?*ppHead)??
  11. ????????{??
  12. ????????????free(*ppHead);??
  13. ????????????*ppHead?=?NULL;??
  14. ????????}??
  15. ????????else??
  16. ????????{??
  17. ????????????free((*ppHead)->pNext);??
  18. ????????????(*ppHead)->pNext?=?pt;??
  19. ????????????pt->pPre?=?*ppHead;??
  20. ????????}??
  21. ????}??
  22. }??

maincpp 測試程序——通過簡單的交互界面判斷函數的功能是否正確

[cpp]?view plain?copy
  1. #include?<stdio.h>??
  2. #include?<stdlib.h>??
  3. #include?"DbCcLinkList.h"??
  4. ??
  5. int?main(void)??
  6. {??
  7. ????int?flag?=?0,?length?=?0;??
  8. ????int?position?=?0,?value?=?0;??
  9. ????pNODE?head?=?NULL;??
  10. ??
  11. ????head?=?CreateDbCcLinkList();??
  12. ??????
  13. ????flag?=?IsEmptyDbCcLinkList(head);??
  14. ????if?(flag)??
  15. ????????printf("雙向循環鏈表為空！\n");??
  16. ????else??
  17. ????{??
  18. ????????length?=?GetLengthDbCcLinkList(head);??
  19. ????????printf("雙向循環鏈表的長度為：%d\n",?length);??
  20. ????????TraverseDbCcLinkList(head);??
  21. ????}??
  22. ??????
  23. ????printf("請輸入要插入節點的位置和元素值(兩個數用空格隔開)：");??
  24. ????scanf("%d?%d",?&position,?&value);??
  25. ????flag?=?InsertEleDbCcLinkList(head,?position,?value);??
  26. ????if?(flag)??
  27. ????{??
  28. ????????printf("插入節點成功！\n");??
  29. ????????TraverseDbCcLinkList(head);??
  30. ????}?????
  31. ????else??
  32. ????????printf("插入節點失敗！\n");??
  33. ??????
  34. ????flag?=?IsEmptyDbCcLinkList(head);??
  35. ????if?(flag)??
  36. ????????printf("雙向循環鏈表為空，不能進行刪除操作！\n");??
  37. ????else??
  38. ????{??
  39. ????????printf("請輸入要刪除節點的位置：");??
  40. ????????scanf("%d",?&position);??
  41. ????????flag?=?DeleteEleDbCcLinkList(head,?position);??
  42. ????????if?(flag)??
  43. ????????{??
  44. ????????????printf("刪除節點成功！\n");??
  45. ????????????TraverseDbCcLinkList(head);??
  46. ????????}?????
  47. ????????else??
  48. ????????????printf("刪除節點失敗！\n");??
  49. ????}??
  50. ??????????
  51. ????FreeMemory(&head);??
  52. ????if?(NULL?==?head)??
  53. ????????printf("已成功刪除雙向循環鏈表，釋放內存完成！\n");??
  54. ????else??
  55. ????????printf("刪除雙向循環鏈表失敗，釋放內存未完成！\n");??
  56. ??
  57. ????return?0;??
  58. }??

PS：到這里為止，鏈表的知識就寫到這里了，后面開始就是隊列和棧了。其實線性表方面的知識都大同小異，只要原理清楚之后，它的形式的變化可以是多鐘多樣的，當然本人水平有限，希望能和同道之人繼續深入探討，共同進步。



本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/384262.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/384262.shtml
英文地址，請注明出處：http://en.pswp.cn/news/384262.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

SIGCHLD

SIGCHLD

SIGCHLD的產生條件 子進程終止時 子進程接收到SIGSTOP信號停止時 子進程處在停止態&#xff0c;接受到SIGCONT后喚醒時 借助SIGCHLD信號回收子進程 子進程結束運行&#xff0c;其父進程會收到SIGCHLD信號。該信號的默認處理動作是忽略。可以捕捉該信號&#xff0c;在捕捉函數中…
閱讀更多...
（C語言版）鏈表（一）——實現單向鏈表創建、插入、刪除等簡單操作（包含個人理解說明及注釋，新手跟著寫代碼）

（C語言版）鏈表（一）——實現單向鏈表創建、插入、刪除等簡單操作（包含個人理解說明及注釋，新手跟著寫代碼）

http://blog.csdn.net/fisherwan/article/details/19701027 我學習了幾天數據結構&#xff0c;今天下午自己寫了一個單向鏈表的程序。我也是新手&#xff0c;所以剛開始學習數據結構的菜鳥們&#xff08;有大牛們能屈尊看一看&#xff0c;也是我的榮幸&#xff09;可以和我一起…
閱讀更多...
中斷系統調用

中斷系統調用

中斷系統調用 系統調用可分為兩類&#xff1a;慢速系統調用和其他系統調用。 慢速系統調用&#xff1a;可能會使進程永遠阻塞的一類。如果在阻塞期間收到一個信號&#xff0c;該系統調用就被中斷,不再繼續執行(早期)&#xff1b;也可以設定系統調用是否重啟。如&#xff0c;rea…
閱讀更多...
（C++版）鏈表（二）——實現單項循環鏈表創建、插入、刪除等操作

（C++版）鏈表（二）——實現單項循環鏈表創建、插入、刪除等操作

http://blog.csdn.net/fisherwan/article/details/25561857 鏈表&#xff08;二&#xff09;單向循環鏈表的實現&#xff0c;下面實現代碼&#xff1a; [cpp] view plaincopy <span style"font-size:18px;" deep"5">#include <iostream> #in…
閱讀更多...
會話

會話

創建會話 創建一個會話需要注意以下6點注意事項&#xff1a; 調用進程不能是進程組組長&#xff0c;該進程變成新會話首進程(session header)該進程成為一個新進程組的組長進程。需有root權限(ubuntu不需要)新會話丟棄原有的控制終端&#xff0c;該會話沒有控制終端該調用進程是…
閱讀更多...
守護進程

守護進程

守護進程 Daemon(精靈)進程&#xff0c;是Linux中的后臺服務進程&#xff0c;通常獨立于控制終端并且周期性地執行某種任務或等待處理某些發生的事件。一般采用以d結尾的名字。 Linux后臺的一些系統服務進程&#xff0c;沒有控制終端&#xff0c;不能直接和用戶交互。不受用戶登…
閱讀更多...
（C++版）鏈表（三）——實現雙向鏈表的創建、插入、刪除等簡單操作

（C++版）鏈表（三）——實現雙向鏈表的創建、插入、刪除等簡單操作

http://blog.csdn.net/fisherwan/article/details/25649073 鏈表&#xff08;三&#xff09;實現雙向鏈表操作&#xff0c;代碼如下&#xff1a; [cpp] view plaincopy <span style"font-size:18px;" deep"5">#include <iostream> #include …
閱讀更多...
（C++版）鏈表（四）——實現雙向循環鏈表創建、插入、刪除等簡單操作

（C++版）鏈表（四）——實現雙向循環鏈表創建、插入、刪除等簡單操作

http://blog.csdn.net/fisherwan/article/details/25649271 鏈表&#xff08;四&#xff09;實現雙向循環鏈表簡單操作&#xff0c;代碼如下&#xff1a; [cpp] view plaincopy <span style"font-size:18px;" deep"5">#include <iostream> #…
閱讀更多...
java web開發環境搭建

java web開發環境搭建

1.安裝并配置JDK環境&#xff08;1&#xff09;安裝過程省略&#xff08;建議安裝在自己指定的統一目錄下&#xff0c;方便后期查找&#xff09;。 &#xff08;2&#xff09;配置環境變量 JAVA_HOME: C:\Java\jdk\jdk1.7.0_45 &#xff08;jdk安裝目錄路徑&#xff09; Path:…
閱讀更多...
java script簡介

java script簡介

一.JavaScript介紹&#xff08;摘抄于百度百科&#xff09; JavaScript一種直譯式腳本語言&#xff0c;是一種動態類型、弱類型、基于原型的語言&#xff0c;內置支持類型。它的解釋器被稱為JavaScript引擎&#xff0c;為瀏覽器的一部分&#xff0c;廣泛用于客戶端的腳本語言&a…
閱讀更多...
雙向鏈表的創建和相關操作

雙向鏈表的創建和相關操作

http://blog.csdn.net/jw903/article/details/38947753 雙向鏈表其實是單鏈表的改進。 當我們對單鏈表進行操作時&#xff0c;有時你要對某個結點的直接前驅進行操作時&#xff0c;又必須從表頭開始查找。這是由單鏈表結點的結構所限制的。因為單鏈表每個結點只有一個存儲直接后…
閱讀更多...
鏈表各類操作詳解

鏈表各類操作詳解

http://blog.csdn.net/hackbuteer1/article/details/6591486/ 鏈表概述 　　 鏈表是一種常見的重要的數據結構。它是動態地進行存儲分配的一種結構。它可以根據需要開辟內存單元。鏈表有一個“頭指針”變量&#xff0c;以head表示&#xff0c;它存放一個地址。該地址指向一個元…
閱讀更多...
信號和槽

信號和槽

信號槽是 Qt 框架引以為豪的機制之一。所謂信號槽&#xff0c;實際就是觀察者模式。當某個事件發生之后&#xff0c;比如&#xff0c;按鈕檢測到自己被點擊了一下&#xff0c;它就會發出一個信號&#xff08;signal&#xff09;。這種發出是沒有目的的&#xff0c;類似廣播。如…
閱讀更多...
登陸界面

登陸界面

界面展示&#xff1a; <!DOCTYPE html> <html><head><meta charset"utf-8"><title>電子郵件登錄</title><link href"style.css" type"text/css" rel"stylesheet"></head><body>…
閱讀更多...
C語言實現雙向鏈表刪除、插入、雙向輸出

C語言實現雙向鏈表刪除、插入、雙向輸出

http://www.cnblogs.com/dyllove98/archive/2013/07/31/3228857.html #include<cstdio> #include<cstdlib> typedef struct DoubleLinkedList {int data;struct DoubleLinkedList *pre;struct DoubleLinkedList *next; }DlinkedList_Node; //建立鏈表 DlinkedList_…
閱讀更多...
servlet概述

servlet概述

一、什么是Servlet呢&#xff1f; servlet 是由sun公司提供的動態web資源開發技術&#xff0c;本質上就是一段Java程序&#xff0c;這段java程序無法獨立運行&#xff0c;必須放在Servlet容器&#xff08;比如&#xff1a;tomcat服務器&#xff09;中運行&#xff0c;由容器調用…
閱讀更多...
運用遞歸將兩個鏈表進行連接

運用遞歸將兩個鏈表進行連接

http://blog.csdn.net/zjut_ym/article/details/45008259 建立2個數據項按從大到小排列的鏈表&#xff0c;實現2個鏈表的合并&#xff0c;并輸出合并后鏈表的數據項。 函數代碼如下 #include<iostream> using namespace std; struct node{int data;node *next; }; node …
閱讀更多...
C++ 類的深拷貝與淺拷貝||深拷貝通過重載拷貝構造函數與重載賦值運算符實現

C++ 類的深拷貝與淺拷貝||深拷貝通過重載拷貝構造函數與重載賦值運算符實現

http://blog.csdn.net/wangshihui512/article/details/9842225 在面向對象程序設計中&#xff0c;對象間的相互拷貝和賦值是經常進行的操作。 如果對象在申明的同時馬上進行的初始化操作&#xff0c;則稱之為拷貝運算。例如&#xff1a; class1 A("Time"); class1…
閱讀更多...
C++ 類的const成員函數

C++ 類的const成員函數

http://blog.csdn.net/wangshihui512/article/details/9823739 我們定義的類的成員函數中&#xff0c;常常有一些成員函數不改變類的數據成員&#xff0c;也就是說&#xff0c;這些函數是"只讀"函數&#xff0c;而有一些函數要修改類數據成員的值。如果把不改變數據…
閱讀更多...
用servlet校驗密碼2

用servlet校驗密碼2

js //創建Ajax對象&#xff0c;不同瀏覽器有不同的創建方法&#xff0c;其實本函數就是一個簡單的new語句而已。 function createXMLHttpRequest() {var XMLHttpRequest1;if (window.XMLHttpRequest) {XMLHttpRequest_test new XMLHttpRequest();} else if (window.ActiveXOb…
閱讀更多...
最新文章

Copyright @ 2022~2023