C 语言 _ 链表总结
作者：DS小龙哥
- 2022 年 5 月 14 日
本文字数：5334 字
阅读完需：约 18 分钟
本篇文章介绍 C 语言链表相关知识点，涉及链表的创建、单向链表、循环链表、双向链表、单向循环链表，链表常见问题总结等，还列出了结构体数组与链表的练习题，将在下篇文章贴出完整代码。
1. 链表
1.1 结构体对比
数组特性: 内存空间连续、只能存放相同类型的数据结构体特性: 内存空间连续、可以存放不同类型的数据
#include <stdio.h>struct MyStruct{ int a; char b;};
int main(){ struct MyStruct *p; struct MyStruct data={12,'A'}; data.a=123; data.b='B';
p=&data; printf("%d\n",p->a); printf("%c\n",p->b); return 0;}
复制代码
数组学生管理系统作业：
作业: 学生管理系统需求: (每一个功能都是使用函数进行封装)1.实现从键盘上录入学生信息。 (姓名、性别、学号、成绩、电话号码)2.将结构体里的学生信息全部打印出来。3.实现根据学生的姓名或者学号查找学生，查找到之后打印出学生的具体信息。4.根据学生的成绩对学生信息进行排序。5.根据学号删除学生信息。
复制代码
1.2 单向链表的创建与运用
链表: 单链表、双链表 区分: 循环和不循环链表链表的特性: 一种数据结构的运行--->结构体。
学习结构体数组(编写学生管理系统): 学生的人数问题不好确定。链表本身就是一个结构体。
单向链表的创建与运用:
#include <stdio.h>#include <stdlib.h>#include <string.h>
//定义结构体struct MyListStruct{ int a; struct MyListStruct *next; //结构体指针。存放下一个节点的地址};
//定义链表头struct MyListStruct *ListHead=NULL;
//函数声明struct MyListStruct *CreateListHead(struct MyListStruct *head);void PintListInfo(struct MyListStruct *head);void AddListNode(struct MyListStruct *head,struct MyListStruct NewNode);void DeleteListNode(struct MyListStruct *head,int a);
int main(){ int i; struct MyListStruct temp; int a; //1. 创建链表头 ListHead=CreateListHead(ListHead);
//2. 添加节点 for(i=0; i<5; i++) { printf("输入新节点数据:"); scanf("%d",&temp.a); AddListNode(ListHead,temp); }
//3. 打印所有节点数据 PintListInfo(ListHead);
//4. 删除节点数据 printf("输入删除的节点数据值:"); scanf("%d",&a); DeleteListNode(ListHead,a);
//5. 打印所有节点数据 PintListInfo(ListHead); return 0;}
/*函数功能: 创建链表头返回值 : 链表头指针*/struct MyListStruct *CreateListHead(struct MyListStruct *head){ if(head==NULL) { head=malloc(sizeof(struct MyListStruct)); head->next=NULL; } return head; //返回链表头}
/*函数功能: 添加链表节点说明: 链表头一般不存放数据*/void AddListNode(struct MyListStruct *head,struct MyListStruct NewNode){ struct MyListStruct *p=head; //保存头地址 struct MyListStruct *new_p=NULL; //新的节点
/*1. 寻找链表尾*/ while(p->next!=NULL) { p=p->next; //移动到下一个地址 } /*2. 创建新节点*/ new_p=malloc(sizeof(struct MyListStruct)); if(new_p==NULL) { printf("新节点内存申请失败!\n"); return; } /*3. 新节点赋值*/ memcpy(new_p,&NewNode,sizeof(struct MyListStruct)); //内存拷贝 new_p->next=NULL; //尾节点指向空
/*4. 新节点添加*/ p->next=new_p;}
/*函数功能: 删除链表节点*/void DeleteListNode(struct MyListStruct *head,int a){ struct MyListStruct *p=head; //保存头地址 struct MyListStruct *tmp=NULL; /*查找数据存在的节点位置*/ while(p->next!=NULL) { tmp=p; //保存上一个节点的地址 p=p->next; if(p->a==a) //查找成功 { tmp->next=p->next; //将要删除节点的指针值赋值给删除节点的上一个节点指针域 //tmp->next=tmp->next->next; free(p); //直接释放p节点空间 //break; p=head; //重新指向链表头 } }}
/*函数功能: 遍历所有链表信息*/void PintListInfo(struct MyListStruct *head){ int cnt=0; struct MyListStruct *p=head; printf("\n链表遍历的数据如下:\n"); while(p->next!=NULL) { p=p->next; cnt++; printf("第%d个节点的数据=%d\n",cnt,p->a); }}
复制代码
作业:
1.看代码、理解链表的创建流程2.编写出单向链表的基础运用3.将之前的学生管理系统使用链表方式做出来
链表的功能:(1)创建链表头(2)在链表结尾添加一个节点(3)删除指定的一个链表节点(4)遍历链表，打印出所有的数据。(5)在链表的指定节点的后面添加一个节点。(6)根据链表节点里的数据对链表进行排序。 双向链表:(1)使用逆向+顺向两种遍历方式删除链表节点，目的: 提高效率。 类似于二分法查找。
复制代码
2. 链表问题总结
动态空间分配:#include <stdio.h>#include <stdlib.h>#include <string.h>
int main(){ char *p=malloc(100); //申请动态空间。 if(p==NULL) { return -1; } strcpy(p,"1234567890"); printf("%s\n",p); return 0;}
#include <stdio.h>#include <stdlib.h>#include <string.h>
int main(){ char *p1=malloc(100); //申请动态空间。 printf("%p\n",p1); char *p2=malloc(100); //申请动态空间。 printf("%p\n",p2); char *p3=malloc(100); //申请动态空间。 printf("%p\n",p3); char *p4=malloc(100); //申请动态空间。 printf("%p\n",p4); return 0;}错误解决:1.第一个错误开始解决2.常规错误: 函数没有声明、分号每加、括号没有加、=3.括号没有对齐。
复制代码
3. 双向链表和循环链表
3.1 单向循环链表:
#include <stdio.h>#include <stdlib.h>#include <string.h>
//定义结构体struct MyListStruct{ int a; struct MyListStruct *next; //结构体指针。存放下一个节点的地址};
//定义链表头struct MyListStruct *ListHead=NULL;
//函数声明struct MyListStruct *CreateListHead(struct MyListStruct *head);void PintListInfo(struct MyListStruct *head);void AddListNode(struct MyListStruct *head,struct MyListStruct NewNode);void DeleteListNode(struct MyListStruct *head,int a);
int main(){ int i; struct MyListStruct temp; int a; //1. 创建链表头 ListHead=CreateListHead(ListHead);
//2. 添加节点 for(i=0; i<5; i++) { printf("输入新节点数据:"); scanf("%d",&temp.a); AddListNode(ListHead,temp); }
//3. 打印所有节点数据 PintListInfo(ListHead);
//4. 删除节点数据 printf("输入删除的节点数据值:"); scanf("%d",&a); DeleteListNode(ListHead,a);
//5. 打印所有节点数据 PintListInfo(ListHead); return 0;}
/*函数功能: 创建链表头返回值 : 链表头指针*/struct MyListStruct *CreateListHead(struct MyListStruct *head){ if(head==NULL) { head=malloc(sizeof(struct MyListStruct)); head->next=head; } return head; //返回链表头}
/*函数功能: 添加链表节点说明: 链表头一般不存放数据*/void AddListNode(struct MyListStruct *head,struct MyListStruct NewNode){ struct MyListStruct *p=head; //保存头地址 struct MyListStruct *new_p=NULL; //新的节点 /*1. 寻找链表尾*/ while(p->next!=head) { p=p->next; //移动到下一个地址 } /*2. 创建新节点*/ new_p=malloc(sizeof(struct MyListStruct)); if(new_p==NULL) { printf("新节点内存申请失败!\n"); return; } /*3. 新节点赋值*/ memcpy(new_p,&NewNode,sizeof(struct MyListStruct)); //内存拷贝 new_p->next=head; //尾节点指向头
/*4. 新节点添加*/ p->next=new_p;}
/*函数功能: 删除链表节点*/void DeleteListNode(struct MyListStruct *head,int a){ struct MyListStruct *p=head; //保存头地址 struct MyListStruct *tmp=NULL;
/*查找数据存在的节点位置*/ while(p->next!=head) { tmp=p; //保存上一个节点的地址 p=p->next; if(p->a==a) //查找成功 { tmp->next=p->next; //将要删除节点的指针值赋值给删除节点的上一个节点指针域 //tmp->next=tmp->next->next; free(p); //直接释放p节点空间 //break; p=head; //重新指向链表头 } }}
/*函数功能: 遍历所有链表信息*/void PintListInfo(struct MyListStruct *head){ int cnt=0; struct MyListStruct *p=head; printf("\n链表遍历的数据如下:\n"); while(p->next!=head) { p=p->next; cnt++; printf("第%d个节点的数据=%d\n",cnt,p->a); }}
复制代码
3.2 双向链表
#include <stdio.h>#include <stdlib.h>#include <string.h>
//定义结构体struct MyListStruct{ int a; struct MyListStruct *next; //结构体指针。存放下一个节点的地址 struct MyListStruct *old; //结构体指针。存放上一个节点的地址};
//定义链表头struct MyListStruct *ListHead=NULL;
//函数声明struct MyListStruct *CreateListHead(struct MyListStruct *head);void PintListInfo(struct MyListStruct *head);void AddListNode(struct MyListStruct *head,struct MyListStruct NewNode);void DeleteListNode(struct MyListStruct *head,int a);void PintListInfo_old(struct MyListStruct *head);
int main(){ int i; struct MyListStruct temp; int a; //1. 创建链表头 ListHead=CreateListHead(ListHead);
//2. 添加节点 for(i=0; i<5; i++) { printf("输入新节点数据:"); scanf("%d",&temp.a); AddListNode(ListHead,temp); }
//3. 打印所有节点数据 PintListInfo(ListHead); PintListInfo_old(ListHead);
//4. 删除节点数据 printf("输入删除的节点数据值:"); scanf("%d",&a); DeleteListNode(ListHead,a);
//5. 打印所有节点数据 PintListInfo(ListHead); PintListInfo_old(ListHead); return 0;}
/*函数功能: 创建链表头返回值 : 链表头指针*/struct MyListStruct *CreateListHead(struct MyListStruct *head){ if(head==NULL) { head=malloc(sizeof(struct MyListStruct)); head->next=NULL; //尾节点指向空 head->old=head; //上一个节点指向头 } return head; //返回链表头}
/*函数功能: 添加链表节点说明: 链表头一般不存放数据*/void AddListNode(struct MyListStruct *head,struct MyListStruct NewNode){ struct MyListStruct *p=head; //保存头地址 struct MyListStruct *new_p=NULL; //新的节点 /*1. 寻找链表尾*/ while(p->next!=NULL) { p=p->next; //移动到下一个地址 } /*2. 创建新节点*/ new_p=malloc(sizeof(struct MyListStruct)); if(new_p==NULL) { printf("新节点内存申请失败!\n"); return; } /*3. 新节点赋值*/ memcpy(new_p,&NewNode,sizeof(struct MyListStruct)); //内存拷贝 new_p->next=NULL; //尾节点指向NULL new_p->old=p; //保存上一个节点的地址 /*4. 新节点添加*/ p->next=new_p;}
/*函数功能: 删除链表节点顺向删除。*/void DeleteListNode(struct MyListStruct *head,int a){ struct MyListStruct *p=head; //保存头地址 struct MyListStruct *tmp=NULL;
/*查找数据存在的节点位置*/ while(p->next!=NULL) { tmp=p; //保存上一个节点的地址 p=p->next; if(p->a==a) //查找成功 { tmp->next=p->next; //将要删除节点的指针值赋值给删除节点的上一个节点指针域 //tmp->next=tmp->next->next; p->next->old=tmp; //保存上一个节点的地址
free(p); //直接释放p节点空间 //break; p=head; //重新指向链表头 } }}
/*函数功能: 遍历所有链表信息从头到尾遍历*/void PintListInfo(struct MyListStruct *head){ int cnt=0; struct MyListStruct *p=head; printf("\n(顺向)链表遍历的数据如下:\n"); while(p->next!=NULL) { p=p->next; cnt++; printf("第%d个节点的数据=%d\n",cnt,p->a); }}
/*函数功能: 遍历所有链表信息从尾到头遍历*/void PintListInfo_old(struct MyListStruct *head){ int cnt=0; struct MyListStruct *p=head; printf("\n(逆向)链表遍历的数据如下:\n"); /*1. 找到链表尾*/ while(p->next!=NULL) { p=p->next; } /*2. 通过链表尾遍历链表的数据*/ while(p!=head) { cnt++; printf("第%d个节点的数据=%d\n",cnt,p->a); p=p->old; //访问上一个节点 }}
复制代码
划线
评论
复制
发布于: 刚刚阅读数: 2
版权声明: 本文为 InfoQ 作者【DS小龙哥】的原创文章。
原文链接:【http://xie.infoq.cn/article/b1b600b0bdf464c179c6997a5】。文章转载请联系作者。
DS小龙哥
关注
之所以觉得累，是因为说的比做的多。 2022.01.06 加入
熟悉C/C++、51单片机、STM32、Linux应用开发、Linux驱动开发、音视频开发、QT开发. 目前已经完成的项目涉及音视频、物联网、智能家居、工业控制领域
评论