欢迎小伙伴的点评✨✨ 本篇章系列是对C语言的深度思考和总结、关于C语言内容会持续更新
文章目录
- 前言
- 一、什么是链表
- 二、建立简单静态链表
- 二、建立简单动态链表
- 三、链表的增加、删除、更改、查询
- 四、总结
前言
本章会给大家带来基于C语言链表的实例。
一、什么是链表
链表是一种常见的重要的数据结构。链表是动态地进行存储分配的一种结构，它会根据所需要开辟内存单元。
链表有一个”头指针“变量，它存放一个地址，该地址指向一个元素，链表中每一个元素称为“结点”，每个结点都应该包括两个部分：
1、用户需要用的实际数据；
2、下一个结点的地址。可以看出，“头指针” 指向地一个元素，第1个元素又指向第2个元素 … 直到最后一个元素，该元素不再指向其他元素，它称为"表尾“，它的地址部分放一个”NULL“ （表示”空地址“），链表到此结束。
这样的一种链表数据结构，其元素在内存中的地址可以是不连续的。要想找到某一元素，必须先找该元素的上一个元素，根据它提供的下一元素地址才能找到下一个元素。如果不提供 ”头指针“，则整个链表都无法访问。链表如同一条铁链一样，一环扣一环，中间是不能断开的。显然，链表这种数据结构，必须利用指针变量才能实现，即一个结点中应包含一个指针变量，用它存放下一结点的地址。
二、建立简单静态链表
例如，可以设计这样一个结构体类型：
struct data
{
int num;
struct data *next; //next 是指针变量，指向结构体变量
};
- 1
- 2
- 3
- 4
- 5
注意：上面只是定义一个struct data 类型，并未实际分配存储空间，只有定义了变量才分配存储单元。
其中，成员num用来存放结点中的数据（用户需要用到的数据），next 是指针类型的成员，它指向struct data 类型数据（就是next 所在的结构体类型）。一个指针类型的成员既可以指向其他类型的结构体数据，也可以指向自己所在的结构体类型数据。现在，next 是struct data 类型中的一个成员，它又指向struct data 类型的数据。用这种方法就可以建立链表。
单结点代码实例如下：
#include <stdio.h>
#pragma pack(1) //字节对齐
struct data
{
int num;
struct data* next; //next 是指针变量，指向结构体变量
};
int main()
{
struct data a, b, c, * head, * p; //定义3个结构体变量a,b,c作为链表的结点；
a.num = 0; //对结点a的num成员赋值；
b.num = 1; //对结点b的num成员赋值；
c.num = 2; //对结点c的num成员赋值；
head = &a; //将结点a的起始地址赋值给头指针head；
a.next = &b; //将结点b的起始地址赋给a结点的next成员；
b.next = &c; //将结点c的起始地址赋给b结点的next成员；
c.next = NULL; //c结点的next成员不存放其他结点地址；
p = head; //使p指向a结点；
while (p != NULL) //输出完c结点后的值为NULL,循环终止；
{
printf("%d\n", p->num); //输出p指向的结点的数据；
p = p->next; //使p指向下一结点；
}
return 0;
}
- 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
编译运行结果如下：
多结点代码实例如下：
#include <stdio.h>
#pragma pack(1) //字节对齐
struct data
{
int num;
struct data* next_1; //next_1 是指针变量，指向结构体变量
struct data* next_2; //next_2 是指针变量，指向结构体变量
};
int main()
{
struct data a, b, c,d,e,f, * head_1,*head_2, * p; //定义3个结构体变量a,b,c作为链表的结点；
a.num = 0; //对结点a的num成员赋值；
b.num = 1; //对结点b的num成员赋值；
c.num = 2; //对结点c的num成员赋值；
d.num = 3; //对结点a的num成员赋值；
e.num = 4; //对结点b的num成员赋值；
f.num = 5; //对结点c的num成员赋值；
head_1 = &a; //将结点a的起始地址赋值给头指针head_1；
a.next_1 = &b; //将结点b的起始地址赋给a结点的next_1成员；
b.next_1 = &c; //将结点c的起始地址赋给b结点的next_1成员；
c.next_1 = NULL; //c结点的next_1成员不存放其他结点地址；
head_2 = &d; //将结点d的起始地址赋值给头指针head_2；
d.next_2 = &e; //将结点e的起始地址赋给d结点的next_2成员；
e.next_2 = &f; //将结点f的起始地址赋给e结点的next_2成员；
f.next_2 = NULL; //f结点的next_2成员不存放其他结点地址
p = head_1; //使p指向a结点；
while (p != NULL) //输出完c结点后的值为NULL,循环终止；
{
printf("%d\n", p->num); //输出p指向的结点的数据；
p = p->next_1; //使p指向下一结点；
}
p = head_2; //使p指向a结点；
while (p != NULL) //输出完c结点后的值为NULL,循环终止；
{
printf("%d\n", p->num); //输出p指向的结点的数据；
p = p->next_2; //使p指向下一结点；
}
return 0;
}
- 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
编译运行结果如下：
二、建立简单动态链表
所谓建立动态链表是指在程序执行过程中从无到有地建立起一个链表，即一个一个地开辟结点和输入各结点数据，并建立起前后相链的关系。使用动态内存分配的形式，对所需的数据分配空间。
代码实例如下：
#include <stdio.h>
#include <stdlib.h>
#pragma pack(1)
struct data
{
int num;
struct data* next; //next是指针变量，指向结构体变量
};
int main()
{
struct data * head ,* p1,*p2; //定义3个结构体指针变量head,p1,p2用来指向struct data类型数据的；
head = p1 = p2 = (struct data*)malloc(sizeof(struct data)); //开辟内存动态存储区，把起始地址赋值给 head;
for (int i = 0; i < 3; i++)
{
p1 -> num = i; //给指针p1指向的结构体成员 num 赋值；
p2 -> next = p1; //把指针p1的地址赋值给 指针p2指向的结构体成员指针next；
p2 = p1; //把指针p1的地址赋值给 p2
/*注意此时指针p1的地址分别赋值给了指针p2和结构体成员指针next*/
p1 = (struct data*)malloc(sizeof(struct data)); //重新给p1开辟新空间；
} //此时进入下一个循环，指针p1、指针p2、当前结构体指针next，向后移动一个sizeof（struct data）单元；
//由于未释放内存动态存储区，故结构体与结构体之间使用指针 next 连接了起来。
//在这个过程中，指针p1 和 指针 p2 的作用就是交换地址，使结构体成员 next 连接到下一个结构体；
p2->next = NULL; //当循环结束时，给指针p2指向的结构体成员指针next赋值为0（NULL）；
while (head != NULL)
{
printf("%d\n", head->num); //输出p指向的结点的数据；
head = head->next; //使p指向下一结点；
}
return 0;
}
- 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
编译后如下所示：
三、链表的增加、删除、更改、查询
1、链表查询：循环遍历所需要的结点信息，或者根据已知第几个结点进行搜索、查询结构体数据即可
2、链表插入：循环遍历所需要的结点信息，或者根据已知第几个结点，当找到所需要的结点时，插入结构体即可
3、链表删除：循环遍历所需要的结点信息，或者根据已知第几个结点，当找到所需要的结点时，删除结构体即可
4、链表更改：循环遍历所需要的结点信息，或者根据已知第几个结点，当找到所需要的结点时，更改结构体数据即可
代码实例如下：
#include <stdio.h>
#include <stdlib.h>
int init(); //初始化结点函数；
int head_add(int da); //在头的前面增加结点函数；
int body_add(int num, int da); //在中间增加结点函数；
int tail_add(int da); //在尾的后面增加结点函数；
int head_dele(); //在头的前面删除结点函数；
int body_dele(int num); //在中间删除结点函数；
int tail_dele(); //在尾的后面删除结点函数；
int head_change(int da); //更改头结点函数；
int body_change(int num, int da); //更改中间结点函数；
int tail_change(int da); //更改尾结点函数；
void examine(int num);//查结点
void Inquire();//遍历输出
#pragma pack(1)
struct data
{
int num;
struct data* next; //next是指针变量，指向结构体变量
};
struct data* head, *tail,* p1 ,* p2,*ptemp,*pt2; //定义3个结构体指针变量head,p1,p2用来指向struct data类型数据的；
int main()
{
if (init() == 0)
{
printf("*******************初始化成功！**********************\n");
}
head_add(12); //增加头
body_add(2,88);//增加中
tail_add(13);//增加尾
head_dele(); //删除头
body_dele(1);//删除中
tail_dele();//删除尾
head_change(9);//更改头
body_change(1,8);//更改中
tail_change(7); //更改尾
examine(1); //查询
return 0;
}
/*************************初始化*****************************/
int init()
{
head = p1 = p2 = (struct data*)malloc(sizeof(struct data)); //开辟内存动态存储区，把起始地址赋值给 head;
for (int i = 0; i < 3; i++)
{
p1->num = i; //给指针p1指向的结构体成员 num 赋值；
p2->next = p1; //把指针p1的地址赋值给 指针p2指向的结构体成员指针next；
p2 = p1; //把指针p1的地址赋值给 p2
/*注意此时指针p1的地址分别赋值给了指针p2和结构体成员指针next*/
p1 = (struct data*)malloc(sizeof(struct data)); //重新给p1开辟新空间；
} //此时进入下一个循环，指针p1、指针p2、当前结构体指针next，向后移动一个sizeof（struct data）单元；
//由于未释放内存动态存储区，故结构体与结构体之间使用指针 next 连接了起来。
//在这个过程中，指针p1 和 指针 p2 的作用就是交换地址，使结构体成员 next 连接到下一个结构体；
p2->next = NULL; //当循环结束时，给指针p2指向的结构体成员指针next赋值为0（NULL）；
tail = p2; //保存到尾结点，用于尾结点的增加和删除；
Inquire();//遍历输出
return 0;
}
int head_add(int da) //在头的前面增加
{
p1 = (struct data*)malloc(sizeof(struct data)); //重新给p1开辟新空间；
p1->num = da; //给新的结点设置数据；
p1->next = head; //结构体指针p1的成员指针next指向头指针head；
head = p1; //将结构体指针p1内存地址赋值给头指针head；
printf("********************head_add执行成功！*************************\n");
Inquire();//遍历输出
return 0;
}
/*******************
int body_add(int num, int da)
num:表示第几个结点，不能为0，因为0结点是头；
da:表示增加的数据；
*******************/
int body_add(int num,int da ) //在中间增加结点函数；
{
struct data* p=head;
for (int i = 0; i < num; i++) //获取在几个结点的后面增加结点数据
{
p=p->next;
}
p1 = (struct data*)malloc(sizeof(struct data)); //重新给p1开辟新空间；
p1->num = da; //给新的结点设置数据；
p1->next = p->next; //把当前结点指向下一个结点的指针，赋值给结构体指针p1指向的下一个结点的指针；
p->next = p1; //然后把结构体p1指针内存地址赋值给当前结点结构体指针指向的下一个结点的指针；
printf("********************body_add执行成功！*************************\n");
Inquire();//遍历输出
return 0;
}
int tail_add(int da) //在尾的后面增加结点函数；
{
p1 = (struct data*)malloc(sizeof(struct data)); //重新给p1开辟新空间；
p1->num = da; //给指针p1指向的结构体成员 num 赋值；
p1->next = NULL; //把指针p1的地址赋值给 指针p2指向的结构体成员指针next；
tail->next = p1; //把结构体指针p1赋值给尾结构体指针指向的下一个结点；
tail = p1;//然后在把p1赋值给尾部指针；
printf("********************tail_add执行成功*************************\n");
Inquire();//遍历输出
return 0;
}
void Inquire() //遍历输出
{
struct data* p = head;
printf("当前链表中的数据是：");
while (p != NULL) //知道结点指向的指针为NULL
{
printf("%d,", p->num); //输出p指向的结点的数据；
p = p->next; //使p指向下一结点；
}
printf("\n");
}
int head_dele() //在头的前面删除结点函数；
{
p1 = head; //把头指针内存地址赋值给p1指针
head=head->next; //把头指针指向的下一个结点赋值给head指针
free(p1); //释放p1指针分配的内存空间；
p1 = NULL;
printf("********************head_dele执行成功！*************************\n");
Inquire();//遍历输出
return 0;
}
int body_dele(int num) //在中间删除结点函数；
{
struct data* p = head;
for (int i = 0; i < num; i++) //获取在几个结点的后面增加结点数据
{
p = p->next;
}
p1 = p->next; //把当前结点的下一个结点内存地址赋值给指着p1
p->next=p->next->next; //把当前结点的下下结点内存地址赋值给下结点内存地址
free(p1); //释放p1指针分配的内存空间；
printf("********************body_dele执行成功！*************************\n");
Inquire();//遍历输出
return 0;
}
int tail_dele() //在尾的后面删除结点函数；
{
struct data* p = head,*pt=head;
pt = pt->next;
pt = pt->next;
while (pt != NULL) //知道结点指向的指针为NULL
{
p = p->next; //使p指向下一结点；
pt = pt->next; //使pt指向下一结点；
} //当pt指向NULL时p指向的下一个结点为尾结点前面的一个结点
p1 = p->next;
tail = p;
free(p1);//释放p1指针分配的内存空间；
p->next = NULL;
printf("********************tail_dele执行成功！*************************\n");
Inquire();//遍历输出
return 0;
}
int head_change(int da) //更改头结点函数；
{
head->num =da; //更改头结点的数据
printf("********************head_change执行成功！*************************\n");
Inquire();//遍历输出
return 0;
}
int body_change(int num, int da) //更改中间结点函数；
{
struct data* p = head;
for (int i = 0; i < num; i++) //获取在几个结点的后面增加结点数据
{
p = p->next;
}
p->num = da; //更改当前结点的数据
printf("********************body_change执行成功！*************************\n");
Inquire();//遍历输出
return 0;
}
int tail_change(int da) //更改尾结点函数；
{
tail->num = da; //更改尾结点的数据；
printf("********************tail_change执行成功！*************************\n");
Inquire();//遍历输出
return 0;
}
void examine(int num) //查结点
{
struct data* p = head;
for (int i = 0; i < num; i++) //获取在几个结点的后面增加结点数据
{
p = p->next;
}
printf("************************查询成功！*********************\n");
printf("当前结点的数据是：%d\n",p->num);
}
- 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
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
- 155
- 156
- 157
- 158
- 159
- 160
- 161
- 162
- 163
- 164
- 165
- 166
- 167
- 168
- 169
- 170
- 171
- 172
- 173
- 174
- 175
- 176
- 177
- 178
- 179
- 180
- 181
- 182
- 183
- 184
- 185
- 186
- 187
- 188
- 189
- 190
- 191
- 192
- 193
- 194
- 195
- 196
- 197
- 198
- 199
- 200
- 201
- 202
- 203
- 204
编译运行如下所示：
四、总结
在对数据存储中链表有着广泛的应用。
文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览42750 人正在系统学习中