北京网站开发哪家好,ui设计和交互设计培训,东莞手工活外发加工网,二级造价工程师朋友们大家好啊#xff0c;在上节完成单链表的讲解后#xff0c;我们本篇文章来对带头循环双向链表进行讲解 双向链表 双向链表、头节点和循环的介绍构建双向链表节点的构建初始化双向循环链表#xff08;空链表#xff09;销毁双向链表 链表的打印双向链表头尾的插与删尾插… 朋友们大家好啊在上节完成单链表的讲解后我们本篇文章来对带头循环双向链表进行讲解 双向链表 双向链表、头节点和循环的介绍构建双向链表节点的构建初始化双向循环链表空链表销毁双向链表 链表的打印双向链表头尾的插与删尾插尾删头插头删 查找特定节点在指定位置前插入数据删除pos节点 总结 双向链表、头节点和循环的介绍 单链表中一个节点存储数据和指向下一个节点的指针而双向链表除了上述两个内容还包括了指向上一个节点的指针 带头的双向链表是指在双向链表的最前端添加了一个额外的节点这个节点被称为头节点哨兵节点但它一般不用于存储实际的数据或者可以说存储的数据不被使用。头节点的主要目的是为了简化链表操作的逻辑避免在处理链表的开始和结束位置时需要进行特殊的条件判断。 在没有头节点的普通双向链表中如果链表为空则链表的第一个节点head pointer直接为NULL这使得插入和删除操作时需要分别检查特定情况如链表是否为空、是否在链表开始或结束位置进行操作等。
循环链表即最后一个节点指向下一个节点的指针并不指向空而是指向头结点且头结点的指向上一个节点的指针也并不指向空而是指向最后一个节点
简单介绍之后我们就来讲解双向循环链表的各个细节吧
构建双向链表
typedef int LTDatatype;typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDatatype val;
}LTNode;这里typedef int LTDatatype;我们多次提到为类型抽象
构建的节点中每个节点包括两个指针 struct ListNode* next; 这是一个指针指向下一个ListNode节点。在链表中每个节点通过这样的next指针连接到下一个节点。对于链表的最后一个节点这个指针通常设为NULL表示没有后续节点。但在循环链表的情况下最后一个节点的next指针会指向链表的第一个节点形成一个闭环。 struct ListNode* prev; 这是另一个指针指向前一个ListNode节点。在双向链表中除了能够向前遍历我们还可以通过这个prev指针向后遍历链表。对于链表的第一个节点这个指针在非循环链表中通常设为NULL表示没有前驱节点**。而在循环链表中第一个节点的prev指针会指向链表的最后一个节点。**
节点的构建
我们首先定义一个函数
LTNode* CreatNode(LTDatatype x)与单链表不同的是这个函数多了一个指向前一个节点的指针其他内容均相同
LTNode* CreatNode(LTDatatype x)
{LTNode* newnode (LTNode*)malloc(sizeof(LTNode));if (newnode NULL){perror(malloc fail);exit(-1);}newnode-val x;newnode-next NULL;newnode-prev NULL;return newnode;
}初始化双向循环链表空链表 在双向循环链表中空链表的标志性质是其头节点的 next 和 prev指针都指向它自身。即使是空的链表依然保持着循环的特性但它不包含任何数据节点只有这一个特殊的头节点 这里有两种初始化的形式
void LTInit(LTNode** phead)
{*phead (LTNode*)malloc(sizeof(LTNode)); if (*phead ! NULL) {(*phead)-next *phead;(*phead)-prev *phead; }
}phead 代表指向链表的“头节点”的指针
在这个初始化函数中新创建的链表头节点的 next 和 prev 指针都被设置为指向自身形成一个空的双向循环链表这里用了二级指针是因为我们对phead进行了改变对指针进行改变则需要二级指针 这种方法我们初始化格式如下首先创造一个plist结构体指针再传参
LTNode* plist;
LTInit(plist);LTNode* LTInit2() {LTNode* phead (LTNode*)malloc(sizeof(LTNode));if (phead ! NULL) {phead-prev phead;phead-next phead;}return phead;
}在这个实现中LTInit函数不接受任何参数而是直接创建并初始化一个新的头节点使其prev和next指针都指向自己从而形成一个空的双向循环链表。这样设计的好处是简化了链表的初始化过程你只需要调用LTInit来获取一个新的链表头节点即可 这种方法我们直接用plist接收返回值即可
LTNode* plistLITnit2();销毁双向链表
void ListDestroy(LTNode* phead) {if (phead NULL) {return;}// 由于是循环链表我们需要一个指针指向第一个节点LTNode* current phead-next;// 如果链表不只是头节点自己循环即有实际数据节点if (current ! phead) {do {LTNode* temp current;current current-next; // 移动到下一个节点free(temp); // 释放当前节点内存} while (current ! phead);}// 最后释放头节点内存如果头节点是哨兵节点并且是动态分配的free(phead);
}函数首先检查传入的链表是否为空。如果不为空它会进入一个 do-while 循环这个循环确保至少运行一次即使链表中只有一个节点头节点 在循环内部它会释放当前节点的内存并移动到下一个节点直到它循环回到头节点。最后它释放头节点的内存
链表的打印
在单链表中我们进行循环打印的判断条件是最后一个节点的指针是否指向NULL而在双向循环链表中没有空指针我们的判断条件也有所不同
void LTPrint(LTNode* phead) {if (phead NULL || phead-next phead) {return;}LTNode* current phead-next;while (current ! phead) { printf(%d , current-val); current current-next; }printf(\n);
}首先
if (phead NULL || phead-next phead) {return;
}这串代码是判断链表是否为空或者链表是否只有一个头结点如果是则没有数据可打印直接返回
遍历链表:
LTNode* current phead-next;
while (current ! phead) { printf(%d , current-val); current current-next;
}这部分代码初始化一个新指针 current 指向链表的第一个节点即 phead-next然后进入一个 while 循环。在循环中只要 current 不指回 phead它就打印当前节点的值并移动到下一个节点。这个循环确保了所有节点都被访问一次。
注意由于它从 phead-next 开始phead 本身不存储有效数据或者说是一个哨兵节点
双向链表头尾的插与删
尾插
void LTPushBack(LTNode* phead, LTDatatype x) {LTNode* newnode CreatNode(x);if (phead NULL) {return;}newnode-next phead; newnode-prev phead-prev;phead-prev-next newnode;phead-prev newnode;
}我们构建newnode
newnode的next指向头结点 newnode-next phead;原来的phead的prev指针指向倒数第二个节点那么newnode的前一个指针则为初始时phead的prev指针newnode-prev phead-prev;现在更新倒数第二个节点的下一个指针原来指向头指针现在指向newnodephead-prev-next newnode;最后更改phead的prev指针指向尾部的newnodephead-prev newnode;
测试代码如下
尾删
void LTPopBack(LTNode* phead) {if (phead NULL || phead-next phead) {return;}LTNode* tail phead-prev; LTNode* tailprev tail-prev; // 断开当前末尾节点与链表的连接形成新的末尾tailprev-next phead;phead-prev tailprev;// 释放原末尾节点占用的内存free(tail);
}首先判断是否为空链表或者只有哨兵节点如果是则没有值可以删除直接返回找到尾部节点tail即头结点的前一个指针指向的节点再找到tail前面的节点即预期的尾节点将这个节点的下一个指针指向头结点并将头节点的前一个指针指向这个节点将tail这个尾部节点内存释放
测试代码如下:
头插
void LTPushFront(LTNode* phead, LTDatatype x) {LTNode* newnode CreatNode(x); if (phead NULL) {return;}newnode-next phead-next; newnode-prev phead; phead-next-prev newnode; phead-next newnode;
}首先判断链表是否为空为空直接返回新节点的next指针指向原来头节点的下一个节点newnode-next phead-next;新节点的prev指针指向头结点newnode-prev phead;接着更新头节点之后的节点的prev指针以及头节点的next指针 - 原来头节点之后的节点的prev指针现在应该指向新节点phead-next-prev newnode; - 头节点的next指针现在应该指向新节点phead-next newnode;
我们更新了四个指针新节点的前后指针头结点的next指针后一个节点的prev指针
测试代码
头删
void LTPopFront(LTNode* phead) {if (phead NULL || phead-next phead) {return;}LTNode* first phead-next;phead-next first-next;first-next-prev phead;free(first);
}首先检查链表是否为空或者只有哨兵节点找到要删除的节点它是头节点的下一个节点LTNode* first phead-next;更新头节点的next指向被删除节点的下一个节点phead-next first-next;更新新的第一个有效数据节点的prev指向头节点first-next-prev phead;最后释放被删除节点所占用的内存
测试代码
查找特定节点
LTNode* ListFind(LTNode* phead, int x) {if (phead NULL || phead-next phead) {return NULL;}LTNode* current phead-next; while (current ! phead) { if (current-val x) {return current;}current current-next; }return NULL;
}如果链表为空或者只有哨兵节点直接返回由于第一个节点没有有效数据我们可以从 phead 的下一个节点开始遍历在这个实现中我们从哨兵节点的下一个节点开始遍历即从链表的第一个实际数据节点开始。循环继续执行直到 current 指针再次回到哨兵节点 phead。如果找到一个节点的值与 x 相等函数返回该节点的指针。如果遍历完所有节点都没有找到则返回 NULL。
在指定位置前插入数据
void ListInsert(LTNode* pos, LTDatatype x)
{if (pos NULL){return;}LTNode* posprev pos-prev;LTNode* newnode CreatNode(x);posprev-next newnode;newnode-prev posprev;newnode-next pos;pos-prev newnode;
}找到pos前面的节点posprev构建新节点posprev的next指针指向newnodenewnode的prev指针指向posprevnext指针指向pospos的前一个指针指向newnode
测试代码在1 2 3 4 5的3前面插入8首先获得3节点的地址在传入插入函数中 如果再哨兵节点位置往前插入则相当于尾插
删除pos节点
我们假设pos不为哨兵节点
void ListErase(LTNode* pos) {if (pos NULL) {return;}pos-prev-next pos-next;pos-next-prev pos-prev;free(pos);
}这个代码就非常简单了改变指针后将空间释放
测试代码删除1 2 3 4 5中的3 这里注意置空temp
总结
对比于顺序表双向带头循环链表有以下优势
在任意位置添加或删除元素的时间复杂度都是O(1)按需要进行申请空间没有浪费
不足之处
下标随机访问不方便需要遍历链表时间复杂度为O(N);
顺序表和双向带头链表根据特定的使用场景和需求具有各自的优势和劣势。选择哪种数据结构取决于对性能、内存使用、以及操作灵活性的具体要求。
本节内容到此结束感谢大家的阅读
