首页 > 其他 > 详细

9.9 链表及其运用

时间：2014-09-15 01:02:28      阅读：338      评论：0      收藏：0      [点我收藏+]
单向链表的实现方法：
    1. #include <stdio.h>
    2. #include <stdlib.h>
    4. struct list
    5. {
    6.         int data;
    7.         struct list *next;
    8. };
    10. /*创建一个节点*/
    11. struct list *create_list()
    12. {
    13.         return calloc(sizeof(struct list) , 1);
    14. }
    16. /*打印链表的内容*/
    17. void traverse(struct list *p)
    18. {
    19.         //循环实现
    20.         //p = p->next;//头节点不需要打印
    21.         //while(p)
    22.         //{
    23.         //      printf("%d\n" , p->data);
    24.         //      p = p->next;
    25.         //}
    27.         //递归实现
    28.         if (p->next == NULL)
    29.                 return;
    30.         printf("%d\n" , p->next->data);
    31.         traverse(p->next);
    32. }
    34. /*向链表插入一个节点*/
    35. int insert_list(struct list *p , int n , int data)
    36. {
    37.         while (p && n--)
    38.                 p = p->next;
    39.         if (p == NULL)
    40.                 return 0;
    42.         struct list *node = create_list();
    43.         node->data = data;
    44.         node->next = p->next;
    45.         p->next = node;
    46.         return 1;
    47. }
    49. /*删除链表的一个节点*/
    50. int delete_list(struct list *p , int n)
    51. {
    52.         while (p && n--)
    53.                 p = p->next;
    55.         if (p == NULL)
    56.                 return 0;
    58.         struct list *temp = p->next;
    59.         if (temp == NULL)
    60.                 return 0;
    61.         p->next = temp->next;
    62.         free(temp);
    63.         return 1;
    64. }
    66. /*计算链表节点的数量*/
    67. int count_list(struct list *p)
    68. {
    69.         int count = 0;
    70.         while(p->next)//不计算头节点
    71.         {
    72.                 p = p->next;
    73.                 count++;
    74.         }
    75.         return count;
    76. }
    78. /*清空一个链表,只保留头节点*/
    79. void clear_list(struct list *p)
    80. {
    81.         struct list *head = p;
    82.         p = p->next;
    83.         while(p)
    84.         {
    85.                 struct list * tmp = p->next;
    86.                 free(p);
    87.                 p = tmp;
    88.         }
    89.         head->next = NULL;
    90. }
    92. /*判断一个链表是否为空*/
    93. int empty_list(struct list *p)
    94. {
    95.         if(p->next != NULL)
    96.                 return 0;
    97.         else
    98.                 return 1;
    99. }
    101. /*返回链表指定位置的节点*/
    102. struct list *locale_list(struct list *p , int n)
    103. {
    104.         p = p->next;
    105.         while(p && n--)
    106.         {
    107.                 p = p->next;
    108.         }
    109.         return p;
    110. }
    112. /*返回数据等于data的节点*/
    113. struct list *data_list(struct list *p , int data)
    114. {
    115.         p = p->next;
    116.         while(p)
    117.         {
    118.                 if(p->data == data)
    119.                         return p;
    120.         }
    121.         return NULL;
    122. }
    124. /*返回数据等于data的节点位置*/
    125. int data_pos(struct list *p , int data)
    126. {
    127.         int index = 0;
    128.         p = p->next;
    129.         while(p)
    130.         {
    131.                 if(p->data == data)
    132.                         break;
    133.                 p = p->next;
    134.                 index++;
    135.         }
    136.         return index;
    137. }
    139. /*返回链表中最后一个节点*/
    140. struct list *last_list(struct list *p)
    141. {
    142.         while(p->next)
    143.         {
    144.                 p = p->next;
    145.         }
    146.         return p;
    147. }
    149. /*合并两个链表，结果放入第一个链表内*/
    150. void merge_list(struct list *p , struct list *q)
    151. {
    152.         struct list *p_last = last_list(p);
    153.         p_last->next = q->next;
    154.         free(q);
    155. }
    157. /*逆置一个链表*/
    158. struct list *reverse_list(struct list *p)
    159. {
    160.         struct list *pre = p;
    161.         struct list *cur = p->next;
    162.         struct list *next = NULL;
    163.         struct list *last = p->next;
    165.         while(cur)
    166.         {
    167.                 next = cur->next;
    168.                 cur->next = pre;
    169.                 pre = cur;
    170.                 cur = next;
    171.         }
    173.         last->next = NULL;
    174.         p->next = pre;
    175. }
    178. int main(void)
    179. {
    180.         struct list *head = create_list();
    181.         int i;
    182.         for (i = 0 ; i < 4 ; i++)
    183.         {
    184.                 insert_list(head,i,i);
    185.         }
    186.         traverse(head);
    187.         printf("%d\n",last_list(head)->data);
    188.         return 0;
    189. }

