头插法和尾插法
链表的定义
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);
}
四、运行结果图
今天的文章单链表头插法和尾插法代码_利用尾插法建立单链表[通俗易懂]分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/75537.html