甘肃省和住房建设厅网站,广宁网站建设公司,wordpress无法修改主题,有关网站建设的公众号单链表
概念
概念#xff1a;链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构#xff0c;数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
结点
与顺序表不同的是#xff0c;链表的结构类似于带车头的火车车厢#xff0c;#xff0c;链表的每个车厢都是独立…单链表
概念
概念链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
结点
与顺序表不同的是链表的结构类似于带车头的火车车厢链表的每个车厢都是独立申请下来的空间每个车厢被叫做结点。
结点由当前结点要保存的数据和保存下一个节点的地址指针变量。
图中指针变量 plist保存的是第⼀个结点的地址我们称plist此时“指向”第⼀个结点如果我们希望plist“指向”第⼆个结点时只需要修改plist保存的内容为0x0012FFc8
链表中每个结点都是独⽴申请的即需要插⼊数据时才去申请⼀块结点的空间我们需要通过指针 变量来保存下⼀个结点位置才能从当前结点找到下⼀个结点 链表的性质
链表在逻辑上是连续的在物理结构上不一定连续
结点一般是从堆上申请的
从堆上申请来的空间是按照⼀定策略分配出来的每次申请的空间可能连续可能不连续
定义链表的结构实际上就是定义链表中结点结构
每个结点对应的结构体代码:
typedef int SLTDataType;//因为我们在事先并不确定数据的类型所以需要定义一下
typedef truct SListNode
{SLTDataType data;//结点要保存的数据struct SListNode* next;//指向下一个结点的指针定义的数据类型是结点类型
}SLTNode;//定义全局变量当我们想要保存一个数据时实际上是向操作系统申请一块内存这块内存不仅要保存数据也要保存指向下一个结点的地址当下一个结点为NULL时地址为NULL
当我们想要从第一个节点走向最后一个结点时只需要在当前结点拿上下⼀个结点的地址就可以了。
链表的打印
void SLTPrint(SLTNode* phead)
{SLTNode* pcur phead;//pcur存储的是当前的结点while (pcur)//等价于pcur ! NULL{printf(%d- ,pcur-data);pcur pcur-next;}//走到这里说明pcur NULL那么直接打印printf(NULL\n);
}单链表的实现
创建三个文件分别是SList.h和SList.c和test.c
SList.h用来包含所需头文件声明函数
SList.c用来定义函数实现方法
test.c用来测试我们想要实现的功能
这里使用的是VS2022 win11环境
手动构造链表
SList.h
#pragma once
#includestdio.h
#includestdlib.htypedef int SLTDataType;//定义数据类型
typedef struct SListNode
{SLTDataType data;//定义下一个结点的地址类型是struct SListNodestruct SListNode* next;
}SLTNode;//定义全局变量//打印链表
void SListPrint(SLTNode* phead);SList.c
#define _CRT_SECURE_NO_WARNINGS
#includeSList.h//打印链表
void SListPrint(SLTNode* phead)
{//创建pcur存储phead的地址直接用phead也可以//这里是因为再次使用第一个结点时还可以找到不会影响后续的使用SLTNode* pcur phead;//判断当前结点是否为NULL等价于pcur ! NULLwhile (pcur){//结点不为NULL打印当前节点数据printf(%d - ,pcur-data);//将下一个结点的地址赋值给pcurpcur pcur-next;}//走到这里说明pcur NULL,直接打印NULLprintf(NULL\n);
}test.c
#define _CRT_SECURE_NO_WARNINGS
#includeSList.h//手动构造链表
void test1()
{//为结点申请内存,大小为结构体大小//node1来接收,类型为SLTNode*,其他同理SLTNode* node1 (SLTNode*)malloc(sizeof(SLTNode));SLTNode* node2 (SLTNode*)malloc(sizeof(SLTNode));SLTNode* node3 (SLTNode*)malloc(sizeof(SLTNode));SLTNode* node4 (SLTNode*)malloc(sizeof(SLTNode));//在结点中放入要存储的数据node1-data 1;node2-data 2;node3-data 3;node4-data 4;//在结点中放入指向下一个结点的地址如果是尾结点则为NULLnode1-next node2;node2-next node3;node3-next node4;node4-next NULL;//打印链表看看效果//将首结点的地址给plist传给实现打印的函数SLTNode* plist node1;SListPrint(plist);
}int main()
{test1();return 0;
}单链表实现
尾插
//向操作系统申请一个新结点
SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));if (newnode NULL){perror(malloc);exit(1);}//成功newnode-data x;newnode-next NULL;return newnode;
}//尾插
//其实在链表为NULL的情况下不需要再改变头结点的内容所以也可以使用SLTNode* pphead
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{//向操作系统申请一个新结点SLTNode* newnode SLTBuyNode(x);//链表为空phead直接指向newNodeif (*pphead NULL){*pphead newnode;}//链表不为空找尾节点将尾节点和新节点连接起来else{SLTNode* ptail *pphead;while (ptail-next ! NULL){ptail ptail-next;}//此时有:ptail-next NULLptail-next newnode;}
}尾删 普遍情况是有多个结点思路是
1找到尾结点
2将尾结点的前驱结点置为空再将尾结点释放并置空 特殊情况是只有一个结点思路是
将唯一一个结点也就是头结点释放并置空
//尾删
void SLTPopBack(SLTNode** phead)
{//二级指针不为空链表不为空assert(phead *phead);//在只有一个结点的情况下prev NULL所以在下面对空指针的操作就是不合法的//所以此时要分离出来特殊处理之后我们再测试assert断言就发挥了作用//注意*的优先级是低于-的所以需要加上括号if ((*phead)-next NULL){free(*phead);*phead NULL;}//此时是结点个数大于一的情况else {SLTNode* prev NULL;SLTNode* ptail *phead;while (ptail-next){prev ptail;ptail ptail-next;}prev-next NULL;free(ptail);ptail NULL;}
}头插
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode SLTBuyNode(x);newnode-next *pphead;*pphead newnode;
}头删
头删时只需要将头结点的next结点保存起来然后将原来的头结点释放最后将next结点变成新的头结点即可。
//头删
void SLTPopFront(SLTNode** phead)
{assert(phead *phead);//经过分析在只有一个结点和多个结点的情况时都是符合预期的所以不必分离讨论SLTNode* next (*phead)-next;free(*phead);*phead next;}查找
如果只是在链表中查找数据那么就不会修改只需传一级指针和要查找的数据
而返回值则是所查找到的结点
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{//创建pcur来遍历链表SLTNode* pcur phead;//当结点不为空进入循环while (pcur){if (pcur-data x){return pcur;}pcur pcur-next;}//没有找到return NULL;
}指定位置pos之前插入
既然是插入数据那么就要对链表进行修改需要传址调用要传二级指针结点pos和数据x
//指定位置pos之前插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead pos);//如果pos的位置就是头结点那么就相当于头插if (pos *pphead){//头插SLTPushFront(pphead, x);}else{//创建新结点SLTNode* newnode SLTBuyNode(x);//创建prev记录pos的前驱结点SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}//此时找到了posnewnode-next pos;prev-next newnode;}
}指定位置之后pos插入
//指定位置之后pos插入
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{//在pos之后插入就不需要知道头结点SLTNode* newnode SLTBuyNode(x);newnode-next pos-next;pos-next newnode;
}指定位置删除
//指定位置删除
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead pos);if (pos *pphead){//头删SLTPopFront(pphead);}else {SLTNode* del *pphead;while (del-next ! pos){del del-next;}del-next pos-next;free(pos);pos NULL;}
}指定位置之后删除
//指定位置之后删除
void SLTEraseAfter(SLTNode* pos)
{assert(pos);SLTNode* del pos-next;pos-next del-next;
}销毁链表
//销毁链表
void SListDestroy(SLTNode** pphead)
{assert(pphead);SLTNode* pcur *pphead;while (pcur){SLTNode* next pcur-next;free(pcur);pcur next;}*pphead NULL;
}链表的分类
