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

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

昨天寫了單向鏈表的代碼，今天上午把單向循環鏈表的程序給敲完了。鏈表的相關操作一樣的，包含鏈表的創建、判斷鏈表是否為空、計算鏈表長度、向鏈表中插入節點、從鏈表中刪除節點、刪除整個鏈表釋放內存。如果單向鏈表理解了，那單向循環鏈表也就不難了。

單向循環鏈表如下圖所示：


看圖可以知道，單向循環鏈表和單向鏈表差不多，只不過是最后的尾節點指向的不是空，而是指向頭節點。理解這一點很重要，因為這是我們寫程序的關鍵。下面我們上代碼：

SqCcLinkList.h 頭文件——定義了節點結構體，以及相關操作的函數聲明。

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


SqCcLinkList.cpp 鏈表源文件——這里包含了各種相關操作的函數的定義。

（1）這部分是創建鏈表，和單向鏈表一樣，一開始也是創建了一個頭節點，初始化時，頭結點的指針指向自己（這是和單向鏈表不一樣的地方）。在寫程序時，主要體現在下面的一行代碼：

[cpp]?view plain?copy
  1. p_new->pNext?=?pHead;????//這里一定是pHead，因為最后一個節點總是指著頭節點??
它的意思就是沒創建一個節點，讓這個節點指向頭節點，然后就形成了一個環，也就成了循環鏈表。

[cpp]?view plain?copy
  1. #include?<stdio.h>??
  2. #include?<stdlib.h>??
  3. #include?"SgCcLinkLIst.h"??
  4. ??
  5. //創建單向循環鏈表??
  6. pNODE?CreateSgCcLinkList(void)??
  7. {??
  8. ????int?i,?length?=?0,?data?=?0;??
  9. ????pNODE?pTail?=?NULL,?p_new?=?NULL;??
  10. ????pNODE?pHead?=?(pNODE)malloc(sizeof(NODE));??
  11. ??
  12. ????if?(NULL?==?pHead)??
  13. ????{??
  14. ????????printf("內存分配失敗！\n");??
  15. ????????exit(EXIT_FAILURE);??
  16. ????}??
  17. ??????
  18. ????pHead->data?=?0;??
  19. ????pHead->pNext?=?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->pNext?=?pHead;????//這里一定是pHead，因為最后一個節點總是指著頭節點??
  40. ????????pTail->pNext?=?p_new;??
  41. ????????pTail?=?p_new;??
  42. ????}??
  43. ??
  44. ????return?pHead;??
  45. }??
（2）這部分是獲得鏈表的相關信息，和單向鏈表一樣，頭節點不參與運算；但是和單向鏈表不同的地方就是判斷的時候是和頭結點進行比較，如何相等的話呢，說明到了鏈表的結尾。