head  -> first -> second -> null

优化后的链表程序：
    1. #include <stdio.h>
    2. #include <stdlib.h>
    4. struct list
    5. {
    6.         int data;
    7.         struct list * next;
    8. };
    10. //打印一个链表
    11. void traverse_list(struct list *ls)
    12. {
    13.         struct list * p = ls->next;//不打印头节点
    14.         while(p)
    15.         {
    16.                 printf("%d\n",p->data);
    17.                 p = p->next;
    18.         }
    19. }
    21. //创建一个节点空间
    22. struct list *create_list()
    23. {
    24.         return calloc(sizeof(struct list) , 1);
    25. }
    27. //插入一个节点
    28. struct list *insert_list(struct list * ls , int n , int data)
    29. {
    30.         struct list * p = ls;
    31.         while(p && n--)
    32.         {
    33.                 p = p->next;
    34.         }
    35.         if(!p)
    36.                 return NULL;
    37.         struct list *node = create_list();
    38.         node->next = p->next;
    39.         node->data = data;
    40.         p->next = node;
    41.         return p;
    42. }
    44. //删除一个节点
    45. int delete_list(struct list *ls , int n)
    46. {
    47.         struct list *p = ls;
    48.         while (p && n--)
    49.         {
    50.                 p = p->next;
    51.         }
    52.         struct list *tmp = p->next;
    53.         p->next = tmp->next;
    54.         free(tmp);
    55. }
    57. //初始化一个链表
    58. struct list *init_list(int n)
    59. {
    60.         struct list *head = create_list();
    61.         int i;
    62.         for(i = 0 ; i < n ; i++)
    63.                 insert_list(head,i,i);
    64.         return head;
    65. }
    67. //统计节点的数量
    68. int count_list(struct list *ls)
    69. {
    70.         struct list * p = ls->next;
    71.         int count = 0;
    72.         while(p)
    73.         {
    74.                 p = p->next;
    75.                 count++;
    76.         }
    77.         return count;
    78. }
    80. //清空链表
    81. void clear_list(struct list *ls)
    82. {
    83.         struct list * p = ls->next;
    84.         while(p)
    85.         {
    86.                 struct list * tmp = p->next;
    87.                 free(p);
    88.                 p = tmp;
    89.         }
    90.         ls->next = NULL;
    91. }
    93. //判断一个链接是否为空
    94. int empty_list(struct list *ls)
    95. {
    96.         struct list *p = ls->next;
    97.         if (p!=NULL)
    98.                 return 0;
    99.         else
    100.                 return 1;
    101. }
    103. //返回链表指定位置的节点
    104. struct list *locale_list(struct list *ls , int n)
    105. {
    106.         struct list * p = ls->next;
    107.         while(p && n--)
    108.         {
    109.                 p = p->next;
    110.         }
    111.         return p;
    112. }
    114. //返回链接等于data的节点
    115. struct list *data_list(struct list *ls , int data)
    116. {
    117.         struct list *p = ls->next;
    118.         while (p)
    119.         {
    120.                 if (p->data == data)
    121.                         break;
    122.                 p = p->next;
    123.         }
    124.         return p;
    125. }
    127. //返回链表等于data的位置
    128. int pos_list(struct list *ls , int data)
    129. {
    130.         struct list *p = ls->next;
    131.         int index = 0;
    132.         while (p)
    133.         {
    134.                 if(p->data == data)
    135.                         break;
    136.                 p = p->next;
    137.                 index++;
    138.         }
    139.         return index;
    140. }
    143. //得到最后一个节点
    144. struct list *last_list(struct list *ls)
    145. {
    146.         struct list *p = ls->next;
    147.         struct list *pre = p;
    148.         while(p)
    149.         {
    150.                 pre = p;
    151.                 p = p->next;
    152.         }
    153.         return pre;
    154. }
    156. //合并两个链表，放入第一个链表中
    157. void merge_list(struct list *ls1 , struct list *ls2)
    158. {
    159.         struct list *last = last_list(ls1);
    160.         last->next = ls2->next;
    161.         free(ls2);
    162. }
    164. //链表逆置
    165. void reverse_list(struct list *ls)
    166. {
    167.         struct list *pre = ls;
    168.         struct list *cur = ls->next;
    169.         struct list *next = NULL;
    170.         struct list *last = ls->next;
    172.         while (cur)
    173.         {
    174.                 next = cur->next;
    175.                 cur->next = pre;
    176.                 pre = cur;
    177.                 cur = next;
    178.         }
    179.         last->next = NULL;
    180.         ls->next = pre;
    181. }
    185. int main(void)
    186. {
    187.         struct list *head = init_list(10);
    188.         traverse_list(head);
    189.         return 0;
    190. }

