【数据结构】：单链表之头插法和尾插法（动图+图解）

2024-02-28 1134阅读

温馨提示：这篇文章已超过454天没有更新，请注意相关的内容是否还可用！

头插法和尾插法

  • 一、头插法
      • 💤思考一：头插法的核心是什么❓
      • ❗❗ 重点一：以带头结点方式实现头插法
      • ❗❗ 重点二：以不带头结点方式实现头插法
      • 二、尾插法
          • 💤思考二：尾插法的核心是什么❓
          • ❗❗ 重点三：以带头结点方式实现尾插法
          • ❗❗ 重点四：以不带头结点方式实现尾插法
          • 三、完整代码
          • 四、运行结果图

            【数据结构】：单链表之头插法和尾插法（动图+图解）

            链表的定义

            typedef int ElemType;
typedef struct LNode{
   ElemType data;           //数据域
   struct LNode *next;      //指针域
}LNode,*LinkList;

            一、头插法

            1. 什么是头插法❓

              在插入时，新的结点插入到当前链表的表头。

            2. 怎么实现头插法❓

              💤思考一：头插法的核心是什么❓

              以有头结点为例：【数据结构】：单链表之头插法和尾插法（动图+图解）

              只需要将新的节点插在头结点和首元结点之间。所以核心代码为:

              s->next=L->next;		①
L->next=s;				②

              注意：①②能否交换顺序❓

              假设可以，那么代码为：② L->next=s; ① s->next=L->next;

              先②后①图：

              【数据结构】：单链表之头插法和尾插法（动图+图解）

              千万不能交换呦

              ❗❗ 重点一：以带头结点方式实现头插法

              1. 动图：

                【数据结构】：单链表之头插法和尾插法（动图+图解）

              2. 图解

                【数据结构】：单链表之头插法和尾插法（动图+图解）

              3. 代码
                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;
}

              ❗❗ 重点二：以不带头结点方式实现头插法

              1. 动图解析

                【数据结构】：单链表之头插法和尾插法（动图+图解）

              2. 图解

                【数据结构】：单链表之头插法和尾插法（动图+图解）

              3. 代码
                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;
}

            【数据结构】：单链表之头插法和尾插法（动图+图解）

            二、尾插法

            1. 什么是尾插法❓

              在插入时，新的结点插入到当前链表的表尾，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。

            2. 怎么实现头插法❓

              💤思考二：尾插法的核心是什么❓

              以有头结点为例：

              【数据结构】：单链表之头插法和尾插法（动图+图解）

              由图可知，

              r->next=s;			//①r的指针域指向S（让新结点插入到链表）
r=s;				//②r指针指向s（保持r指针一直在链表尾端，方便插入新的结点）

              那上面两句可以交换吗❓我们来试一试

              【数据结构】：单链表之头插法和尾插法（动图+图解）

              还是不能交换呦

              ❗❗ 重点三：以带头结点方式实现尾插法

              1. 动图解析

                【数据结构】：单链表之头插法和尾插法（动图+图解）

              2. 图解

                【数据结构】：单链表之头插法和尾插法（动图+图解）

              3. 代码
                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;
}

              ❗❗ 重点四：以不带头结点方式实现尾插法

              1. 动图解析

                （略，参考上）

              2. 图解

                【数据结构】：单链表之头插法和尾插法（动图+图解）

              3. 代码
                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);
}

            四、运行结果图

            【数据结构】：单链表之头插法和尾插法（动图+图解）

VPS购买请点击我

免责声明：我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理! 部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理! 图片声明：本站部分配图来自人工智能系统AI生成,觅知网授权图片,PxHere摄影无版权图库和百度，360，搜狗等多加搜索引擎自动关键词搜索配图，如有侵权的图片，请第一时间联系我们，邮箱：ciyunidc@ciyunshuju.com。本站只作为美观性配图使用,无任何非法侵犯第三方意图,一切解释权归图片著作权方,本站不承担任何责任。如有恶意碰瓷者,必当奉陪到底严惩不贷!

相关阅读

目录[+]