尹成 雙循環鏈表

? 今天，我們一起用C++寫一個雙鏈表，具體代碼如下：

DoubleList.h具體內容如下：

[cpp]?view plain?copy
  1. #include?"NodeList.h"??
  2. ??
  3. template<typename?Type>?class?DoublyList{??
  4. public:??
  5. ????DoublyList()?:head(new?ListNode<Type>()){????//the?head?node?point?to?itself??
  6. ????????head->m_pprior?=?head;??
  7. ????????head->m_pnext?=?head;??
  8. ????}??
  9. ????~DoublyList(){??
  10. ????????MakeEmpty();??
  11. ????????delete?head;??
  12. ????}??
  13. ??
  14. public:??
  15. ????void?MakeEmpty();???//make?the?list?empty??
  16. ????int?Length();???????//get?the?length?of?the?list??
  17. ????ListNode<Type>?*Find(int?n?=?0);??//find?the?nth?data??
  18. ????ListNode<Type>?*?FindData(Type?item);???//find?the?data?which?is?equal?to?item??
  19. ????bool?Insert(Type?item,?int?n?=?0);?????//insert?item?in?the?nth?data??
  20. ????Type?Remove(int?n?=?0);???//delete?the?nth?data??
  21. ????Type?Get(int?n?=?0);??????//get?the?nth?data??
  22. ????void?Print();???????????//print?the?list??
  23. ??
  24. private:??
  25. ????ListNode<Type>?*head;??
  26. };??
  27. ??
  28. template<typename?Type>?void?DoublyList<Type>::MakeEmpty(){??
  29. ????ListNode<Type>?*pmove?=?head->m_pnext,?*pdel;??
  30. ????while?(pmove?!=?head){??
  31. ????????pdel?=?pmove;??
  32. ????????pmove?=?pdel->m_pnext;??
  33. ????????delete?pdel;??
  34. ????}??
  35. ????head->m_pnext?=?head;??
  36. ????head->m_pprior?=?head;??
  37. }??
  38. ??
  39. template<typename?Type>?int?DoublyList<Type>::Length(){??
  40. ????ListNode<Type>?*pprior?=?head->m_pprior,?*pnext?=?head->m_pnext;??
  41. ????int?count?=?0;??
  42. ????while?(1){??
  43. ????????if?(pprior->m_pnext?==?pnext){ ?// 避免偶數個元素情況 不能使用條件 if(pprior == head) break;
  44. ????????????break;??
  45. ????????}??
  46. ????????if?(pprior?==?pnext&&pprior?!=?head){ ?//避免偶數個元素
  47. ????????????count++;??
  48. ????????????break;??
  49. ????????}??
  50. ????????count?+=?2;??
  51. ????????pprior?=?pprior->m_pprior;??
  52. ????????pnext?=?pnext->m_pnext;??
  53. ????}??
  54. ????return?count;??
  55. }??
  56. ??
  57. template<typename?Type>?ListNode<Type>*?DoublyList<Type>::Find(int?n?=?0){??
  58. ????if?(n?<?0){??
  59. ????????cout?<<?"The?n?is?out?of?boundary"?<<?endl;??
  60. ????????return?NULL;??
  61. ????}??
  62. ????ListNode<Type>?*pmove?=?head->m_pnext;??
  63. ????for?(int?i?=?0;?i?<?n;?i++){??
  64. ????????pmove?=?pmove->m_pnext;??
  65. ????????if?(pmove?==?head){??
  66. ????????????cout?<<?"The?n?is?out?of?boundary"?<<?endl;??
  67. ????????????return?NULL;??
  68. ????????}??
  69. ????}??
  70. ????return?pmove;??
  71. }??
  72. ??
  73. template<typename?Type>?bool?DoublyList<Type>::Insert(Type?item,?int?n){??
  74. ????if?(n?<?0){??
  75. ????????cout?<<?"The?n?is?out?of?boundary"?<<?endl;??
  76. ????????return?0;??
  77. ????}??
  78. ????ListNode<Type>?*newnode?=?new?ListNode<Type>(item),?*pmove?=?head;??
  79. ????if?(newnode?==?NULL){??
  80. ????????cout?<<?"Application?Erorr!"?<<?endl;??
  81. ????????exit(1);??
  82. ????}??
  83. ????for?(int?i?=?0;?i?<?n;?i++){???//find?the?position?for?insert??
  84. ????????pmove?=?pmove->m_pnext;??
  85. ????????if?(pmove?==?head){??
  86. ????????????cout?<<?"The?n?is?out?of?boundary"?<<?endl;??
  87. ????????????return?0;??
  88. ????????}??
  89. ????}??
  90. ??
  91. ????//insert?the?data??
  92. ????newnode->m_pnext?=?pmove->m_pnext;??
  93. ????newnode->m_pprior?=?pmove;??
  94. ????pmove->m_pnext?=?newnode;??
  95. ????newnode->m_pnext->m_pprior?=?newnode;??
  96. ????return?1;??
  97. }??
  98. ??
  99. template<typename?Type>?Type?DoublyList<Type>::Remove(int?n?=?0){??
  100. ????if?(n?<?0){??
  101. ????????cout?<<?"The?n?is?out?of?boundary"?<<?endl;??
  102. ????????exit(1);??
  103. ????}??
  104. ????ListNode<Type>?*pmove?=?head,?*pdel;??
  105. ????for?(int?i?=?0;?i?<?n;?i++){???//find?the?position?for?delete??
  106. ????????pmove?=?pmove->m_pnext;??
  107. ????????if?(pmove?==?head){??
  108. ????????????cout?<<?"The?n?is?out?of?boundary"?<<?endl;??
  109. ????????????exit(1);??
  110. ????????}??
  111. ????}??
  112. ??
  113. ????//delete?the?data??
  114. ????pdel?=?pmove;??
  115. ????pmove->m_pprior->m_pnext?=?pdel->m_pnext;??
  116. ????pmove->m_pnext->m_pprior?=?pdel->m_pprior;??
  117. ????Type?temp?=?pdel->m_data;??
  118. ????delete?pdel;??
  119. ????return?temp;??
  120. }??
  121. ??
  122. template<typename?Type>?Type?DoublyList<Type>::Get(int?n?=?0){??
  123. ????if?(n?<?0){??
  124. ????????cout?<<?"The?n?is?out?of?boundary"?<<?endl;??
  125. ????????exit(1);??
  126. ????}??
  127. ????ListNode<Type>?*pmove?=?head;??
  128. ????for?(int?i?=?0;?i?<?n;?i++){??
  129. ????????pmove?=?pmove->m_pnext;??
  130. ????????if?(pmove?==?head){??
  131. ????????????cout?<<?"The?n?is?out?of?boundary"?<<?endl;??
  132. ????????????exit(1);??
  133. ????????}??
  134. ????}??
  135. ????return?pmove->m_data;??
  136. }??
  137. ??
  138. template<typename?Type>?void?DoublyList<Type>::Print(){??
  139. ????ListNode<Type>?*pmove?=?head->m_pnext;??
  140. ????cout?<<?"head";??
  141. ????while?(pmove?!=?head){??
  142. ????????cout?<<?"--->"?<<?pmove->m_data;??
  143. ????????pmove?=?pmove->m_pnext;??
  144. ????}??
  145. ????cout?<<?"--->over"?<<?endl?<<?endl?<<?endl;??
  146. ??
  147. }??
  148. ??
  149. template<typename?Type>?ListNode<Type>*?DoublyList<Type>::FindData(Type?item){??
  150. ????ListNode<Type>?*pprior?=?head->m_pprior,?*pnext?=?head->m_pnext;??
  151. ????while?(pprior->m_pnext?!=?pnext?&&?pprior?!=?pnext) {?//find?the?data?in?the?two?direction??
  152. ????????if?(pprior->m_data?==?item){??
  153. ????????????return?pprior;??
  154. ????????}??
  155. ????????if?(pnext->m_data?==?item){??
  156. ????????????return?pnext;??
  157. ????????}??
  158. ????????pprior?=?pprior->m_pprior;??
  159. ????????pnext?=?pnext->m_pnext;??
  160. ????}??
  161. ????cout?<<?"can't?find?the?element"?<<?endl;??
  162. ????return?NULL;??
  163. }??
