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

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

上午寫了下單向循環鏈表的程序，今天下午我把雙向鏈表的程序寫完了。其實雙向鏈表和單向鏈表也是有很多相似的地方的，聽名字可以猜到，每個節點都包含兩個指針，一個指針指向上一個節點，一個指針指向下一個節點。這里有兩個特殊的地方，第一就是頭節點的一個指針指向NULL空指針（沒有前驅節點），第二就是尾節點的一個指針指向NULL指針（沒有后繼節點）。

我們可以看下雙向鏈表的示意圖（自己畫的比較難看）：


所以，我們在編程序的時候，這兩個指針的控制就是我們的難點，因為我們始終要讓這個鏈表保持這樣的鏈接不管是在創建的時候、插入的時候、刪除的時候等，一定要讓節點的兩個指針指向正確的節點。下面我們來看下雙向鏈表的代碼。

DbLinkList.h? 頭文件——包含節點結構的定義和各種操作函數的聲明。

[cpp]?view plain?copy
  1. #ifndef?DOUBLY_LINKED_LIST_H??
  2. #define?DOUBLY_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?CreateDbLinkList(void);??
  13. ??
  14. //打印鏈表??
  15. void?TraverseDbLinkList(pNODE?pHead);??
  16. ??
  17. //判斷鏈表是否為空??
  18. int?IsEmptyDbLinkList(pNODE?pHead);??
  19. ??
  20. //計算鏈表長度??
  21. int?GetLengthDbLinkList(pNODE?pHead);??
  22. ??
  23. //向鏈表插入節點??
  24. int?InsertEleDbLinkList(pNODE?pHead,?int?pos,?int?data);??
  25. ??
  26. //從鏈表刪除節點??
  27. int?DeleteEleDbLinkList(pNODE?pHead,?int?pos);??
  28. ??
  29. //刪除整個鏈表，釋放內存??
  30. void?FreeMemory(pNODE?*ppHead);??
  31. ??
  32. #endif??

DbLinkList.cpp 雙向鏈表的源文件——包含了各種操作函數的定義。

（1）這部分是創建雙向鏈表，和單向鏈表很相似，但是呢，有些地方還是得注意，就是每創建一個節點的時候都要注意初始化它的兩個指針。

[cpp]?view plain?copy
  1. #include?<stdio.h>??
  2. #include?<stdlib.h>??
  3. #include?"DbLinkList.h"??
  4. ??
  5. //創建雙向鏈表??
  6. pNODE?CreateDbLinkList(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->pPre?=?NULL;??
  20. ????pHead->pNext?=?NULL;??
  21. ????pTail?=?pHead;??
  22. ??
  23. ????printf("請輸入想要創建鏈表的長度：");??
  24. ????scanf("%d",?&length);??
  25. ??
  26. ????for?(i=1;?i<length+1;?i++)??
  27. ????{??
  28. ????????p_new?=?(pNODE)malloc(sizeof(NODE));??
  29. ??
  30. ????????if?(NULL?==?p_new)??
  31. ????????{??
  32. ????????????printf("內存分配失敗！\n");??
  33. ????????????exit(EXIT_FAILURE);??
  34. ????????}??
  35. ??
  36. ????????printf("請輸入第%d個元素的值：",?i);??
  37. ????????scanf("%d",?&data);??
  38. ??
  39. ????????p_new->data?=?data;??
  40. ????????p_new->pNext?=?NULL;??
  41. ????????p_new->pPre?=?pTail;??
  42. ????????pTail->pNext?=?p_new;??
  43. ????????pTail?=?p_new;??
  44. ????}??
  45. ??
  46. ????return?pHead;??
  47. }??

（2）這部分是獲得雙向鏈表的信息，這里和單向鏈表基本一致，因為遍歷的時候只用到了一個指針。

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

（3）這部分是向雙向鏈表插入節點，也跟單向鏈表很多相似的地方。我們先來看下插入節點時的示意圖：


從圖中可以看到，每次我們添加一個節點都有很多地方要調節的，也就是每個節點的那兩個指針，一定要認真仔細自己動手寫一遍，有可能有些細節就會出錯。這里有一個地方需要注意，是和單向鏈表不同的地方，單向鏈表在插入節點的時候不需要判斷最后一個節點是否為空，因為這不影響程序的結果，但是對于雙向鏈表就不一樣了，因為我們后面要用到最后一個節點的一個指針指向前一個節點，如果最后一個節點是空的話（就是程序中的pt），就不存在pt->pPre了,那么程序運行到這里時就會報錯，所以我們要加個判斷，判斷此時節點是NULL的話就不需要控制它的指針了。