注重理解下面左值和右值的区别
  1. node->next = p->next;
  2. p->next = node;


把本班的同学读入到结构体数组里，加上序号，利用链表并且冒泡排序。
    1. #include <stdio.h>
    2. #include <stdlib.h>
    3. #include <string.h>
    4. #include <time.h>
    5. struct student
    6. {
    7.         int ID;
    8.         char name[20];
    9. };
    11. struct list
    12. {
    13.         struct student st;
    14.         struct list *next;
    15. };
    17. struct list *create_list()
    18. {
    19.         return calloc(1,sizeof(struct list));
    20. }
    22. struct list *insert_list(struct list *ls , int n, struct student s)
    23. {
    24.         struct list *p = ls;
    25.         while (p && n--)
    26.                 p = p->next;
    27.         if(!p)
    28.                 return NULL;
    29.         struct list *node = create_list();
    30.         node->st = s;
    31.         node->next = p->next;
    32.         p->next = node;
    33.         return node;
    34. }
    35. void traverse_list(struct list *ls)
    36. {
    37.         struct list *p = ls->next;
    38.         while(p)
    39.         {
    40.                 printf("%d:%s\n",p->st.ID,p->st.name);
    41.                 p = p->next;
    42.         }
    43. }
    45. void init_list(struct list *ls)
    46. {
    47.         struct list *head = ls;
    48.         FILE *fp = fopen("student.bin","r");
    49.         while(!fp)
    50.                 return;
    52.         struct student st;
    53.         int index = 0;
    54.         while(fread(&st,sizeof(struct student),1,fp) > 0)
    55.         {
    56.                 insert_list(head,index,st);
    57.                 index++;
    58.         }
    60. }
    62. void sort_list(struct list *ls , int n)
    63. {
    64.         struct list *p = NULL;
    65.         struct student tmp;
    66.         int i,j,min;
    67.         for (i = 0; i < n ; i++)
    68.         {
    69.                 p = ls->next;
    70.                 for (j = 0; j < n-i-1; j++)
    71.                 {
    72.                         if (p->st.ID > p->next->st.ID)
    73.                         {
    74.                                 tmp = p->st;
    75.                                 p->st = p->next->st;
    76.                                 p->next->st = tmp;
    77.                         }
    78.                         p = p->next;
    79.                 }
    80.         }
    81. }
    83. void init_stubin()
    84. {
    85.         srand((unsigned)time(NULL));
    86.         FILE *fp1 = fopen("student.txt","r");
    87.         FILE *fp2 = fopen("student.bin","w");
    88.         while(!fp1 || !fp2)
    89.                 return;
    91.         char buf[1024];
    92.         struct student st;
    93.         memset(&st,0,sizeof(st));
    95.         int arr[42] = {0};
    96.         int pos;
    97.         while(fgets(buf,sizeof(buf),fp1) != NULL)
    98.         {
    99.                 if(buf[strlen(buf)-1] == ‘\n‘)
    100.                         buf[strlen(buf)-1] = ‘\0‘;
    101.                 pos = rand()%42;
    102.                 while(arr[pos] == 1)
    103.                         pos = rand()%42;
    104.                 arr[pos] = 1;
    105.                 st.ID = pos;
    106.                 strcpy(st.name,buf);
    107.                 fwrite(&st,sizeof(st),1,fp2);
    108.         }
    109.         fclose(fp1);
    110.         fclose(fp2);
    111. }
    113. int main(void)
    114. {
    115.         init_stubin();
    116.         struct list *head = create_list();
    117.         init_list(head);
    118.         //traverse_list(head);
    119.         sort_list(head,42);
    120.         traverse_list(head);
    121.         return 0;
    122. }
bubuko.com,布布扣




9.9 链表及其运用

原文：http://www.cnblogs.com/l6241425/p/3972022.html
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！
      
↑
↓