本文主要是介绍数据结构--带头双向循环链表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
目录
一、前言:
单链表存在缺陷:不能找到前驱,即不能从后往前找数据。
解决方法:双向链表。
二、带头双向循环链表:
1.实现的接口总数
2.建立链表及上述接口
(1)链表的建立
(2)创立新节点的函数
(3)初始化函数
(4)销毁函数
(5)打印函数
(6)尾插函数
(7).头插函数
(8).头删函数
(9)尾删函数
(10)查找函数
(11)pos位置之前插入x的函数
(12)删除pos位置的值的函数
三、总结:
1. 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了。
一、前言:
单链表存在缺陷:不能找到前驱,即不能从后往前找数据。
解决方法:双向链表。
二、带头双向循环链表:
1.实现的接口总数
//初始化函数
ListNode* ListInit();
//摧毁函数
void ListDestory(ListNode* phead);
//打印函数
void ListPrint(ListNode* phead);
//尾插函数
void ListPushBack(ListNode* phead, LTDataType x);
//头插函数
void ListPushFront(ListNode* phead, LTDataType x);
//头删函数
void ListPopFront(ListNode* phead);
//尾删函数
void ListPopBack(ListNode* phead);
//查找函数
ListNode* ListFind(ListNode* phead, LTDataType x);
// pos位置之前插入x
void ListInsert(ListNode* pos, LTDataType x);
// 删除pos位置的值
void ListErase(ListNode* pos);
2.建立链表及上述接口
(1)链表的建立
typedef int LTDataType;
// 带头双向循环 -- 最有链表结构,任意位置插入删除数据都是O(1)
//除了查找的空间复杂度是O(N)
typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType data;
}ListNode;
(2)创立新节点的函数
//创建新节点的函数
ListNode* BuyListNode(LTDataType x)
{ ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}
(3)初始化函数
//初始化函数
ListNode* ListInit()
{ListNode* phead = BuyListNode(0);phead->next = phead;phead->prev = phead;return phead;
}
(4)销毁函数
//摧毁函数
void ListDestory(ListNode* phead)
{assert(phead);ListNode* cur = phead->next;while (cur != phead){ListNode* next = cur->next;free(cur);cur = next;}free(phead);phead = NULL;
}
(5)打印函数
//打印函数,和单链表不一样的是条件不是空指针停止
//而是一个循环从phead->next到phead之间都遍历才停止
void ListPrint(ListNode* phead)
{assert(phead);ListNode* cur = phead->next;while (cur != phead){printf("%d ", cur->data);cur = cur->next;}printf("\n");
}
(6)尾插函数
//尾插函数
void ListPushBack(ListNode* phead, LTDataType x)
{assert(phead);ListNode* tail = phead->prev;ListNode* newnode = BuyListNode(x);tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;
}
(7)头插函数
//头插函数
void ListPushFront(ListNode* phead, LTDataType x)
{assert(phead);ListNode* first = phead->next;ListNode* newnode = BuyListNode(x);first->prev = newnode;newnode->next = first;phead->next = newnode;newnode->prev = phead;
}
(8)头删函数
//头删函数
void ListPopFront(ListNode* phead)
{assert(phead);//assert(phead->next!=phead);//防止头结点被删//ListNode* first = phead->next;//ListNode* second= first->next;删除first后连接建立双向链表//phead->next = second;//second->prev = phead;//free(first);//first = NULL;ListErase(phead->next);
}
(9)尾删函数
//尾删函数
void ListPopBack(ListNode* phead)
{assert(phead);/*assert(phead->next != phead);ListNode* tail = phead->prev;ListNode* prev = tail->prev;prev->next = phead;phead->prev = prev;free(tail);tail = NULL;*/ListErase(phead->prev);
}
(10)查找函数
//查找函数
ListNode* ListFind(ListNode* phead, LTDataType x)
{assert(phead);ListNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;}
(11)pos位置之前插入x的函数
// pos位置之前插入x
void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* prev = pos->prev;ListNode* newnode = BuyListNode(x);// prev newnode posprev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;}
(12)删除pos位置的值的函数
// 删除pos位置的值
void ListErase(ListNode* pos)
{assert(pos);ListNode* prev = pos->prev;ListNode* next = pos->next;prev->next = next;next->prev = prev;free(pos);}
三、总结:
1. 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了。
这篇关于数据结构--带头双向循环链表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!