devbox
小丑西瓜9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

链表超细详解_创建一个新的节点用来保存输入学生成绩

作者：小丑西瓜9 | 2024-05-05 03:38:32

赞

踩

创建一个新的节点用来保存输入学生成绩

前言：今天花了一下午时间学习了链表，讲自己所学内容分享给大家，本篇内容对于链表的使用进行了非常详细的讲解，搭配代码的编写事半功倍，希望对大家有所帮助，喜欢的可以一键三连（点赞，收藏，评论）

线性表

含义：当一组数据元素形成了前后关系时，我们称之为线性表

线性表在内存中的两种形式：

  1. 顺序表：以数组的形式存放，元素在内存中是连续存放的

特点：插入或删除一个数据元素时，需要移动其他数据元素

  1. （线性）链表：数据元素在内存中不需要连续存放，而是通过指针将个数据单元链接起来，就像一条”链子“一样将数据单元前后元素链接起来

特点：插入或删除一个数据元素时，不需要移动其他数据元素

（线性）链表

线性链表如何定义？

线性链表的节点可以用一个结构体类型来定义，其形式为

  1. struct 结构体类型名
  2. {
  3.    数据成员定义；
  4.    struct 节点结构体类型名 *指针变量名；
  5. }；
  6.  
  7. 例子：
  8. struct GRADE_iInfo
  9. {
  10.   int score;
  11.     struct GRADE_iInfo *next;
  12. };
  13. typedef struct GRADE_iInfo NODE;//类型重命名

链表的节点

节点包括：数据域和指针域

数据域：存放本节点的数据

指针域：存放下一节点的地址

头节点指针：存放第一个节点的指针（在下面创建链表中有详细图解）

线性链表的基本操作

基本操作有：创建，插入，删除，输出，销毁

以题目为例：

建立一个学生成绩的线性链表，然后对其进行插入，删除，显示，最后销毁该链表

1、主函数：
  1. #include<stdio.h>
  2. #include<stdlib.h>//动态内存函数的头文件
  3. //创建结构体类型，因为节点可以用结构体类型来定义
  4. struct Grade_Info
  5. {
  6. 	int score;
  7. 	struct Grade_Info *next;//节点的基类型要和节点的类型一致，相当于结构体的自引用
  8. };
  9. typedef struct Grade_Info NODE;//类型重命名
  10. //函数声明
  11. NODE*Creat_LinkList();//创建链表
  12. void Insert_LinkList(NODE*head,NODE*pnew,int i);//插入节点
  13. void Delete_LinkList(NODE*head,int i);//删除节点
  14. void Display_Linklist(NODE*head);//输出链表
  15. void Free_LinkList(NODE*head);//销毁链表
  16. int main()
  17. {
  18.     NODE*head = NULL;//头节点
  19.     NODE*pnew = NULL;//存放新节点的地址
  20.     head = Creat_LinkList();//创建链表
  21.     if(head == NULL)//创建失败
  22.       return 0 ;
  23.     printf("after creat:");
  24.     Display_Linklist(head);//输出链表的值
  25.     //新建一个要插入的节点
  26.     pnew = (NODE*)malloc(sizeof(NODE));//动态内存开辟
  27.     if(pnew == NULL)//新节点创建失败，则返回
  28.     {
  29.         printf("no enough memory\n");
  30.         return 0;
  31.     }
  32.     pnew->score = 88;
  33.     //将新节点插入节点2的后面
  34.     Insert_LinkList(head,pnew,2);
  35.     return 0;
  36. }

2、创建线性链表

含义：从无到有创建一个链表，即往空链表中依次插入若干个节点，并保持节点之间的前驱和 后继关系

基本思想：首先创建一个头节点，让头指针（head）和尾指针（tail）都指向该节点，并设置该节点的指针域为NULL（链尾标志）；然后为实际数据创建一个节点，用指针pnew（用来存放新节点的地址）指向它，并将实际数据放在该节点的数据域，其指针与为NULL；最后将该节点插入到tail所指向节点的后面，同时时tail指向pnew指向的节点

  1. NODE*Creat_LinkList()
  2. {
  3.     NODE*head = NULL;//头节点
  4.     NODE*tail = NULL;//尾节点
  5.     NODE*pnew = NULL;//存放新节点的地址
  6.     int score = 0;
  7.     head = (NODE*)malloc(sizeof(NODE));//创建头节点
  8.     if(head==NULL)
  9.     {
  10.         printf("no enough memory!\n");
  11.         return NULL;
  12.     }
  13.     head->next = NULL;
  14.     tail = head;
  15.     printf("intput the score of students:\n");
  16.     while(1)//创建学生成绩线性链表
  17.     {
  18.         scanf("%d",&score);//输入成绩
  19.         if(score<0)//成绩为负，循环退出
  20.         {
  21.         break;
  22.         }
  23.         //创建一个新的节点，存放成绩
  24.         pnew = (NODE*)malloc(sizeof(NODE));
  25.         if(pnew == NULL)
  26.         {
  27.             printf("no enough memory!\n");
  28.             return NULL;
  29.         }
  30.     	pnew->score = score;
  31.     	pnew->next = NULL;
  32.         tail->next = pnew;
  33.         tail = pnew;
  34.     }
  35.     return head;
  36. }

