头插法和尾插法
- 一、头插法
- 💤思考一：头插法的核心是什么❓
- ❗❗ 重点一：以带头结点方式实现头插法
- ❗❗ 重点二：以不带头结点方式实现头插法
- 二、尾插法
- 💤思考二：尾插法的核心是什么❓
- ❗❗ 重点三：以带头结点方式实现尾插法
- ❗❗ 重点四：以不带头结点方式实现尾插法
- 三、完整代码
- 四、运行结果图
链表的定义
typedef int ElemType;
typedef struct LNode{
ElemType data; //数据域
struct LNode *next; //指针域
}LNode,*LinkList;
一、头插法
-
什么是头插法❓
在插入时，新的结点插入到当前链表的表头。 -
怎么实现头插法❓
💤思考一：头插法的核心是什么❓
以有头结点为例：
只需要将新的节点插在头结点和首元结点之间。所以核心代码为:s->next=L->next; ① L->next=s; ②
注意：①②能否交换顺序❓
假设可以，那么代码为：② L->next=s; ① s->next=L->next;
先②后①图：
千万不能交换呦❗❗ 重点一：以带头结点方式实现头插法
- 动图：
- 图解
- 代码
LinkList HeadInster(LinkList &L,int n){ LNode *s; int x=1; L= (LinkList)malloc(sizeof(LNode)); //创建头结点 L->next=NULL; //初始为空链表 while(x!=n){ s=(LNode*) malloc(sizeof(LNode)); //创建新结点 s->data=x; s->next=L->next; //核心代码 L->next=s; //核心代码 x++; } return L; }
❗❗ 重点二：以不带头结点方式实现头插法
- 动图解析
- 图解
- 代码
LinkList Headinster(LinkList &L,int n){ LNode *s; int x=1; L= (LinkList)malloc(sizeof(LNode)); L->data=x++; L->next=NULL; while(x!=n){ s=(LNode*) malloc(sizeof(LNode)); s->data=x; s->next=L; L=s; x++; } return L; }
- 动图：
二、尾插法
-
什么是尾插法❓
在插入时，新的结点插入到当前链表的表尾，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。 -
怎么实现头插法❓
💤思考二：尾插法的核心是什么❓
以有头结点为例：
由图可知，r->next=s; //①r的指针域指向S（让新结点插入到链表） r=s; //②r指针指向s（保持r指针一直在链表尾端，方便插入新的结点）
那上面两句可以交换吗❓我们来试一试
还是不能交换呦❗❗ 重点三：以带头结点方式实现尾插法
- 动图解析
- 图解
- 代码
LinkList TailInster(LinkList &L,int n){ int x=1; L= (LinkList)malloc(sizeof(LNode)); LNode *s,*r=L; while(x!=n){ s=(LNode*) malloc(sizeof(LNode)); s->data=x; r->next=s; r=s; x++; } r->next=NULL; return L; }
❗❗ 重点四：以不带头结点方式实现尾插法
- 动图解析
（略，参考上） - 图解
- 代码
LinkList Tailinster(LinkList &L,int n){ int x=1; L= (LinkList)malloc(sizeof(LNode)); L->data=x++; LNode *s,*r=L; while(x!=n){ s=(LNode*) malloc(sizeof(LNode)); s->data=x; r->next=s; r=s; x++; } r->next=NULL; return L; }
- 动图解析
三、完整代码
#include "stdio.h"
#include "stdlib.h"
typedef int ElemType;
typedef struct LNode{
ElemType data; //数据域
struct LNode *next; //指针域
}LNode,*LinkList;
/*
* 头插法 有头结点
*/
LinkList HeadInster(LinkList &L,int n){
LNode *s;
int x=1;
L= (LinkList)malloc(sizeof(LNode)); //创建头结点
L->next=NULL; //初始为空链表
while(x!=n){
s=(LNode*) malloc(sizeof(LNode)); //创建新结点
s->data=x;
s->next=L->next;
L->next=s;
x++;
}
return L;
}
/*
* 头插法 无头结点
*/
LinkList Headinster(LinkList &L,int n){
LNode *s;
int x=1;
L= (LinkList)malloc(sizeof(LNode));
L->data=x++;
L->next=NULL;
while(x!=n){
s=(LNode*) malloc(sizeof(LNode));
s->data=x;
s->next=L;
L=s;
x++;
}
return L;
}
/*
* 尾插法、有结点
*/
LinkList TailInster(LinkList &L,int n){
int x=1;
L= (LinkList)malloc(sizeof(LNode));
LNode *s,*r=L;
while(x!=n){
s=(LNode*) malloc(sizeof(LNode));
s->data=x;
r->next=s;
r=s;
x++;
}
r->next=NULL;
return L;
}
/*
* 尾插法、无结点
*/
LinkList Tailinster(LinkList &L,int n){
int x=1;
L= (LinkList)malloc(sizeof(LNode));
L->data=x++;
LNode *s,*r=L;
while(x!=n){
s=(LNode*) malloc(sizeof(LNode));
s->data=x;
r->next=s;
r=s;
x++;
}
r->next=NULL;
return L;
}
/*
* 便利链表、头结点
*/
void PrintList(LinkList L){
LNode *s;
s=L->next;
while (s!=NULL) {
printf("%d\t",s->data);
s=s->next;
}
}
/*
* 便利链表
*/
void Print(LinkList L){
LNode *s;
s=L;
while (s!=NULL) {
printf("%d\t",s->data);
s=s->next;
}
}
int main(){
LinkList L,S,P,Q;
printf("有头结点的头插法：");
HeadInster(L,10);
PrintList(L);
printf("\n无头结点的头插法：");
Headinster(P,10);
Print(P);
printf("\n有头结点的尾插法：");
TailInster(S,10);
PrintList(S);
printf("\n无头结点的尾插法：");
Tailinster(Q,10);
Print(Q);
}
四、运行结果图
