1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef struct LinkNode
4 {
5 int data;
6 LinkNode* next;
7 }LinkNode;
8 LinkNode *InitList() //创建空的单链表
9 {
10 LinkNode *L = (LinkNode*)malloc(sizeof(LinkNode));
11 L->next = NULL;
12 return L;
13 }
14 void initLinkList(LinkNode *L)//尾插法插入数据
15 {
16 LinkNode *current = (LinkNode *)malloc(sizeof(LinkNode));
17 L->next = current;
18 printf("请输入结点数据（-1退出）");
19 int tmp = 0;
20 scanf("%d",&tmp);
21 current->data=tmp;
22 while (1)
23 {
24 scanf("%d", &tmp);
25 if (tmp == -1)
26 {
27 break;
28 }
29 LinkNode *node = (LinkNode *)malloc(sizeof(LinkNode));
30 node->next = NULL;
31 node->data = tmp;
32 current->next = node;//建立连接
33 current = node;//更新
34 }
35 }
36
37 int printLinkList(LinkNode* pHeader)//依次输出当前链表每个元素
38 {
39 if (pHeader == NULL)
40 {
41 return 0;
42 }
43 if (pHeader->next == NULL)
44 {
45 printf("当前链表为空！\n");
46 }
47 LinkNode* cur = pHeader->next;
48 int num = 1;
49 while (cur!=NULL)
50 {
51 printf("第%d个结点: %d ", num, cur->data);
52 cur = cur->next;
53 num++;
54 }
55 cout<<'\n';
56 return 0;
57 }
58 int getLengthLinkList(LinkNode* pHeader)//输出链表的长度
59 {
60 if (pHeader == NULL)
61 {
62 return 0;
63 }
64 LinkNode* cur = pHeader;
65 int length = 0;
66 while (cur->next != NULL)
67 {
68 cur = cur->next;
69 length++;
70 }
71 return length;
72 }
73
74 int printLinkListnumber(LinkNode* pHeader,int n)//输出位置n的数字
75 {
76 if (pHeader == NULL)
77 {
78 return 0;
79 }
80 if (pHeader->next == NULL)
81 {
82 printf("当前链表为空！\n");
83 }
84 LinkNode* cur = pHeader->next;
85 int num = 1;
86 while (cur!=NULL)
87 {
88 if(num==n)
89 {
90 printf("第%d个结点: %d\n", num, cur->data);
91 break;
92 }
93 cur = cur->next;
94 num++;
95 }
96 return 0;
97 }
98
99 int printLinkListvalue(LinkNode* pHeader,int val)//输出值为n的元素位置
100 {
101 if (pHeader == NULL)
102 {
103 return 0;
104 }
105 if (pHeader->next == NULL)
106 {
107 printf("当前链表为空！\n");
108 }
109 LinkNode* cur = pHeader->next;
110 int num = 1;
111 while (cur!=NULL)
112 {
113 if(cur->data==val)
114 {
115 printf("值为%d的元素位于第%d个节点里\n", cur->data, num);
116 break;
117 }
118 cur = cur->next;
119 num++;
120 }
121 return 0;
122 }
123
124 //loc 插入到链表的第几个位置，从1开始 loc <=1 放在第一个位置 ，超过结点最后一个位置放在尾结点
125 int insertPositionLinkList(LinkNode* pHeader,int loc, int val)
126 {
127 if (pHeader == NULL)
128 {
129 return 0;
130 }
131 LinkNode* cur = pHeader;
132 int i = 1;
133 while (cur->next!=NULL && i<loc)
134 {
135 i++;
136 cur = cur->next;
137 }
138 //cur 为插入元素的前驱结点
139 LinkNode* newNode = (LinkNode*)malloc(sizeof(LinkNode));
140 newNode->data = val;
141 newNode->next = cur->next;
142 cur->next = newNode;
143 return 1;
144 }
145 //删除结点
146 int deleteLinkList(LinkNode* pHeader,int val)
147 {
148 if (pHeader == NULL)
149 {
150 return 0;
151 }
152 LinkNode* pre = pHeader;
153 LinkNode* cur = pHeader->next;
154 while (cur != NULL)
155 {
156 if (cur->data == val)
157 {
158 break;
159 }
160 pre = pre->next;
161 cur = cur->next;
162 }
163 if (cur != NULL)
164 {
165 pre->next = cur->next;
166 free(cur);
167 cur = NULL;
168 }
169 return 1;
170 }
171 //清空链表 保留头结点
172 int clearLinkList(LinkNode* pHeader)
173 {
174 if (pHeader == NULL)
175 {
176 return 0;
177 }
178 LinkNode* cur = pHeader->next;
179 while (cur != NULL)
180 {
181 LinkNode* next = cur->next;
182 free(cur);
183 cur = next;
184 }
185 pHeader->next = NULL;
186 return 1;
187 }
188 //销毁链表
189 int destroyLinkList(LinkNode* pHeader)
190 {
191 if (pHeader == NULL)
192 {
193 return 0;
194 }
195 clearLinkList(pHeader);
196 free(pHeader);
197 return 1;
198 }
199 //删除第loc位置的元素
200 int delPositionLinkList(LinkNode* pHeader, int loc)
201 {
202 if (pHeader == NULL || loc < 1)
203 {
204 cout<<"不可以！"<<endl;
205 return 0;
206 }
207 LinkNode* cur = pHeader;
208 int i = 1;
209 while (cur->next != NULL&&i<loc)
210 {
211 i++;
212 cur = cur->next;
213 }
214 //cur 为删除元素的前驱结点
215 if (i == loc && cur->next!=NULL)
216 {
217 LinkNode* del = cur->next;
218 cur->next = del->next;
219 free(del);
220 del = NULL;
221 return 1;
222 }
223 return 0;
224 }
225 //链表反转
226 int reverseLinkList(LinkNode* pHeader)
227 {
228 if (pHeader == NULL)
229 {
230 return 0;
231 }
232 LinkNode* pre = NULL;
233 LinkNode* cur = pHeader->next;
234 LinkNode* next = NULL;
235 while (cur !=NULL)
236 {
237 //保存当前节点的下一个结点
238 next = cur->next;
239 //将当前节点的next域指向前一个结点
240 cur->next = pre;
241
242 //pre、cur 往后移动
243 pre = cur;
244 cur = next;
245 }
246 //循环结束 pre 指向最后一个结点，将头结点指向 它
247 pHeader->next = pre;
248 return 1;
249 }
250
251 int main()
252 {
253 LinkNode* tmp;
254 int x,y;
255 int menu = 0;
256 printf("-------------------菜单--------------------\n");
257 printf("---1、初始化链表---------------------------\n");
258 printf("---2、一次采用尾插法插入a、b、c、d、e元素--\n");
259 printf("---3、输出单链表；-------------------------\n");
260 printf("---4、判断单链表是否为空并输出单链表长度---\n");
261 printf("---5、输出单链表的第3个元素----------------\n");
262 printf("---6、输出元素d的位置----------------------\n");
263 printf("---7、在第4个元素位置上插入f元素-----------\n");
264 printf("---8、输出插入后的单链表-------------------\n");
265 printf("---9、删除单链表中的第2个元素；------------\n");
266 printf("---10、输出删除后的单链表；----------------\n");
267 printf("---11、单链表“原地”逆转，------------------\n");
268 printf("---12、输出逆转后的单链表；----------------\n");
269 printf("---0、退出---------------------------------\n");
270 while (1)
271 {
272 printf("请输入:");
273 scanf("%d",&menu);
274 if (menu == 0)
275 {
276 break;
277 }
278 switch (menu)
279 {
280 case 1:
281 tmp=InitList();
282 cout<<"初始化链表成功"<<endl;
283 break;
284 case 2:
285 initLinkList(tmp);
286 cout<<"成功"<<endl;
287 break;
288 case 3:
289 printLinkList(tmp);
290 break;
291 case 4:
292 cout<<"当前链表长度为："<<getLengthLinkList(tmp)<<endl;
293 break;
294 case 5:
295 cout<<"请输入你要查询元素的位置";
296 scanf("%d",&x);
297 printLinkListnumber(tmp,x);
298 break;
299 case 6:
300 cout<<"请输入你要查询元素的值";
301 scanf("%d",&x);
302 printLinkListvalue(tmp,x);
303 break;
304 case 7:
305 cout<<"请输入你要插入的元素以及它位置";
306 scanf("%d %d",&x,&y);
307 insertPositionLinkList(tmp,x,y);
308 break;
309 case 8:
310 printLinkList(tmp);
311 break;
312 case 9:
313 cout<<"请输入你要删除元素的位置"<<endl;
314 scanf("%d",&x);
315 delPositionLinkList(tmp,x);
316 break;
317 case 10:
318 printLinkList(tmp);
319 break;
320 case 11:
321 reverseLinkList(tmp);
322 break;
323 case 12:
324 printLinkList(tmp);
325 break;
326 default:
327 break;
328 }
329
330 }
331 return 0;
332 }
好像就是以前弄得作业
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef struct LinkNode
4 {
5 int data;
6 LinkNode* next;
7 } LinkNode;
8 LinkNode *InitList() //创建空的单链表
9 {
10 LinkNode *L = (LinkNode*)malloc(sizeof(LinkNode));
11 L->next = NULL;
12 return L;
13 }
14 void initLinkList(LinkNode *L)//尾插法插入数据
15 {
16 LinkNode *current = (LinkNode *)malloc(sizeof(LinkNode));
17 L->next = current;
18 printf("请输入结点数据（-1退出）");
19 int tmp = 0;
20 scanf("%d",&tmp);
21 current->data=tmp;
22 while (scanf("%d",&tmp)&&tmp!=-1)
23 {
24 LinkNode *node = (LinkNode *)malloc(sizeof(LinkNode));
25 node->next = NULL;
26 node->data = tmp;
27 current->next = node;//建立连接
28 current = node;//更新
29 }
30 }
31
32 int printLinkList(LinkNode* pHeader,int x)//依次输出当前链表每个元素
33 {
34 if (pHeader == NULL)
35 {
36 return 0;
37 }
38 if (pHeader->next == NULL)
39 {
40 printf("当前链表为空！\n");
41 }
42 LinkNode* cur = pHeader->next;
43 cout<<"当前链表("<<x<<")存放的元素依次为："<<endl;
44 while (cur!=NULL)
45 {
46 cout<<cur->data<<' ';
47 cur = cur->next;
48 }
49 cout<<'\n';
50 return 0;
51 }
52 void Union(LinkNode *a,LinkNode *b,LinkNode *c)
53 {
54 LinkNode *current = (LinkNode *)malloc(sizeof(LinkNode));
55 c->next = current;
56 LinkNode *pa = a->next;
57 current->data=pa->data;
58 pa=pa->next;
59 while (pa!=NULL)
60 {
61 LinkNode *node = (LinkNode *)malloc(sizeof(LinkNode));
62 node->next = NULL;
63 node->data = pa->data;
64 pa=pa->next;
65 current->next = node;//建立连接
66 current = node;//更新
67 }
68 LinkNode *pb = b->next;
69 while(pb!=NULL)
70 {
71 pa=c->next;
72 while(pa!=NULL)
73 {
74 if(pb->data==pa->data)
75 {
76 break;
77 }
78 pa=pa->next;
79 }
80 if(pa==NULL)
81 {
82 LinkNode *node = (LinkNode *)malloc(sizeof(LinkNode));
83 node->next = NULL;
84 node->data = pb->data;
85 current->next = node;//建立连接
86 current = node;
87 }
88 pb=pb->next;
89 }
90 }
91 void Intersection(LinkNode *a,LinkNode *b,LinkNode *c)
92 {
93 LinkNode *current = (LinkNode *)malloc(sizeof(LinkNode));
94 c->next = current;
95 LinkNode *pa;
96 LinkNode *pb = b->next;
97 bool flag=0;
98 while(pb!=NULL)
99 {
100 pa=a->next;
101 while(pa!=NULL)
102 {
103 if(pb->data==pa->data)
104 {
105 if(flag==0)
106 {
107 current->data=pb->data;
108 flag=1;
109 }
110 else
111 {
112 LinkNode *node = (LinkNode *)malloc(sizeof(LinkNode));
113 node->next = NULL;
114 node->data = pb->data;
115 current->next = node;//建立连接
116 current = node;
117 }
118 }
119 pa=pa->next;
120 }
121 pb=pb->next;
122 }
123 }
124 void destroyLinkList(LinkNode* L)
125 {
126 LinkNode *pre,*p;
127 pre=L;//头节点
128 p=L->next;
129 free(pre);
130 while(p!=NULL)
131 {
132 pre=p;
133 p=p->next;
134 free(pre);
135 }
136 free(p);
137 }
138 int main()
139 {
140 LinkNode* tmp1,*tmp2,*tmp3;
141 int x,y;
142 int menu = 0;
143 printf("-------------------菜单----------------------\n");
144 printf("---1、初始化链表(1)--------------------------\n");
145 printf("---2、一次采用尾插法插入元素并输出单链表(1)--\n");
146 printf("---3、初始化链表(2)--------------------------\n");
147 printf("---4、一次采用尾插法插入元素并输出单链表(2)--\n");
148 printf("---5、求单链表a、b的并集并输出最终的结果---\n");
149 printf("---6、求单链表a、b的交集并输出最终的结果---\n");
150 printf("---0、退出---------------------------------\n");
151 while (1)
152 {
153 printf("请输入:");
154 scanf("%d",&menu);
155 if (menu == 0)
156 {
157 break;
158 }
159 switch (menu)
160 {
161 case 1:
162 tmp1=InitList();
163 cout<<"初始化链表(1)成功"<<endl;
164 break;
165 case 2:
166 initLinkList(tmp1);
167 cout<<"成功"<<endl;
168 printLinkList(tmp1,1);
169 break;
170 case 3:
171 tmp2=InitList();
172 cout<<"初始化链表(2)成功"<<endl;
173 break;
174 case 4:
175 initLinkList(tmp2);
176 cout<<"成功"<<endl;
177 printLinkList(tmp2,2);
178 break;
179 case 5:
180 tmp3=InitList();
181 Union(tmp1,tmp2,tmp3);
182 printLinkList(tmp3,3);
183 destroyLinkList(tmp3);
184 break;
185 case 6:
186 tmp3=InitList();
187 Intersection(tmp1,tmp2,tmp3);
188 printLinkList(tmp3,3);
189 destroyLinkList(tmp3);
190 break;
191 default:
192 break;
193 }
194
195 }
196 return 0;
197 }