目录
思维导图:
学习内容:
1. 链表的引入
1.1 顺序表的优缺点
1.1.1 优点
能够直接通过下标进行定位元素,访问效率高,对元素进行查找和修改比较快
1.1.2 不足
插入和删除元素需要移动大量的元素,效率较低
1.1.3 缺点
存储数据元素有上限,当达到MAX后,就不能再添加元素了
1.2 链表的概念
1.2.1 链式存储的线性表叫做链表
链式存储:表示数据元素的存储地址不一定连续
线性表:数据元素之间存在一对一的关系
1.2.2 链表的基础概念
1、节点:节点是链表的基本单位,由数据域和指针域组成
2、数据域:存放数据元素的部分
3、指针域:存放下一个节点地址的部分
4、前驱节点:当前节点的上一个节点
5、后继节点:当前节点的下一个节点
6、头节点:虚设的一个节点,数据域不存放数据元素,可以存放链表的长度
7、头指针:指向第一个节点的指针称为头指针
8、第一个节点:实际存储数据元素的链表上的第一个节点
注意:头节点的指针域其实就是头指针,也可以单独定义一个指针,指向第一个节点
1.3 链表的分类
1、单向链表:只能从头节点或第一个节点出发,单向访问其后继节点的链表称为单向链表
2、双向链表:从头部出发,既可以访问前驱节点,也可以访问后继节点
3、循环链表:首尾相接的链表称为循环链表
2. 单向链表
2.1 节点结构体类型
1> 头节点和普通节点数据域可以合到一起,使用一格共用体表示
2> 指针域都是指向普通节点的地址
//定义数据类型
typedef int datatype;
//定义结点类型
typedef struct Node
{
union
{
int len; //头结点数据域
datatype data; //普通结点数据域
};
struct Node *next; //指针域
};
2.2 创建链表
1> 在堆区申请一格头节点的空间,就创建了一个链表
2> 需要对头节点的数据域初始化链表长度,指针域初始化NULL
//创建链表
NodePtr list_create()
{
//只需要在堆区申请一个头结点
NodePtr L = (NodePtr)malloc(sizeof(Node));
if(NULL == L)
{
printf("创建失败\n");
return NULL;
}
//程序执行至此,说明头结点创建结束
L->len = 0; //表示链表长度为0
L->next = NULL; ///防止野指针
printf("链表创建成功\n");
return L;
}
2.3 申请节点封装数据
1> 需要将要封装的数据当做函数的参数进行传递
2> 同样在堆区申请节点,就传入的数据放入数据域
//申请结点封装数据函数
NodePtr apply_node(datatype e)
{
//在堆区申请一个结点的大小
NodePtr p = (NodePtr)malloc(sizeof(Node));
if(NULL == p)
{
printf("结点申请失败\n");
return NULL;
}
//给结点内容赋值
p->data = e; //数据域赋值
p->next = NULL; //指针域
return p;
}
2.4 链表判空
只需要判断头节点的指针域中是否为空即可
//链表判空
int list_empty(NodePtr L)
{
return L->next == NULL;
}
2.5 头插
1> 表示将新插入的节点放入第一个节点中
2> 插入数据时,不能先将前面节点与后面节点先断开。一定要从新节点出发,指向后面的节点,然后将前驱节点指向字节
//头插
int list_insert_head(NodePtr L, datatype e)
{
//判断逻辑
if(NULL==L)
{
printf("链表不合法\n");
return -1;
}
//申请结点封装数据
NodePtr p = apply_node(e);
if(NULL==p)
{
return -1;
}
//头插逻辑
p->next = L->next;
L->next = p;
//表的变化
L->len ++;
printf("头插成功\n");
return 0;
}
2.6 链表遍历
需要使用一个遍历指针,将每一个节点进行遍历一遍,如果该指针指向的节点不为空,就访问其数据域,向后偏移
//链表遍历函数
int list_show(NodePtr L)
{
//判断逻辑
if(NULL==L || list_empty(L))
{
printf("遍历失败\n");
return -1;
}
printf("链表中的元素分别是:");
//遍历逻辑
NodePtr q = L->next; //定义遍历指针从第一个结点出发
while(q != NULL)
{
//输出数据域
printf("%d\t", q->data);
q = q->next; //指针向后偏移一个
}
}
2.7 通过位置查找节点
1> 参数:链表、位置
2> 返回值:对应节点的地址
//通过位置查找结点
NodePtr list_search_pos(NodePtr L, int pos)
{
//判断逻辑
if(NULL==L || list_empty(L) || pos<0 || pos>L->len)
{
printf("查找失败\n");
return NULL;
}
//查找逻辑
//定义遍历指针从头结点出发
NodePtr q = L;
for(int i=0; i<pos; i++)
{
q = q->next;
}
return q; //将找到的结点地址返回
}
2.8 任意位置插入元素
1> 参数:链表、位置、要插入的元素
2> 返回值:int
3> 注意:必须找到要插入位置的节点的前驱节点,将前驱节点当作头节点,进行头插操作
//任意位置插入
int list_insert_pos(NodePtr L, int pos, datatype e)
{
//判断逻辑
if(NULL==L || pos<1 || pos>L->len+1)
{
printf("插入失败\n");
return -1;
}
//申请结点封装数据
NodePtr p = apply_node(e);
if(NULL==p)
{
return -1;
}
//调用函数查找前驱结点
NodePtr q = list_search_pos(L, pos-1);
//插入逻辑
p->next = q->next;
q->next = p;
//表的变化
L->len++;
printf("插入成功\n");
return 0;
}
2.9 头删
1> 参数:链表
2> 返回值:int
3> 注意:需要将要删除的节点先标记一下,头节点的指针,指向第二个节点后,将标记的节点释放
//链表头删
int list_delete_head(NodePtr L)
{
//判断逻辑
if(NULL==L || list_empty(L))
{
printf("删除失败\n");
return -1;
}
//删除三部曲
NodePtr p = L->next; //标记
L->next = p->next; //L->next->next 孤立
free(p); //释放
p = NULL;
//表长变化
L->len--;
printf("头删成功\n");
return 0;
}
2.10 任意位置删除函数
1> 参数:链表、要删除的位置
2> 返回值:int
3> 注意:需要找到要删除的节点的前驱节点,将其当作头节点,进行头删逻辑
//链表任意位置删除
int list_delete_pos(NodePtr L, int pos)
{
//判断逻辑
if(NULL==L || list_empty(L) || pos<1 || pos>L->len)
{
printf("删除失败\n");
return -1;
}
//找到前驱结点
NodePtr q = list_search_pos(L, pos-1);
//删除逻辑
NodePtr p = q->next; //标记
q->next = q->next->next; //p->next 孤立
free(p); //释放
p = NULL;
//表的变化
L->len--;
printf("删除成功\n");
return 0;
}
2.11 按值查找返回位置
1> 参数:链表、要查找的值
2> 返回值:元素在链表中的位置
//链表按值查找返回位置
int list_search_value(NodePtr L, datatype e)
{
//判断逻辑
if(NULL==L || list_empty(L))
{
printf("查找失败\n");
return -1;
}
//查找逻辑
//定义遍历指针从第一个结点出发
NodePtr q = L->next;
for(int index=1; index<=L->len; index++)
{
//判断当前结点的值是否为要找的数据
if(q->data == e)
{
return index;
}
q = q->next; //继续向后遍历
}
//程序执行至此,表示没找到
printf("没找到\n");
return -1;
}
2.12 按位置修改
1> 参数:链表、要修改的元素位置、要被更新的值
2> 返回值:int
3> 注意:先通过位置,找到对应的元素,更改该元素中的内容即可
//链表按位置进行修改
int list_update_pos(NodePtr L, int pos, datatype e)
{
//判断逻辑
if(NULL==L || list_empty(L) || pos<1 || pos>L->len)
{
printf("修改失败\n");
return -1;
}
//按位置查找逻辑
NodePtr p = list_search_pos(L, pos);
//修改逻辑
p->data = e;
printf("修改成功\n");
return 0;
}
2.13 按值进行修改函数
1> 参数:链表、旧值、新值
2> 返回值:int
3> 思路:先通过旧值找到位置,通过位置进行修改
//按值进行修改
int list_update_value(NodePtr L, datatype old_e, datatype new_e)
{
//判断逻辑
if(NULL==L || list_empty(L))
{
printf("修改失败\n");
return -1;
}
//按值查找位置
int res = list_search_value(L, old_e);
if(res == -1)
{
printf("没有要修改的值\n");
return -1;
}
//按位置修改
list_update_pos(L, res, new_e);
printf("修改成功\n");
return 0;
}
2.14 链表的反转
1> 参数:链表
2> 返回值:int
3> 注意:在该操作中,没有节点被删除,也没有节点被释放
//将链表进行翻转
void list_reverse(NodePtr L)
{
//判断逻辑
if(NULL==L || L->len<=1)
{
printf("翻转失败\n");
return ;
}
//翻转逻辑
NodePtr H = L->next; //将链表元素进行托付
L->next = NULL; //自己白手起家
NodePtr p = NULL; //结点的搬运工
while(H != NULL)
{
p = H; //搬运第一个结点
H = H->next; //头指针后移
//将p以头插的方式放入L中
p->next = L->next;
L->next = p;
}
printf("翻转成功\n");
}
2.15 链表的释放
1> 参数:链表
2> 返回值:无
3> 注意:需要先将所有的节点内存全部释放后,再将头节点释放
//释放链表
void list_destroy(NodePtr L)
{
//判断逻辑
if(NULL == L)
{
return;
}
//将所有结点进行释放
while(!list_empty(L))
{
//头删
list_delete_head(L);
}
//释放头结点
free(L);
L = NULL;
printf("释放成功\n");
}
课外作业:
1.链表的排序
解析:
//排序
void list_sort(NodePtr L)
{
if(NULL == L || list_empty(L))
{
printf("排序失败\n");
return ;
}for (int i = 0; i < L->len; i++)
{
NodePtr q=L->next;
NodePtr q1 = q->next;
while(q1 != NULL){
if(q->data > q1->data)
{
datatype temp = q->data;
q->data = q1->data;
q1->data =temp;
}
q=q->next; //指针向后偏移一个
q1= q1->next;
}
}
printf("排序成功\n");
list_print(L);
}
2.链表的反转(递归实现)
解析:
3. 链表去重
解析:
void list_rep(NodePtr L)
{
if(NULL == L || L->len<=1)
{
printf("去重失败\n");
return ;
}
NodePtr q = L;
while(q->next != NULL){
if(q->data == q->next->data)
{
NodePtr temp = q->next;
q->next = temp->next;
free(temp);
}else{
q=q->next;
}
}
printf("去重成功\n");
list_print(L);
}