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

http://blog.csdn.net/jw903/article/details/38947753

? ?雙向鏈表其實是單鏈表的改進。 當我們對單鏈表進行操作時，有時你要對某個結點的直接前驅進行操作時，又必須從表頭開始查找。這是由單鏈表結點的結構所限制的。因為單鏈表每個結點只有一個存儲直接后繼結點地址的鏈域，那么能不能定義一個既有存儲直接后繼結點地址的鏈域，又有存儲直接前驅結點地址的鏈域的這樣一個雙鏈域結點結構呢？這就是雙向鏈表。

?? 在雙向鏈表中，結點除含有數據域外，還有兩個鏈域，一個存儲直接后繼結點地址，一般稱之為右鏈域；一個存儲直接前驅結點地址，一般稱之為左鏈域。

?? 在c語言中雙向鏈表結點類型可以定義為：

[cpp]?view plain?copy
  1. typedef?struct?Node??
  2. {??
  3. ????int?item;??
  4. ????struct?Node?*pre;??
  5. ????struct?Node?*next;??
  6. }DListNode,*DList;??

下面的代碼就是對雙向鏈表的創建和相關操作：

[cpp]?view plain?copy
  1. /***************************************************************************?
  2. ?*name:jae?chia????????????????????????????????????????????????????????????*?
  3. ?*date:2014.8.29???????????????????????????????????????????????????????????*?
  4. ?*version:?1.0?????????????????????????????????????????????????????????????*?
  5. ?**************************************************************************/??
  6. #include<iostream>??
  7. #include<cassert>??
  8. using?namespace?std;??
  9. ??
  10. //雙向鏈表的建立與操作??
  11. typedef?struct?Node??
  12. {??
  13. ????int?item;??
  14. ????struct?Node?*pre;??
  15. ????struct?Node?*next;??
  16. }DListNode,*DList;??
  17. DList?InsertNodeToTail(DList?head,int?data)//將節點插入到雙向鏈表的尾部??
  18. {??
  19. ????if(head==NULL)??
  20. ????{??
  21. ????????head=(DList)malloc(sizeof(DListNode));??
  22. ????????assert(head!=NULL);??
  23. ????????head->item=data;??
  24. ????????head->next=NULL;??
  25. ????????head->pre=NULL;??
  26. ????}??
  27. ????else??
  28. ????{??
  29. ????????DListNode?*newnode=(DList)malloc(sizeof(DListNode));//創建新的鏈表節點??
  30. ????????assert(newnode!=NULL);??
  31. ????????newnode->item=data;??
  32. ????????newnode->next=NULL;??
  33. ????????newnode->pre=NULL;??
  34. ??
  35. ????????DListNode?*p=head;??
  36. ????????while(p->next!=NULL)??
  37. ????????{??
  38. ????????????p=p->next;??
  39. ????????}??
  40. ????????p->next=newnode;??
  41. ????????newnode->pre=p;??
  42. ????}??
  43. ????return?head;??
  44. }??
  45. ??
  46. DList?InsertDListByOrder(DList?head,int?data)//這里的插入操作是按序插入（保證雙向鏈表中的節點以遞增有序）??
  47. {??
  48. ????DListNode?*newnode=(DList)malloc(sizeof(DListNode));??
  49. ????assert(newnode);??
  50. ????newnode->item=data;??
  51. ????//newnode->next=NULL;??
  52. ????//newnode->pre=NULL;??
  53. ??
  54. ????DListNode?*p=head;??
  55. ????DListNode?*prenode;??
  56. ????for(;p!=NULL;p=p->next)??
  57. ????{?????
  58. ????????prenode=p;??
  59. ????????if(newnode->item?<=p->item)??
  60. ????????????break;???????
  61. ????}??
  62. ????if(p==NULL)//如果遍歷整個鏈表，結點的值都比要插入的小，那么只能在尾端插入??
  63. ????{??
  64. ????????prenode->next=newnode;??
  65. ????????newnode->pre=prenode;??
  66. ????????newnode->next=NULL;??
  67. ????}??
  68. ????else?if(p==head)//如果鏈表中的數都比要插入的數大則在頭部插入；??
  69. ????{??
  70. ????????newnode->pre=NULL;??
  71. ????????newnode->next=head;??
  72. ????????head=newnode;??
  73. ????}??
  74. ????else???//在中間插入??
  75. ????{??
  76. ????????p->pre->next=newnode;??
  77. ????????newnode->pre=p->pre;??
  78. ??
  79. ????????newnode->next=p;??
  80. ????????p->pre=newnode;??
  81. ????}??
  82. ????return?head;??
  83. }??
  84. ??
  85. bool?FindNode(DList?head,int?data)//查找鏈表中含有某元素的節點是否存在??
  86. {??
  87. ????if(head==NULL)??
  88. ????{??
  89. ????????cout<<"the?Dlist?is?NULL"<<endl;??
  90. ????????return?false;??
  91. ????}??
  92. ????DListNode?*p=head;??
  93. ????while(p!=NULL)??
  94. ????{??
  95. ????????if(p->item==data)??
  96. ????????????return?true;??
  97. ????????p=p->next;??
  98. ????}??
  99. ????return?false;??
  100. }??
  101. ??
  102. DList?DeleteNode(DList?head,int?data)//刪除節點??
  103. {??
  104. ????DListNode?*p=head;??
  105. ????while(p!=NULL)??
  106. ????{??
  107. ????????if(p->item==data)??
  108. ????????????break;??
  109. ????????p=p->next;??
  110. ??????????
  111. ????}??
  112. ????if(p==NULL)??
  113. ????{??
  114. ????????cout<<"the?node?with?data?is?not?existed?in?the?List"<<endl;??
  115. ????????exit(0);??
  116. ????}??
  117. ????if(p==head)//要刪除的結點恰好是雙向鏈表的頭結點??
  118. ????{??
  119. ????????DListNode?*tmp=head;??
  120. ????????head=head->next;??
  121. ????????head->pre=NULL;//---------------------------------------------------??
  122. ????????free(tmp);??
  123. ????}??
  124. ????else?if(p->next==NULL)//如果要刪除的節點是鏈表的最后一個節點??
  125. ????{??
  126. ????????p->pre->next=NULL;??
  127. ????????free(p);??
  128. ????}??
  129. ????else?//刪除中間節點??
  130. ????{??
  131. ????????p->pre->next=p->next;??
  132. ????????p->next->pre=p->pre;??
  133. ????}??
  134. ????return?head;????
  135. }??
  136. void?PrintDList(DList?head)//打印??
  137. {??
  138. ????cout<<"現在，鏈表如下:"<<endl;??
  139. ????if(head==NULL)??
  140. ????{??
  141. ????????cout<<"the?Dlist?is?NULL"<<endl;??
  142. ????????return?;??
  143. ????}??
  144. ????DListNode?*p=head;??
  145. ????while(p!=NULL)??
  146. ????{??
  147. ????????cout<<p->item<<"?";??
  148. ????????p=p->next;??
  149. ????}??
  150. ????cout<<endl<<endl;??
  151. }??
  152. void?DestroyDList(DList?head)//銷毀雙向鏈表??
  153. {??
  154. ????DListNode?*p=head;??
  155. ????while(p!=NULL)??
  156. ????{??
  157. ????????DListNode?*tmp=p;??
  158. ????????p=p->next;??
  159. ????????free(tmp);??
  160. ????}??
  161. }??
  162. ??
  163. void?Test()??
  164. {??
  165. ????DListNode?*head=NULL;??
  166. ??
  167. ????for(int?i=0;i<10;i++)???/*利用尾部插入來構造雙向鏈表*/??
  168. ????????head=InsertNodeToTail(head,i);??
  169. ????PrintDList(head);??
  170. ??????
  171. ????int?a;??
  172. ????cout<<"輸入要查找的結點的值"<<endl;??
  173. ????cin>>a;??
  174. ????if(FindNode(head,a))??
  175. ????????cout<<"結點存在！"<<endl<<endl;??
  176. ????else??
  177. ????????cout<<"結點不存在!"<<endl<<endl;??
  178. ??
  179. ????cout<<"刪除結點4..."<<endl;????/*刪除指定節點*/??
  180. ????head=DeleteNode(head,4);??
  181. ????PrintDList(head);??
  182. ??
  183. ????cout<<"插入結點4..."<<endl;?????/*按序插入*/??
  184. ????head=InsertDListByOrder(head,4);??
  185. ????PrintDList(head);??
  186. ??????
  187. ????cout<<"刪除頭結點..."<<endl;????/*刪除指定節點*/??
  188. ????head=DeleteNode(head,0);??
  189. ????PrintDList(head);??
  190. ??????
  191. ????cout<<"刪除尾結點..."<<endl;??
  192. ????head=DeleteNode(head,9);??
  193. ????PrintDList(head);??
  194. ??????
  195. ????cout<<"插入頭結點..."<<endl;?????/*按序插入*/??
  196. ????head=InsertDListByOrder(head,0);??
  197. ????PrintDList(head);??
  198. ??????
  199. ????cout<<"插入尾結點..."<<endl;?????/*按序插入*/??
  200. ????head=InsertDListByOrder(head,10);??
  201. ????PrintDList(head);??
  202. ??
  203. ????DestroyDList(head);??
  204. }??
  205. int?main(void)??
  206. {??
  207. ????Test();??
  208. }??

