一.笔记
一.链表的引入
1.1 总结顺序表的优缺点
1> 优点：能够直接通过下标进行定位元素，访问效率高，对元素进行查找和修改比较快
2> 不足：插入和删除元素需要移动大量的元素，效率较低
3> 缺点：存储数据元素有上限，当达到MAX后，就不能再添加元素了
1.2 链表的概念
1> 链式存储的线性表叫做链表
1、链式存储：表示数据元素的存储地址不一定连续
2、线性表：数据元素之间存在一对一的关系
2>链表的原理图如下：
3>链表的基础概念
1、节点：节点是链表的基本单位，由数据域和指针域组成
2、数据域：存放数据元素的部分
3、指针域：存放下一个节点地址的部分
4、前驱节点：当前节点的上一个节点
5、后继节点：当前节点的下一个节点
6、头节点：虚设的一个节点，数据域不存放数据元素，可以存放链表的长度
7、头指针：指向第一个节点的指针称为头指针
8、第一个节点：实际存储数据元素的链表上的第一个节点
注意：头节点的指针域其实就是头指针，也可以单独定义一个指针，指向第一个节点
4> 链表的分类
1、单向链表：只能从头节点或第一个节点出发，单向访问其后继节点的链表称为单向链表
2、双向链表：从头部出发，既可以访问前驱节点，也可以访问后继节点
3、循环链表：首尾相接的链表称为循环链表
二.单向链表
只能从头节点或第一个节点出发，单向访问其后继节点的链表称为单向链表
2.1 节点结构体类型
1> 头节点和普通节点数据域可以合到一起，使用一格共用体表示
2> 指针域都是指向普通节点的地址
2.2 创建链表
1> 在堆区申请一格头节点的空间，就创建了一个链表
2> 需要对头节点的数据域初始化链表长度，指针域初始化NULL
2.3 申请节点封装数据
1> 需要将要封装的数据当做函数的参数进行传递
2> 同样在堆区申请节点，就传入的数据放入数据域
2.4 链表判空
1> 只需要判断头节点的指针域中是否为空即可
2.5 头插
1> 表示将新插入的节点放入第一个节点中
2> 插入数据时，不能先将前面节点与后面节点先断开。一定要从新节点出发，指向后面的节点，然后将前驱节点指向字节
2.6 链表遍历
需要使用一个遍历指针，将每一个节点进行遍历一遍，如果该指针指向的节点不为空，就访问其数据域，向后偏移
2.7 通过位置查找节点
1> 参数：链表、位置
2> 返回值：对应节点的地址
2.8 任意位置插入元素
1> 参数：链表、位置、要插入的元素
2> 返回值：int
3> 注意：必须找到要插入位置的节点的前驱节点，将前驱节点当作头节点，进行头插操作
2.9 链表头删
1> 参数：链表
2> 返回值：int
3> 注意：需要将要删除的节点先标记一下，头节点的指针，指向第二个节点后，将标记的节点释放
2.10 任意位置删除函数
1> 参数：链表、要删除的位置
2> 返回值:int
3> 注意：需要找到要删除的节点的前驱节点，将其当作头节点，进行头删逻辑
2.11 按值查找返回位置
1> 参数：链表、要查找的值
2> 返回值：元素在链表中的位置
2.12 按位置修改
1> 参数：链表、要修改的元素位置、要被更新的值
2> 返回值：int
3> 注意：先通过位置，找到对应的元素，更改该元素中的内容即可
2.13 按值进行修改函数
1> 参数：链表、旧值、新值
2> 返回值：int
3> 思路：先通过旧值找到位置，通过位置进行修改
2.14 链表的反转
1> 参数：链表
2> 返回值：int
3> 注意：在该操作中，没有节点被删除，也没有节点被释放
2.15 链表的释放
1> 参数：链表
2> 返回值：无
3> 注意：需要先将所有的节点内存全部释放后，再将头节点释放
#include "lianbiao.h"
//创建链表
Nodeptr list_create()
{
//只需要在堆区申请一个头节点
Nodeptr L=(Nodeptr)malloc(sizeof(Node));
if(L==NULL)
{
printf("创建失败\n");
return NULL;
}
//程序创建至此，说明头节点创建结束
L->len=0;//表示链表长度为0
L->next=NULL;//防止野指针
printf("链表创建成功\n");
return L;
}
//申请节点封装数据函数
Nodeptr apply_node(datatype e)
{
//在堆区申请一个节点的大小
Nodeptr P=(Nodeptr)malloc(sizeof(Node));
if(P==NULL)
{
printf("节点申请失败\n");
return NULL;
}
//给节点内容赋值
P->data=e;//数据域赋值
P->next=NULL;//指针域
return P;
}
//链表判空
int list_empty(Nodeptr L)
{
return L->next==NULL;
}
//头插
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;
}
//调用输出函数
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;//指针向后偏移
}
printf("\n");
}
//通过位置查找节点
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;//将找到的节点返回
}
//任意位置插入
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;
}
//链表头删
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;
}
//链表任意位置删除函数
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=p->next;//q->next->next 孤立
free(p);//释放
p=NULL;
//表的变化
L->len--;
printf("删除成功\n");
return 0;
}
//按值查找返回位置
int list_search_value(Nodeptr L,datatype e)
{
//判断逻辑
if(NULL==L||list_empty(L))
{
printf("查找失败\n");
return -1;
}
//查找逻辑
//定义遍历指针从第一个节点出发
Nodeptr q=L->next;
for(int i=1;i<=L->len;i++)
{
//判断当前节点的值是否为要找的值
if(q->data==e)
{
return i;
}
q=q->next;//继续向后遍历
}
//程序执行至此，表示没找到
printf("没找到\n");
return -1;
}
//按位置修改节点
int list_updata_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;
}
//按值进行修改
int list_updata_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_updata_pos(L,res,new_e);
printf("修改成功\n");
return 0;
}
//链表的翻转
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");
}
//链表的释放
void list_destroy(Nodeptr L)
{
if(NULL==L)
{
return;
}
//将所有节点进行释放
while (!list_empty(L))
{
//h头删
list_delete_head(L);
}
//释放头结点
free(L);
L=NULL;
printf("释放成功\n");
}