Chinaunix首页 | 论坛 | 博客

除e尘chaofan.blog.chinaunix.net

首页　| 　博文目录　| 　关于我

915546302

  • 博客访问： 27394
  • 博文数量： 10
  • 博客积分： 25
  • 博客等级： 民兵
  • 技术积分： 60
  • 用 户 组： 普通用户
  • 注册时间： 2012-04-06 18:51
文章分类

全部博文（10）

文章存档

2012年（10）

我的朋友
最近访客
推荐博文
单链表

分类：

2012-04-08 10:18:00

原文地址：单链表 作者：onezeroone


  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <assert.h>

  5. #define return_val_if_fail(expr, val) if (!(expr)) return (val)

  7. typedef void* mypointer;
  8. typedef int (*myCompareFunc)(mypointer a, mypointer b);
  9. typedef void (*myfunc)(mypointer a, mypointer b);
  10. typedef struct _SList SList;

  12. struct _SList
  13. {
  14.         mypointer data;
  15.         SList *next;
  16. };

  18. SList*
  19. myAlloc()
  20. {
  21.         SList *psl = (SList*)malloc(sizeof(SList));
  22.         if (NULL == psl) {
  23.                 printf("out of memory");
  24.                 return NULL;
  25.         }
  26.         psl->data = NULL;
  27.         psl->next = NULL;

  29.         return (psl);
  30. }

  32. void
  33. myFree(SList *psl)
  34. {
  35.         assert(NULL != psl);
  36.         free(psl);
  37.         psl = NULL;
  38. }

  40. SList*
  41. slistLast(SList *list)
  42. {
  43.         if (list) {
  44.                 while (list->next)
  45.                         list = list->next;
  46.         }

  48.         return (list);
  49. }

  51. SList*
  52. slistAppend(SList *list, mypointer data)
  53. {
  54.         SList *new_list;
  55.         SList *last;

  57.         new_list = myAlloc();
  58.         new_list->data = data;
  59.         new_list->next = NULL;

  61.         if (list) {
  62.                 last = slistLast(list);
  63.                 last->next = new_list;

  65.                 return (list);
  66.         } else {
  67.                 return (new_list);
  68.         }
  69. }

  71. SList*
  72. slistPrepend(SList *list, mypointer data)
  73. {
  74.         SList *new_list;

  76.         new_list = myAlloc();
  77.         new_list->data = data;
  78.         new_list->next = list;

  80.         return (new_list);
  81. }

  83. SList*
  84. slistInsert(SList *list, mypointer data, int pos)
  85. {
  86.         SList *pre_list;
  87.         SList *tmp_list;
  88.         SList *new_list;

  90.         if (pos < 0)
  91.                 return slistAppend(list, data);
  92.         else if (pos == 0)
  93.                 return slistPrepend(list, data);

  95.         new_list = myAlloc();
  96.         new_list->data = data;

  98.         if (!list) {
  99.                 new_list->next = NULL;
  100.                 return (new_list);
  101.         }

  103.         pre_list = NULL;
  104.         tmp_list = list;

  106.         while ((pos-- > 0) && tmp_list) {
  107.                 pre_list = tmp_list;
  108.                 tmp_list = tmp_list->next;
  109.         }

  111.         if (pre_list) {
  112.                 new_list->next = pre_list->next;
  113.                 pre_list->next = new_list;
  114.         } else {
  115.                 new_list->next = list;
  116.                 list = new_list;
  117.         }

  119.         return (list);
  120. }

  122. SList*
  123. slistInsertBefore(SList *list, SList *sibling, mypointer data)
  124. {
  125.         if (!list) {
  126.                 list = myAlloc();
  127.                 list->data = data;
  128.                 list->next = NULL;
  129.                 return (list);
  130.         } else {
  131.                 SList *node, *last = NULL;
  132.                 for (node = list; node; last = node, node = node->next)
  133.                         if (node == sibling)
  134.                                 break;
  135.                 if (!last) {
  136.                         node = myAlloc();
  137.                         node->data = data;
  138.                         node->next = list;

  140.                         return (node);
  141.                 } else {
  142.                         node = myAlloc();
  143.                         node->data = data;
  144.                         node->next = last->next;
  145.                         last->next = node;

  147.                         return (list);
  148.                 }
  149.         }
  150. }

  152. SList*
  153. slistConcat(SList *list1, SList *list2)
  154. {
  155.         if (list2) {
  156.                 if (list1)
  157.                         slistLast(list1)->next = list2;
  158.                 else
  159.                         list1 = list2;
  160.         }

  162.         return (list1);
  163. }

  165. SList*
  166. slistRemove(SList *list, mypointer data)
  167. {
  168.         SList *tmp, *prev = NULL;

  170.         tmp = list;
  171.         while (tmp) {
  172.                 if (tmp->data == data) {
  173.                         if (prev)
  174.                                 prev->next = tmp->next;
  175.                         else
  176.                                 list = tmp->next;

  178.                         myFree(tmp);
  179.                         break;
  180.                 }
  181.                 prev = tmp;
  182.                 tmp = tmp->next;
  183.         }

  185.         return (list);
  186. }

  188. SList*
  189. slistRemoveAll(SList *list, mypointer data)
  190. {
  191.         SList *tmp, *prev = NULL;

  193.         tmp = list;
  194.         while (tmp) {
  195.                 if (tmp->data == data) {
  196.                         SList *next = tmp->next;

  198.                         if (prev)
  199.                                 prev->next = next;
  200.                         else
  201.                                 list = next;

  203.                         myFree(tmp);
  204.                         tmp = next;
  205.                 } else {
  206.                         prev = tmp;
  207.                         tmp = prev->next;
  208.                 }
  209.         }

  211.         return (list);
  212. }

  214. SList*
  215. slistRemoveLink(SList *list, SList *link)
  216. {
  217.         SList *tmp, *prev = NULL;

  219.         tmp = list;
  220.         while (tmp) {
  221.                 if (tmp == link) {
  222.                         if (prev)
  223.                                 prev->next = tmp->next;
  224.                         if (list == tmp)
  225.                                 list = list->next;

  227.                         tmp->next = NULL;
  228.                         break;
  229.                 }

  231.                 prev = tmp;
  232.                 tmp = tmp->next;
  233.         }

  235.         return (list);
  236. }

  238. SList*
  239. slistDeleteLink(SList *list, SList *link)
  240. {
  241.         SList *tmp, *prev = NULL;

  243.         tmp = list;
  244.         while (tmp) {
  245.                 if (tmp == link) {
  246.                         if (prev)
  247.                                 prev->next = tmp->next;
  248.                         if (list == tmp)
  249.                                 list = list->next;

  251.                         tmp->next = NULL;
  252.                         myFree(tmp);
  253.                         break;
  254.                 }

  256.                 prev = tmp;
  257.                 tmp = tmp->next;
  258.         }

  260.         return (list);
  261. }

  263. SList*
  264. slistCopy(SList *list)
  265. {
  266.         SList *new_list = NULL;

  268.         if (list) {
  269.                 SList *last;

  271.                 new_list = myAlloc();
  272.                 new_list->data = list->data;
  273.                 last = new_list;
  274.                 list = list->next;

  276.                 while (list) {
  277.                         last->next = myAlloc();
  278.                         last = last->next;
  279.                         last->data = list->data;
  280.                         list = list->next;
  281.                 }

  283.                 last->next = NULL;
  284.         }

  286.         return (new_list);
  287. }

  289. SList*
  290. slistReverse(SList *list)
  291. {
  292.         SList *prev = NULL;

  294.         while (list) {
  295.                 SList *next = list->next;
  296.                 list->next = prev;
  297.                 prev = list;
  298.                 list = next;
  299.         }

  301.         return (prev);
  302. }

  304. SList*
  305. slistNTH(SList *list, unsigned int n)
  306. {
  307.         while (n-- > 0 && list)
  308.                 list = list->next;

  310.         return (list);
  311. }

  313. mypointer
  314. slistNTHdata(SList *list, unsigned int n)
  315. {
  316.         while (n-- > 0 && list)
  317.                 list = list->next;

  319.         return list ? list->data : NULL;
  320. }

  322. SList*
  323. slistFind(SList *list, mypointer data)
  324. {
  325.         while (list) {
  326.                 if (list->data == data)
  327.                         break;
  328.                 list = list->next;
  329.         }

  331.         return (list);
  332. }

  334. SList*
  335. slistFindCustom(SList *list, mypointer data, myCompareFunc func)
  336. {
  337.         return_val_if_fail(func != NULL, list);

  339.         while (list) {
  340.                 if (! func(list->data, data))
  341.                         return (list);
  342.                 list = list->next;
  343.         }

  345.         return (NULL);
  346. }

  348. int
  349. slistPosition(SList *list, SList *link)
  350. {
  351.         int i;

  353.         i = 0;
  354.         while (list) {
  355.                 if (list == link)
  356.                         return i;
  357.                 i++;
  358.                 list = list->next;
  359.         }

  361.         return (-1);
  362. }

  364. int
  365. slistIndex(SList *list, mypointer data)
  366. {
  367.         int i;

  369.         i = 0;
  370.         while (list) {
  371.                 if (list->data == data)
  372.                         return i;
  373.                 i++;
  374.                 list = list->next;
  375.         }

  377.         return (-1);
  378. }

  380. int
  381. slistLength(SList *list)
  382. {
  383.         int len;

  385.         len = 0;
  386.         while (list) {
  387.                 len++;
  388.                 list = list->next;
  389.         }

  391.         return (len);
  392. }

  394. void
  395. slistForeach(SList *list, myfunc func, mypointer user_data)
  396. {
  397.         while (list) {
  398.                 SList *next = list->next;
  399.                 (*func) (list->data, user_data);
  400.                 list = next;
  401.         }
  402. }

  404. void
  405. print(int *a, int *b)
  406. {
  407.         printf("%d,", *a);
  408. }

  410. void
  411. myFreeAll(SList *list)
  412. {
  413.         SList *next;
  414.         while (list) {
  415.                 next = list->next;
  416.                 myFree(list);
  417.                 list = next;
  418.         }
  419. }

  421. int
  422. main(void)
  423. {
  424.         int i;
  425.         int key = 100;
  426.         int a[5] = {1,3,5,7,9};
  427.         int b[5] = {2,4,6,8,0};
  428.         SList *psl = NULL;
  429.         SList *psl2 = NULL;
  430.         SList *psl3 = NULL;
  431.         SList *psl4 = NULL;
  432.         SList *tmp = NULL;

  434.         printf("a: 1,3,5,7,9\n");
  435.         printf("b: 2,4,6,8,0\n");

  437.         for (i = 0; i < 5; i++)
  438.                 psl = slistAppend(psl, &a[i]);

  440.         printf("Append: a\n");
  441.         slistForeach(psl, (myfunc)print, NULL);
  442.         printf("\n");

  444.         for (i = 0; i < 5; i++)
  445.                 psl2 = slistPrepend(psl2, &b[i]);

  447.         printf("Prepend: b\n");
  448.         slistForeach(psl2, (myfunc)print, NULL);
  449.         printf("\n");

  451.         psl3 = slistConcat(psl, psl2);

  453.         printf("Concat a and b:\n");
  454.         slistForeach(psl3, (myfunc)print, NULL);
  455.         printf("\n");

  457.         psl3 = slistInsert(psl3, &key, 3);

  459.         printf("Insert %d at 3:\n", key);
  460.         slistForeach(psl3, (myfunc)print, NULL);
  461.         printf("\n");

  463.         tmp = psl3->next;
  464.         psl3 = slistInsertBefore(psl3, tmp, &key);

  466.         printf("Insert %d before %d(index):\n", key, 1);
  467.         slistForeach(psl3, (myfunc)print, NULL);
  468.         printf("\n");

  470.         psl3 = slistRemove(psl3, &b[4]);

  472.         printf("Remove %d:\n", b[4]);
  473.         slistForeach(psl3, (myfunc)print, NULL);
  474.         printf("\n");

  476.         psl3 = slistRemoveAll(psl3, &key);

  478.         printf("Remove all %d:\n", key);
  479.         slistForeach(psl3, (myfunc)print, NULL);
  480.         printf("\n");

  482.         psl4 = slistCopy(psl3);
  483.         printf("Copy all :\n", key);
  484.         slistForeach(psl4, (myfunc)print, NULL);
  485.         printf("\n");

  487.         psl4 = slistReverse(psl4);
  488.         printf("Reverse:\n", key);
  489.         slistForeach(psl4, (myfunc)print, NULL);
  490.         printf("\n");

  492.         printf("NTHdata: %d(index) is %d\n", 2, *(int *)slistNTHdata(psl4, 2));

  494.         printf("Index: %d is %d(index)\n", key, slistIndex(psl4, &key));

  496.         printf("Length: %d\n", slistLength(psl4));

  498.         myFreeAll(psl);
  499.         myFreeAll(psl2);
  500.         myFreeAll(psl3);
  501.         myFreeAll(psl4);
  502.         return (0);
  503. }
Result:
  1. a: 1,3,5,7,9
  2. b: 2,4,6,8,0
  3. Append: a
  4. 1,3,5,7,9,
  5. Prepend: b
  6. 0,8,6,4,2,
  7. Concat a and b:
  8. 1,3,5,7,9,0,8,6,4,2,
  9. Insert 100 at 3:
  10. 1,3,5,100,7,9,0,8,6,4,2,
  11. Insert 100 before 1(index):
  12. 1,100,3,5,100,7,9,0,8,6,4,2,
  13. Remove 0:
  14. 1,100,3,5,100,7,9,8,6,4,2,
  15. Remove all 100:
  16. 1,3,5,7,9,8,6,4,2,
  17. Copy all :
  18. 1,3,5,7,9,8,6,4,2,
  19. Reverse:
  20. 2,4,6,8,9,7,5,3,1,
  21. NTHdata: 2(index) is 6
  22. Index: 100 is -1(index)
  23. Length: 9


阅读(410) | 评论(0) | 转发(0) |
0

上一篇：没有了

下一篇：网络设备

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6