简单链表练习

今天的任务 :简单链表练习用 C 语言

明天贴上源代码

//以下代码并未通过测试,

  2
  5 #include <malloc.h>
  6 #include <iostream>
  7
  8 typedef struct studentInfo
  9 {
10     char *  No;
11     char * Name;
12     float Score;
13     struct studentInfo * next;
14
15
16 }student;
17
18
19 /*对节点数据进行初始化*/
20 void InitStudent(student * s)
21 {
22     if(s)
23     {
24         s->Name = (char * )malloc(18);
25         s->next = NULL;
26         s->No = (char * )malloc(18);
27         s->Score = -1;
28
29         //初始化为空格
30         memset(s->Name,032,sizeof(s->Name));
31         memset(s->No,032,sizeof(s->No));
32
33     }
34 }
35
36
37 /*为  分配内存空间*/
38  student * NewStudent()
39  {
40      student * s = (student * )malloc(sizeof(student));
41      InitStudent(s);
42
43      return s;
44  }
45
46
47
48
49
50 /*初始化链表头*/
51 bool InitListHead(student * head)
52 {
53     head = (student * )malloc(sizeof(student));
54     if(head!=NULL)
55     {
56         InitStudent(head);
57         return true;
58     }
59     else
60     {
61         return false;
62     }
63 }
64
65
66 /*DestroyList  销毁整个线性表*/
67 void DestroyList(student * head)
68 {
69     student * h = head;
70
71     /*临时变量用于指向需要销毁的内存空间*/
72     student * temp =h;
73
74     /*注意保留下一个节点的地址 ,否则无法全部回收数据 --leak memory!*/
75     while(temp)
76     {
77
78         student * temp = h;
79
80         /*在销毁之前移动到下一位以免空指针错误*/
81         h = h->next;
82
83         //记得销毁 NO, Name
84         free(temp->Name);
85         free(temp->No);
86
87         //销毁结构体
88         free(temp);
89     }
90 }
91
92
93 /*删除链表中的所有数据*/
94 void ClearList(student * head)
95 {
96     /*养成好习惯保存好重要数据,以免改动.函数中使用 h 替代 head*/
97     student * h = head;
98
99     do
100     {
101         h->No = NULL;
102         h->Name = NULL;
103         h->Score = -1;
104
105     }while(h->next);
106
107 }
108
109 /*判断是否为空*/
110 bool isEmpty(student * head)
111 {
112     /*head 为 NULL*/
113     if(head==NULL && head->next==NULL)
114     {
115         return true;
116     }
117     else  /*head 不为 NULL*/
118     {
119         return false;
120     }
121 }
122
123
124 int ListLength(student * head)
125 {
126     /*again ,

指针操作 ,记得保存啊*/
127     student  * h = head;
128
129     int index = 0 ;
130
131     while(h)
132     {
133         index++;
134
135         h = h->next;
136     }
137     return index;
138 }
139
140
141 /*注意:next 会被置为 NULL,. 老外的习惯目标←源, 老子不太习惯,cao!,,*/
142 void CopyTo(student * destination,student * source)
143 {
144     if(source!=NULL)
145     {
146         destination->No = source->No;
147         destination->Name = source->Name;
148         destination->Score = source->Score;
149         destination->next =NULL;
150     }
151     else
152     {
153         destination = NULL;
154     }
155 }
156
157
158 /* 用户交互. 请求用户输入数据
159 */
160 void GetValue(student * s)
161 {
162     if(s)
163     {
164         printf("\nplease input the No of the student:");
165         //scanf("%s",s->No);
166         gets(s->No);
167
168         printf("\nplease input the Name of the student:");
169         //scanf("%s",s->Name);
170         gets(s->Name);
171
172         printf("\nplease input the Score of the student:");
173         scanf("%f",&(s->Score));
174     }
175 }
176
177
178 /*setValue  用于在代码中直接设置节点中的数据*/
179
180 bool setValue(student * item,char * no,char * name,float score)
181 {
182     if(item == NULL)
183     {
184         return false;
185     }
186     else
187     {
188         item->No = no;
189         item->Name = name;
190         item->Score = score;
191         return true;
192     }
193 }
194
195
196 /*获取指定节点 , 获取第i 个,并取出其值赋给 tmp
197 */
198 bool GetElement(student * head,int i,student *tmp )
199 {
200
201     student * h = head;
202
203     int index = 0;
204
205     if(isEmpty(h)||i>ListLength(h))
206     {
207         return false;
208     }
209     else
210     {
211         while(h)
212         {
213             index++;
214             if(index != i)
215             {
216                 h = h->next;
217             }
218             else
219             {
220                 /*将数据写到 tmp 指向的内出空间 ,这样外部就可以使用了*/
221                 CopyTo(tmp , h);
222                 return true;
223             }
224         }
225     }
226 }
227
228 /*定义一个指向函数的指针类型, 此函数返回 bool
229 */
230 typedef bool (*compare)(student * one, student * another);
231
232 bool comp(student * one, student * another)
233 {
234     if(one->No == another->No && one->Name == another->Name && one->Score == another->Score &&    one->next == another->next)
235     {
236         return true;
237     }
238     else
239     {
240         return false;
241     }
242
243 }
244
245 bool compName(student * one, student * another)
246 {
247     if(strcmp(one->Name,another->Name ) == 0)
248     {
249         return true;
250     }
251     else /*为加上 else 语句会默认返回 true.,可能是环境问题*/
252     {
253         return false;
254     }
255 }
256
257
258 /*将函数作为参数 ,并根据此函数的返回值(bool), 判断是否匹配
259 */
260 int LocateElem(student * head,student * e, compare comp)
261 {
262     student * h = head;
263     int i =0;
264
265     while(h)
266     {
267         i++;
268
269         if(comp(h,e))
270         {
271             CopyTo(e,h);
272
273             return i;
274         }
275         else
276         {
277             h = h->next;
278         }
279     }
280     return 0 ;
281 }
282
283
284 /*找到前一个节点
285 */
286 student * PriorEle(student *head,student *cur,student *pre)
287 {
288     /*/由于非双向也非循环 ,故需要两个指针 ,first ,second , second 用于判断当前指向是否与cur相同 ,相同则返回 first,否则继续,没找到返回 NULL
289     */
290     student * first = head;
291
292     student * second = first->next;
293
294     if(first == cur)
295     {
296         return NULL;
297     }
298     else
299     {
300
301
302         while(second)
303         {
304             if (comp(second,cur))
305             {
306                 CopyTo(pre,first);
307                 return pre;
308             }
309             else
310             {
311                 first = second;
312                 second= second->next;
313             }
314         }
315
316         return NULL;
317     }
318 }
319
320
321 student * NextEleOfThis(student * head,student *cur,student * nextEle)
322 {
323     student * h = head;
324
325     while(h)
326     {
327         if(comp(cur,h))
328         {
329             CopyTo(nextEle,h->next);
330
331             return nextEle;
332         }
333     }
334     return NULL;
335 }
336
337 /*/把 e 插到 p 后面.  /*还存在问题
338 */
339 bool   AddItem(student * p ,student * e)
340 {
341     if(p ==NULL || e == NULL)
342     {
343         #ifdef DEBUG
344                 printf("AddItem(student * p ,student *e) function  error!  null pointer !");
345         #endif
346
347         return false;
348     }
349     else
350     {
351         student * temp = p->next;
352         p->next = e;
353         e->next = temp;
354
355         return true;
356     }
357 }
358
359 /*此处考虑尚不周全 */
360 bool ListInsert(student * head,int i,student * e)
361 {
362     student * h = head;
363
364     int index = 0;
365     int length = ListLength(h);
366
367     /* 判断 i  是否合格 */
368     if( 0 < i <= length )
369     {
370         /* 找到适合的位置然后插入 */
371         while(h)
372         {
373             index++;
374
375             /*要求插入到第一位的情况 */
376             if(i==index && i==1)
377             {
378                 e->next = h;
379                 head = e;
380                 return true;
381             }
382             else if(i == index)
383             {
384                 AddItem(h,e);
385
386                 return true;
387             }
388
389             /* 插入到第二位的时候 , 会出现问题 ,因为第一次之后就已经换到了第三个 */
390             if(index >= 2)
391             {
392                 h = h->next;
393             }
394         }
395     }
396     else
397     {
398         return false;
399     }
400 }
401
402
403 /*删除第i 个 , 并用 e 返回其值.
404 ********注意 head 被删除的情况.!!!!!!!!!!!!!!!!!!!!!!!!!
405 */
406 bool ListDelete(student * head ,int i, student * e)
407 {
408     student * h = head;
409     int index = 0;
410
411     //
412     if( 0 < i < ListLength(h) )
413     {
414         while(h)
415         {
416             index++;
417             if(h!=NULL)
418             {
419
420                 if(i==index)
421                 {
422                     CopyTo(h,e);
423
424
425                     /*保存好要删除的元素节点的指针*/
426                     student * temp = h;
427
428                     /*修改链表 ,*/
429                     if(index != 1)
430                     {
431                         h = PriorEle(head,h,h);
432                         h->next = h->next->next;
433                     }
434                     /* 删除头指针的情况*/
435                     else
436                     {
437                         head = h->next;
438                     }
439
440                     /*销毁数据*/
441                     free(temp);
442                 }
443
444                 /*移动指针*/
445                 h = h->next;
446             }
447             else
448             {
449                 InitStudent(e);
450                 return false;
451             }
452
453         }
454     }
455 }
456
457 void Display(student * head,char * title)
458 {
459     student *  h = head;
460     printf("\n\n=======================%18s============================\n",title);
461     while(h)
462     {
463         printf("NO:%-15s \n",h->No);
464         printf("Name:%-15s \n",h->Name);
465         printf("Score:%-15f \n",h->Score);
466         h = h->next;
467     }
468     printf("\n\n===========================================================\n");
469 }
470
471 /*将函数作为参数的第二种写法,---第一种见上面.*/
472 bool ListTraverse(student * head,bool (*visit)(student * p))
473 {
474     student * h = head;
475
476     while(h)
477     {
478         if(!visit(h))
479         {
480             return false;
481         }
482         else
483         {
484             h = h->next;
485         }
486     }
487
488     return true;
489 }
490
491
492
493
494 int _tmain(int argc, _TCHAR* argv[])
495 {
496
497
498     student  * head = NewStudent();
499
500
501     /*isEmpty() Test! */
502     printf("is empty ? %s",isEmpty(head)? "true" : "false");
503
504     GetValue(head);
505
506     /*isEmpty() Test! */
507     printf("is empty ? %s \n",isEmpty(head)? "true" : "false");
508
509     student * item =  NewStudent();
510     setValue(item,"80001060011","second",80.5);
511     Display(item,"Second's Value");
512
513     student * third =  NewStudent();
514     setValue(third,"8000106047","third",90);
515     Display(third,"Third's Value");
516
517     student * fourth=  NewStudent();
518
519     /*检验copyTo()函数  将数据复制到fourth 中, 然后修改,*/
520     CopyTo(fourth,third);
521     Display(fourth,"The Fourth's Value");
522     fourth->Name = "Test Insert -Fourth";
523     Display(fourth,"The Fourth Value");
524
525     AddItem(head,item);
526
527     AddItem(head ,third );
528
529     /*ListInsert(head,4,fourth); Test! */
530     ListInsert(head,3,fourth);
531
532     /*NextEleOfThis(head,head,tmp); Test! */
533     student * tmp = NewStudent();
534     NextEleOfThis(head,head,tmp);
535     Display(tmp," tmp Data");
536
537
538     /*LocateElem(student * head,student * e, compare comp) */
539     int i = LocateElem(head,third,compName);
540     printf("\n Locate at the  %dth  item \n",i);
541
542     /*ListLength(head) Test! */
543     printf("Length:%d",ListLength(head));
544
545     Display(head,"  ALL Students !");
546
547     /*ListDelete(head,6,fourth);  Test!
548     *此时第六号不存在,
549     */
550     ListDelete(head,6,fourth);
551     Display(fourth,"Item deleted  list");
552
553     scanf("%d",i);
554
555     return 0;
556 }
557

争取爱上数据结构....

Orz... 累死了..

洗洗睡吧

简单 链表 练习

简单链表练习