卢氏县住房和城乡规划建设局网站,长春网站建设sok,哪里有建设公司官网,有域名了建立免费网站前言顺序表要求是具有连续的物理空间#xff0c;并且数据的话是在这些空间当中是连续的存储。但这样会带来很多问题#xff0c;比如说在头部或者说中间插入的话#xff0c;效率不是很高#xff1b;并且申请空间可能需要扩容#xff0c;并且越往后一般来说都是异地扩容并且数据的话是在这些空间当中是连续的存储。但这样会带来很多问题比如说在头部或者说中间插入的话效率不是很高并且申请空间可能需要扩容并且越往后一般来说都是异地扩容虽然看起来的话是简单的调用了一下realloc但是从底层来看的话这个代价很大。而且扩容的话也会存在一定程度的浪费因此就需要链表的存在。链表的话是一个数据存一个内存块。这些内存块之间并不一定要求是物理上连续的这些内存块之间用指针进行相关的链接链表实际上具有八种结构。链表其实就是用指针这么链接起来的一些个内存块。链表当中各个节点在物理上不一定是连续的这个节点之间也并没有任何的顺序关系(都是各自随意malloc出来的)根本就不需要去考虑顺序孤岛之间只需要有一根桥梁即可单链表就关注这三个有机组成部分节点 SLTNode节点地址(指向节点的指针) SLTNode*一级指针(指向链表第一个节点) phead二级指针(指向上面的一级指针) pphead逻辑结构与物理结构虽然有时候平时画图的时候画链表的时候可能会带一些箭头之类的但是真正在内存里面是不可能有箭头这些东西的。内存里面是不可能存着箭头→这些东西的。我们把这些箭头叫做逻辑结构是我们想象出来的因为这些箭头比指针更为直观。在内存里面实实在在怎么存的被称为物理结构。我们画图的时候看起来好像指针啊什么呀都是在动的但实际上在内存里面的话一切都是死的没有动无非就是不断的给指针变量进行赋值。然后在我们脑海中直观的形象表现就是该指针变量不断的指来指去。逻辑结构就是我们为了方便理解形象化画出来的但是在计算机内存里面是十分枯燥的实实在在数据在内存中的变化是物理结构。单链表节点(结构体类型)的创建从语言的角度来讲凡是有多个数据都需要存到结构体里面去。链表的每一个节点就是通过结构体来表示。结构体里面有当前的数值data并且还需要一个指针。因为上一个节点需要存下一个节点的地址这样我才有寻找的依据这样的话各个内存块之间才可以像链条一样这么串起来。并且我们已经知道每一个节点实际上就是一个结构体。既然上一个节点需要存下一个节点的地址。那么因此显而易见无非就是一个结构体指针罢了我们叫做next。之前在c语言当中我们也讲过结构体里面是不能够嵌套结构体的就是无穷套娃了。但我们刚才结构体里面并没有结构体是一个结构体指针大小是确定的就是四个字节。//节点结构体的创建
typedef int SLTDataType;
typedef struct SLTNode
{SLTDataType data;struct SLTNode* next;
}SLTNode;单链表的打印1. 空的顺序表可以打印当然一样道理空的链表也可以打印给我显示为空不就可以了2. phead就是链表第一个节点的地址如果这个链表是空链表那么phead就是NULL3. 当我为空链表的时候phead就为NULL在打印链表的时候不能够进行断言不然的话空链表我就打印不出来了直接把我程序终止了。4. 链表的话在物理上并不是连续的它的每一个节点都是malloc出来的。5. 每一个节点说白了就是结构体都会存放下一个节点的地址因此就需要这一很关键的一步:cur cur - next6. 0就是假非0就是真NULL本质就是0。//单链表的打印
void SLTPrint(SLTNode* phead)
{SLTNode* cur phead;while (cur ! NULL){printf(%d-,cur-data);cur cur-next;}printf(NULL\n);
}单链表malloc一个新节点并赋值//单链表malloc一个新节点并赋值
SLTNode* BuySLTNode(SLTDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));if (newnode NULL){perror(BuySLTNode::Malloc);return NULL;}newnode-data x;;newnode-next NULL;return newnode;
}单链表的尾插1. 由于之前一样的在这个地方是不能够进行空指针断言的因为如果是断言的话我在空链表的情形下想要去尾插但是断言了的话给我程序提前终止了这还玩个屁啊。2. 尾插的第一步是先得搞一个节点出来这个地方就不像顺序表一样了要考虑什么空间够不够啊要不要扩容啊之类的就不需要考虑了。在这边的话就自己去malloc新创建一个节点。3. 然后对于这个新节点newnode的值给进去next指针为NULL。4. 然后就是找到原先的尾巴原尾节点的next成员要存储新尾节点的地址。5. 刚才讲的情况都是链表不为空的情况如果链表是空的话这种情况需要额外处理。这时候只需要把phead指向新节点newnode就可以了。//单链表的尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode BuySLTNode(x);if (*pphead NULL){*pphead newnode;}else{SLTNode* tail *pphead;while (tail-next ! NULL){tail tail-next;}tail-next newnode;}
}单链表的头插1. 这个也需要分两种情况以总是链表为空的情况第二种就是链表非空。但是发现仅有的三行代码可以完全解决空的情况。2. 然后发现在这个函数内部也需要创建一个新的节点。那么就是说可以把创建新的节点这个过程给他单独的提取出来。//单链表的头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode BuySLTNode(x);newnode-next *pphead;*pphead newnode;
}单链表的尾删1. 删除的时候也是需要用二级指针。因为万一你要把指针置空的时候如果你传一级指针的话就完蛋了。那么原先那个指针就变成野指针了。2. 链表在尾删的时候要注意分几种特殊情况第一种情况是当前只有一个节点第二种特殊情况就是整个链表都是空的。对于第一种情况直接free然后把指针置空就完事儿了。对于第二种情况直接暴力assert检查就可以。//单链表的尾删
void SLTPopBack(SLTNode** pphead)
{assert(*pphead);if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{SLTNode* prev NULL;SLTNode* tail *pphead;while (tail-next ! NULL){prev tail;tail tail-next;}prev-next NULL;free(tail);tail NULL;}
}单链表的头删1. 首先也可以暴力检查一下这个链表是不是空的。但头删不需要特判链表只有一个节点的情况。//单链表的头删
void SLTPopFront(SLTNode** pphead)
{assert(*pphead);SLTNode* first *pphead;*pphead (*pphead)-next;free(first);first NULL;
}单链表的初始化这个非常简单直接初始化就可以因为只有一个值。直接创建一个结构体指针赋为NULL就可以SLTNode* plist NULL;关于单链表函数操作中的有关于assert断言的问题不是在参数里面碰到一个指针就assert一下不是这么一根筋的。像这边单链表的话当phead为NULL时我们都知道此时此刻表示一个空链表但是空链表我就不能头插尾插插入了吗我照样可以这么插入空链表难道我就不能打印了吗我照样可以打印只是什么都没有而已。但是对于删除而言如果此时此刻你已经是一个空链表了那么你还删个毛线啊所以此时此刻呢又需要用assert断言一下这种东西都是具体问题具体分析。关于参数为二级指针的问题1. 尤其要注意形参的改变不会影响实参这个其实底层要理解的话就是得通过函数栈帧。当传址调用的时候实际上地址也是在拷贝但由于你是在函数里面对指针进行解引用操作因此产生的影响是持久性的即使调用的函数退出回来了。2. malloc向堆区动态申请内存的时候是随机在内存里面划分一块区域的。3. 当你的实参是一个指针的时候虽然这时候函数传参看起来好像也是传址调用但实际上调用函数内部执行的各种操作对于函数外头的这个参数指针不会发生任何影响。因为实际上无论如何都会有拷贝这个环节会发生。4. 在这边想要着重说明的是我们在进行函数传参的时候这时候就必须传二级指针。我们在函数体外已经先有一个指针我们的函数内部操作都离不开要改变该指针的指向位置要实现这个操作就不能传一级指针因为这样只有我这个一级指针自己在捣鼓如果我传指针的地址也就是二级指针这样子我才能在函数体内去改变函数体外这个指针所指向的位置。5. 我这个phead是一个实实在在的结构体指针各种有关于单链表的操作其中都需要phead指向的位置发生变化如果在函数里面传一级指针的话函数里面的各种乱七八糟的运转跟我函数外面的phead指针一点关系都没有因为你在函数内部自己有一个参数指针(形参)也许这个形参与phead指向的地址是一样的但是当你传一级指针的时候在函数里面各种捣鼓运算改变的都是你形参指向的位置。如果想要改变我这个phead指针指向的位置就必须把phead的地址当成参数传给函数因此这个参数也就是指针的地址显而易见即为二级指针。
