简单链表练习

今天的任务 :简单链表练习用 C 语言明天贴上源代码//以下代码并未通过测试,25#include<malloc.h>6#include<iostream>78typedefstructstudentInfo9{...

weixin_30768175

50人浏览 · 2009-06-27 23:59:00

weixin_30768175 · 2009-06-27 23:59:00 发布

今天的任务 :简单链表练习用 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... 累死了..

洗洗睡吧

转载于:https://www.cnblogs.com/ToDoToTry/archive/2009/06/27/1512477.html