NodeList.h具體內容如下：

[cpp]?view plain?copy
  1. template<typename?Type>?class?DoublyList;??
  2. ??
  3. template<typename?Type>?class?ListNode{??
  4. private:??
  5. ????friend?class?DoublyList?<?Type?>?;??
  6. ????ListNode()?:m_pprior(NULL),?m_pnext(NULL){}??
  7. ????ListNode(const?Type?item,?ListNode<Type>?*prior?=?NULL,?ListNode<Type>?*next?=?NULL)??
  8. ????????:m_data(item),?m_pprior(prior),?m_pnext(next){}??
  9. ????~ListNode(){??
  10. ????????m_pprior?=?NULL;??
  11. ????????m_pnext?=?NULL;??
  12. ????}??
  13. public:??
  14. ????Type?GetData();??
  15. private:??
  16. ????Type?m_data;??
  17. ????ListNode?*m_pprior;??
  18. ????ListNode?*m_pnext;??
  19. };??
  20. ??
  21. template<typename?Type>?Type?ListNode<Type>::GetData(){??
  22. ????return?this->m_data;??
  23. }??
main.cpp的內容如下：

[cpp]?view plain?copy
  1. #include?<iostream>??
  2. #include?"DoubleList.h"??
  3. ??
  4. using?namespace?std;??
  5. ??
  6. int?main()??
  7. {??
  8. ????DoublyList<int>?list;??
  9. ????for?(int?i?=?0;?i?<?20;?i++){??
  10. ????????list.Insert(i?*?3,?i);??
  11. ????}??
  12. ????cout?<<?"the?Length?of?the?list?is?"?<<?list.Length()?<<?endl;??
  13. ????list.Print();??
  14. ????for?(int?i?=?0;?i?<?5;?i++){??
  15. ????????list.Insert(3,?i?*?3);??
  16. ????}??
  17. ????cout?<<?"the?Length?of?the?list?is?"?<<?list.Length()?<<?endl;??
  18. ????list.Print();??
  19. ??
  20. ????list.Remove(5);??
  21. ????cout?<<?"the?Length?of?the?list?is?"?<<?list.Length()?<<?endl;??
  22. ????list.Print();??
  23. ??
  24. ????cout?<<?list.FindData(54)->GetData()?<<?endl;??
  25. ??
  26. ????cout?<<?"The?third?element?is?"?<<?list.Get(3)?<<?endl;??
  27. ??
  28. ????list.MakeEmpty();??
  29. ????cout?<<?"the?Length?of?the?list?is?"?<<?list.Length()?<<?endl;??
  30. ????list.Print();??
  31. ??
  32. ????cin.get();??
  33. ????return?0;??
  34. }??
