数据结构与算法 - 链表(表头插入、表尾插入、循环链表)
最编程
2024-06-11 12:50:44
...
????个人主页:bit..
????系列专栏:Linux(Ubuntu)入门必看 C语言刷题 数据结构与算法
目录
一.头插法
二.尾插法(后插法)
三.循环链表
一.头插法
建立单链表;头插法——元素插入在链表头部,也叫前插法。
算法步骤:
- 从一个空表开始,重复读入数据元素。
- 生成新结点,将读入数据存放到新结点的数据域中。
- 从最后一个结点开始,依次将各结点插入到链表的前端。
例如:建立链表L
算法描述:
void CreataList_H(LinkList &L,int n){
L=new LNode;
L-->next=NULL; //先建立一个带头结点的单链表
for(i=n;i>0;--i){
p=new LNode; //生成新结点 p=(LNode*)malloc(sizeof(LNode));
cin>>p-->data; //输入元素值 scanfs(&p-->data);
p-->next=L-->next; //插入到头表
L-->next=p;
}
}//Create List_H
二.尾插法(后插法)
算法步骤:
从一个空表L开始,将新结点逐个插入到链表的尾部,尾指针r指向链表的为节点。
初始时,r同L均指向头节点,每读入一个数据元素则申请一个新结点,将新结点插入到尾部结点后,r指向新结点。
算法描述:
//正位序输入n个元素的值,建立带头节点的单链表L
void CreateList_R(LinkList &L,int n){
L=new LNode;
L-->next=NULL;
r=L; //尾指针r指向头结点
for(i=0;i<n;++i){
p=new LNode;
cin>>p-->data; //生成新结点,输入元素的值
p-->next=NULL;
r-->next=p; //插入到表尾
r=p; //r指向新的尾结点
}
}//LreateList_R
三.循环链表
循环链表:是一种头尾相接的链表(即:表中最后一个结点的指针域指向头结点,整个链表形成一个环状)
优点:
从表中任意结点出发均可找到表中其他结点。
注意:由于循环链表没有NULL指针,故涉及遍历操作时,其终止条件就不再像非循环链表那样判断p或p-->next是否为空,而是判断它们是否等于头指针)
循环链表的写发与单链表类似 只需改变循环条件
单链表循环条件:
p!=NULL;
p-->next!=NULL;
单循环链表 循环条件:
p!=L;
p-->next!=L;
例如:带尾指针循环链表的合并
操作:
- Tb表头连接到Ta表尾
- Tb头节点释放
- 修改指针
LinkList connect(LinkList Ta,LinkList Tb){
//假设Ta,Tb是非空单循环链表
p=Ta-->next;
Ta-->next=Tb-->next-->next;
delete Tb-->next;
Tb-->next=p;
return Tb;
}
下一篇: JAVA 链表表头插入方法 - 掘金
推荐阅读
-
创建链表:表头和表尾插入方法
-
py 单链表头插入和表尾插入方法的实现(附代码测试)
-
创建链表 "表头插入 "和 "表尾插入 "方法详情
-
单链表的表头插入与表尾插入,你真的明白吗?
-
链表学习:链表表头插入法和表尾插入法以及 HashMap 中的链表节点插入法
-
数据结构:图解单个链表的各种操作(插入表头、插入表尾、插入任意位置、删除节点、查询节点、查找链表长度、清空链表)
-
链表基础知识(即单链表、表头插入、表尾插入、表头删除、表尾删除、查找、删除、插入)
-
数据结构:双向链表各种操作的图解(表头插入、表尾插入、任意位置插入、查询节点、删除节点、查找链表长度......)。...)
-
单链表创建--头部插入法创建带头部节点的单链表,超详细--头部插入法和尾部插入法,这里记录头部插入法创建带头部节点的单链表的具体过程: 以 C 语言为例。 1)首先使用 typedef 关键字定义节点数据类型 1 typedef struct LNode{ 2 int var; // 以整数数据为例 3 struct LNode* next; // 需要定义一个 LNode 结构指针,即指向后继节点的节点指针 4 }LNode, *LinkList. 第 4 行中的 LNode 和 *LinkList 是可选的,但如果有了它们,以后再定义节点和指针变量会更方便,而且不必在 LNode 前面添加 struct 关键字,而是可以直接这样定义变量。 LNode l1, l2; // 定义节点变量。 LinkList p1, p2; // 定义指针变量。 与上述 typedef 关键字定义的单一链表数据类型的方法相同: struct LNode{ struct LNode* next; //定义指针变量 struct LNode* next; } } 如果使用这种方法定义链表节点的类型,则在定义节点变量和指针变量时,必须在 LNode 前面加上 struct 关键字,即 struct LNode l1, l2; // 定义节点变量 struct LNode *p1, *p2; //define pointer variables. 这两种方法的效果是一样的,都是定义一个包含整数变量数据字段和后续指针字段的单一链表节点类型。 (2)通过表头插入的函数构建一个链表,并返回 LinkList 类型表头指针变量 L。 算法的基本思想:一个有头节点的单链表有两类节点,头节点和元素节点,头节点通常不存储数据,用 L 表示,元素节点存储数据,用 s 表示。 2.1 定义头节点指针变量 L 和元素节点 s
-
数据结构]:单链表头插入和表尾插入(动画+图表)