设为首页收藏本站官方微博
开启辅助访问 切换到窄版

飘云阁

 找回密码
 加入我们

QQ登录

只需一步，快速开始

[x86]PYG官方Dll优雅破解补丁制作工具[x64]PYG官方DLL优雅破解补丁制作工具[x86]PYG官方Exe优雅破解补丁制作工具[x86/x64]Baymax Patch Tools飘云阁工具包(已更新第4季)
返回列表 发新帖
查看: 4869|回复: 1

[C/C++] 学习Nisy的C教程第31课--链表双链

[复制链接]
lucky_789
  • TA的每日心情
    开心
    2018-9-27 19:17

    • 签到天数: 31 天

    [LV.5]常住居民I
    发表于 2015-2-8 11:17:36 | 显示全部楼层 |阅读模式
    本帖最后由 lucky_789 于 2015-2-8 12:03 编辑

    第30课视频教程两个半小时，看了几次才看完{:soso_e110:}，模仿着写了个简单的链表和双链。欢迎大家提出宝贵意见。
    一、单向链表

    1. /* list1.h -- 单向链表头文件   */

    3. #define NULL 0

    5. typedef int ElementType;

    7. typedef struct _ChainNode
    8. {
    9.         ElementType data;
    10.         struct _ChainNode *next;
    11. }ChainNode;

    13. typedef struct
    14. {
    15.         ChainNode *head;
    16.         ChainNode *tail;
    17.         int total;
    18. }List;

    20. List * ListInit();

    22. /* 销毁链表 */
    23. int ListDestory(List *lp);

    25. /* 向链首插入节点 */
    26. int InsertHead(List *lp, ElementType *pdata);

    28. /* 向链尾插入节点 */
    29. int InsertTail(List *lp, ElementType *pdata);

    31. /* 向链中间插入节点 */
    32. int InsertNode(List *lp, int n, ElementType *pdata);

    34. /* 清空链表 */
    35. int ListClear(List *lp);

    37. /*删除节点 */
    38. int RemoveNode(List *lp, int n);

    40. /* 新建节点 */
    41. ChainNode * NewChainNode(ElementType *pdata);

    43. /* 查找节点 */
    44. ChainNode * GetChainNode(List *lp, int n);

    46. int IsEmpty(List *lp);

    48. /* 遍历显示链表 */
    49. int ListTraverse(List * lp, void (*f)(ElementType *pdata));
    复制代码

    1. /* list1.c -- 单向链表    */

    3. #include "list1.h"

    5. List * ListInit()
    6. {
    7.         List *lp = NULL;
    8.         lp = (List *)malloc(sizeof(List));
    9.         lp->head = NULL;
    10.         lp->tail = NULL;
    11.         lp->total = 0;
    12.         return lp;
    13. }

    15. int ListDestory(List *lp)
    16. {
    17.         ChainNode *p = NULL;
    18.         ChainNode *tmp = NULL;
    19.         if(!lp)
    20.                 return 0;
    21.         p = lp->head;
    22.         while(p)
    23.         {
    24.                 tmp = p->next;
    25.                 free(p);
    26.                 p = tmp;
    27.         }
    28.         free(lp);        
    29.         return 1;
    30. }

    32. int ListClear(List *lp)
    33. {
    34.         ChainNode *p = NULL;
    35.         ChainNode *tmp = NULL;
    36.         if(!lp) return 0;

    38.         p = lp->head;
    39.         while(p)
    40.         {
    41.                 tmp = p->next;
    42.                 free(p);
    43.                 p = tmp;
    44.         }
    45.         lp->head = NULL;        
    46.         lp->tail = NULL;
    47.         lp->total = 0;
    48.         return 1;
    49. }

    51. int InsertHead(List *lp, ElementType *pdata)
    52. {
    53.         ChainNode *newp = NULL;

    55.         if(!lp) return 0;

    57.         newp = NewChainNode(pdata);
    58.         if(!newp) return 0;

    60.         if(IsEmpty(lp))
    61.         {
    62.                 /* 为空则以此为首节点和尾节点 */
    63.                 lp->head = lp->tail = newp;
    64.                 lp->total++;
    65.         }
    66.         else
    67.         {
    68.                 /* 非空则以新节点为首节点 */
    69.                 newp->next = lp->head;
    70.                 lp->head = newp;
    71.                 lp->total++;
    72.         }
    73.         return 1;
    74. }

    76. int InsertTail(List *lp, ElementType *pdata)
    77. {
    78.         ChainNode *newp = NULL;

    80.         if(!lp) return 0;

    82.         newp = NewChainNode(pdata);
    83.         if(!newp) return 0;

    85.         if(IsEmpty(lp))
    86.         {
    87.                 /* 为空则以此为首节点和尾节点 */
    88.                 lp->head = lp->tail = newp;
    89.                 lp->total++;
    90.         }
    91.         else
    92.         {
    93.                 /* 非空则以新节点为尾节点 */
    94.                 (lp->tail)->next = newp;
    95.                 lp->tail = newp;
    96.                 lp->total++;
    97.         }
    98.         return 1;
    99. }

    101. int InsertNode(List *lp, int n, ElementType *pdata)
    102. {
    103.         ChainNode *p = NULL;
    104.         ChainNode *newp = NULL;

    106.         if(!lp) return 0;
    107.         if(n <= 1 || n > lp->total) return 0;

    109.         p = GetChainNode(lp, n - 1);
    110.         if(!p) return 0;

    112.         newp = NewChainNode(pdata);
    113.         if(!newp) return 0;

    115.         newp->next = p->next;
    116.         p->next = newp;
    117.         lp->total++;
    118.         return 1;
    119. }

    121. int RemoveNode(List *lp, int n)
    122. {
    123.         ChainNode *p = NULL;
    124.         ChainNode *tmp = NULL;

    126.         if(!lp) return 0;
    127.         if(n < 1 || n > lp->total) return 0;

    129.         if(lp->total == 1)
    130.         {
    131.                 free(lp->head);
    132.                 lp->head = NULL;
    133.                 lp->tail = NULL;
    134.                 lp->total = 0;
    135.         }
    136.         else
    137.         {
    138.                 if(n == 1)
    139.                 {
    140.                         tmp = (lp->head)->next;
    141.                         free(lp->head);
    142.                         lp->head = tmp;
    143.                         lp->total--;
    144.                 }
    145.                 else if(n == lp->total)
    146.                 {
    147.                         p = GetChainNode(lp, n - 1);
    148.                         p->next = NULL;
    149.                         free(lp->tail);
    150.                         lp->tail = p;
    151.                         lp->total--;
    152.                 }
    153.                 else
    154.                 {
    155.                         p = GetChainNode(lp, n - 1);
    156.                         tmp = (p->next)->next;
    157.                         free(p->next);
    158.                         p->next = tmp;
    159.                         lp->total--;
    160.                 }
    161.         }
    162.         return 1;
    163. }

    165. ChainNode * NewChainNode(ElementType *pdata)
    166. {
    167.         ChainNode *p = NULL;
    168.         p = (ChainNode *)malloc(sizeof(ChainNode));
    169.         if(!p) return p;
    170.         memcpy(&p->data, pdata, sizeof(ElementType));
    171.         p->next = NULL;
    172.         return p;
    173. }

    175. int IsEmpty(List *lp)
    176. {
    177.         return lp->total == 0;
    178. }

    180. ChainNode * GetChainNode(List *lp, int n)
    181. {
    182.         ChainNode *p = NULL;
    183.         int i = 0;

    185.         if(!lp) return 0;
    186.         if(n < 1 || n > lp->total) return 0;

    188.         for(i = 1, p = lp->head; i < n; i++, p = p->next);

    190.         return p;
    191. }

    193. int ListTraverse(List * lp, void (*pfn)(ElementType *pdata))
    194. {
    195.         int i = 0;
    196.         ChainNode *p = NULL;
    197.         if(!lp) return 0;
    198.         /* for (p = lp->head; p; p = p->next) */
    199.         for (p = lp->head, i = 0; i < lp->total; i++, p = p->next)
    200.                 pfn(&p->data);
    201.         printf("\n");
    202.         return 1;
    203. }
    复制代码

    1. /* test1.c -- 单向链表     */
    2. /* 和list1.c一起编译       */


    5. #include "List1.h"

    7. void myprintf(ElementType * pdata)
    8. {
    9.         printf("%d ", *pdata);
    10. }

    12. int main()
    13. {
    14.         int i;
    15.         List *lp = ListInit();
    16.         ElementType a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    17.         ElementType data = 99;

    19.         if(!lp)
    20.         {
    21.                 printf("\nInitList error!\n");
    22.                 return 0;
    23.         }

    25.         for (i = 0; i < 10; i++)
    26.         {
    27.                 InsertTail(lp, a+i);
    28.         }

    30.         ListTraverse(lp, myprintf);

    32.         InsertHead(lp, &data);
    33.         ListTraverse(lp, myprintf);

    35.         InsertTail(lp, &data);
    36.         ListTraverse(lp, myprintf);

    38.         InsertNode(lp, 3, &data);
    39.         ListTraverse(lp, myprintf);

    41.         RemoveNode(lp, 3);
    42.         ListTraverse(lp, myprintf);

    44.         RemoveNode(lp, 12);
    45.         ListTraverse(lp, myprintf);

    47.         RemoveNode(lp, 1);
    48.         ListTraverse(lp, myprintf);

    50.         ListDestory(lp);
    51.         return 1;
    52. }
    复制代码


    二、双向链表（在单向链表的基础上略加修改而来）

    1. /* list2.h -- 双向链表头文件     */

    3. #define NULL 0

    5. typedef int ElementType;

    7. typedef struct _ChainNode
    8. {
    9.         struct _ChainNode *prev;
    10.         ElementType data;
    11.         struct _ChainNode *next;
    12. }ChainNode;

    14. typedef struct
    15. {
    16.         ChainNode *head;
    17.         ChainNode *tail;
    18.         int total;  /* 保留此项主要是考虑以空间换时间。其实程序体还节省了更多的代码空间 */
    19. }List;

    21. List * ListInit();

    23. int ListDestory(List *lp);

    25. int InsertHead(List *lp, ElementType *pdata);

    27. int InsertTail(List *lp, ElementType *pdata);

    29. int InsertNode(List *lp, int n, ElementType *pdata);

    31. int ListClear(List *lp);

    33. int RemoveNode(List *lp, int n);

    35. ChainNode * NewChainNode(ElementType *pdata);

    37. ChainNode * GetChainNode(List *lp, int n);

    39. int IsEmpty(List *lp);

    41. int ListTraverse(List * lp, void (*f)(ElementType *pdata));
    复制代码

    1. /* list2.c -- 双向链表      */

    3. #include "list2.h"

    5. List * ListInit()
    6. {
    7.         List *lp = NULL;
    8.         lp = (List *)malloc(sizeof(List));
    9.         lp->head = NULL;
    10.         lp->tail = NULL;
    11.         lp->total = 0;
    12.         return lp;
    13. }

    15. int ListDestory(List *lp)
    16. {
    17.         ChainNode *p = NULL;
    18.         ChainNode *tmp = NULL;
    19.         if(!lp) return 0;

    21.         p = lp->head;
    22.         while(p)
    23.         {
    24.                 tmp = p->next;
    25.                 free(p);
    26.                 p = tmp;
    27.         }
    28.         free(lp);        
    29.         return 1;
    30. }

    32. int ListClear(List *lp)
    33. {
    34.         ChainNode *p = NULL;
    35.         ChainNode *tmp = NULL;
    36.         if(!lp) return 0;

    38.         p = lp->head;
    39.         while(p)
    40.         {
    41.                 tmp = p->next;
    42.                 free(p);
    43.                 p = tmp;
    44.         }

    46.         lp->head = NULL;        
    47.         lp->tail = NULL;
    48.         lp->total = 0;
    49.         return 1;
    50. }

    52. int InsertHead(List *lp, ElementType *pdata)
    53. {
    54.         ChainNode *newp = NULL;

    56.         if(!lp) return 0;

    58.         newp = NewChainNode(pdata);
    59.         if(!newp) return 0;

    61.         if(IsEmpty(lp))
    62.         {
    63.                 /* 为空则以此为首节点和尾节点 */
    64.                 lp->head = lp->tail = newp;
    65.                 lp->total++;
    66.         }
    67.         else
    68.         {
    69.                 /* 非空则以新节点为首节点 */
    70.                 (lp->head)->prev = newp;
    71.                 newp->next = lp->head;
    72.                 lp->head = newp;
    73.                 lp->total++;
    74.         }
    75.         return 1;
    76. }

    78. int InsertTail(List *lp, ElementType *pdata)
    79. {
    80.         ChainNode *newp = NULL;

    82.         if(!lp) return 0;

    84.         newp = NewChainNode(pdata);
    85.         if(!newp) return 0;

    87.         if(IsEmpty(lp))
    88.         {
    89.                 /* 为空则以此为首节点和尾节点 */
    90.                 lp->head = lp->tail = newp;
    91.                 lp->total++;
    92.         }
    93.         else
    94.         {
    95.                 /* 非空则将新节点接在后面 */
    96.                 (lp->tail)->next = newp;
    97.                 newp->prev = lp->tail;
    98.                 lp->tail = newp;
    99.                 lp->total++;
    100.         }
    101.         return 1;
    102. }

    104. int InsertNode(List *lp, int n, ElementType *pdata)
    105. {
    106.         ChainNode *p = NULL;
    107.         ChainNode *newp = NULL;

    109.         if(!lp) return 0;
    110.         if(n <= 1 || n > lp->total) return 0;

    112.         p = GetChainNode(lp, n - 1);
    113.         if(!p) return 0;

    115.         newp = NewChainNode(pdata);
    116.         if(!newp) return 0;

    118.         /* 插入点后的节点的prev指向新节点 */
    119.         (p->next)->prev = newp;

    121.         /* 新节点的next指向插入点后的节点 */
    122.         newp->next = p->next;

    124.         /* 新节点的prev指向插入点前的节点 */
    125.         newp->prev = p;

    127.         /* 插入点前的节点的next指向新节点 */
    128.         p->next = newp;

    130.         lp->total++;
    131.         return 1;
    132. }

    134. int RemoveNode(List *lp, int n)
    135. {
    136.         ChainNode *p = NULL;

    138.         if(!lp) return 0;
    139.         if(n < 1 || n > lp->total) return 0;

    141.         if(lp->total == 1)
    142.         {
    143.                 /* 只有一个节点则清除之 */
    144.                 free(lp->head);
    145.                 lp->head = NULL;
    146.                 lp->tail = NULL;
    147.                 lp->total = 0;
    148.         }
    149.         else
    150.         {
    151.                 if(n == 1)
    152.                 {
    153.                         /* 删除多节点的首节点，先保存第二节点 */
    154.                         p = (lp->head)->next;

    156.                         /* 删除首节点 */
    157.                         free(lp->head);

    159.                         /* 将第二节点设为首节点 */
    160.                         p->prev = NULL;
    161.                         lp->head = p;

    163.                         lp->total--;
    164.                 }
    165.                 else if(n == lp->total)
    166.                 {
    167.                         /* 删除多节点的尾节点，先保存倒数第二节点 */
    168.                         p = (lp->tail)->prev;

    170.                         /* 删除尾节点 */
    171.                         free(lp->tail);

    173.                         /* 将倒数第二节点设为尾节点 */
    174.                         p->next = NULL;
    175.                         lp->tail = p;

    177.                         lp->total--;
    178.                 }
    179.                 else
    180.                 {
    181.                         /* 删除多节点的中间节点，获取删除节点信息 */
    182.                         p = GetChainNode(lp, n);

    184.                         /* 删除点前一节点的next设为删除点后一节点 */
    185.                         (p->prev)->next = p->next;

    187.                         /* 删除点后一节点的prev设为删除点前一节点 */
    188.                         (p->next)->prev = p->prev;

    190.                         /* 删除节点 */
    191.                         free(p);

    193.                         lp->total--;
    194.                 }
    195.         }
    196.         return 1;
    197. }

    199. ChainNode * NewChainNode(ElementType *pdata)
    200. {
    201.         ChainNode *p = NULL;
    202.         p = (ChainNode *)malloc(sizeof(ChainNode));
    203.         if(!p) return p;
    204.         memcpy(&p->data, pdata, sizeof(ElementType));
    205.         p->prev = NULL;
    206.         p->next = NULL;
    207.         return p;
    208. }

    210. int IsEmpty(List *lp)
    211. {
    212.         return lp->total == 0;
    213. }

    215. ChainNode * GetChainNode(List *lp, int n)
    216. {
    217.         ChainNode *p = NULL;
    218.         int i = 0;

    220.         if(!lp) return 0;
    221.         if(n < 1 || n > lp->total) return 0;

    223.         for(i = 1, p = lp->head; i < n; i++, p = p->next);

    225.         return p;
    226. }

    228. int ListTraverse(List * lp, void (*pfn)(ElementType *pdata))
    229. {
    230.         ChainNode *p = NULL;
    231.         if(!lp) return 0;

    233.         for (p = lp->head; p; p = p->next)
    234.                 pfn(&p->data);
    235.         printf("\n");
    236.         return 1;
    237. }
    复制代码

    1. /* test2.c -- 单向链表      */
    2. /* 和list2.c一起编译        */


    5. #include "List2.h"

    7. void myprintf(ElementType * pdata)
    8. {
    9.         printf("%d ", *pdata);
    10. }

    12. int main()
    13. {
    14.         int i;
    15.         List *lp = ListInit();
    16.         ElementType a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    17.         ElementType data = 99;

    19.         if(!lp)
    20.         {
    21.                 printf("\nInitList error!\n");
    22.                 return 0;
    23.         }

    25.         for (i = 0; i < 10; i++)
    26.         {
    27.                 InsertTail(lp, a+i);
    28.         }

    30.         ListTraverse(lp, myprintf);

    32.         InsertHead(lp, &data);
    33.         ListTraverse(lp, myprintf);

    35.         InsertTail(lp, &data);
    36.         ListTraverse(lp, myprintf);

    38.         InsertNode(lp, 3, &data);
    39.         ListTraverse(lp, myprintf);

    41.         RemoveNode(lp, 3);
    42.         ListTraverse(lp, myprintf);

    44.         RemoveNode(lp, 12);
    45.         ListTraverse(lp, myprintf);

    47.         RemoveNode(lp, 1);
    48.         ListTraverse(lp, myprintf);

    50.         ListDestory(lp);
    51.         return 1;
    52. }
    复制代码
    QQ图片20150208111722.jpg
    PYG19周年生日快乐！
    回复

    使用道具 举报

    Nisy

    该用户从未签到
    发表于 2015-2-9 10:56:18 | 显示全部楼层

    赞！学编程非写代码，拍错误方可学会。Why，因为语法不是我们定义的，编译器不是我们实现的，所以必须要动手写代码才能学会编程。

    还有一种实现在这里：http://www.sicaril.com/thread-529-1-2.html
    PYG19周年生日快乐！
    回复 支持 反对

    使用道具 举报

    返回列表 发新帖
    高级模式
    B Color Image Link Quote Code Smilies
    您需要登录后才可以回帖 登录 | 加入我们

    本版积分规则

    快速回复 返回顶部 返回列表