双向链表的相关操作C++实现

我会带着你远行 2022-08-21 08:52 202阅读 0赞

对于循环双向链表

判断一个链表是否为空的条件为：head->next==head (头指针)

判断\*p为最后一个节点的条件为：p->next=head

**\[cpp\]**  [view plain][]   [copy][view plain]

1.  \#include<iostream>  
2.  **using** **namespace** std;  
3.    
4.  /\*双链表结构\*/  
5.  **typedef** **struct** node  
6.  \{  
7.      **int** data;  
8.      **struct** node \*prior;  
9.      **struct** node \*next;  
10.   
11. \}DNode;   
12. /\*创建一个带头节点的双链表\*/  
13. **void** CreateDLink(DNode \*&head)  
14. \{  
15.     **int** x;  
16.     DNode \*p,\*s;  
17.     s=(DNode \*)malloc(**sizeof**(DNode));  
18.     **if**(s==NULL)  
19.     \{  
20.         cout<<"Fail to malloc the head node!"<<endl;  
21.           
22.     \}  
23.        s->data=0;  
24.         s->prior=NULL;  
25.         s->next=NULL; //建立一个头结点为head的双链表  
26.     head=s;   //若是循环双向链表则为：s->next=s->prior=s;  
27.     cout<<"please input the data of the node"<<endl;  
28.   cin>>x;  
29.     **while**(x!=0)  
30.     \{  
31.       p=(DNode \*)malloc(**sizeof**(DNode));  
32.      **if**(p==NULL)  
33.      \{  
34.         cout<<"Fail to malloc a new  node!"<<endl;  
35.           
36.      \}  
37.        
38.      p->data=x;  
39.      s->next=p;  
40.      p->prior=s;  
41.      p->next=NULL;  
42.      s=p;  
43.   
44.        
45.     cin>>x;  
46.     \}  
47.   
48. \}  
49.   
50. **void** PrintLink(DNode \*head)  
51. \{  
52.     **if**(head->next==NULL)  
53.     \{  
54.         cout<<"The list is NULL"<<endl;  
55.         **return** ;  
56.     \}  
57.     DNode \*p;  
58.     p=head->next;  
59.     **while**(p!=NULL)  
60.     \{  
61.         cout<<p->data<<" ";  
62.         p=p->next;  
63.           
64.     \}  
65.    cout<<endl;  
66. \}  
67. **int** Length(DNode \*head) //求双链表长度  
68. \{  
69.     **int** len=0;  
70.     DNode \* p=head->next;  
71.     **while**(p!=NULL)  
72.     \{  
73.         len++;  
74.         p=p->next;  
75.     \}  
76.     **return** len;  
77.   
78. \}  
79. DNode \* Get(DNode \*head,**int** i) //获取链表第i个节点地址  
80. \{  
81.     **int** j=0;  
82.     DNode \*p=head->next;  
83.     **while**(j<i&&p!=NULL)  
84.     \{  
85.         p=p->next;  
86.         j++;  
87.     \}  
88.     **if**(p!=NULL)  
89.         **return** p;  
90.     **else**   
91.         **return** NULL;  
92. \}  
93. **int** InsertNode(DNode \*head,**int** x,**int** i)//在第i个位置插入一个节点  
94. \{  
95.     DNode \*s,\*p;  
96.     s=(DNode \*)malloc(**sizeof**(DNode));  
97.     s->data=x;  
98.     **if**(i==0)  
99.     \{  
100.         s->next=head->next;  
101.         **if**(head->next!=NULL)  
102.             head->next->prior=s;  
103.         s->prior=head;  
104.         head->next=s;  
105.           
106.     \}  
107.     **else**  
108.     \{  
109.         p=Get(head,i-1); //查找待插入节点前一个位置  
110.         **if**(p==NULL)  
111.             **return** 0;  
112.         **else**  
113.         \{  
114.             s->next=p->next;  
115.             **if**(p->next!=NULL)  
116.                 p->next->prior=s;  
117.             s->prior=p;  
118.             p->next=s;  
119.         \}  
120.     \}  
121.   
122.     **return** 1;  
123. \}  
124.   
125. **void** DeleteNode(DNode \*head,**int** index) //删除第index个节点  
126. \{  
127.     **if**(head->next==NULL)  
128.     \{  
129.         cout<<"The list is NULL"<<endl;  
130.         **return**;  
131.     \}  
132.     DNode \*p,\*s/\*保存待删除的节点\*/;  
133.     **if**(index==0)  
134.     \{  
135.         s=head->next;  
136.         head->next=s->next;  
137.         **if**(s->next!=NULL)  
138.             s->next->prior=head;  
139.          free(s);  
140.     \}  
141.     **else**  
142.     \{  
143.         p=Get(head,index-1);  
144.         **if**(p==NULL)  
145.             cout<<"The Node "<<index<<"is not exist"<<endl;  
146.         **else**  
147.         \{  
148.             s=p->next;  
149.             p->next=s->next;  
150.             **if**(s->next!=NULL)  
151.                 s->next->prior=p;  
152.             free(s);  
153.         \}  
154.     \}  
155.   
156. \}  
157. **int** main(**int** argc,**char** \*argv\[\])  
158. \{  
159.   DNode \*head;  
160.   CreateDLink(head);   
161.   cout<<"链表长度为："<<Length(head)<<endl;  
162.    PrintLink(head);  
163.    cout<<"第3个节点的值为:"<<Get(head,3)->data<<endl;  
164.    
165.    cout<<"输入插入节点的位置及值："<<endl;  
166.     **int** value, index;  
167.     cin>>index>>value;  
168.    InsertNode(head,value,index);  
169.    cout<<"插入后的链表为："<<endl;  
170.        PrintLink(head);  
171.   
172.        cout<<"请输入要删除的节点位置："<<endl;  
173.        cin>>index;  
174.        DeleteNode(head,index);  
175.    PrintLink(head);  
176.     **return** 0;  
177. \}  
178.

[view plain]: http://blog.csdn.net/xiaoding133/article/details/7736379#