C语言_链表总结

网友投稿 732 2022-05-29

本篇文章介绍C语言链表相关知识点,涉及链表的创建、单向链表、循环链表、双向链表、单向循环链表,链表常见问题总结等,还列出了结构体数组与链表的练习题,将在下篇文章贴出完整代码。

1. 链表

1.1 结构体对比

数组特性: 内存空间连续、只能存放相同类型的数据

结构体特性: 内存空间连续、可以存放不同类型的数据

C语言_链表总结

#include 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 #include #include //定义结构体 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 #include #include int main() { char *p=malloc(100); //申请动态空间。 if(p==NULL) { return -1; } strcpy(p,"1234567890"); printf("%s\n",p); return 0; } #include #include #include 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 #include #include //定义结构体 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 #include #include //定义结构体 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; //访问上一个节点 } }

C 语言 数据结构

版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:python基础之字符串(七)
下一篇:【Linux】文件权限解读
相关文章