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

大家好，欢迎来到IT知识分享网。

链表的定义

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

四、运行结果图