• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

数据结构之双向带头循环链表

互联网 diligentman 5小时前 2次浏览

双向带头循环链表

  • 一、双向带头循环链表的优劣势
  • 二、双向带头循环链表的实现
    • 一、定义结构体
    • 二、创建节点函数
    • 三、初始化链表
    • 四、链表的尾插
    • 五、链表的头插
    • 六、链表的尾删
    • 七、链表的头删
    • 八、链表的查找
    • 九、链表的插入
    • 十、链表的打印

一、双向带头循环链表的优劣势

结构复杂,但由于结点信息中多包含了一个指向上一个结点的指针,这样操作起来就特别方便,它弥补了单链表的缺点,使得链表更加灵活、实用。
数据结构之双向带头循环链表

二、双向带头循环链表的实现

一、定义结构体

typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* next;
	struct ListNode* prev;
}; 

二、创建节点函数

struct ListNode* BuyListNode(LTDataType x)
{
	struct ListNode* Node = (struct ListNode*)malloc(sizeof(struct ListNode));
	Node->next = NULL;
	Node->prev = NULL;
	Node->data = x;
	return Node;
}

三、初始化链表

struct ListNode* ListInit()
{
	struct ListNode* phead = BuyListNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

四、链表的尾插

这点就可以体现出双向循环带头链表的好处了,不需要进行遍历,只需要改变指针的位置即可。

void  ListPushBack(struct ListNode* phead, LTDataType x)
{
	assert(phead);
	struct ListNode* tail = phead->prev;
	struct ListNode* newnode = BuyListNode(x);
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

五、链表的头插

头插从第二个节点开始,也就是第一个保存有效数据的节点。

void ListPushFront(struct ListNode* phead, LTDataType x)
{
	assert(phead);
	struct ListNode* newnode = BuyListNode(x);
	struct ListNode* first = phead->next;
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;
}

六、链表的尾删

void ListPopBack(struct ListNode* phead)
{
	assert(phead);
	assert(phead != phead->next);
	struct ListNode* tail = phead->prev;
	struct ListNode* second = tail->prev;
	free(tail);
	tail = NULL;
	second->next = phead;
	phead->prev = second;
}

七、链表的头删

头删仍然不改变第一个节点,从第二个节点开始。

void ListPopFront(struct ListNode* phead)
{
	assert(phead);
	assert(phead != phead->next);
	struct ListNode* first = phead->next;
	struct ListNode* firstNext = first->next;
	free(first);
	first = NULL;
	phead->next = firstNext;
	first->prev = phead;
}

八、链表的查找

遍历找,与单链表类似。

struct ListNode* ListFind(struct ListNode* phead, LTDataType x)
{
	assert(phead);
	struct ListNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

九、链表的插入

与头插的方法类似。

void ListInsert(struct ListNode* pos, LTDataType x)
{
	assert(pos);
	struct ListNode* newnode = BuyListNode(x);
	struct ListNode* prev = pos->prev;
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}

十、链表的打印

这里我们要注意结束条件,是等于第一个节点。

void ListPrint(struct ListNode* phead)
{
	assert(phead);
	struct ListNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d-->", cur->data);
		cur = cur->next;
	}
	printf("NULLn");
}


程序员灯塔
转载请注明原文链接:数据结构之双向带头循环链表
喜欢 (0)