链表调通
数据结构-链表
新手学习，代码还很死板，不灵活。期待改进。
环境：vc6
语言：c
运行结果： $ 为结束符号，不会读入$
qwe$ 全部元素为:qwe 一共有:3个元素 查找节点的内容,元素序号为:2 2:w 查找节点的位置，内容为:e e:3 删除节点，节点的位置:1 删除内容为：q 剩余元素为:we 在i插入e:2r 全部元素为:wre 排序后元素为:erw 新链表q:ert$ q合并p后:全部元素为:erwert Press any key to continue
全部代码：
1 #include "stdio.h"
2 #include "malloc.h"
3 #include "string.h"
4
5 typedef struct Node
6 {
7 char data;
8 struct Node * next;
9 }Node, *LinkList;/* LinkList为结构指针类型*/
10
11 //创建一个链表
12 LinkList CreateFromHead();//头插
13 LinkList CreateFromTail(); //尾插/*将新增的字符追加到链表的末尾*/
14
15 int ListLength(LinkList L); //L为带头结点的链表求长度
16 //查找
17 Node * Get2(LinkList L, int i);//按元素序号查找
18 Node *Locate2(LinkList L,char key);//按元素值查找
19 void Get1(LinkList L, int i);//按元素序号查找
20 void Locate1(LinkList L,char key);//按元素值查找
21 //更改
22
23 //删除
24 void DelList(LinkList L,int i,char *e);//删除结点 序号
25 //插入
26 void InsList(LinkList L,int i,char e);//插入结点
27 //合并
28 LinkList Merge(LinkList LA, LinkList LB);
29 //排序
30 void sore(LinkList head);
31 //打印
32 void printList(LinkList L);
33
34 //合并 有序
35 LinkList MergeLinkList(LinkList LA, LinkList LB);//两个从小到大有序链表合并成为有序链表 LC
36
37 int main()
38 { /* LinkList为结构指针类型*/
39 Node *p, *q;
40 char c, e;
41 int i;
42
43 p = (Node*)malloc(sizeof(Node));
44 p = CreateFromTail();
45
46 printf("全部元素为:");
47 printList(p);
48 printf("\n一共有:%d个元素\n", ListLength(p));
49
50 //查找
51 printf("查找节点的内容,元素序号为:");
52 scanf("%d", &i);
53 Get1(p, i);
54 printf("查找节点的位置，内容为:");
55 scanf(" %c", &c);
56 Locate1(p,c);
57 //删除
58 printf("删除节点，节点的位置:");
59 scanf("%d", &i);
60 DelList(p,i,&e);
61 printf("删除内容为：%c\n", e);
62 printf("剩余元素为:");
63 printList(p);
64 printf("\n");
65 //插入
66 printf("在i插入e:");
67 scanf("%d%c", &i, &e);
68 InsList(p,i,e);
69 printf("全部元素为:");
70 printList(p);
71 printf("\n");
72
73 //排序
74 sore(p);
75 printf("排序后元素为:");
76 printList(p);
77 printf("\n");
78
79 printf("新链表q:");
80 q = (Node*)malloc(sizeof(Node));
81 q = CreateFromTail();
82
83 //合并
84 printf("q合并p后:");
85 //q 为NULL !!
86 p = Merge(p, q);
87
88 printf("全部元素为:");
89 printList(p);
90 printf("\n");
91 /*
92 //有序合并
93 p = MergeLinkList(q, p);
94 printf("合并后全部元素为:");//(原来的两个链表本来就有序,p长度短)
95 printList(p);
96 printf("\n");
97 */
98
99 return 0;
100 }
101
102
103
104
105
106 //头插
107 LinkList CreateFromHead()
108 {
109 int flag=1;
110 LinkList L;
111 Node *s;
112 char c;
113 L=(LinkList)malloc(sizeof(Node));
114 L->next=NULL;
115
116 while(flag) //因为flag是1，所以进入循环体执行
117 {
118 scanf("%c", &c);
119 //c = getchar(); //假设用户输入ab$,首先读入'a’
120 if(c !='$') //'a’不等于'$’,因此判断成立
121 {
122 s=(Node*)malloc(sizeof(Node));
123 s->data=c;
124 s->next=L->next;
125 L->next=s;
126 }
127 }
128 return L;
129 }
130 //尾插
131 LinkList CreateFromTail() /*将新增的字符追加到链表的末尾*/
132 {
133 char c;
134 LinkList L;
135 Node *r, *s;
136 L=(LinkList)malloc(sizeof(Node));
137 L->next=NULL;
138 r=L; /*r指针始终动态指向链表的当前表尾*/
139 fflush(stdin);
140 c=getchar();
141 while(c!='$')/*输入“$”时flag为0，建表结束*/
142 {
143
144 s=(LinkList)malloc(sizeof(Node));
145 s->data=c;
146 r->next=s;
147 r=s;
148 c=getchar();
149 }
150 r->next=NULL;
151 return L;
152 }
153 //按元素序号查找
154 void Get1(LinkList L, int i)
155 { //假设开始的情况是：
156 Node *p;
157 int j=0;
158 p=L;
159 while((p->next!=NULL)&&(j<i))
160 {
161 p=p->next;
162 j++;
163 }
164 // p->next是NULL
165 if(i==j)
166 {
167 printf("%d:%c\n", i,p->data);
168 }
169 else //不满足判断条件，因此执行else部分
170 printf("未找到");
171 }
172
173 //按元素值查找
174 void Locate1(LinkList L,char key)
175 {
176 int i = 1;
177 Node *p;
178 p=L->next;
179 while(p !=NULL)
180 {
181 if(p->data != key)
182 {
183 i++;
184 p=p->next;
185 }
186 else
187 {
188 printf("%c:%d\n", key, i);
189 break;
190 }
191 }
192 }
193
194
195 //按元素序号查找
196 Node *Get2(LinkList L, int i)
197 { //假设开始的情况是：
198 Node *p;
199 int j=0;
200 p=L;
201 while((p->next!=NULL)&&(j<i))
202 { //满足条件，因此进入循环体执行
203 p=p->next;
204 j++;
205 }
206 // p->next是NULL，不满足条件，因此不再执行循环体
207 if(i==j)
208 {
209 printf("%d:%c\n", i,p->data);
210 return p;
211 }
212 else //不满足判断条件，因此执行else部分
213 return NULL;
214 }
215
216 //按元素值查找
217 Node *Locate2(LinkList L,char key)
218 {
219 int i = 1;
220 Node *p;
221 p=L->next;
222 while(p !=NULL)
223 {
224 if(p->data != key)
225 {
226 i++;
227 p=p->next;
228 }
229 else
230 {
231 printf("%c:%d\n", key, i);
232 break;
233 }
234 }
235 return p;
236 }
237
238 //删除结点
239 void DelList(LinkList L,int i,char *e)
240 {
241 Node *p,*r;
242 int k =0;
243 p=L;
244 while(p->next != NULL && k < i-1)
245 {
246 p=p->next;
247 k=k+1;
248 }
249 if(k!=i-1)
250 {
251 printf("无此节点");
252 }
253 else
254 {
255 r=p->next;
256 p->next=p->next->next;
257 *e=r->data;//通过变量e返回删掉的元素值
258 free(r); //r这个变量及值都没有变动，但是不能再使用r指向的那个空间（因为已经释放）。
259 }
260 }
261 //插入结点
262 void InsList(LinkList L,int i,char e)
263 {
264 Node *pre,*s;
265 int k=0;
266 pre=L;
267 while(pre!=NULL&&k<i-1) /*先找到第i-1个数据元素的存储位置,使指针pre指向它*/
268 {
269 pre=pre->next;
270 k=k+1;
271 }
272 if(k!=i-1)
273 {
274 printf("插入位置不合理！");
275 return;
276 }
277 s=(Node*)malloc(sizeof(Node));/*为e申请一个新的结点*/
278 s->data=e; /*将待插入结点的值e赋给s的数据域*/
279 s->next=pre->next;
280 pre->next=s;
281 }
282
283
284
285 //求长度
286 int ListLength(LinkList L) /*L为带头结点的链表*/
287 {
288 Node *p;
289 int j=0; /*用来存放链表的长度*/
290 p=L->next;
291 while(p!=NULL)
292 {
293 p=p->next;
294 j++;
295 }
296 return j;
297 }
298
299
300 //合并
301 LinkList Merge(LinkList LA, LinkList LB)
302 {
303 LinkList p;
304 p = LA->next;
305 while(p->next)
306 p = p->next;
307 p->next = LB->next;
308 free(LB);
309 return LA;
310 }
311 //两个从小到大有序链表合并成为有序链表 LC
312 LinkList MergeLinkList(LinkList LA, LinkList LB)
313 {
314 Node *pa,*pb;
315 LinkList LC;
316 LinkList r;
317
318 pa=LA->next;
319 pb=LB->next;
320 LC=LA;
321 LC->next=NULL;
322 r=LC;
323
324 while(pa!=NULL && pb!=NULL)
325 {
326 if(pa->data <= pb->data)
327 {
328 r->next=pa;
329 r=pa;
330 pa=pa->next;
331 }
332 else
333 {
334 r->next=pb;
335 r=pb;
336 pb=pb->next;
337 }
338 }
339 if(pa != NULL)
340 r->next=pa;
341 //return NULL;
342 else//
343 r->next=pb;
344 free(LB);
345 return (LC);
346 }
347 /*
348 bcd$
349 新链表q:aef$
350 合并后全部元素为:abcdef
351 bc$
352 新链表q:adef$
353 合并后全部元素为:abcdef
354 acdg$
355 新链表q:be$
356 合并后全部元素为:abcdeg
357 */
358 //排序
359 void sore(LinkList head)
360 {
361 LinkList pre,cur,next,end, temp;
362 end = NULL;
363 while(head->next != end)
364 {
365 //初始化三个指针 ; 判断是否到达结束位置 ; 三个指针集体后移
366 for(pre=head,cur=pre->next,next=cur->next; next!=end; pre=pre->next,cur=cur->next,next=next->next)
367 {
368 if(cur->data > next->data) //从小到大
369 {
370 pre->next=next;
371 cur->next=next->next;
372 next->next=cur;
373 //此时next变前一项，cur变后一项 交换next cur
374 temp=cur;
375 cur=next;
376 next=temp;
377 }
378 }
379 //一轮循环结束 最后一项已经排好 end提前一项 (冒泡原理)
380 end = cur;
381 }
382 }
383
384 void printList(LinkList L)
385 {
386 Node *p = L;
387 while(p->next)
388 {
389 p = p->next;
390 if(p->data >= 'a' || p->data <='z')
391 printf("%c", p->data);
392 //printf(" ", p->data);
393 }
394 }
赞 (0)