C++双向循环列表用法实例

这篇文章主要介绍了C++双向循环列表,实例分析了C++双向循环列表的创建、输出、添加、删除、移动的相关操作技巧,具有一定参考借鉴价值,需要的朋友可以参考下

本文实例讲述了C++双向循环列表用法。分享给大家供大家参考。具体如下：

1. /*  
2. 双向循环链表  
3. */ 
4. #include <iostream> 
5. using namespace std; 
6. //结构体构造链表的指针域和数据域 
7. struct ChainNode 
8. { 
9. int data; //节点数据  
10. ChainNode *left; //节点的前驱指针 
11. ChainNode *right; //节点的后继指针  
12. }; 
13. ////////////创建n个双向循环链表 并返回链表头指针/////////  
14. ChainNode* CreateNode(int n) 
15. { 
16. ChainNode *head = NULL; //链表头节点 
17. ChainNode *pCur=NULL,*pNew=NULL; //当前节点，新建节点 
18. //初始化头结点的前驱和后继节点都为NULL  
19. if (n<1) //没有节点 返回头节点  
20. { 
21. return head;  
22. }  
23. //创建头节点并将器左右指针指向空  
24. head = new ChainNode;  
25. head->left = NULL; 
26. head->right = NULL;  
27. head->data = 0; 
28. pCur = head; 
29. //为防止指针互指带来的混乱，用pCur节点保存了头节点 也表示当前指针移动到了头指针  
30. //创建n个节点 并连接成链表  
31. for (int i=0; i<n; i++) 
32. { 
33. pNew = new ChainNode; //创建一个新节点 
34. cout<<"请输入数据："; 
35. cin>>pNew->data; 
36. pCur->right = pNew; //头指针的右指针指向新建节点  
37. pNew->left = pCur; //新建节点的左指针执行头节点  
38. pNew->right = NULL; //用于最后和头指针进行交换  
39. pCur = pNew; //指针往下移动  
40. }  
41. //最后将头指针的左指针指向最后一个节点， 
42. //最后一个节点的有指针指向头指针，构成循环  
43. head->left = pCur;  
44. pCur->right = head; 
45. return head;  
46. } 
47. //////////////输出链表头节点///////////////////////  
48. void OutList(ChainNode *head) //参数为头指针 从头指针开始  
49. { 
50. cout<<"链表元素输出如下："<<endl; 
51. ChainNode *pCur = head->right; 
52. //重第一个节点开始输出  
53. //没有指向空节点，则链表没结束 输出链表元素  
54. while (pCur->right != head)  
55. { 
56. cout<<pCur->data<<" "; 
57. pCur = pCur->right; 
58. //当前节点指向下一个节点 可以遍历链表  
59. }  
60. cout<<pCur->data<<endl; 
61. //输入最后一个元素，它的右指针执行head  
62. } 
63. ///////在双向循环链表后添加n个节点////// 
64. ChainNode* AddNode(ChainNode* head, int n) 
65. { 
66. ChainNode *pNew,*pCur; 
67. //新添加节点和当前节点 
68. pCur = head;  
69. //移动到最节点 
70. while (pCur->right != head)  
71. { 
72. pCur = pCur->right; 
73. //当前节点往下移动 一直移到最后一个节点  
74. } 
75. //新添加n个节点并插入链表 
76. for (int i=0; i<n; i++) 
77. { 
78. pNew = new ChainNode; 
79. cout<<"输入要添加的节点元素："; 
80. cin>>pNew->data; 
81. pCur->right = pNew; //头指针的右指针指向新建节点  
82. pNew->left = pCur; //新建节点的左指针执行头节点  
83. pNew->right = NULL; //用于最后和头指针进行交换  
84. pCur = pNew; //指针往下移动  
85. }  
86. //最后将头指针的左指针指向最后一个节点， 
87. //最后一个节点的有指针指向头指针，构成循环  
88. head->left = pCur;  
89. pCur->right = head; 
90. return head;  
91. }  
92. /////在双向循环链表中删除一个节点///////  
93. ChainNode* DeleteNode(ChainNode* head, unsigned num) 
94. //删除第num个节点 
95. { 
96. ChainNode *pNew,*pCur,*temp; 
97. //新添加节点和当前节点 ,临时交换节点  
98. pCur = head;  
99. int ncount = 0;  
100. //移动到第num-1个节点 
101. while (1) 
102. { 
103. ncount++; 
104. pCur = pCur->right; //当前节点往下移动  
105. if (num == ncount) 
106. { 
107. break; //此时pCur还是指向了第num个节点  
108. }  
109. } 
110. //当前节点的前一个节点的右指针 指向 当前节点的下一个节点 
111. //当前节点的下一个节点的左指针 指向 当前节点的上一个节点 构成连接 
112. //最后 删除当前节点  
113. (pCur->left)->right = pCur->right; 
114. (pCur->right)->left = pCur->left; 
115. delete pCur; 
116. return head;  
117. } 
118. int main() 
119. { 
120. int num; 
121. //创建num个节点并显示  
122. cout<<"输入要创建的链表节点个数:"; 
123. cin>>num; 
124. ChainNode *head = CreateNode(num); 
125. OutList(head);  
126. //往链表后添加n个节点 
127. int addnum; 
128. cout<<"输入要添加的节点个数:"; 
129. cin>>addnum;  
130. AddNode(head, addnum); 
131. OutList(head);  
132. //删除链表的第del个元素 
133. int del; 
134. cout<<"输入要删除的第几个位置的节点:"; 
135. cin>>del; 
136. DeleteNode (head, del); 
137. OutList(head); 
138. system("pause"); 
139. return 0; 
140. } 

希望本文所述对大家的C++程序设计有所帮助。