C语言之链表
单链表,双链表,循环双链表 选自《C语言整理-双向链表和单项链表那些事》
链表可以为空但不能没有head指针(可作为链表名字),头节点非必须,只是为了增删操作的统一和规范。
单链表的插入只能从后面插入即尾插法。
链表就像一个铁链,每个节点node除了自身数据外,还包括一个指向下一个数据的指针(*nest),也就是该该指针即是节点数据结构体的成员又是一个指向下个元素的指针。链表都有一个头(*head指针指向首个元素地址)和尾指针(*tail=NULL),加上每个节点就构成了简单的链表。
链表的创建可以静态地用结构体实现,也可以动态的用malloc实现。
链表据说打破了C的2个特例:先定义后使用(链表里自己定义自己,递归函数)
简单链表的基本操作:创建链表、定位、插入、删除、输出内容。
一 创建链表:创建结构体,初始化节点数据,head,tail,nest指针的初始化
1 void CreatList_Demo(void) 2 { 3 struct student a,b,c; 4 struct student *head,*p; 5 6 /*初始化静态链表成员*/ 7 a.ID =1001;a.score =90; 8 b.ID =1002;b.score =80; 9 c.ID =1003;c.score =100; 10 11 /*初始化链表指针*/ 12 head =&a;a.nest=&b;b.nest=&c;c.nest =NULL; 13 p=head; 14 15 /*打印输出,注意p指针的变化*/ 16 do{ 17 printf("学号:%ld,分数:%5.1f\n",p->ID,p->score); 18 p=p->nest; 19 }while(p!=NULL); 20 }
二 节点的删除:
1 struct student * DelList_Demo(struct student **head,long num) 2 { 3 4 struct student *p1,*p2; 5 if(*head ==NULL)/*空链表情况*/ 6 { 7 printf("list is empty!!!\n"); 8 goto end; 9 } 10 p1 =*head;/*从头开始查找*/ 11 while((p1->ID !=num) &&(p1->nest !=NULL)) 12 { 13 p2=p1;/*p2始终是p1的前继*/ 14 p1=p1->nest; 15 } 16 if(p1->ID ==num)/*找到了*/ 17 { 18 if(p1 ==*head)/*第一个*/ 19 { 20 *head =p1->nest; 21 } 22 else 23 { 24 p2->nest =p1->nest; 25 } 26 } 27 else/*没找到*/ 28 { 29 printf("no find this node!!!\n"); 30 } 31 end: 32 return *head; 33 }
三节点的添加:注意空链表,插入头部等特殊处理
/* (**head):链表,二维指针,实参调用List_Insert(struct node &head,p0)这样更改才会对链表有修改 p0:待插入的节点指针 */ void List_Insert(struct node **head,struct node *p0) { struct node *front,*behind; if((*head)==NULL)/*空链表*/ { *head=p0; return; } else { if((*head)->num > p0->num)/*插入第一个位置*/ { p0->nest =*head; *head =p0; return; } front =*head; behind =(*head)->nest; while(behind!=NULL) { if(behind->num < p0->num) { front =behind; behind =behind->nest; } else break; } front->nest =p0;/*找到位置后正确插入*/ p0->nest =behind; } }
工程代码:https://www.onlinegdb.com/edit/HJAdIuM2H
参考学习https://wenku.baidu.com/view/d85a996c561252d380eb6ebc.html?sxts=1574257668264
循环链表与双向链表 :参考https://www.cnblogs.com/dengfaheng/p/9245770.html
循环链表:
引入原因:单链表要想访问某个元素,必须从head指针开始顺序访问,即使是尾元素也需要遍历一遍,效率很低,当将尾指针指向头指针折成一个环时就成了单循环链表。也可以只定义尾指针,顺序移动一个位置就到了头位置,对单循环链表的操作与单链表差不多,唯一区别就是判断结束条件不再是p=null,而是p=head
双向链表:
引入原因:单链表只能顺序逐一朝后,不能朝前;所以在单链表结构体中增加一个pre前继指针就成了双向链表,可以向前遍历了。
双向链表的创建:给首尾节点分配空间,且首节点的前继与尾结点的后继都为null,且前继的next指向尾节点的前继pre.
双向链表的插入和删除:画个模拟图就能搞明白。
相关文章
- 【C语言】动态内存常见错误及经典笔试题
- C语言双链表,循环链表,静态链表讲解(王道版)
- C语言基础:【int=4字节(Byte)】【1K=1024B】【1字节(Byte)=8比特(bit)】【1比特(bit)=1位】【比特(bit)指的是二进制中的一位(0/1),是二进制最小信息单位】
- C语言实现链表
- C语言关键字—-sizeof 、typedef、const、static、register、extern、#define
- C语言运算符的优先级
- 05【C语言 & 趣味算法】经典:兔子产子问题(即:Fibonacci数列)
- 【C语言】switch语句 输出成绩判断成绩档次 (基础 需多次回看 加深记忆)
- C语言动态库和静态库的使用及实践
- 数据结构 内部排序(综合所有)C语言实现
- C语言中将数字转换为字符串的方法
- C语言和设计模式(策略模式)
- C语言程序设计基础|数独
- C语言通过文件名在Linux上当前目录及子目录中查找
- C-指针,二级指针,二维数组作为函数参数使用,指针数组,C语言链表(详解)
- 李洪强漫谈iOS开发[C语言-053]-小结
- 李洪强iOS开发之OC语言BLOCK和协议
- [数据结构 - 第3章] 线性表之双向链表(C语言实现)