摘要:虽然有这么多的链表的结构,但是我们实际中最常用还是这两种结构单向无头不循环链表,双向带头循环链表,下面我们来学习这两种链表。
在学了顺序表之后,我们发现顺序表有一定的缺陷。第一个缺陷,从头部和中间的插入删除,都要移动后面的数据,时间复杂度为O(N)。第二个缺陷,增容需要申请新空间,拷贝数据,释放旧空间,会有不小的消耗。第三个缺陷,增容一般是呈2倍的增长,这会造成一定的空间浪费。比如说当前顺序表数据有1024个,容量也恰好是1024,这时我们只想插入一个数据,但是扩容却要扩大到2048个,这样有1023个空间大小就浪费了。刚刚提到的这些问题,链表就能很好地解决。下面我们就来一起学习一下链表,看看链表是怎么去解决这些问题的,链表又存在什么缺陷?
malloc
向内存申请的,用的时候再申请。从下图我们可以看出,链表的每个节点都有一个next
指针指向下一个节点的地址,从逻辑上每个节点都是链接起来的。从内存的地址上看,每一个节点地址之间的距离大小都是不一样的,所以物理结构上他们不在的空间是不连续的。单向和双向
带头和不带头
循环和不循环
实际中链表的结构非常多样,以上情况组合起来就有8种链表结构。虽然有这么多的链表的结构,但是我们实际中最常用还是这两种结构:单向无头不循环链表,双向带头循环链表,下面我们来学习这两种链表。
data
和一个next
,data
是用来存放数据的,next
是一个指向下一个节点地址的指针,最后一个节点的next
指向NULL
。在实现链表上,一个创建了三个文件,分别是SList.h
,SList.c
,main.c
,下面内容我们先定义链表的结构体和实现各个函数接口的代码,最后再把三个文件的代码展示出来。// 重定义数据类型名typedef int SLTDataType;// 定义链表结构体typedef struct SListNode{ // 定义一个指向下一个节点地址的指针 struct SListNode* next; // 定义一个存放数据的变量 SLTDataType data;}SListNode;
int
型,后面要存储char
型的或者其他类型的数据,需要把代码里面的int
都改一遍,非常麻烦。如果我们重新定义了类型名,并且在代码里用重新定义好的名字,下次需要存储其他类型的数据,直接在重定义那里把int
改成想存储的类型就好了。// 申请一个节点SListNode* BuySListNode(SLTDataType x){ // 向内存申请一个节点 SListNode* newnode = (SListNode*)malloc(sizeof(SListNode)); // 判断申请是否成功 assert(newnode); // 对节点初始化以及赋值 newnode->next = NULL; newnode->data = x; return newnode;}
// 头插/*********************** 为什么会用到二级指针 ** 后面3.7会讲到 ***********************/void SListPushFront(SListNode** pplist, SLTDataType x){ // 防止传进来的pplist是空指针 assert(pplist); // 申请一个新节点 SListNode* newnode = BuySListNode(x); // 判断链表是否为空 if (*pplist == NULL) { *pplist = newnode; } else { 方法一 申请一个指针指向当前的头节点 //SListNode* next = *pplist; //*pplist = newnode; //newnode->next = next; // 方法二 newnode->next = *pplist; *pplist = newnode; }}// 方法一和方法二的补充// 从上面我们可以看到方法一多定义了一个指针,指向当前头节点的地址//这样做的好处是,在接下来的两条代码的顺序你可以随意变换// 你可以这样写*pplist = newnode;newnode->next = next;// 也可以这样写newnode->next = next;*pplist = newnode;// 如果你像方法二那样没有定义指针的话,你的代码只能写成上面这个顺序// 要是你顺序写反的话,*pplist会直接放弃原来的头节点去指向newnode,而当newnode的next想去指向原来的头节点时,已经找不到地址了。// 所以正确的顺序是上面那样,先让newnode的next先指向原来的头节点,后面*pplist才去指向newnode。// 总结,方法一多定义一个变量更加省心,方法二相对来说要思考得细一点,也便于我们更好地去理解链表结构。
assert
是一个断言函数,程序运行的时候,当括号里面的结果为假时,就会停止运行并且报错。报错显示的信息包括断言的内容和断言的位置,还有一个错误框,如下图所示。断言能够快速地帮我们定位程序的错误,在实际开发中可以减少很多不必要的麻烦,所以建议大家在写代码的时候也尽量在需要的时候加上断言。
温馨提示在使用assert
函数时,记得包含一下assert.h
这个头文件。
// 尾插void SListPushBack(SListNode** pplist, SLTDataType x){ assert(pplist); // 申请一个新节点 SListNode* newnode = BuySListNode(x); // 分两种情况,链表为空和非空 if (*pplist == NULL) { *pplist = newnode; } else { // 定义一个指针,去遍历寻找尾节点 SListNode* tail = *pplist; while (tail->next) { tail = tail->next; } // 插入节点 tail->next = newnode; }}
// 在pos之后插入一个节点void SListInsertAfter(SListNode* pos, SLTDataType x){ assert(pos); // 申请一个新节点 SListNode* newnode = BuySListNode(x); 这里也是有两个方法,跟之前头插的差不多 方法一 定义一个指针指向pos的next //SListNode* posNext = pos->next; //newnode->next = posNext; //pos->next = newnode; // 方法二 newnode->next = pos->next; pos->next = newnode;}
// 在pos之前插入一个节点void SListInsertBefore(SListNode** pplist, SListNode* pos, SLTDataType x){ assert(pplist); assert(pos); // 申请一个新节点 SListNode* newnode = BuySListNode(x); // 判断pos是否为第一个节点 if (*pplist == pos) { newnode->next = pos; *pplist = newnode; } else { // 先找到pos之前的一个节点 SListNode* prev = *pplist; while (prev->next != pos) { prev = prev->next; } // 插入新节点 newnode->next = pos; prev->next = newnode; }}
// 头删void SListPopFront(SListNode** pplist){ // 防止pplist指针为空 assert(pplist); // 防止pplist指向的地址为空,即链表为空 assert(*pplist); // 定义一个指针指向第一个节点的地址,后面释放空间需要用到 SListNode* temp = *pplist; // 让*pplist直接指向它的下一个节点 *pplist = (*pplist)->next; // 释放被删节点空间,并把temp指针置空 free(temp); temp = NULL;}
// 尾删void SListPopBack(SListNode** pplist){ assert(pplist); assert(*pplist); // 分两种情况,链表只有一个节点,和有一个以上节点 if ((*pplist)->next == NULL) { free(*pplist); *pplist = NULL; } else { // 找到尾节点之前的一个节点 SListNode* tail = *pplist; while (tail->next->next) { tail = tail->next; } SListNode* temp = tail->next; tail->next = NULL; free(temp); temp = NULL; }}
// 删去pos节点void SListErase(SListNode** pplist, SListNode* pos){ assert(pplist); assert(*pplist); // 分两种情况,pos为第一个节点和不是第一个节点 if (*pplist == pos) { free(*pplist); *pplist = NULL; } else { // 找到pos之前的节点 SListNode* posPrev = *pplist; while (posPrev->next != pos) { posPrev = posPrev->next; } posPrev->next = pos->next; free(pos); pos = NULL; }}
// 查找SListNode* SListFind(SListNode* plist, SLTDataType x){ // 当链表为空,返回NULL if (plist == NULL) { return NULL; } // 链表不为空,遍历链表 SListNode* find = plist; while (find) { // 判断是否为所找节点,是则返回节点地址 if (find->data == x) { return find; } // 继续迭代 find = find->next; } // 没有找到,返回NULL return NULL;}
// 修改void SListModify(SListNode* pos, SLTDataType x){ assert(pos); pos->data = x;}
// 销毁void SListDestroy(SListNode** pplist){ assert(pplist); SListNode* temp = NULL; // 头删,依次释放空间 while (*pplist) { temp = *pplist; *pplist = (*pplist)->next; free(temp); } temp = NULL;}
#pragma once // 防止头文件被重复包含// 包含头文件#include #include #include // 重新定义数据类型名typedef int SLTDataType;// 定义链表结构体typedef struct SListNode{ // 定义一个指向下一个节点地址的指针 struct SListNode* next; // 定义一个存放数据的变量 SLTDataType data;}SListNode;// 函数接口// 打印void SListPrint(SListNode* plist);// 申请一个节点SListNode* BuySListNode(SLTDataType x);// 头插void SListPushFront(SListNode** pplist, SLTDataType x);// 尾插void SListPushBack(SListNode** pplist, SLTDataType x);// 在pos之前插入一个节点void SListInsertBefore(SListNode** pplist, SListNode* pos, SLTDataType x);// 在pos之后插入一个节点void SListInsertAfter(SListNode* pos, SLTDataType x);// 头删void SListPopfront(SListNode** pplist);// 尾删void SListPopBack(SListNode** pplist);// 删去pos节点void SListErase(SListNode** pplist, SListNode* pos);// 查找SListNode* SListFind(SListNode* plist, SLTDataType x);// 修改void SListModify(SListNode* pos, SLTDataType x);// 销毁void SListDestroy(SListNode** pplist)
#define _CRT_SECURE_NO_WARNINGS // 这句是我的VS2019用scanf报错才加的,大家可以不用理#include"SList.h"// 打印void SListPrint(SListNode* plist){ while (plist) { printf("%d", plist->data); printf("-->"); plist = plist->next; } printf("NULL");}// 申请一个节点SListNode* BuySListNode(SLTDataType x){ // 向内存申请一个节点 SListNode* newnode = (SListNode*)malloc(sizeof(SListNode)); // 判断申请是否成功 assert(newnode); // 对节点初始化以及赋值 newnode->next = NULL; newnode->data = x; return newnode;}// 头插void SListPushFront(SListNode** pplist, SLTDataType x){ // 防止传进来的pplist是空指针 assert(pplist); // 申请一个新节点 SListNode* newnode = BuySListNode(x); // 判断链表是否为空 if (*pplist == NULL) { *pplist = newnode; } else { 方法一 申请一个指针指向当前的头节点 //SListNode* next = *pplist; //*pplist = newnode; //newnode->next = next; // 方法二 newnode->next = *pplist; *pplist = newnode; }}// 尾插void SListPushBack(SListNode** pplist, SLTDataType x){ assert(pplist); // 申请一个新节点 SListNode* newnode = BuySListNode(x); // 分两种情况,链表为空和非空 if (*pplist == NULL) { *pplist = newnode; } else { // 定义一个指针,去遍历寻找尾节点 SListNode* tail = *pplist; while (tail->next) { tail = tail->next; } // 插入节点 tail->next = newnode; }}// 在pos之前插入一个节点void SListInsertBefore(SListNode** pplist, SListNode* pos, SLTDataType x){ assert(pplist); assert(pos); // 申请一个新节点 SListNode* newnode = BuySListNode(x); // 判断pos是否为第一个节点 if (*pplist == pos) { newnode->next = pos; *pplist = newnode; } else { // 先找到pos之前的一个节点 SListNode* prev = *pplist; while (prev->next != pos) { prev = prev->next; } // 插入新节点 newnode->next = pos; prev->next = newnode; }}// 在pos之后插入一个节点void SListInsertAfter(SListNode* pos, SLTDataType x){ assert(pos); // 申请一个新节点 SListNode* newnode = BuySListNode(x); 这里也是有两个方法,跟之前头插的差不多 方法一 定义一个指针指向pos的next //SListNode* posNext = pos->next; //newnode->next = posNext; //pos->next = newnode; // 方法二 newnode->next = pos->next; pos->next = newnode;}// 头删void SListPopFront(SListNode** pplist){ // 防止pplist指针为空 assert(pplist); // 防止pplist指向的地址为空,即链表为空 assert(*pplist); // 定义一个指针指向第一个节点的地址,后面释放空间需要用到 SListNode* temp = *pplist; // 让*pplist直接指向它的下一个节点 *pplist = (*pplist)->next; // 释放被删节点空间,并把temp指针置空 free(temp); temp = NULL;}// 尾删void SListPopBack(SListNode** pplist){ assert(pplist); assert(*pplist); // 分两种情况,链表只有一个节点,和有一个以上节点 if ((*pplist)->next == NULL) { free(*pplist); *pplist = NULL; } else { // 找到尾节点之前的一个节点 SListNode* tail = *pplist; while (tail->next->next) { tail = tail->next; } SListNode* temp = tail->next; tail->next = NULL; free(temp); temp = NULL; }}// 删去pos节点void SListErase(SListNode** pplist, SListNode* pos){ assert(pplist); assert(*pplist); // 分两种情况,pos为第一个节点和不是第一个节点 if (*pplist == pos) { *pplist = pos->next; free(pos); } else { // 找到pos之前的节点 SListNode* posPrev = *pplist; while (posPrev->next != pos)
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/123619.html
摘要:之所以这样说不要认为学就不需要学语言,是因为一味的只学而没有语言等这些基础语言的支撑,是很难深入理解的很多东西的。 之所以这样说不要认为学PHP就不需要学C语言,是因为一味的只学PHP而没有C语言等这些基础语言的支撑,是很难深入理解PHP的很多东西的。 这样的例子其实很多,这里我就举这个例子吧:PHP的数组和C语言的数组的区别和联系。 学过C语言的朋友当然知道C语言里有数组; PHP里...
阅读 1774·2023-04-25 14:28
阅读 1865·2021-11-19 09:40
阅读 2763·2021-11-17 09:33
阅读 1350·2021-11-02 14:48
阅读 1628·2019-08-29 16:36
阅读 3239·2019-08-29 16:09
阅读 2884·2019-08-29 14:17
阅读 2345·2019-08-29 14:07