3、插入节点

基本思想：通过单链表的头指针head，首先找到链表的第一个节点；然后顺着节点的指针域找到第i个节点，最后将pnew指向的新节点插入到第i个节点之后。插入时首先将新节点的指针域指向第i个节点的后继节点，然后再将第i个节点的指针域指向新节点。注意顺序不能颠倒。当i=0时；表示头节点

  1. void Insert_LinkList(NODE*head,NODE*pnew，int i)
  2. {
  3.     //i == 2
  4.     NODE*p = NULL;
  5.     int j = 0;
  6.     p = head;
  7.     for(j = 0;j<i&&p!=NULL;j++)//将p指向要插入的第i个节点
  8.     {
  9.         p = p->next;
  10.     }
  11.     if(p == NULL)//表明链表中的第i个节点不存在
  12.     {
  13.         printf("the %d nonde not found\n",i);
  14.         return;
  15.     }
  16.     pnew->next = p->next;;//将插入节点的指针域指向第i个节点后继节点
  17.     p->next=pnew;//将第i个节点的指针域指插入的节点
  18. }

4、删除节点
  1. void Delete_LinkList(NODE*head,int i)
  2. {
  3.     NODE*p = NULL;
  4.     NODE*q = NULL;
  5.     int j = 0;
  6.     if(i == 0)//删除的是头指针
  7.     {
  8.         return ;
  9.     }
  10.     p = head;
  11.     //将p指向要删除的第i个节点的前驱节点
  12.     for(j = 1;j<i&&p->next!=NULL;j++)
  13.     {
  14.         p = p->next;
  15.     }
  16.     if(p->next == NULL)//表明要删除的第i个节点不存在
  17.     {
  18.         printf("the %d node not found\n",i);
  19.         return;
  20.     }
  21.     q = p->next;//q指向待删除的节点i
  22.     p->next = q->next;//删除节点i
  23.     free(q);//释放节点的内存单元
  24. }

5、输出线性链表
  1. void Display_Linklist(NODE*head)
  2. {
  3.     NODE*p = NULL;
  4.     for(p = head->next;p!=NULL;p = p->next)//注意区分节点的地址和节点的指针域
  5.     {
  6.         printf("%d ",p->score);
  7.     }
  8.     printf("\n");
  9. }

6、销毁线性链表

基本思想：每次删除头节点的后继节点，最后删除头节点。注意，不是删除了头节点就可以删除震整个链表，要知道链表是一个节点一个接待你建立起来的，所以销毁它也必须一个节点一个节点的删除才行

  1. void Free_LinkList(NODE*head)
  2. {
  3.     NODE*p = NULL;
  4.     NODE*q = NULL;
  5.     p = head;
  6.     while(p->next != NULL)
  7.     {
  8.         q = p->next;
  9.         p->next = q->next;
  10.         free(q);
  11.     }
  12.     free(head);
  13. }

