西安o2o网站设计公司,美团企业邮箱认证怎么弄,wordpress html5 视频播放,app教程上一篇【数据结构】顺序表-CSDN博客 我们了解了顺序表#xff0c;但是呢顺序表涉及到了一些问题#xff0c;比如#xff0c;中间/头部的插入/删除#xff0c;时间复杂度为O(N);增容申请空间、拷贝、释放旧空间会有不小的消耗#xff1b;增容所浪费的空间... 我们如何去解…上一篇【数据结构】顺序表-CSDN博客 我们了解了顺序表但是呢顺序表涉及到了一些问题比如中间/头部的插入/删除时间复杂度为O(N);增容申请空间、拷贝、释放旧空间会有不小的消耗增容所浪费的空间... 我们如何去解决这些问题本篇介绍另一个数据结构——链表
1. 链表的概念及结构
链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针连接次序实现的链表也是线性表的一种 链表大概是什么样的呢看下图 链表是由一个一个的节点组成再顺序表中数据是连续存放的我们想找到下一个数据顺着前一个数据找就行了而链表中数据存放空间是不连续的所以我们就需要一个指针来保存下一个节点的地址所以我们如果要定义链表只需要定义链表的节点结构就行了
(在【C语言】结构体详解-CSDN博客 的1.3 结构体的自引用 中介绍过)
struct SListNode
{int data;//数据struct SListNode* next;//下一个数据的地址
}; 和上一篇一样创建一个头文件两个源文件 也是一样在头文件SList.h中定义单链表的结构并对类型和结构体改名
#include stdio.h
#include stdlib.h
#include assert.h
typedef int Type;
//定义节点结构
typedef struct SListNode
{Type data;struct SListNode* next;
}SLNode;
我们先创建几个节点在test.c中实现
#include SList.h //包含头文件
void SListtest1()
{SLNode* node1 (SLNode*)malloc(sizeof(SLNode));//创建节点1node1-data 1;//赋值SLNode* node2 (SLNode*)malloc(sizeof(SLNode));//创建节点2node2-data 2;//赋值SLNode* node3 (SLNode*)malloc(sizeof(SLNode));//创建节点3node3-data 3;//赋值SLNode* node4 (SLNode*)malloc(sizeof(SLNode));//创建节点4node4-data 4;//赋值
}
int main()
{SListtest1();return 0;
}
虽然我们创建好了节点但是这几个节点现在还不能互相找到所以我们接下来要将这几个节点连接起来怎么连接存下一个节点的地址
void SListtest1()
{SLNode* node1 (SLNode*)malloc(sizeof(SLNode));//创建节点1node1-data 1;//赋值SLNode* node2 (SLNode*)malloc(sizeof(SLNode));//创建节点2node2-data 2;//赋值SLNode* node3 (SLNode*)malloc(sizeof(SLNode));//创建节点3node3-data 3;//赋值SLNode* node4 (SLNode*)malloc(sizeof(SLNode));//创建节点4node4-data 4;//赋值//将四个节点连接起来node1-next node2;node2-next node3;node3-next node4;node4-next NULL;
}
现在就构成了一个链表有了这个简单的链表我们来写一个函数打印一下里面的数据
链表的打印
在SList.h中进行函数的声明
void SLPrint(SLNode* ps);//打印
参数是链表的节点的地址
在SList.c中进行函数的实现
#include SList.h
void SLPrint(SLNode* ps) //打印
{SLNode* pcur ps;//pcur指向当前链表的第一个节点
}
要打印当然就要循环遍历写一个while循环判断条件为pcur不为NULL进入循环
void SLPrint(SLNode* ps) //打印
{SLNode* pcur ps;//pcur指向当前链表的第一个节点while (pcur) //判断第一个节点是否为NULL{//....}
} 进入循环后打印内容
void SLPrint(SLNode* ps) //打印
{SLNode* pcur ps;//pcur指向当前链表的第一个节点while (pcur){printf(%d-, pcur-data);//打印内容}
}
打印完一个数据后要把下一个节点值部分的地址给pcur 也就是pcur要存node2中2的地址此时pcur不再指向node1指向了node2
void SLPrint(SLNode* ps) //打印
{SLNode* pcur ps;//pcur指向当前链表的第一个节点while (pcur){printf(%d-, pcur-data);//打印内容pcur pcur-next;//指向下一个节点}printf(NULL\n);
} 在test.c中测试
测试时我们不直接传链表的第一个节点node1而是再定义一个结构体指针plist去指向node1让plist作为参数传过去 SLNode* plist node1;SLPrint(plist);虽然有点多此一举但这样会让我们的代码更完善
运行结果 2.链表的插入
实际使用链表的时候我们不会像上面那样一个一个创建初始时候是一个空链表会跟顺序表类似进行空间开辟然后插入数据
2.1空间申请创建节点
插入数据前依旧是要判断空间够不够
在SList.h中进行函数的声明
SLNode* SLBuyNode(Type x);//申请空间创建节点
返回值是节点的地址参数就是要插入的数据 在SList.c中进行函数的实现
SLNode* SLBuyNode(Type x)//申请空间创建节点
{SLNode* newnode (SLNode*)malloc(sizeof(SLNode));if (newnode NULL) //空间申请失败{perror(malloc);return 1;}newnode-data x;newnode-next NULL;return newnode;
} 2.2 尾插
在SList.h中进行函数的声明
void SLPushBack(SLNode** ps, Type x);//尾插
参数是链表的节点地址是一个二级指针和要插入的数据
我们要给函数传地址这样形参的改变才能影响实参对参数的理解如下这很重要这里提前展示将要在test.c中测试用的部分代码 在SList.c中进行函数的实现 尾插要先找到尾节点再将尾节点和新节点连接起来 此时node4的地址部分就不再是NULL 而是新节点的地址 代码如何实现呢 先找尾节点
void SLPushBack(SLNode* ps, Type x)//尾插
{SLNode* ptail ps;//定义尾节点开始时指向头节点while (ptail-next ! NULL)//遍历链表数据找尾节点{ptail ptail-next;}//跳出循环后ptail指向尾节点
}
然后我们直接调用创建节点的函数放在找尾节点前面最后赋值
void SLPushBack(SLNode* ps, Type x)//尾插
{SLNode* newnode SLBuyNode(x);//申请空间创建节点SLNode* ptail ps;//定义尾节点开始时指向头节点while (ptail-next ! NULL)//遍历链表数据找尾节点{ptail ptail-next;}//跳出循环后ptail指向尾节点ptail-next newnode;//直接赋值
} 但是呢链表在没有赋值的时候是空链表所以我们要讨论空链表的情况如果是空链表直接让ps指向新节点newnode所以最终的代码如下
void SLPushBack(SLNode** pps, Type x)//尾插
{assert(pps);//pps不可以为NULLSLNode* newnode SLBuyNode(x);//申请空间创建节点if (*pps NULL) //*pps可以为NULL表示空链表{*pps newnode;}else //非空链表{SLNode* ptail *pps;//定义尾节点开始时指向头节点while (ptail-next)//遍历链表数据找尾节点{ptail ptail-next;}//跳出循环后ptail指向尾节点ptail-next newnode;//直接赋值}
} 我们再来看test.c中测试的代码
void SListtest2()
{SLNode* plist NULL;//空链表SLPushBack(plist, 1);//尾插SLPushBack(plist, 2);SLPushBack(plist, 3);SLPushBack(plist, 4);SLPrint(plist);//打印
}
int main()
{//SListtest1();SListtest2();return 0;
}
多插入几个数据运行看结果插入成功 2.3 头插 在SList.h中进行函数的声明
void SLPushHead(SLNode** pps, Type x);//头插
同样的参数也是一个二级指针还有要插入的数据 在SList.c中进行函数的实现 我们需要做两件事一个是将newnode和原本的首节点连接在一起另一件事是*pps要指向新的首节点 链表不为NULL时代码如下
void SLPushHead(SLNode** pps, Type x)//头插
{assert(pps);//pps不能为NULLSLNode* newnode SLBuyNode(x);//申请空间创建节点newnode-next *pps;*pps newnode;
}
当链表为NULL时分析一下 当前代码也可以实现 在test.c中测试
void SListtest2()
{SLNode* plist NULL;//空链表SLPushBack(plist, 1);//尾插SLPushBack(plist, 2);SLPushBack(plist, 3);SLPushBack(plist, 4);SLPrint(plist);//打印SLPushHead(plist, 6);//头插SLPushHead(plist, 7);SLPushHead(plist, 8);SLPrint(plist);//打印
}
看一下运行结果 3.链表的删除
删除数据链表就不能为空不然删啥呢? 3.1 尾删
在SList.h中进行函数的声明
void SLPopBack(SLNode** pps);//尾删 在SList.c中进行函数的实现 很显然首先就是找尾节点找到尾节点之后直接释放吗node4释放后node3-next里面依然存放着node4的地址但此时指向的空间已经没了此时的指针就成了一个野指针 所以我们还要将被释放节点的前一个节点的指针置空
所以我们还要找尾节点的前一个节点
void SLPopBack(SLNode** pps)//尾删
{assert(pps *pps);//pps和链表都不能为空SLNode* prev *pps;//定义尾节点前一个节点SLNode* ptail *pps;//定义尾节点while (ptail-next){prev ptail;ptail ptail-next;}//此时找到了尾节点和尾节点前一个节点free(ptail);//释放尾节点ptail NULL;//置空prev-next NULL;//置空尾节点前一个节点
}
如果这个链表只有一个节点呢这个代码可行吗来分析一下 我们把节点释放并置空后prev-next就不存在了函数最后一句代码就不能实现所以当链表里只有一个节点时直接释放就行了
void SLPopBack(SLNode** pps)//尾删
{assert(pps *pps);//pps和链表都不能为空if ((*pps)-next NULL)//链表只有一个节点{free(*pps);//释放节点*pps NULL;//置空}else //链表不止一个节点{SLNode* prev *pps;//定义尾节点前一个节点SLNode* ptail *pps;//定义尾节点while (ptail-next){prev ptail;ptail ptail-next;}//此时找到了尾节点和尾节点前一个节点free(ptail);//释放尾节点ptail NULL;//置空prev-next NULL;//置空尾节点前一个节点}
} 在test.c中测试
void SListtest2()
{SLNode* plist NULL;//空链表SLPushBack(plist, 1);//尾插SLPushBack(plist, 2);SLPrint(plist);//打印SLPushHead(plist, 6);//头插SLPushHead(plist, 7);SLPrint(plist);//打印SLPopBack(plist);//尾删SLPrint(plist);//打印
}
看下结果尾删成功 3.2 头删
在SList.h中进行函数的声明
void SLPopHead(SLNode** pps);//头删 在SList.c中进行函数的实现 我们要删除头节点跟删除尾节点不一样如果我们把首节点释放掉还能找到首节点里的next吗不能不能的话就找不到第二个节点以及剩下的节点
我们应该先把下一个节点的信息存储起来 SLNode* Next (*pps)-next;//存节点 然后把原头节点释放 free(*pps);最后让*pps指向新的头节点 *pps Next;所以代码如下
void SLPopHead(SLNode** pps)//头删
{assert(pps *pps);//pps和链表都不能为空SLNode* Next (*pps)-next;//存节点free(*pps);*pps Next;
}
当链表只有一个节点时分析一下上面的代码也是可以完成的 我们在test.c中测试一下
void SListtest2()
{SLNode* plist NULL;//空链表SLPushBack(plist, 1);//尾插SLPushBack(plist, 2);SLPrint(plist);//打印SLPushHead(plist, 6);//头插SLPushHead(plist, 7);SLPrint(plist);//打印SLPopBack(plist);//尾删SLPrint(plist);//打印SLPopHead(plist);//头删SLPrint(plist);//打印
} 下篇我们再继续介绍更多内容拜拜~