[cpp]?view plain?copy
  1. //打印鏈表??
  2. void?TraverseSgCcLinkList(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?IsEmptySgCcLinkList(pNODE?pHead)??
  17. {??
  18. ????if?(pHead->pNext?==?pHead)??
  19. ????????return?1;??
  20. ????else??
  21. ????????return?0;??
  22. }??
  23. ??
  24. //計算鏈表長度??
  25. int?GetLengthSgCcLinkList(pNODE?pHead)??
  26. {??
  27. ????int?length?=?0;??
  28. ????pNODE?pt?=?pHead->pNext;??
  29. ??
  30. ????while?(pt?!=?pHead)??
  31. ????{??
  32. ????????length++;??
  33. ????????pt?=?pt->pNext;??
  34. ????}??
  35. ????return?length;??
  36. }??

（3）這部分是鏈表的插入和刪除操作，和單向鏈表一樣。

[cpp]?view plain?copy
  1. //向鏈表中插入節點??
  2. int?InsertEleSgCcLinkList(pNODE?pHead,?int?pos,?int?data)??
  3. {??
  4. ????pNODE?p_new?=?NULL;??
  5. ??
  6. ????if?(pos?>?0?&&?pos?<?GetLengthSgCcLinkList(pHead)?+?2)??
  7. ????{??
  8. ????????p_new?=?(pNODE)malloc(sizeof(NODE));??
  9. ??
  10. ????????if?(NULL?==?<span?style="font-family:?Arial,?Helvetica,?sans-serif;">p_new?</span><span?style="font-family:?Arial,?Helvetica,?sans-serif;">)</span>??
  11. ????????{??
  12. ????????????printf("內存分配失敗！\n");??
  13. ????????????exit(EXIT_FAILURE);??
  14. ????????}??
  15. ??
  16. ????????while?(1)??
  17. ????????{??
  18. ????????????pos--;??
  19. ????????????if?(0?==?pos)??
  20. ????????????????break;??
  21. ????????????pHead?=?pHead->pNext;??
  22. ????????}??
  23. ??????????
  24. ????????p_new->data?=?data;??
  25. ????????p_new->pNext?=?pHead->pNext;??
  26. ????????pHead->pNext?=?p_new;??
  27. ??
  28. ????????return?1;??
  29. ????}??
  30. ????else??
  31. ????????return?0;??
  32. }??
[cpp]?view plain?copy
  1. <span?style="font-family:?Arial,?Helvetica,?sans-serif;">//從鏈表中刪除節點</span>??
[cpp]?view plain?copy
  1. int?DeleteEleSgCcLinkList(pNODE?pHead,?int?pos)??
  2. {??
  3. ????pNODE?pt?=?NULL;??
  4. ??
  5. ????if?(pos?>?0?&&?pos?<?GetLengthSgCcLinkList(pHead)?+?1)??
  6. ????{??
  7. ????????while?(1)??
  8. ????????{??
  9. ????????????pos--;??
  10. ????????????if?(0?==?pos)??
  11. ????????????????break;??
  12. ????????????pHead?=?pHead->pNext;??
  13. ????????}??
  14. ??
  15. ????????pt?=?pHead->pNext->pNext;??
  16. ????????free(pHead->pNext);??
  17. ????????pHead->pNext?=?pt;??
  18. ??
  19. ????????return?1;??
  20. ????}??
  21. ????else??
  22. ????????return?0;??
  23. }??
（4）這部分是釋放內存，和單向鏈表有些不一樣，因為單向循環鏈表是個環，最后只剩下頭節點的時候要單獨處理，這個受我判斷條件的限制。當然可能有更好的方法，我們可以共同討論。這里我分了兩種情況來釋放內存。
[cpp]?view plain?copy
  1. //刪除整個鏈表，釋放內存??
  2. void?FreeMemory(pNODE?*ppHead)??
  3. {??
  4. ????pNODE?pt?=?NULL;??
  5. ??
  6. ????while?(*ppHead?!=?NULL)??
  7. ????{??
  8. ????????if?(*ppHead?==?(*ppHead)->pNext)?//如果只有頭節點一個??
  9. ????????{??
  10. ????????????free(*ppHead);??
  11. ????????????*ppHead?=?NULL;??
  12. ????????}??
  13. ????????else????????????????????//如果不止頭節點一個??
  14. ????????{??
  15. ????????????pt?=?(*ppHead)->pNext->pNext;??
  16. ????????????free((*ppHead)->pNext);??
  17. ????????????(*ppHead)->pNext?=?pt;??
  18. ????????}??
  19. ????}??
  20. }??


main.cpp 測試程序源文件——這個程序通過一些簡單的交互用來測試各個函數是否實現了各自的功能。

[cpp]?view plain?copy
  1. #include?<stdio.h>??
  2. #include?<stdlib.h>??
  3. #include?"SgCcLinkList.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?=?CreateSgCcLinkList();??
  12. ??
  13. ????flag?=?IsEmptySgCcLinkList(head);??
  14. ????if?(flag)??
  15. ????????printf("單向循環鏈表為空！\n");??
  16. ????else??
  17. ????{??
  18. ????????length?=?GetLengthSgCcLinkList(head);??
  19. ????????printf("單向循環鏈表的長度為：%d\n",?length);??
  20. ????????TraverseSgCcLinkList(head);??
  21. ????}??
  22. ??
  23. ????printf("請輸入要插入節點的位置和元素值(兩個數用空格隔開)：");??
  24. ????scanf("%d?%d",?&position,?&value);??
  25. ????flag?=?InsertEleSgCcLinkList(head,?position,?value);??
  26. ????if?(flag)??
  27. ????{??
  28. ????????printf("插入節點成功！\n");??
  29. ????????TraverseSgCcLinkList(head);??
  30. ????}?????
  31. ????else??
  32. ????????printf("插入節點失敗！\n");??
  33. ??
  34. ????flag?=?IsEmptySgCcLinkList(head);??
  35. ????if?(flag)??
  36. ????????printf("單向循環鏈表為空，不能進行刪除操作！\n");??
  37. ????else??
  38. ????{??
  39. ????????printf("請輸入要刪除節點的位置：");??
  40. ????????scanf("%d",?&position);??
  41. ????????flag?=?DeleteEleSgCcLinkList(head,?position);??
  42. ????????if?(flag)??
  43. ????????{??
  44. ????????????printf("刪除節點成功！\n");??
  45. ????????????TraverseSgCcLinkList(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/384265.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/384265.shtml
英文地址，請注明出處：http://en.pswp.cn/news/384265.shtml

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

相關文章

計科院首頁靜態網頁

計科院首頁靜態網頁

一.HTML代碼 <!DOCTYPE html><html><head><meta charset"UTF-8"><title>首頁</title> </head><body><div id"page"> <div id"page_head"> <div id"logo" aligncenter…
閱讀更多...
可重入函數

可重入函數

一個函數在被調用執行期間(尚未調用結束)&#xff0c;由于某種時序又被重復調用&#xff0c;稱之為“重入”。根據函數實現的方法可分為“可重入函數”和“不可重入函數”兩種。 注意事項 定義可重入函數&#xff0c;函數內不能含有全局變量及static變量&#xff0c;不能使用ma…
閱讀更多...
（C語言版）鏈表（四）——實現雙向循環鏈表創建、插入、刪除、釋放內存等簡單操作

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

http://blog.csdn.net/fisherwan/article/details/19801993 雙向循環鏈表是基于雙向鏈表的基礎上實現的&#xff0c;和雙向鏈表的操作差不多&#xff0c;唯一的區別就是它是個循環的鏈表&#xff0c;通過每個節點的兩個指針把它們扣在一起組成一個環狀。所以呢&#xff0c;每個…
閱讀更多...
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 …
閱讀更多...
最新文章

Copyright @ 2022~2023