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

2023-07-12

data next 结点

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

头插法和尾插法

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

链表的定义

typedef int ElemType;
typedef struct LNode{
   ElemType data;           //数据域
   struct LNode *next;      //指针域
}LNode,*LinkList;
1
2
3
4
5

一、头插法

什么是头插法❓
在插入时，新的结点插入到当前链表的表头。

怎么实现头插法❓

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

以有头结点为例：
只需要将新的节点插在头结点和首元结点之间。所以核心代码为:
s->next=L->next;①
L->next=s;②
1
2
注意：①②能否交换顺序❓
假设可以，那么代码为：② 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

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

动图解析
图解

代码

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15

二、尾插法

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

怎么实现头插法❓

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

以有头结点为例：

由图可知，
r->next=s;//①r的指针域指向S（让新结点插入到链表）
r=s;//②r指针指向s（保持r指针一直在链表尾端，方便插入新的结点）
1
2
那上面两句可以交换吗❓我们来试一试

还是不能交换呦

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

动图解析
图解

代码

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
4
5
6
7
8
9
10
11
12
13
14

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

动图解析
（略，参考上）
图解

代码

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

三、完整代码

#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);
    Print(S);

    printf("\n无头结点的尾插法：");
    Tailinster(Q,10);
    Print(Q);

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126