運行效果如圖1所示：

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

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

相關文章

堆的基本操作

堆的基本操作

堆的數據結構 對于堆, 有最大堆和最小堆, 在定義一個堆的時候用一個數組表示堆, 同時為了方便定義堆的大小, 用一個 size 表示堆的有效元素, 同時為了區別最大堆和最小堆, 我們用一個函數指針表示這個堆是最大堆還是最小堆. typedef int (*Compare)(HeapType parent, HeapTyp…
閱讀更多...
UVa1605

UVa1605

完完全全的構造題 一種比較好想到&#xff08;雖然我沒有想到。。&#xff09;的方法是做成一個兩層的表格&#xff0c;第一層每一行相同&#xff0c;第二層每一列相同&#xff0c;這樣每個都能和其他的相鄰了。 輸出格式稍微注意一下 #include<cstdio> #include<c…
閱讀更多...
Linux下的TCP/IP編程----IO復用及IO復用服務端

Linux下的TCP/IP編程----IO復用及IO復用服務端

http://blog.csdn.net/wqc_csdn/article/details/51583901 在之前我們實現的并發服務端時通過床將多個進程來實現的&#xff0c;這種并實現并發的方式簡單方便&#xff0c;但是進程的創建和銷毀是很消耗系統資源的&#xff0c;在訪問量大時服務器很容易出現資源不夠用的情況。除…
閱讀更多...
UVa120

UVa120

相當于是一個模擬&#xff0c;為了得到合適的順序&#xff0c;我們的策略是每次找到當前沒有被翻的里面最大的&#xff0c;然后把他翻到最前面&#xff0c;然后再翻到合適的位置。 需要判斷一下當前是否已經有序&#xff0c;有序就不用翻了。 如果在最開頭找到了合適的當前應…
閱讀更多...
二叉樹的相關操作

二叉樹的相關操作

二叉樹的數據結構 typedef char SearchTreeType; typedef struct SearchTreeNode { SearchTreeType key; // 關鍵碼 struct SearchTreeNode* lchild; struct SearchTreeNode* rchild; } SearchTreeNode; 二叉樹的初始化 由于我們是用一個指向根節點的指針表示一個二叉樹, …
閱讀更多...
網絡層:網關協議

網絡層:網關協議

一. 網關 所謂的網管即就是之前路由器的名字, 即路由器和網關是一個東西 二. 內部網關協議 1. RIP協議 路由信息協議 RIP 是內部網關協議 IGP中最先得到的廣泛使用的協議. 同時 RIP 是一種分布式基于距離向量的路由選擇協議. RIP 協議要求網絡中的每一個路由都必須維護自己…
閱讀更多...
UVa1152

UVa1152

題意很好理解&#xff0c;就是從四個集合里面取出四個數字的和為0&#xff0c;問有多少種取法。 直接枚舉肯定是會超時的&#xff0c;所以得想辦法優化一下。我們可以將兩個集合的所有的和都放在一個數組里面&#xff0c;這樣得到兩個數組&#xff0c;然后排序&#xff0c;對第…
閱讀更多...
Linux函數--inet_pton / inet_ntop

Linux函數--inet_pton / inet_ntop

http://blog.csdn.net/lindyl/article/details/10427925 inet_pton 和 inet_ntop Linux下這2個IP地址轉換函數&#xff0c;可以在將IP地址在“點分十進制”和“整數”之間轉換而且&#xff0c;inet_pton和inet_ntop這2個函數能夠處理ipv4和ipv6。算是比較新的函數了。 inet_pto…
閱讀更多...
網絡基礎: 淺析應用層一

網絡基礎: 淺析應用層一

應用層 1. http協議 在 http 中協議分為了協議方案名, 登錄信息名, 服務器地址, 服務器端口號(http協議綁定的端口號), 文件類型, 查詢的字符串, 片段標識位 2. http 請求協議格式 httpp 總共分為三大部分, 其中首行即就是第一部分, 分為三個區域, 第一去個區域是請方法, 第…
閱讀更多...
socket 編程篇六之IPO多路復用-select poll epoll

socket 編程篇六之IPO多路復用-select poll epoll

http://blog.csdn.net/woxiaohahaa/article/details/51498951 文章參考自&#xff1a;http://blog.csdn.net/tennysonsky/article/details/45745887&#xff08;秋葉原 — Mike VS 麥克《Linux系統編程——I/O多路復用select、poll、epoll的區別使用》&#xff09; 此外&#x…
閱讀更多...
UVa11054

UVa11054

挺簡單的小模擬。 還是要注意思維的方向&#xff0c;要有切入點&#xff0c;不能像無頭蒼蠅一樣東想一下西想一下&#xff0c;而應該分析問題的性質&#xff0c;然后嘗試思維的方向&#xff0c;從不同的方向思考&#xff08;順序&#xff0c;逆序&#xff0c;排序后&#xff0…
閱讀更多...
淺談傳輸層

淺談傳輸層

1. 傳輸層的作用 在傳輸層中有兩個特別重要的協議 TCP/UDP . 以快遞員送快遞為例說明這個問題吧. 在進行包裹傳輸的過程中快遞員需要根據快遞上的目的地址(目的計算機)來投遞包裹(IP數據報), 加入在快遞單上只寫了收件人的所在地, 所在單位, 而只寫了收件人的姓沒有寫收件人的…
閱讀更多...
UVa10375

UVa10375

題目描述很簡單,就是求兩個組合數的商.可是數字范圍很大,肯定不能直接計算. 因此要用到唯一分解定理,即將結果全部表示為素因子的冪的形式. #include<cstdio> #include<cstring> #include<algorithm> #include<climits> #include<cctype> #inc…
閱讀更多...
I/O復用的 select poll和epoll的簡單實現

I/O復用的 select poll和epoll的簡單實現

http://www.cnblogs.com/wj9012/p/3876734.html 一個tcp的客戶端服務器程序 服務器端不變&#xff0c;客戶端通過I/O復用輪詢鍵盤輸入與socket輸入&#xff08;接收客戶端的信息&#xff09; 服務器端&#xff1a; 1 /*服務器:2 1.客戶端關閉后&#xff0c;服務器再向客戶端發送…
閱讀更多...
netstat 相關命令解析

netstat 相關命令解析

1.列出所有的端口 netstat -a 列出TCP協議的端口 netstat -at UDP協議的端口 netstat -au 2.列出處于監聽狀態的socket netstat -l 列出監聽的TCP端口 netstat -lt 列出監聽的UDP端口 netstat -lu 列出監聽的UNIX端口 netstat -lx 3.列出協議的統計信息 nestat …
閱讀更多...
UVa10791

UVa10791

我們可以先用唯一分解定理將這個數字分解成素因子冪的乘積&#xff0c;為了得到最小的和&#xff0c;我們可以發現&#xff1a;每個 素因子的冪單獨分開的和是最小的。 先說明每個素因子都是以出現的最大的次數出現。因為最小公倍數一定&#xff0c;因此至少有一個數字的這個素…
閱讀更多...
TCP相關代碼

TCP相關代碼

TCP 基礎代碼 //tcp_server.c #include<stdio.h> #include<error.h> #include<sys/types.h> #include<string.h> #include<unistd.h> #include<sys/socket.h> #include<netinet/in.h> #include <arpa/inet.h> #include<st…
閱讀更多...
UVa1635

UVa1635

我們很容易發現最后每一項的系數就是二項式展開&#xff0c;余數和m沒有關系就意味著可以被m整除&#xff0c;因此我們就需要求出每一個二項式的系數。但是數據實在太大我們根據唯一分解定理將m和系數都進行分解&#xff0c;然后比較因子的冪。 二項式的計算我們可以根據楊輝三…
閱讀更多...
幾種并發服務器模型的實現：多線程，多進程，select，poll，epoll

幾種并發服務器模型的實現：多線程，多進程，select，poll，epoll

http://www.cnblogs.com/wj9012/p/3879605.html 客戶端使用select模型&#xff1a; 1 #include <stdio.h>2 #include <stdlib.h>3 #include <string.h>4 #include <errno.h>5 #include <sys/types.h>6 #include <sys/socket.h>7 #include …
閱讀更多...
哈希表1

哈希表1

1. 初始化 void HashInit(HashTable* ht, HashFunc func) {if(ht NULL || func NULL){return;}ht -> size 0;ht -> func func;int i 0;for(; i < HashMaxSize; i){ht -> data[i].state Empty;} } 2. 哈希表的銷毀 void HashDestroy(HashTable* ht) {if(ht…
閱讀更多...
最新文章

Copyright @ 2022~2023