運行：


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

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

相關文章

鏈表各類操作詳解

鏈表各類操作詳解

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…
閱讀更多...
【筆試】：編程實現C++string 類成員函數

【筆試】：編程實現C++string 類成員函數

http://blog.csdn.net/wangshihui512/article/details/9792309 已知String類聲明如下&#xff1a; [cpp] view plaincopy print?class String { public: String(const char *str NULL); // 通用構造函數 String(const String &another); // 拷貝…
閱讀更多...
Qt中字符串之間的轉換

Qt中字符串之間的轉換

//QString -> C string -> char * str.ToStdString().data(); //先轉換為C的標準編碼//QString -> QByteArray QString buf "123456"; QByteArray a buf.toUtf8();//中文 a buf.toLocal8Bit(); //轉換為本地編碼 //QByteArray -> char * char *b …
閱讀更多...
（C語言版）棧和隊列（一）——實現鏈式棧和鏈式隊列的基本操作以及遇到的問題

（C語言版）棧和隊列（一）——實現鏈式棧和鏈式隊列的基本操作以及遇到的問題

http://blog.csdn.net/fisherwan/article/details/20055179 首先要感謝這位大牛的一篇博客&#xff0c;地址如下&#xff1a;http://blog.csdn.net/hguisu/article/details/7674195 當然還有網上一些其他的資料&#xff0c;今天自己寫了一下鏈式棧和鏈式隊列的程序。其中在釋放…
閱讀更多...
Cookie的使用

