本文實(shí)例講述了C++雙向循環(huán)列表用法。分享給大家供大家參考。具體如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
|
/* 雙向循環(huán)鏈表 */#include <iostream>using namespace std;//結(jié)構(gòu)體構(gòu)造鏈表的指針域和數(shù)據(jù)域struct ChainNode{ int data; //節(jié)點(diǎn)數(shù)據(jù) ChainNode *left; //節(jié)點(diǎn)的前驅(qū)指針 ChainNode *right; //節(jié)點(diǎn)的后繼指針 };////////////創(chuàng)建n個(gè)雙向循環(huán)鏈表 并返回鏈表頭指針///////// ChainNode* CreateNode(int n){ ChainNode *head = NULL; //鏈表頭節(jié)點(diǎn) ChainNode *pCur=NULL,*pNew=NULL; //當(dāng)前節(jié)點(diǎn)，新建節(jié)點(diǎn) //初始化頭結(jié)點(diǎn)的前驅(qū)和后繼節(jié)點(diǎn)都為NULL if (n<1) //沒(méi)有節(jié)點(diǎn) 返回頭節(jié)點(diǎn) { return head; } //創(chuàng)建頭節(jié)點(diǎn)并將器左右指針指向空 head = new ChainNode; head->left = NULL; head->right = NULL; head->data = 0; pCur = head; //為防止指針互指帶來(lái)的混亂，用pCur節(jié)點(diǎn)保存了頭節(jié)點(diǎn) 也表示當(dāng)前指針移動(dòng)到了頭指針 //創(chuàng)建n個(gè)節(jié)點(diǎn) 并連接成鏈表 for (int i=0; i<n; i++) { pNew = new ChainNode; //創(chuàng)建一個(gè)新節(jié)點(diǎn) cout<<"請(qǐng)輸入數(shù)據(jù)："; cin>>pNew->data; pCur->right = pNew; //頭指針的右指針指向新建節(jié)點(diǎn) pNew->left = pCur; //新建節(jié)點(diǎn)的左指針執(zhí)行頭節(jié)點(diǎn) pNew->right = NULL; //用于最后和頭指針進(jìn)行交換 pCur = pNew; //指針往下移動(dòng) } //最后將頭指針的左指針指向最后一個(gè)節(jié)點(diǎn)， //最后一個(gè)節(jié)點(diǎn)的有指針指向頭指針，構(gòu)成循環(huán) head->left = pCur; pCur->right = head; return head; }//////////////輸出鏈表頭節(jié)點(diǎn)/////////////////////// void OutList(ChainNode *head) //參數(shù)為頭指針 從頭指針開(kāi)始 { cout<<"鏈表元素輸出如下："<<endl; ChainNode *pCur = head->right; //重第一個(gè)節(jié)點(diǎn)開(kāi)始輸出 //沒(méi)有指向空節(jié)點(diǎn)，則鏈表沒(méi)結(jié)束 輸出鏈表元素 while (pCur->right != head) { cout<<pCur->data<<" "; pCur = pCur->right; //當(dāng)前節(jié)點(diǎn)指向下一個(gè)節(jié)點(diǎn) 可以遍歷鏈表 } cout<<pCur->data<<endl; //輸入最后一個(gè)元素，它的右指針執(zhí)行head }///////在雙向循環(huán)鏈表后添加n個(gè)節(jié)點(diǎn)//////ChainNode* AddNode(ChainNode* head, int n){ ChainNode *pNew,*pCur; //新添加節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn) pCur = head; //移動(dòng)到最節(jié)點(diǎn) while (pCur->right != head) { pCur = pCur->right; //當(dāng)前節(jié)點(diǎn)往下移動(dòng) 一直移到最后一個(gè)節(jié)點(diǎn) } //新添加n個(gè)節(jié)點(diǎn)并插入鏈表 for (int i=0; i<n; i++) { pNew = new ChainNode; cout<<"輸入要添加的節(jié)點(diǎn)元素："; cin>>pNew->data; pCur->right = pNew; //頭指針的右指針指向新建節(jié)點(diǎn) pNew->left = pCur; //新建節(jié)點(diǎn)的左指針執(zhí)行頭節(jié)點(diǎn) pNew->right = NULL; //用于最后和頭指針進(jìn)行交換 pCur = pNew; //指針往下移動(dòng) } //最后將頭指針的左指針指向最后一個(gè)節(jié)點(diǎn)， //最后一個(gè)節(jié)點(diǎn)的有指針指向頭指針，構(gòu)成循環(huán) head->left = pCur; pCur->right = head; return head; } /////在雙向循環(huán)鏈表中刪除一個(gè)節(jié)點(diǎn)/////// ChainNode* DeleteNode(ChainNode* head, unsigned num)//刪除第num個(gè)節(jié)點(diǎn){ ChainNode *pNew,*pCur,*temp; //新添加節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn) ,臨時(shí)交換節(jié)點(diǎn) pCur = head; int ncount = 0; //移動(dòng)到第num-1個(gè)節(jié)點(diǎn) while (1) { ncount++; pCur = pCur->right; //當(dāng)前節(jié)點(diǎn)往下移動(dòng) if (num == ncount) { break; //此時(shí)pCur還是指向了第num個(gè)節(jié)點(diǎn) } } //當(dāng)前節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的右指針 指向 當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn) //當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的左指針 指向 當(dāng)前節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn) 構(gòu)成連接 //最后 刪除當(dāng)前節(jié)點(diǎn) (pCur->left)->right = pCur->right; (pCur->right)->left = pCur->left; delete pCur; return head; }int main(){ int num; //創(chuàng)建num個(gè)節(jié)點(diǎn)并顯示 cout<<"輸入要?jiǎng)?chuàng)建的鏈表節(jié)點(diǎn)個(gè)數(shù):"; cin>>num; ChainNode *head = CreateNode(num); OutList(head); //往鏈表后添加n個(gè)節(jié)點(diǎn) int addnum; cout<<"輸入要添加的節(jié)點(diǎn)個(gè)數(shù):"; cin>>addnum; AddNode(head, addnum); OutList(head); //刪除鏈表的第del個(gè)元素 int del; cout<<"輸入要?jiǎng)h除的第幾個(gè)位置的節(jié)點(diǎn):"; cin>>del; DeleteNode (head, del); OutList(head); system("pause"); return 0;} |
希望本文所述對(duì)大家的C++程序設(shè)計(jì)有所幫助。
