赞
踩
实际中链表的结构非常多样,以下的情况组合起来就有8种链表结构,
今天我们将学习链表中最复杂的一种结构——带头双向循环链表,虽然此链表结构复杂,但他的实现反而比带头单向非循环链表要简单,形如下图的链表,即为带头双向循环链表。
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> //节点的定义 typedef int LTDataType; typedef struct ListNode { struct ListNode* prev; struct ListNode* next; LTDataType data; }LTNode; //初始化链表 LTNode* LTInit(); //头插 void LTPushFront(LTNode* phead, LTDataType x); //尾插 void LTPushBack(LTNode* phead, LTDataType x); //头删 void LTPopFront(LTNode* phead); //尾删 void LTPopBack(LTNode* phead); //判空 bool LTEmpty(LTNode* phead); //打印链表 void Print(LTNode* phead); //查找 LTNode* LTFind(LTNode* phead, LTDataType x); // 在pos之前插入节点 void LTInsert(LTNode* pos, LTDataType x); // 删除pos位置的节点 void LTErase(LTNode* pos); //销毁链表 void LTDestroy(LTNode* phead);
#include "list.h" //节点的创建 LTNode* BuyNewNode(LTDataType x) { LTNode* node = (LTNode*)malloc(sizeof(LTNode)); if (node == NULL) { perror("malloc"); return NULL; } node->data = x; node->next = NULL; node->prev = NULL; return node; } //初始化链表 LTNode* LTInit() { LTNode* phead = BuyNewNode(-1); phead->next = phead; phead->prev = phead; return phead; } //头插 void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = BuyNewNode(x); LTNode* first = phead->next; newnode->next = first; newnode->prev = phead; first->prev = newnode; phead->next = newnode; } //尾插 void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = BuyNewNode(x); LTNode* tail = phead->prev;//尾结点是头节点的prev所指的节点 newnode->next = phead; newnode->prev = tail; tail->next = newnode; phead->prev = newnode; } //头删 void LTPopFront(LTNode* phead) { assert(phead); assert(!LTEmpty(phead)); //去掉第一个节点,即phead->next LTNode* first = phead->next; LTNode* newfirst = first->next; phead->next = newfirst; newfirst->prev = phead; free(first); } //尾删 void LTPopBack(LTNode* phead) { assert(phead); assert(!LTEmpty(phead)); //去掉尾结点,即phead的prev LTNode* tail = phead->prev; LTNode* newtail = tail->prev; newtail->next = phead; phead->prev = newtail; free(tail); } //判空 bool LTEmpty(LTNode* phead) { assert(phead); if (phead->next == phead) return true; else return false; } //打印链表 void Print(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { printf("<-%d->", cur->data); cur = cur->next; } } //查找 LTNode* LTFind(LTNode* phead, LTDataType x) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { if (cur->data == x) return cur; cur = cur->next; } return NULL; } // 在pos之前插入节点 void LTInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* node = BuyNewNode(x); node->next = pos; node->prev = pos->prev; pos->prev->next = node; pos->prev = node; } //删除pos位置的节点 void LTErase(LTNode* pos) { assert(pos); pos->prev->next = pos->next; pos->next->prev = pos->prev; free(pos); } //销毁链表 void LTDestroy(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { LTNode* next = cur->next; free(cur); cur = next; } free(phead); }
其实双向链表的实现很容易,只要控制节点prev
和next
的指针指向即可,由于头节点head
的存在,它也无需像单链表那样找尾。为了避免出错,在编写代码时最好画图参考。
LTNode* LTInit()
{
LTNode* phead = BuyNewNode(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}
创建一个节点(我们假设-1为head的值,是一个无意义的数据),让它的头尾都指向自己,如下图所示,这样我们就创建好了一个带哨兵位的头结点。
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = BuyNewNode(x);
LTNode* first = phead->next;
newnode->prev = phead;
newnode->next = first;
phead->next = newnode;
first->prev = newnode;
}
下面我们画图讲解:
先将新建节点链接入链表之中,再改变原链表的指针指向新节点,也可以选择改变原有指针后,再改变插入节点的指针,只要画图明白其中的步骤即可写出正确的代码。
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = BuyNewNode(x);
LTNode* tail = phead->prev;//尾结点是头节点的prev所指的节点
newnode->next = phead;
newnode->prev = tail;
tail->next = newnode;
phead->prev = newnode;
}
指针改变步骤如下图所示:
void LTPopFront(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
//去掉第一个节点,即phead->next
LTNode* first = phead->next;
LTNode* newfirst = first->next;
phead->next = newfirst;
newfirst->prev = phead;
free(first);
}
标记好原链表节点的位置,即可对原链表的指针进行修改,最后free掉第一个节点。
void LTPopBack(LTNode* phead)
{
assert(phead);
assert(!LTEmpty(phead));
//去掉尾结点,即phead->prev
LTNode* tail = phead->prev;
LTNode* newtail = tail->prev;
newtail->next = phead;
phead->prev = newtail;
free(tail);
}
原理如头删,但此时要删除的节点是尾节点。
bool LTEmpty(LTNode* phead)
{
assert(phead);
if (phead->next == phead)
return true;
else
return false;
}
链表为空的意思是在该链表中除了哨兵位之外没有其他的节点,所以我们只要判断phead的next是否指向他自己即可。
void Print(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
printf("<-guard->");
while (cur != phead)
{
printf("<-%d->", cur->data);
cur = cur->next;
}
}
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
return cur;
cur = cur->next;
}
return NULL;
}
当找到指定值的节点时,返回该节点,反之返回NULL
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* node = BuyNewNode(x);
node->next = pos;
node->prev = pos->prev;
pos->prev->next = node;
pos->prev = node;
}
插入节点其实原理和尾插一样,只要理解了尾插的过程,这一操作也不难实现。
void LTErase(LTNode* pos)
{
assert(pos);
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
free(pos);
}
与头删或尾删的原理相同,都是改变原有链表节点的指针,free掉要删除的节点。
void LTDestroy(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
LTNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
}
逐个free掉节点,最终free掉头结点,如果想要给头结点置空的话应该在调用销毁函数的程序中置空,因为这里传入的是一级指针,在销毁函数中置空应该要传入二级指针此置空才真正有效,但是为了和前面传参类型相同,我们这里仍旧选择一级指针。
上述讲解过程中,我们知道头插、尾插的原理其实和插入函数是一样的,头删、尾删的原理和删除函数的原理是一样的,那么我们可以将链表的实现简化成下述代码:
#include "list.h" //创建节点 LTNode* BuyNewNode(LTDataType x) { LTNode* node = (LTNode*)malloc(sizeof(LTNode)); if (node == NULL) { perror("malloc"); return NULL; } node->data = x; node->next = NULL; node->prev = NULL; return node; } //初始化 LTNode* LTInit() { LTNode* phead = BuyNewNode(-1); phead->next = phead; phead->prev = phead; return phead; } //头插 void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTInsert(phead->next, x); } //尾插 void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTInsert(phead, x); } //尾删 void LTPopBack(LTNode* phead) { assert(phead); assert(!LTEmpty(phead)); LTErase(phead->prev); } //头删 void LTPopFront(LTNode* phead) { assert(phead); assert(!LTEmpty(phead)); LTErase(phead->next); } //判空 bool LTEmpty(LTNode* phead) { assert(phead); if (phead->next == phead) return true; else return false; } //打印 void Print(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { printf("<-%d->", cur->data); cur = cur->next; } } //查找 LTNode* LTFind(LTNode* phead, LTDataType x) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { if (cur->data == x) return cur; cur = cur->next; } return NULL; } //在pos前插入节点 void LTInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* node = BuyNewNode(x); node->next = pos; node->prev = pos->prev; pos->prev->next = node; pos->prev = node; } //删除节点 void LTErase(LTNode* pos) { assert(pos); pos->prev->next = pos->next; pos->next->prev = pos->prev; free(pos); } //链表销毁 void LTDestroy(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { LTNode* next = cur->next; free(cur); cur = next; } free(phead); }
#include "list.h" void test() { LTNode* phead=LTInit(); LTPushBack(phead,1); LTPushBack(phead,2); LTPushFront(phead,3); LTPushFront(phead,4); LTPushFront(phead,5); LTPushFront(phead,6); printf("头插、尾插的打印:\n"); Print(phead); printf("\n"); LTPopBack(phead); LTPopFront(phead); printf("头删、尾删的打印:\n"); Print(phead); printf("\n"); LTNode* node = LTFind(phead, 3); LTInsert(node, 10); printf("pos前插入节点\n"); Print(phead); printf("\n"); LTErase(node); printf("删除pos节点:\n"); Print(phead); printf("\n"); LTDestroy(phead); phead = NULL; } int main() { test(); return 0; }
以上就是带头双向循环链表实现的所有内容,希望对您的学习有帮助。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。