当前位置：网站首页>链表基本操作（详解）
链表基本操作（详解）
2022-08-09 11:08:00 【追梦杰尼龟】
链表的基本操作
一：单链表的基础操作
为什么需要链表？
我们在使用数组存放数据是非常方便，但是由于数组的长度是
固定的，所以当存储不同的元素数量时，就很容易出现问题。如果向数组中添加的数量大于数组大小时候，信息无法完全被保存。所以我们需要另一种存储方式来存储数据，其中存储的元素的个数不受限制。这种存储方式就是链表。
链表结构示意
链表的基础知识：
每一个结点包含数据域和指针域：
数据域：存放用户需要的数据信息
指针域：指向下一个结点的地址
头指针：head就是头指针变量，我们把指向第一个结点的指针成为头指针
（无论链表是不是空，头指针是必不可少的）
头结点：第一个结点前可以虚加一个头结点，头指针指向头结点，头结点的指针域（head->next）指向第一个实际有效的结点（即首元结点），头结点的数据域可以不使用，在单链表中可以不添加头结点
首元结点：第一个实际有效的结点
链表是环环相扣的，head头指针指向头结点，头结点指向首元结点，首元结点指向第二个结点…直到最后的结点。
二：单链表的建立
单链表的建立即从无到有创建一个链表，
一个一个的分配结点的储存空间，然后输出每一个结点的数据域，然后建立结点之间的关系。
单链表的建立可以分为两种方法，（1）头插法，（2）尾插法(更易理解)
头插法
即在单链表的头部插入新的结点的方法成为头插法。数据读入顺序和链表的结点顺序正好相反。
图解：
结点的结构体类型定义如下：
struct Student
{
char name[100]; //学生姓名
int number; //学号
struct Student *next; //指向下一个结点的指针
};
头插法创建链表的函数代码如下：
struct Student* Create()
{
struct Student *Head;
Head = (struct Student *)malloc(sizeof(struct Student)); //头指针
Head->next = NULL; //头指针指向空
struct Student *s;
int num;
char a[20];
while(1) //当 学号>0时
{
printf("please input the name:\n");
scanf("%s",&a);
printf("please input the number:\n");
scanf("%d",&num);
if(num <= 0)
{
break;
}
s = (struct Stduent *)malloc(sizeof(struct Student));
s->number = num;
strcpy(s->name,a);
//用头插法创建链表
s->next = Head->next; //新结点指向原来的首元结点
Head->next = s; //链表的头结点指向新结点
}
return Head;
}
运行结果：倒序输出
步骤：
1.对头指针进行初始化，
对其开辟动态空间，并且将头结点的指针域置空(顺序不要弄反)
2.定义指针变量s,用来指向新创建的结点
3.循环，在循环中开辟s（新结点）的动态空间，并赋予新结点数据域的信息
4.头插法关键的两行代码，新结点指向原来的首结点，链表的头结点指向新结点，结合上面的图解去了解（不可写反，写反之后，链表的头结点无法与新结点相连，无法创建链表，输出时只会循环输出该结点的信息）
尾插法
图解：
代码实现：
struct Student *Creat() //初始化链表
{
struct Student *Head;
Head = (struct Student *)malloc(sizeof(struct Student));
Head->next = NULL;
struct Student *r,*s; //定义指针变量r,s,r指向当前单链表的表尾结点
//s用来指向新创建的结点
r = Head; //r指向头结点
int num;
char a[20];
while(1)
{
printf("please input the name:\n");
scanf("%s",&a);
printf("please input the number:\n");
scanf("%d",&num);
if(num <= 0)
{
break;
}
s = (struct Student *)malloc(sizeof(struct Student));
strcpy(s->name ,a);
s->number = num;
//尾插法创立链表
r->next = s; //原来的结点指向新结点
r = s; //r指向新的结点
}
s->next = NULL; //链表的尾结点指针为空
return Head;
}
正序输出
运行结果：
相较于头插法创立链表，尾插法更易于结合图解理解
步骤注意点：
1.在空链表时候，
r指针指向头结点
2.尾插法的关键两行代码也不可以互相调换顺序，调换顺序的结果并不会循环输出，而是无法读取存储的信息，即输入了5个姓名，输出0个信息
3.注意的是，在循环结束时，新结点的指针域一定要指向空
三：单链表的遍历
代码实现：
void print(struct Student *Head) //输出链表
{
struct Student *Temp = Head->next ; //临时指针指向首元结点
printf("****学生信息如下*****\n");
while(Temp!=NULL)
{
printf("姓名: %s\n",Temp->name );
printf("学号: %d\n",Temp->number );
printf("\n");
Temp = Temp->next ; //移动临时指针到下一个结点
}
}
步骤注意点：
1.定义临时指针变量Temp指向首元结点
2.循环输出
3.关键：每输出一个结点的内容，就移动Temp指针到下一个结点的地址，如果是最后一个结点，指针指向NULL，循环结束
四：单链表结点数目判断
代码实现:
int length(struct Student *Head) //链表长度计数
{
struct Student *p = Head->next ; //p指针指向首元结点
int iCount = 0; //计数器
while(p!=NULL)
{
iCount++;
p = p->next ; //移动p指针到下一个结点的地址
}
return iCount;
}
运行结果：
步骤注意点:
定义iCount计数器，每移动一次p指针且p指向不为空，iCount++;
五：单链表的插入
链表的插入，有三种方式，可以从链表的头部插入，可以从链表的尾部插入，也可以在指定位置进行插入。
链表头插入
图解：
代码实现：
void insert(struct Student *Head) //在链表头部插入
{
struct Student *s;
s = (struct Student *)malloc(sizeof(struct Student)); //定义s指向新分配的空间
printf("please input the insert name:\n");
scanf("%s",&s->name );
printf("please input the insert number:\n");
scanf("%d",&s->number );
//
s->next = Head->next ; //新结点的指针指向首元结点
Head->next = s; //头结点的指针指向新结点
}
步骤注意点：
1.首先为插入的新结点分配内存
2.首先将新结点的指针指向链表的首元结点(s->next = Head->next)
3.将头结点的指针指向新结点(Head->next = s)
任意结点插入
图解：
代码实现：
void insert(struct Student *Head,int i) //在第i个位置上插入新结点
{
struct Student *p = Head;
struct Student *s;
int j = 0;
while(j<i-1 && p != NULL) //找到第i-1个地址
{
p = p->next ;
j++;
}
if(p != NULL)
{
s = (struct Student *)malloc(sizeof(struct Student)); //定义s指向新分配的空间
printf("please input the insert name:\n");
scanf("%s",&s->name );
printf("please input the insert number:\n");
scanf("%d",&s->number );
//
s->next = p->next ; //新结点指向原来第i个结点
p->next = s; //新结点成为新链表第i个结点
}
}
步骤注意点:
1.首先找到链表第i-1个结点的地址p，如果存在，则在i-1后面插入第i个结点
2.为插入的新结点分配空间
3.注意插入的两行代码联系图解理解
链表尾部插入
图解：
代码实现：
void insert(struct Student *Head) //在链表尾部插入
{
struct Student *p,*s; //s是需要插入的结点
p = Head;
while(p && p->next ) //找到最后一个结点p
{
p = p->next ;
}
s = (struct Student *)malloc(sizeof(struct Student));
printf("please input the insert name:\n");
scanf("%s",&s->name );
printf("please input the insert number:\n");
scanf("%d",&s->number );
//
p->next = s; //尾结点指针指向新结点
s->next = NULL; //新结点指针指向空
}
（尾部插入较好理解）
步骤注意点：
1.首先找到尾结点，即循环中的条件，每一次p指针移动到下一个结点的地址
2.插入时为新插入的结点分配空间
3.尾部插入的两行代码联系图解理解，新结点指针指向空
六：单链表的删除
图解：
代码实现：
void Delete(struct Student *Head,int pos) //删除函数
{
int j = 1; //定义循环变量去寻找p结点
struct Student *p,*q; //q是要删除的结点
p = Head;
while(j < pos && p) //p是q的前一个结点
{
j++;
p = p->next ;
}
if(p== NULL || p->next == NULL) //如果没有，就报错
{
printf("ERROR!\n");
}
else
{
q = p->next ; //q指针指向需要删除的结点
p->next = q->next ; //跨过删除的结点连接q的前一个结点和后一个结点
free(q); //删除q结点
}
}
运行结果:
步骤注意点：
1.pos表示的是需要删除结点的位置，定义j用来控制循环次数
2.定义指针q和p，利用循环找到要删除结点之前的结点p，然后让q指向准备删除的结点即(q = p->next)
3.连接删除结点两边的结点(p->next = q->next)
4.用free(q)释放q指向的内存空间达到删除的目的
七 ：单链表的查询
代码实现：
相当于遍历查找
struct Student *search(struct Student *Head,char name[]) //查询函数
{
struct Student *p = Head->next ; //p指针指向首元结点
while(p!=NULL)
{
if(strcmp(p->name ,name) != 0) //利用字符串函数查询
{
p = p->next ; //如果没有，移动p指针到下一个结点地址
}
else
{
break; //查到了跳出循环
}
}
if(p == NULL)
{
printf("没有查到该学生的信息\n");
}
return p; //返回指针p的地址
}
步骤注意点：
1.定义指针变量p，使其从首元结点开始到链表结束
2.利用字符串函数strcmp来查询
增删改查完整代码如下：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct Student
{
int number;
char name[20];
struct Student *next;
};
struct Student *Creat() //初始化链表
{
struct Student *Head;
Head = (struct Student *)malloc(sizeof(struct Student));
Head->next = NULL;
struct Student *r,*s;
r = Head;
int num;
char a[20];
while(1)
{
printf("please input the name:\n");
scanf("%s",&a);
printf("please input the number:\n");
scanf("%d",&num);
if(num <= 0)
{
break;
}
s = (struct Student *)malloc(sizeof(struct Student));
strcpy(s->name ,a);
s->number = num;
//尾插法创立链表
r->next = s; //原来的结点指向新结点
r = s; //r指向新的结点
}
s->next = NULL; //链表的尾结点指针为空
return Head;
}
int length(struct Student *Head) //链表长度计数
{
struct Student *p = Head->next ; //p指针指向首元结点
int iCount = 0; //计数器
while(p!=NULL)
{
iCount++;
p = p->next ; //移动p指针到下一个结点的地址
}
return iCount;
}
//void insert(struct Student *Head) //在链表头部插入
//{
// struct Student *s;
// s = (struct Student *)malloc(sizeof(struct Student)); //定义s指向新分配的空间
// printf("please input the insert name:\n");
// scanf("%s",&s->name );
// printf("please input the insert number:\n");
// scanf("%d",&s->number );
// //
// s->next = Head->next ; //新结点的指针指向首元结点
// Head->next = s; //头结点的指针指向新结点
//}
void insert(struct Student *Head) //在链表尾部插入
{
struct Student *p,*s; //s是需要插入的结点
p = Head;
while(p && p->next ) //找到最后一个结点p
{
p = p->next ;
}
s = (struct Student *)malloc(sizeof(struct Student));
printf("please input the insert name:\n");
scanf("%s",&s->name );
printf("please input the insert number:\n");
scanf("%d",&s->number );
//
p->next = s; //尾结点指针指向新结点
s->next = NULL; //新结点指针指向空
}
//void insert(struct Student *Head,int i) //在第i个位置上插入新结点
//{
// struct Student *p = Head;
// struct Student *s;
// int j = 0;
// while(j<i-1 && p != NULL) //找到第i-1个地址
// {
// p = p->next ;
// j++;
// }
// if(p != NULL)
// {
// s = (struct Student *)malloc(sizeof(struct Student)); //定义s指向新分配的空间
// printf("please input the insert name:\n");
// scanf("%s",&s->name );
// printf("please input the insert number:\n");
// scanf("%d",&s->number );
// //
// s->next = p->next ; //新结点指向原来第i个结点
// p->next = s; //新结点成为新链表第i个结点
// }
//}
void Delete(struct Student *Head,int pos) //删除函数
{
int j = 1; //定义循环变量去寻找p结点
struct Student *p,*q; //q是要删除的结点
p = Head;
while(j < pos && p) //p是q的前一个结点
{
j++;
p = p->next ;
}
if(p== NULL || p->next == NULL) //如果没有，就报错
{
printf("ERROR!\n");
}
else
{
q = p->next ; //q指针指向需要删除的结点
p->next = q->next ; //跨过删除的结点连接q的前一个结点和后一个结点
free(q); //删除q结点
}
}
void print(struct Student *Head) //输出链表
{
struct Student *Temp = Head->next ; //临时指针指向首元结点
printf("****学生信息如下*****\n");
while(Temp!=NULL)
{
printf("姓名: %s\n",Temp->name );
printf("学号: %d\n",Temp->number );
printf("\n");
Temp = Temp->next ; //移动临时指针到下一个节点
}
}
struct Student *search(struct Student *Head,char name[]) //查询函数
{
struct Student *p = Head->next ;
while(p!=NULL)
{
if(strcmp(p->name ,name) != 0)
{
p = p->next ;
}
else
{
break;
}
}
if(p == NULL)
{
printf("没有查到该学生的信息\n");
}
return p;
}
int main()
{
int n;
struct Student *Head; //创建头指针
Head = Creat(); //返回头指针
print(Head); //输出链表函数
printf("一共有%d个学生信息\n",length(Head));
insert(Head); //插入链表
print(Head);
printf("please input the delete the number:\n");
scanf("%d",&n);
Delete(Head,n); //删除结点函数
print(Head);
char name[20];
printf("please input the search name:\n");
scanf("%s",&name);
struct Student *p = search(Head,name); //查询函数
printf("***查询信息如下:****\n");
printf("姓名:%s\n",p->name );
printf("学号:%d\n",p->number );
}
边栏推荐
猜你喜欢
程序员的专属浪漫——用3D Engine 5分钟实现烟花绽放效果
PoseNet: A Convolutional Network for Real-Time 6-DOF Camera Relocalization Paper Reading
golang 标准库json Marshal、Unmarshal坑
x86异常处理与中断机制（2）中断向量表
End-to-End Object Detection with Fully Convolutional Network学习笔记
MDK添加注释模板
双向链表的各种操作
Cesium加载三维模型数据
x86异常处理与中断机制（3）中断处理过程
ICML 2022 | Out-of-Distribution Detection with Deep Nearest Neighbors
随机推荐
信息系统项目的十大管理
PTA 换硬币
centos7.5 设置Mysql开机自启动
从位图到布隆过滤器
1006 Sign In and Sign Out (25分)
kubernetes中不可见的OOM
依赖注入(Dependency Injection)框架是如何实现的
Cluster understanding
uni-app 自带的picker封装一个日期-时间选择器
electron 应用开发优秀实践
x86异常处理与中断机制（2）中断向量表
Qt获取EXE可执行文件的上一级目录下的文件
【VIBE: Video Inference for Human Body Pose and Shape Estimation】论文阅读
golang 标准库json Marshal、Unmarshal坑
FreeRTOS列表和列表项源码分析
TensorFlow: NameError: name 'input_data' is not defined
备战金三银四：如何成功拿到阿里offer（经历+面试题+如何准备）
彻底理解工厂模式
b站up主：空狐公子 --矩阵求导（分母布局）课程笔记
无刷无霍尔BLCD电机控制