单链表头插法和尾插法代码_利用尾插法建立单链表[通俗易懂]

单链表头插法和尾插法代码_利用尾插法建立单链表[通俗易懂]单链表,头插法和尾插法,有头结点,无头结点,详细解析,图解_头插法和尾插法图解

请添加图片描述
链表的定义

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);

}

四、运行结果图

在这里插入图片描述

今天的文章单链表头插法和尾插法代码_利用尾插法建立单链表[通俗易懂]分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/75537.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注