网站编辑外包,网站后台开发 必备技能,建筑设计资质等级标准,wordpress 4.7 有广告1.链表 目录
1.链表 1.1链表的概念及结构
1.2 链表的分类
2.单链表的实现(不带哨兵位#xff09;
2.1接口函数
2.2函数的实现
3.双向链表的实现#xff08;带哨兵位#xff09;
3.1接口函数
3.2函数的实现 1.1链表的概念及结构 概念#xff1a;链表是一种物理存储结…1.链表 目录
1.链表 1.1链表的概念及结构
1.2 链表的分类
2.单链表的实现(不带哨兵位
2.1接口函数
2.2函数的实现
3.双向链表的实现带哨兵位
3.1接口函数
3.2函数的实现 1.1链表的概念及结构 概念链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。 现实中 数据结构中 1.2 链表的分类 实际中链表的结构非常多样以下情况组合起来就有8种链表结构 1. 单向或者双向 2. 带头或者不带头 3. 循环或者非循环 1. 无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。 2. 带头双向循环链表结构最复杂一般用在单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。另外这个结构虽然结构复杂但是使用代码实现以后会发现结构会带来很多优势实现反而简单了后面我们代码实现了就知道了。 2.单链表的实现(不带哨兵位 2.1接口函数
// 1、无头单向非循环链表增删查改实现
typedef int SLTDateType;
typedef struct SListNode
{SLTDateType data;struct SListNode* next;
}SListNode;
// 动态申请一个结点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置
void SListEraseAfter(SListNode* pos);
//销毁单链表
void SLTDestroy(SLNode** pphead); 2.2函数的实现 1. 动态申请一个结点 SListNode* BuySListNode(SLTDateType x)
{SListNode* new (SListNode*)malloc(sizeof(SListNode));if (new NULL){perror(malloc);exit(-1);}new-data x;new-next NULL;return new;
} 动态申链表并给新malloc出的空间传值。 2.单链表尾插 void SListPushBack(SListNode** pplist, SLTDateType x)
{assert(pphead);SListNode* newlist BuySListNode(x);if (*pplist NULL){*pplist newlist;}else {SListNode* tail NULL;tail *pplist;while (tail-next ! NULL){tail tail-next;}tail-next newlist;}
} 1. 创建一个新节点并为其分配内存空间。 2. 将新节点的数据赋值为要插入的数据。 3. 将新节点的指针域next设置为NULL表示它是链表的最后一个节点。 4. 如果链表为空将头指针指向新节点否则找到链表的最后一个节点将其指针域指向新节点。 3.单链表的尾删 void SListPopBack(SListNode** pplist)
{assert(pphead);assert(*pplist);if ((*pplist)-next NULL){free(*pplist);*pplist NULL;}else {SListNode* tail *pplist;SListNode* prve NULL;while (tail-next ! NULL){ prve tail;tail tail-next;}free(tail);tail NULL;//不置空也没问题出作用域自动销毁prve-next NULL;}} 1. 如果链表为空直接返回空链表。 2. 如果链表只有一个节点释放该节点的内存空间并将头指针指向NULL。 3. 遍历链表找到倒数第二个节点。 4. 将倒数第二个节点的指针域设置为NULL表示它是链表的最后一个节点。 5. 释放最后一个节点的内存空间。 3.单链表的头插 void SListPushFront(SListNode** pplist, SLTDateType x)
{assert(pphead);SListNode* newlist BuySListNode(x);newlist-next *pplist;*pplist newlist;
} 1. 创建一个新节点并为其分配内存空间。 2. 将新节点的数据赋值为要插入的数据。 3. 将新节点的指针域指向当前的头节点。 4. 将头指针指向新节点。 4.单链表头删 void SListPopFront(SListNode** pplist)
{assert(pphead);assert(*pplist);SListNode* tmp (*pplist)-next;free(*pplist);*pplist tmp;
} 1. 如果链表为空直接返回空链表。 2. 将头指针指向第二个节点。 3. 释放第一个节点的内存空间。 5.单链表查找 SListNode* SListFind(SListNode* plist, SLTDateType x)
{SListNode* find plist;while (find ! NULL){if (find-data x){return find;break;}find find-next;}return NULL;
} 1. 如果链表为空返回NULL。 2. 遍历链表逐个比较节点的数据与目标值。 3. 如果找到匹配的节点返回该节点的指针否则返回NULL。 6.在pos节点后插入 void SListInsertAfter(SListNode* pos, SLTDateType x)
{assert(pphead);if (pos NULL) {return;}SListNode* newlist BuySListNode(x);newlist-next pos-next;pos-next newlist;
} 1.判断了指定位置是否为NULL如果为NULL则直接返回不进行插入操作。2.我们创建一个新节点并将新节点的数据赋值为要插入的数据。3.我们将新节点的指针域指向指定位置节点原来的下一个节点然后将指定位置节点的指针域指向新节点完成插入操作。 7.删除pos节点后的值 void SListEraseAfter(SListNode* pos)
{assert(pphead);if (pos NULL || pos-next NULL) {return;}SListNode* temp pos-next;pos-next temp-next;free(temp);
} 1.判断了指定位置是否为NULL或者指定位置的下一个节点是否为NULL如果是则直接返回不进行删除操作。2.我们创建一个临时指针temp指向指定位置节点的下一个节点。3.我们将指定位置节点的指针域指向temp节点的下一个节点然后释放temp节点的内存空间完成删除操作。 8.销毁单链表 void SLTDestroy(SLNode** pphead)
{assert(pphead);SLNode* cur *pphead;while (cur){SLNode* next cur-next;free(cur);cur next;}*pphead NULL;
} 先保存下一个的地址在销毁当前节点。 9.分析思考为什么不在pos位置之前插入为什么不删除pos位置 这是因为单链表的节点只有一个指针指向下一个节点没有指向前一个节点的指针。那该如何解决呢请看后面双向链表的实现。 3.双向链表的实现带哨兵位 3.1接口函数
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.htypedef int LTDataType;
typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType data;
}LTNode;LTNode* BuyLTNode(LTDataType x);
LTNode* LTInit();
void LTPrint(LTNode* phead);
void LTPushBack(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);void LTPushFront(LTNode* phead, LTDataType x);
void LTPopFront(LTNode* phead);int LTSize(LTNode* phead);LTNode* LTFind(LTNode* phead, LTDataType x);// pos֮ǰx
void LTInsert(LTNode* pos, LTDataType x);
// ɾposλ
void LTErase(LTNode* pos);3.2函数的实现 我们可以注意到在单链表和双线链表出参的不同单链表传的是二级指针而双向链表传的是一级指针。实际上这是有无哨兵位造成的当没有哨兵位时我们需要用二级指针去保存链表第一个节点的地址此时改变的是结构体的指针因此需要用结构体的二级指针而带哨兵位我们只需要改变哨兵位后面的节点结构体此时改变的是结构体因此只需要用结构体的一级指针。 双向链表相较于单链表实际上就多了头指针域这样就能找到当前节点的上一个节点也就是可以轻松的做到在任意节点前插入。双向链表做到了“首尾呼应”自然为节点不用指向NULL。 这样很多操作就变的简单快捷高效。 1.动态申请一个结点 LTNode* BuyLTNode(LTDataType x)
{LTNode* node (LTNode*)malloc(sizeof(LTNode));if (node NULL){perror(malloc fail);exit(-1);}node-data x;node-next NULL;node-prev NULL;return node;
} 2.头节点哨兵位的初始化 LTNode* LTInit()
{LTNode* phead BuyLTNode(0);phead-next phead;phead-prev phead;return phead;
}这里涉及到改变结构体的值的操作当然也可以写成接收二级指针的形式档期当前的方式当然也是可行的。这里的操作就是对哨兵位的初始化我们可以看到我们将头节点的前后指针域都指向了自己这样就保持了循环的效果。 3.双向链表尾插 void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* tail phead-prev;LTNode* newnode BuyLTNode(x);newnode-prev tail;tail-next newnode;newnode-next phead;phead-prev newnode;
} 双向链表要实现尾删是非常便捷的不用循环找到尾节点因为头节点的前指针域就指向了尾节点所以我们只需要一步就能找到尾了。然后我们只需尾节点 指向新节点然后让新节点指向尾节点之后再让新节点指向头节点最后让头节点指向新节点就好了。 4.尾删 void LTPopBack(LTNode* phead)
{assert(phead);assert(phead-next ! phead);LTNode* tail phead-prev;LTNode* tailPrev tail-prev;free(tail);tailPrev-next phead;phead-prev tailPrev;} 要删除尾节点首先要找到尾节点和尾节点的前一个节点然后释放掉尾节点让新的尾节点指向头再让头指向尾。 5.打印双向链表 void LTPrint(LTNode* phead)
{assert(phead);assert(phead-next!phead);printf(phead);LTNode* cur phead-next;while (cur ! phead){printf(%d, cur-data);cur cur-next;}printf(\n);
} 当我们打印双向链表时只存在头节点就不要打印了所以我们可以加上第二句断言。 打印的时候我们从头节点的下一个节点开始打印最后走一圈遍历到头的时候就停止打印。 这里我就省略头插头删求节点个数和查找了因为操作大同小异十分简单最后会奉上完整代码。 6.pos节点前插入 void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* posPrev pos-prev;LTNode* newnode BuyLTNode(x);posPrev-next newnode;newnode-prev posPrev;newnode-next pos;pos-prev newnode;
} 想要在pos节点的前面插入那么只需要找到pos节点和pos节点前面的节点就可以了找pos节点我们可以配合查找函数来使用找到想要的pos节点就可以了。 7.删除pos节点 void LTErase(LTNode* pos)
{assert(pos);LTNode* posPrev pos-prev;LTNode* posNext pos-next;free(pos);posPrev-next posNext;posNext-prev posPrev;
} 想要删除pos节点只需要找到pos节点的前一个和pos节点的后一个free掉pos节点然后让pos节点的前一个和pos节点的后一个连接就好了。 这就是链表的全部内容了希望对各位老铁有帮助接下来我会更新链表的OJ题目希望各位老铁多多支持
