数据结构与算法链表头插法,尾插法,循环链表
目录
数据结构与算法——链表(头插法，尾插法，循环链表）
🍓个人主页：
🍒系列专栏：
目录
一.头插法
建立单链表;头插法——元素插入在链表头部，也叫前插法。
算法步骤：
- 从一个空表开始，重复读入数据元素。
- 生成新结点，将读入数据存放到新结点的数据域中。
- 从最后一个结点开始，依次将各结点插入到链表的前端。
例如：建立链表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;
}