Cookie的使用

ookie簡介 1. 定義 cookie是由服務器發送給客戶端&#xff08;瀏覽器&#xff09;的小量信息。 2. 作用 cookie是鍵值對形式存儲的少量信息&#xff0c;那它有什么作用呢&#xff1f; 我們知道&#xff0c;平時上網時都是使用無狀態的HTTP協議傳輸出數據&#xff0c;這意味著客…
閱讀更多...
循環鏈表解決約瑟夫問題（簡化版）

循環鏈表解決約瑟夫問題（簡化版）

http://blog.csdn.net/jw903/article/details/38965477 約瑟夫環是一個經典的數學的應用問題&#xff1a;已知N個人&#xff08;以編號1&#xff0c;2&#xff0c;3...N分別表示&#xff09;圍坐在一張圓桌周圍。從編號為1的人開始報數&#xff0c;數到M的那個人出列&#xff1…
閱讀更多...
Linux平臺上SQLite數據庫教程（一）——終端使用篇

Linux平臺上SQLite數據庫教程（一）——終端使用篇

http://blog.csdn.net/u011192270/article/details/48031763 SQLite是一款輕型的數據庫&#xff0c;它的設計目標是嵌入式的&#xff0c;而且目前已經在很多嵌入式產品中使用了它&#xff0c;它占用資源非常的低&#xff0c;可能只需要幾百K的內存就夠了。能夠支持Windows/Lin…
閱讀更多...
多路IO轉接服務器 epoll

多路IO轉接服務器 epoll

創建一個epoll句柄&#xff0c;參數size用來告訴內核監聽的文件描述符的個數&#xff0c;跟內存大小有關。 #include <sys/epoll.h> int epoll_create(int size)　　 size&#xff1a;監聽數目 通過創建一個size大小的紅黑數來實現epoll句柄&#xff0c;返回epfd是該…
閱讀更多...
Linux平臺上SQLite數據庫教程（二）——C語言API介紹

Linux平臺上SQLite數據庫教程（二）——C語言API介紹

http://blog.csdn.net/u011192270/article/details/48086961 前言&#xff1a;本文將介紹幾個基本的SQLite3數據庫的C語言API接口&#xff0c;主要用到兩個文件&#xff1a;sqlite3.c、sqlite3.h。源碼地址&#xff1a;https://github.com/AnSwErYWJ/SQLite。 打開數據庫 1.原型…
閱讀更多...
epoll非阻塞IO

epoll非阻塞IO

設置connfd套接字為非阻塞 flag fcntl(connfd, F_GETFL); flag | O_NONBLOCK; fcntl(connfd, F_SETFL, flag); 轉載于:https://www.cnblogs.com/lr1402585172/p/10758740.html
閱讀更多...
小白創建網站的曲折之路

小白創建網站的曲折之路

小白創建網站的曲折之路 在虛擬機上創建網站 顧名思義&#xff0c;首先要有一個虛擬機。在網上百度一下后&#xff0c;我發現大家都在說使用一種叫做VMware Workstation的軟件進行虛擬機的構建 在這位好心人的幫助下我找到了Vmware Workstation的下載資源&#xff0c;并成功下…
閱讀更多...
Ubuntu 14.04數據庫服務器--mysql的安裝和配置

Ubuntu 14.04數據庫服務器--mysql的安裝和配置

https://jingyan.baidu.com/article/425e69e6bbc6c7be14fc1640.html mysql是Oracle公司的一種開放源代碼的關系型數據庫管理系統&#xff0c;被廣泛應用于各中小網站&#xff0c;是一種跨平臺的數據庫管理系統&#xff0c;現在介紹一下如何在Ubuntu 14.04上安裝和配置mysql 工具…
閱讀更多...
最新文章

Copyright @ 2022~2023