深圳专业建设网站服务,专业黑帽seo,做应用级网站用什么语言好,微信推广平台链表 前言链表链表的概念及结构链表的分类 无头单向非循环链表的相关实现带头双向循环链表的相关实现顺序表和链表#xff08;带头双向循环链表#xff09;的区别 前言
顺序表是存在一些固有的缺陷的#xff1a;
中间/头部的插入删除#xff0c;时间复杂度为O(N)#xf… 链表 前言链表链表的概念及结构链表的分类 无头单向非循环链表的相关实现带头双向循环链表的相关实现顺序表和链表带头双向循环链表的区别 前言
顺序表是存在一些固有的缺陷的
中间/头部的插入删除时间复杂度为O(N)效率比较低因为需要挪动数据增容需要开辟新空间释放旧空间需要申请新空间拷贝数据释放旧空间。会有不小的消耗。增容一般是呈2倍的增长势必会有一定的空间浪费。例如当前容量为100满了以后增容到200再继续插入了5个数据后面没有数据插入了那么就浪费了95个数据空间。
其中链表就可以很好的解决上面的问题。
链表
链表的概念及结构
链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。 数据结构中 注
链表在逻辑上是线性物理上不一定是线性的phead一般是指向第一个节点的指针头指针
链表的分类
实际中链表的结构非常多样以下情况组合起来就有8种链表结构
单向或者双向 2. 带头或者不带头 注
d1-头节点head-哨兵位的头节点这个节点不存储有效数据带哨兵位头节点的好处是如果头指针指向的是不带哨兵位的头节点时再做头插尾插等操作就得传二级指针因为头插尾插等操作只要动到头节点就需要改变头指针。如果是带哨兵位的头节点就不用传二级指针因为头指针永远都不会变一直指向带哨兵位的头节点头插是在带哨兵位的头节点之后插入尾插也一样。永远不会动到头指针因为带哨兵位的头节点没有存储有效数据。这里的带头指的是哨兵位的头节点不存储有效数据
循环或者非循环 虽然有这么多的链表的结构但是实际中最常用还是两种结构无头单项非循环链表、带头双向循环链表 无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。带头双向循环链表结构最复杂一般用在单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。另外这个结构虽然结构复杂但是使用代码实现以后会发现结构会带来很多优势实现反而简单了。
无头单向非循环链表的相关实现 链表的定义 typedef int SLTDataType;typedef struct SListNode
{SLTDataType data; // int val;struct SListNode* next; //注意这个地方不能使用SLTNode* next;这个地方还没有typedef出来就开始使用SLTNode编译器找定义时只会向上找然而上面并没有SLTNode。
}SLTNode; 链表的打印 链表的打印需要将头节点的地址进行传参从指向头节点位置的指针开始依次循环遍历直到遇到NULL为止停止打印节点的数据
void SListPrint(SLTNode* phead)
{SLTNode* cur phead;while (cur ! NULL){printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
} 链表的尾插 链表的尾插首先通过循环的方式找到链表中的最后一个节点接着要创建一个新节点节点里面存放尾插的数据最后将新节点的地址存放到最后一个节点中从而完成连接的过程。这时是最常见的一种情况还有一种是当链表为空时没有一个节点头指针存放NULL需要创建一个新节点并把新节点的地址存放到头指针中即可。
SLTNode* BuySListNode(SLTDataType x)
{SLTNode* node (SLTNode*)malloc(sizeof(SLTNode));if (node NULL){printf(malloc fail\n);exit(-1);}node-data x;node-next NULL;return node;
}void SListPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);//头指针可能为空但是头指针的地址是不可能为空的if (*pphead NULL){SLTNode* newnode BuySListNode(x);*pphead newnode;}else{SLTNode* tail *pphead;while (tail-next ! NULL){tail tail-next;}SLTNode* newnode BuySListNode(x);tail-next newnode;}
}注意
这里不要使用一级指针进行传参因为指针传值相当于把plist指针变量得值拷贝给pheadphead里面赋值newnode而phead的改变不会影响plist。因此想在函数内部修改外面plist的值就得使用二级指针进行传参。要改变传过来的指向第一个节点的指针就传二级不改变传过来的指向第一个节点的指针就传一级 链表的头插 链表的头插只需要创建一个新节点将头指针内存放的第一个节点的地址存储到新结点中再将新节点的地址存放到头指针中其中这两步顺序不能颠倒从而完成头插的连接。注意当链表为空时这个头插不会出现问题。
void SListPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode BuySListNode(x);newnode-next *pphead;*pphead newnode;
}链表的尾删 链表尾删的方式有两种
一种是定义两个指针prev、tail当tail指向下一个节点之前先将tail赋给prev然后tail在指向下一个节点。这样以此往复直到tail指向最后一个节点停止此时prev指向tail所指向节点的前一个节点。最后将tail所指向的节点释放掉再将prev所指向节点的next置成NULL。另一种是定义一个指针tail利用单链表的特点完成链表的尾删单链表的特点是只能向一个方向走只要走完就回不去了。因此tail指针找得到下一个节点但是找不到当前节点的前一个节点。 那直接找前一个从而也就能找到它的下一个单链表是在当前位置找不到前一个但是在前一个位置是可以找到后一个的。此时就需要看tail所指向当前节点的下一个节点的下一个节点是否为NULL如此往复直到它为NULL停止就说明tail所指向当前节点的下一个节点就是单链表的最后一个节点那tail所指向当前节点就是最后一个节点的前一个节点。最后将tail所指向当前节点的下一个节点释放掉并将tail所指向当前节点的next置成NULL即可。
注
当链表尾删删除的是最后一个节点时需要注意头指针的指向问题egphead以及节点指针的野指针问题egprev、tail-next链表尾删时需要分三种情况无节点、一个节点、多个节点。当链表为空时进行尾删此时需要对头指针进行判断egassert、if。当链表有一个节点时即头节点的next存储的是NULL直接对该节点进行释放并把头指针指向空。当链表有多个节点时按照上述方式处理即可。
//第一种void SListPopBack(SLTNode** pphead)
{// 检查参数是否传错assert(pphead);// 没有节点断言报错 -- 处理比较激进// 无节点assert(*pphead);// 一个节点if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}// 多个节点else{SLTNode* tail *pphead;while (tail-next-next ! NULL){tail tail-next;}free(tail);tail-next NULL;}
}//第二种
void SListPopBack(SLTNode** pphead)
{// 参数传错assert(pphead);// 无节点// 温和处理if (*pphead NULL){return;}// 一个节点if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}// 多个节点else{SLTNode* prev NULL;SLTNode* tail *pphead;while (tail-next ! NULL){prev tail;tail tail-next;}free(tail);prev-next NULL;}
}//第三种
void SListPopBack(SLTNode** pphead)
{// 参数传错assert(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;}free(tail);prev-next NULL;}
}//第四种
void SListPopBack(SLTNode** pphead)
{// 参数传错assert(pphead);// 无节点// 温和处理if (*pphead NULL){return;}// 一个节点if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}// 多个节点else{SLTNode* prev NULL;SLTNode* tail *pphead;while (tail-next ! NULL){prev tail;tail tail-next;}free(tail);prev-next NULL;}
}注pphead的意义是能够在增删的函数中改变外面的plist 链表的头删 链表的头删首先判断头指针的地址是否为空其次再处理链表中无节点、一个节点、多个节点的情况即可。
注
链表头删处理多个节点一个节点时需要先对头节点的下一个节点进行保存再对头节点进行删除最后再将头节点的下一个节点的地址存放到头指针里即可。链表头删中的处理多个节点的情况也包含了一个节点的情况。
//第一种void SListPopFront(SLTNode** pphead)
{// plist一定有地址所以pphead不为空assert(pphead);// 链表为空assert(*pphead);// 只有一个节点if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}// 多个节点else{SLTNode* next (*pphead)-next;free(*pphead);(*pphead) next;}
}//第二种void SListPopFront(SLTNode** pphead)
{// plist一定有地址所以pphead不为空assert(pphead);//链表为空assert(*pphead);//只有一个节点//多个节点SLTNode* next (*pphead)-next;free(*pphead);(*pphead) next;
}链表中节点的个数 可以通过循环的方式终止条件是当前节点的地址是否为空求链表中节点的个数。
注phead不需要进行断言因为phead有可能为空链表为空空链表可以求节点个数
int SListSize(SLTNode* phead)
{int size 0;SLTNode* cur phead;while (cur){size;cur cur-next;}return size;
}链表判空 链表的判空只需对头指针进行判空即可如果头指针为空返回true否则返回false。
注C语言中用bool类型需要引头文件stdbool.h
//第一种bool SListEmpty(SLTNode* phead)
{return phead NULL;
}//第二种bool SListEmpty(SLTNode* phead)
{if (phead NULL){return true;}else{return false;}
}//第三种bool SListEmpty(SLTNode* phead)
{return phead NULL ? true : false;
}链表的查找 链表的查找是通过循环遍历的方式进行查找如果找到了返回该节点的地址否则返回NULL。
SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur phead;while (cur){if (cur-data x){return cur;}else{cur cur-next;}}return NULL;
}链表的插入 链表的前插入分两种情况处理头插、后面插入。这里注意后面插入时首先需要找到pos位置之前的节点的位置通过循环的方式找到pos位置之前的节点的位置其次创建要插入的新节点最后进行插入使其新节点的next指向pos位置的节点next存储pos的值并使前一个节点的next指向新节点next存储新节点的地址即可。
// 在pos位置之前去插入x
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);// 头插if (*pphead pos){SListPushFront(pphead, x);}// 后面插入else{// 找到pos位置的前一个节点SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}SLTNode* newnode BuySListNode(x);newnode-next pos;prev-next newnode;}
}链表的后插入首先要创建一个新节点其次使其新节点的next指向pos位置上的节点的下一个节点最后将pos位置上节点的next指向新节点。
// 在pos位置后面去插入x
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);//注意插入顺序不可颠倒SLTNode* newnode BuySListNode(x);newnode-next pos-next;pos-next newnode;
}注单链表不适合在某个位置之前插入因为需要找前一个位置。单链表适合在某个位置之后插入。 链表的删除 链表删除当前位置的节点分两种情况头删、后面删除。这里注意后面删除首先需要找当前位置节点的前一个节点其次使其前一个节点的next指向当前位置节点的后一个节点最后再将pos位置上的节点释放掉。
// 删除pos位置的值
void SListErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);// 头删if (pos *pphead){SListPopFront(pphead);}// 后面节点删除else{// 找到pos位置的前一个节点SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);pos NULL;}
}链表删除当前位置的之后的节点只需将当前位置的节点的next指向当前位置的节点的下一个节点的下一个节点即可不过在此之前需要对当前位置的节点的下一个节点进行保存避免找不到该节点。最后再将该节点释放掉即可。
void SListEraseAfter(SLTNode* pos)
{assert(pos);assert(pos-next);SLTNode* next pos-next;pos-next next-next;free(next);next NULL;
} 链表的销毁 链表的销毁是将所有节点释放掉通过循环的方式对链表进行销毁。这里注意释放节点时需要对下一个节点的地址进行保存避免找不到下一个节点的地址最后需要将头指针置空即可。
注节点的释放会引发一些问题会把这块节点的使用权还给操作系统并且指向这块空间上的值会被置成随机值
void SListDestory(SLTNode** pphead)
{assert(pphead);SLTNode* cur *pphead;while (cur){SLTNode* next cur-next;free(cur);cur next;}*pphead NULL;
}带头双向循环链表的相关实现 链表的定义 typedef int LTDataType;typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType data;
}LTNode; 链表的初始化 链表初始化首先要创建一个哨兵位的头节点其次将哨兵位的头节点的前驱和后继都指向该头节点即可
LTNode* BuyListNode(LTDataType x)
{LTNode* node (LTNode*)malloc(sizeof(LTNode));if (node NULL){printf(malloc fail\n);exit(-1);}node-next NULL;node-prev NULL;node-data x;return node;
}//第一种void ListInit(LTNode** pphead)
{*pphead BuyListNode(-1);(*pphead)-next *pphead;(*pphead)-prev *pphead;
}//第二种LTNode* ListInit()
{LTNode* phead BuyListNode(0);phead-next phead;phead-prev phead;return phead;
}链表的打印 链表打印通过循环的方式从头节点的下一个节点开始进行打印节点带有哨兵位的头节点是无效节点不存储有效数据注意当循环遍历到头节点时结束循环。
void ListPrint(LTNode* phead)
{assert(phead);LTNode* cur phead-next;while (cur ! phead){printf(%d , cur-data);cur cur-next;}printf(\n);
}链表的尾插 链表尾插首先通过头节点的前驱找到尾节点的地址其次创建新节点然后修改头节点、新节点、尾节点三者的连接关系即可
注链表尾插的过程中没有修改头指针
//第一种void ListPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* tail phead-prev;LTNode* newnode BuyListNode(x);tail-next newnode;newnode-prev tail;newnode-next phead;phead-prev newnode;
}//第二种//利用函数复用只需将头节点的指针传给链表的插入函数相当于在头节点之前插入链表的尾插即可。
void ListPushBack(LTNode* phead, LTDataType x)
{assert(phead);ListInsert(phead, x);
}注时间复杂度为O(1) 链表的头插 利用函数复用只需将头节点的后继传给链表的插入函数相当于在头节点的后继所指向的节点之前插入链表的头插即可。
void ListPushFront(LTNode* phead, LTDataType x)
{assert(phead);ListInsert(phead-next, x);
}补充C语言中复用函数是指在编程过程中重复使用代码段的一种方法。每个程序中都存在很多相似的或者相同的代码段把这些相同的代码段抽取出来形成一个独立的函数就叫做复用函数。复用函数的好处在于可以有效提高程序的可维护性、可读性提高代码的可复用性,还可以明显减少程序的开发时间,简化程序的结构。 链表的尾删 链表尾删通过头节点的前驱找到尾节点的地址再通过尾节点的前驱找到尾节点的前一个节点的地址然后删除尾节点最后完成头节点和尾节点的前一个节点的连接关系即可。
//第一种void ListPopBack(LTNode* phead)
{assert(phead);assert(!ListEmpty(phead));LTNode* tail phead-prev;LTNode* tailPrev tail-prev;free(tail);tailPrev-next phead;phead-prev tailPrev;
}//第二种//利用函数复用只需将头节点的前驱传给链表的删除函数相当于在头节点的前驱所指向的节点进行删除链表的尾删即可。
void ListPopBack(LTNode* phead)
{assert(phead);assert(!ListEmpty(phead));ListErase(phead-prev);
}链表的判空 链表的判空通过判断头节点的后继是否是本身如果是返回真否则返回假。
bool ListEmpty(LTNode* phead)
{assert(phead);return phead-next phead;
}链表中有效节点的个数 求链表中有效节点的个数通过循环遍历的方式实现即可。
size_t ListSize(LTNode* phead)
{assert(phead);size_t n 0;LTNode* cur phead-next;while (cur ! phead){n;cur cur-next;}return n;
}链表的头删 利用函数复用只需将头节点的后继传给链表的删除函数相当于在头节点的后继所指向的节点进行删除链表的头删即可。
void ListPopFront(LTNode* phead)
{assert(phead);assert(!ListEmpty(phead));ListErase(phead-next);
}链表的插入在某个位置之前插入节点 链表的插入首先通过pos位置上节点的前驱找到前一个节点再创建一个新节点最后将pos位置上的节点、新节点、pos位置的节点的前一个节点三个节点完成连接即可。
void ListInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode BuyListNode(x);LTNode* prev pos-prev;// prev newnode posprev-next newnode;newnode-prev prev;newnode-next pos;pos-prev newnode;
}链表的删除删除某个位置的节点 链表的删除首先找到pos位置上的节点的前一个节点其次再找到pos位置上的节点的后一个节点然后释放pos位置上的节点最后将pos位置上的节点的前一个节点和pos位置上的节点的后一个节点进行连接即可。
// 删除pos位置
void ListErase(LTNode* pos)
{assert(pos);LTNode* prev pos-prev;LTNode* next pos-next;free(pos);pos NULL;prev-next next;next-prev prev;
}链表的查找 链表的查找是通过循环遍历的方式进行查找如果找到了返回该节点的地址否则返回NULL。
LTNode* ListFind(LTNode* phead, LTDataType x)
{LTNode* cur phead-next;while (cur ! phead){if (cur-data x){return cur;}cur cur-next;}return NULL;
}链表的销毁 链表的销毁是将所有节点释放掉包括带哨兵位的头节点通过循环的方式对链表进行销毁。这里注意释放节点时需要对下一个节点的地址进行保存避免找不到下一个节点的地址最后需要将头指针置空即可。
注节点的释放会引发一些问题会把这块节点的使用权还给操作系统并且指向这块空间上的值会被置成随机值
//第一种void ListDestroy(LTNode* phead)
{LTNode* cur phead-next;while (cur ! phead){LTNode* next cur-next;free(cur);//cur NULL;cur next;}free(phead);//phead NULL; // 这里其实置空不置空都可以的因为出了函数作用域没人能访问phead// 其次就是phead形参的置空也不会影响外面的实参
}//第二种void ListDestroy(LTNode** pphead)
{LTNode* cur (*pphead)-next;while (cur ! *pphead){LTNode* next cur-next;free(cur);cur next;}free(*pphead);*pphead NULL;
}注链表销毁函数的参数可以用一级指针也可以用二级指针。参数用一级指针外面用了以后实参存在野指针的问题。但是这个函数保持了接口的一致性。参数用二级指针虽然解决了野指针问题但是从接口设计的角度有点混乱。
顺序表和链表带头双向循环链表的区别
不同点顺序表链表存储空间上物理上一定连续逻辑上连续但物理上不一定连续随机访问用下标访问支持O(1)不支持O(N)任意位置插入或者删除元素可能需要搬移元素效率低O(N)只需修改指针指向效率O(1)插入动态顺序表空间不够时需要扩容没有容量的概念按需申请空间应用场景元素高效存储频繁访问任意位置插入和删除频繁缓存利用率(缓存命中率)高低
注
链表和顺序表它们是不能比较出谁更优的它们各有优缺点相辅相成。扩容有一定的消耗拷贝数据释放空间以及扩容后可能存在一定的空间浪费。尾插尾删多并且经常随机访问用顺序表合适。随时需要任意位置插入删除用链表合适。 存储体系结构以及局部原理性。 寄存器和三级缓存是围绕在CPU附近的主存运行内存是带电存储的磁盘是不带电存储CPU运算速度快取内存速度跟不上。CPU一般就不会直接访问内存而是把要访问的数据先加载的到缓存体系。如果是小于等于8字节的数据会直接到寄存器而大数据就会到三级缓存。CPU直接跟缓存交互。CPU要访问内存中某个地址的数据首先要去缓存中去找如果发现找不到没有命中此时就会把主存中这个地址开始的一段空间都读进来缓存缓存预加载某个部分的空间和一段空间的成本时间成本是一样的便于下一次访问。缓存利用率缓存命中率低会造成一定的缓存污染。