[cpp]?view plain?copy
  1. //向雙向鏈表中插入節點??
  2. int?InsertEleDbLinkList(pNODE?pHead,?int?pos,?int?data)??
  3. {??
  4. ????pNODE?pt?=?NULL,?p_new?=?NULL;??
  5. ??
  6. ????if?(pos?>?0?&&?pos?<?GetLengthDbLinkList(pHead)+2)??
  7. ????{??
  8. ????????p_new?=?(pNODE)malloc(sizeof(NODE));??
  9. ??
  10. ????????if?(NULL?==?p_new)??
  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. ????????pt?=?pHead->pNext;??
  25. ????????p_new->data?=?data;??
  26. ????????p_new->pNext?=?pt;??
  27. ????????if?(NULL?!=?pt)??
  28. ????????????pt->pPre?=?p_add;??
  29. ????????p_new->pPre?=?pHead;??
  30. ????????pHead->pNext?=?p_new;??
  31. ??????????
  32. ????????return?1;??
  33. ????}??
  34. ????else??
  35. ????????return?0;??
  36. }??

（4）這部分是從鏈表中刪除節點，當然這里和單向鏈表差不多，要注意的地方和插入節點時是一樣的，上面已經說明了。

[cpp]?view plain?copy
  1. //從鏈表中刪除節點??
  2. int?DeleteEleDbLinkList(pNODE?pHead,?int?pos)??
  3. {??
  4. ????pNODE?pt?=?NULL;??
  5. ??
  6. ????if?(pos?>?0?&&?pos?<?GetLengthDbLinkList(pHead)?+?1)??
  7. ????{??
  8. ????????while?(1)??
  9. ????????{??
  10. ????????????pos--;??
  11. ????????????if?(0?==?pos)??
  12. ????????????????break;??
  13. ????????????pHead?=?pHead->pNext;??
  14. ????????}??
  15. ??
  16. ????????pt?=?pHead->pNext->pNext;??
  17. ????????free(pHead->pNext);??
  18. ????????pHead->pNext?=?pt;??
  19. ????????if?(NULL?!=?pt)??
  20. ????????????pt->pPre?=?pHead;??
  21. ??
  22. ????????return?1;??
  23. ????}??
  24. ????else??
  25. ????????return?0;??
  26. }??

（5）這部分是用來釋放內存的，注意的地方和上面一樣。

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

main.cpp 測試程序源文件——通過簡單的交互信息來測試各個函數功能是否正確。

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

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

相關文章

競態條件

競態條件

pause函數 調用該函數可以造成進程主動掛起&#xff0c;等待信號喚醒。調用該系統調用的進程將處于阻塞狀態(主動放棄cpu) 直到有信號遞達將其喚醒。 int pause(void); 返回值&#xff1a;-1 并設置errno為EINTR 返回值&#xff1a; ① 如果信號的默認處理動作是終止進程&#…
閱讀更多...
（C++版）鏈表（一）——實現單向鏈表創建、插入、刪除等相關操作

（C++版）鏈表（一）——實現單向鏈表創建、插入、刪除等相關操作

http://blog.csdn.net/fisherwan/article/details/25557545 前段時間用C語言實現了鏈表的相關操作&#xff0c;但是發現當時挺清楚的&#xff0c;過了一段時間又忘的差不多了&#xff0c;所以現在打算用C再實現一遍&#xff0c;由于初次用C實現&#xff0c;存在錯誤的地方還望大…
閱讀更多...
（C語言版）鏈表（二）——實現單向循環鏈表創建、插入、刪除、釋放內存等簡單操作

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

http://blog.csdn.net/fisherwan/article/details/19754585 昨天寫了單向鏈表的代碼&#xff0c;今天上午把單向循環鏈表的程序給敲完了。鏈表的相關操作一樣的&#xff0c;包含鏈表的創建、判斷鏈表是否為空、計算鏈表長度、向鏈表中插入節點、從鏈表中刪除節點、刪除整個鏈表…
閱讀更多...
計科院首頁靜態網頁

計科院首頁靜態網頁

一.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>…
閱讀更多...
最新文章

Copyright @ 2022~2023