网站建设开发服务费怎么做账,制作ppt的软件电脑版,模板下载器,厦门酒店团购网站建设#x1f525;博客主页#xff1a;小王又困了
#x1f4da;系列专栏#xff1a;数据结构
#x1f31f;人之为学#xff0c;不日近则日退
❤️感谢大家点赞#x1f44d;收藏⭐评论✍️ 目录
一、什么是链表
1.1链表的概念及结构
1.2单链表的结构
二、链表的实现 … 博客主页小王又困了
系列专栏数据结构
人之为学不日近则日退
❤️感谢大家点赞收藏⭐评论✍️ 目录
一、什么是链表
1.1链表的概念及结构
1.2单链表的结构
二、链表的实现
2.1创建节点
2.2头插
2.3头删
2.4尾插
链表为空的插入
链表不为空
2.5尾删
2.6查找
2.7在pos位置之前插入
2.8在pos位置之后插入
2.9删除pos位置 ️前言 在上一期中我们学习了顺序表但它却有缺点例如头插或从中间插入效率低等而链表可以有效的解决这些问题。那么就让我们走进链表的学习。 一、什么是链表
1.1链表的概念及结构 概念链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。 结构 注意 1.链式结构在逻辑上是连续的但在物理上不一定连续。 2.节点都是从堆上申请的。 3.从堆上申请空间是按一定策略分配的申请的空间可能连续也可能不连续。 1.2单链表的结构
typedef int STLDataType;typedef struct STLNode
{STLDataType date;struct STLNode* next;
}STLNode;
这种链表被称为无头单向非循环链表
二、链表的实现
2.1创建节点 我们想使用链表来实现各种功能得先有链表所以首先使用malloc创建节点。 STLNode* BuyListNode(STLDataType x)
{STLNode* newnode (STLNode*)malloc(sizeof(STLNode));if (newnode NULL){perroe(malloc);exit(-1);}newnode-date x;newnode-next NULL;return newnode;
} 2.2头插 要想让链表连起来就要让newnode-next存放下一个节点的地址也就是旧链表phead的值然后将newnode的地址存放在phead中形成新的链表。无论一开始有没有节点头插都是相同的。 //头插
void STLPushFront(STLNode** pphead, STLDataType x)
{STLNode* newnode BuyListNode(x);newnode-next *pphead;*pphead newnode;
} 2.3头删 头删时如果先释放空间就会找不到下一个节点的地址如果先把下一个节点的地址赋给*pphead就会导致无法释放空间所以我们要创建一个临时变量来存放下一个节点的地址。 //头删
void STLPopFront(STLNode** pphead)
{assert(*pphead);STLNode* newnode (*pphead)-next;free(*pphead);*pphead newnode;
} 2.4尾插
我们在尾插时会有两种情况链表为空的插入和有其他节点的尾插。第一种情况会出现一些理解性的错误接下来就让我们学习学习这两种尾插的情况。
链表为空的插入 当我们传递的是plist的值屏幕上并没有打印出我们想要的结果。这是为什么呢 形参是实参的一份临时拷贝形参的改变不会影响实参phead的改变不会影响plist。 临时变量出作用域销毁phead和newnode销毁找不带开辟的节点会造成内存泄漏。 正确做法是要将plist的地址传递过去我们通过解引用就可以改变plist。plist中存放的是指针我们传递指针的地址要用二级指针接收。 链表不为空 链表不为空时我们要找到尾节点。这里我们要注意不能使用 tail!NULL 判断。这样我们无法把链表连接起来。 //尾插
void STLPushBack(STLNode** pphead, STLDataType x)
{assert(pphead);STLNode* newnode BuyListNode(x);if (NULL *pphead){*pphead newnode;}else{STLNode* tail *pphead;while (tail-next ! NULL){tail tail-next;}tail-next newnode;}
}
2.5尾删 在尾删时也有两种情况一种是有很多节点另一种是只剩一个节点当删最后一个节点时要改变plist的值所以我们要传递plist的指针。我们要使用两个指针当后面的指针释放后可以利用前面的指针将最后一个节点的next置为空。 //尾删
void STLPopBack(STLNode** pphead)
{assert(*pphead);//只剩一个if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}//多个else{STLNode* prev NULL;STLNode* tail *pphead;while (tail-next){prev tail;tail tail-next;}free(tail);prev-next NULL;}
} 2.6查找 循环判断时不要使用cur-next这样写最后一个数据要单独处理不方便找到时就返回此时的地址。 //查找
STLNode* STLFind(STLNode* phead, STLDataType x)
{STLNode* cur phead;while (cur ! NULL){if (cur-date x){return cur;}cur cur-next;}return 0;
} 2.7在pos位置之前插入 在pos位置之前插入有一种特殊的情况就是头插要改变plist的值我们要传二级指针进去。同时我们要创建一个指针变量找到pos之前的位置才能使链表连接起来。 void STLInsert(STLNode** pphead, STLNode* pos, STLDateType x)
{assert(pos);if(pos *pphead){STLPushFront(pphead, x);}else{STLNode* prev *pphead;while(prev-next ! pos){prev prev-next;}STLNode* newnode BuySListNode(x);newnode-next pos;prev-next newnode;}} 2.8在pos位置之后插入 这里我们要注意地址赋值的顺序顺序不对会造成内存泄漏。如果先把newnode的地址赋给pos的指针域就会丢失下一个节点的地址。 void STLInsertAfter(STLNode* pos, STLDateType x)
{ assert(pos);STLNode* newnode BuySListNode(x);newnode-next pos-next;pos-next newnode;} 2.9删除pos位置 有可能删除的是头节点所以要传递二级指针。 void STLErase(STLNode** pphead, STLNode* pos)
{assert(pos);if(pos *pphead){STLPopFront(pphead, x);}else{STLNode* prev *pphead;while(prev-next ! pos){prev prev-next;}prev-next newnode;free(pos);}} 本次的内容到这里就结束啦。希望大家阅读完可以有所收获同时也感谢各位读者三连支持。文章有问题可以在评论区留言博主一定认真认真修改以后写出更好的文章。你们的支持就是博主最大的动力。