7、总代码：
  1. #include<stdio.h>
  2. #include<stdlib.h>//动态内存函数的头文件
  3. //创建结构体类型，因为节点可以用结构体类型来定义
  4. enum choice
  5. {
  6.     no,//0
  7.     yes//1
  8. };
  9. struct Grade_Info
  10. {
  11.     int score;
  12.     struct Grade_Info* next;//节点的基类型要和节点的类型一致，相当于结构体的自引用
  13. };
  14. typedef struct Grade_Info NODE;//类型重命名
  15. //函数声明
  16. NODE* Creat_LinkList();//创建链表
  17. void Insert_LinkList(NODE* head, NODE* pnew, int i);//插入节点
  18. void Delete_LinkList(NODE* head, int i);//删除节点
  19. void Display_Linklist(NODE* head);//输出链表
  20. void Free_LinkList(NODE* head);//销毁链表
  21. int main()
  22. {
  23.     NODE* head = NULL;//头节点
  24.     NODE* pnew = NULL;//存放新节点的地址
  25.     head = Creat_LinkList();//创建链表
  26.     if (head == NULL)//创建失败
  27.         return 0;
  28.     printf("after creat:");
  29.     Display_Linklist(head);//输出链表的值
  30.     printf("是否要插入一个学生的成绩?是：1，否：0\n");
  31.     int n = 0;
  32.     scanf("%d", &n);
  33.     switch (n)
  34.     {
  35.         case no:
  36.             break;
  37.         case yes:
  38.         {
  39.             int i = 0;
  40.             printf("要插入到第几个学生后？\n");
  41.             scanf("%d", &i);
  42.             //新建一个要插入的节点
  43.             pnew = (NODE*)malloc(sizeof(NODE));//动态内存开辟
  44.             if (pnew == NULL)//新节点创建失败，则返回
  45.             {
  46.                 printf("no enough memory\n");
  47.                 return 0;
  48.             }
  49.             int score = 0;
  50.             printf("输入插入学生的成绩：");
  51.             scanf("%d", &score);
  52.             pnew->score = score;
  53.             Insert_LinkList(head, pnew,i );//将新节点插入节点n的后面
  54.             printf("afte insert:");
  55.             Display_Linklist(head);//输出链表的值
  56.         }
  57.     } 
  58.     printf("要删除某个学生的成绩吗？是：1，否：0\n");
  59.     int m = 0;
  60.     scanf("%d", &m);
  61.     switch (m)
  62.     {
  63.     case no:
  64.         break;
  65.     case yes:
  66.     {
  67.         int i = 0;
  68.         printf("要删除第几个学生的成绩？请输入：");
  69.         scanf("%d", &i);
  70.         Delete_LinkList(head,i);
  71.         printf("after Delete:");
  72.         Display_Linklist(head);//输出链表的值
  73.     }
  74.     }
  75.     //没有以上操作就销毁链表
  76.     Free_LinkList(head);
  77.     return 0;
  78. }
  79. //创建链表
  80. NODE* Creat_LinkList()
  81. {
  82.     NODE* head = NULL;//头节点
  83.     NODE* tail = NULL;//尾节点
  84.     NODE* pnew = NULL;//存放新节点的地址
  85.     int score = 0;
  86.     head = (NODE*)malloc(sizeof(NODE));//创建头节点
  87.     if (head == NULL)
  88.     {
  89.         printf("no enough memory!\n");
  90.         return NULL;
  91.     }
  92.     head->next = NULL;
  93.     tail = head;
  94.     printf("intput the score of students:\n");
  95.     while (1)//创建学生成绩线性链表
  96.     {
  97.         scanf("%d", &score);//输入成绩
  98.         if (score < 0)//成绩为负，循环退出
  99.         {
  100.             break;
  101.         }
  102.         //创建一个新的节点，存放成绩
  103.         pnew = (NODE*)malloc(sizeof(NODE));
  104.         if (pnew == NULL)
  105.         {
  106.             printf("no enough memory!\n");
  107.             return NULL;
  108.         }
  109.         pnew->score = score;
  110.         pnew->next = NULL;
  111.         tail->next = pnew;
  112.         tail = pnew;
  113.     }
  114.     return head;
  115. }
  116. //插入节点
  117. void Insert_LinkList(NODE* head, NODE* pnew,int i)
  118. {
  119.     //i == 2
  120.     NODE* p = NULL;
  121.     int j = 0;
  122.     p = head;
  123.     for (j = 0; j < i && p != NULL; j++)//将p指向要插入的第i个节点
  124.     {
  125.         p = p->next;
  126.     }
  127.     if (p == NULL)//表明链表中的第i个节点不存在
  128.     {
  129.         printf("the %d nonde not found\n", i);
  130.         return;
  131.     }
  132.     pnew->next = p->next;;//将插入节点的指针域指向第i个节点后继节点
  133.     p->next = pnew;//将第i个节点的指针域指插入的节点
  134. }
  135. //删除节点
  136. void Delete_LinkList(NODE* head, int i)
  137. {
  138.     NODE* p = NULL;
  139.     NODE* q = NULL;
  140.     int j = 0;
  141.     if (i == 0)//删除的是头指针
  142.     {
  143.         return;
  144.     }
  145.     p = head;
  146.     //将p指向要删除的第i个节点的前驱节点
  147.     for (j = 1; j < i && p->next != NULL; j++)
  148.     {
  149.         p = p->next;
  150.     }
  151.     if (p->next == NULL)//表明要删除的第i个节点不存在
  152.     {
  153.         printf("the %d node not found\n", i);
  154.         return;
  155.     }
  156.     q = p->next;//q指向待删除的节点i
  157.     p->next = q->next;//删除节点i
  158.     free(q);//释放节点的内存单元
  159. }
  160. //输出链表
  161. void Display_Linklist(NODE* head)
  162. {
  163.     NODE* p = NULL;
  164.     for (p = head->next; p != NULL; p = p->next)//注意区分节点的地址和节点的指针域
  165.     {
  166.         printf("%d ", p->score);
  167.     }
  168.     printf("\n");
  169. }
  170. //销毁链表
  171. void Free_LinkList(NODE* head)
  172. {
  173.     NODE* p = NULL;
  174.     NODE* q = NULL;
  175.     p = head;
  176.     while (p->next != NULL)
  177.     {
  178.         q = p->next;
  179.         p->next = q->next;
  180.         free(q);
  181.     }
  182.     free(head);
  183. }
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小丑西瓜9/article/detail/537082
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号