数据结构--双向链表的实现(复习)

2022/1/27 23:04:57

本文主要是介绍数据结构--双向链表的实现(复习),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

相比于之前的顺序表和单链表,双向链表的实现更复杂,但是到了实操环节则更简单。就好比高速公路相比一般的柏油马路更难修建,但是汽车在高速公路上却可以跑得更快。

需要特别注意的是,双向带头链表为空的条件是head->next=next。head节点处不存储数据,head节点充当哨兵位节点。当双向链表中只有一个哨兵位节点时,说明双向链表为空。

结构体的定义:双向链表有两个指针,和一个数值。定义结构体时考虑这三个部分即可。

typedef int LTDateType;
typedef struct ListNode
{
	LTDatetype data;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;

哨兵位头节点的初始化:需要初始化一个头节点,以便后续构造链表。与所有节点的初始化相同,首先都需要向内存申请一块结构体类型的空间。然后将前后指针置空即可。(该点是一个哨兵位头节点,因此不需要赋值)

LTNode* ListInit()
{
	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
	phead->next = NULL;
	phead->prev = NULL;
	return phead;//初始化一个头节点自然是要用的,需要返回这个节点的地址以便后续使用
}

节点的初始化:与哨兵位头节点的初始化类似,只不过需要额外为节点赋值。

LTNode* BuyListNode(LTDateType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	newnode->prev = NULL;
	newnode->next = NULL;
	newnode->data = x;
	return newnode;
}

打印双向链表:

void ListPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;//这里要注意,phead是哨兵位节点,想要从第一个节点开始打印,需要找哨兵位节点的下一个节点
	while (cur)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

尾插一个节点:又涉及到节点的增加,首先就要申请一块空间,最后面的四条语句画图即可。

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

尾删一个节点:

void ListPopBack(LTNode* phead)
{
	assert(phead);//想要尾删,首先要有东西可删,因此前面两条语句就是判断该双向链表中有没有大于等于1个节点,需要注意的是两条语句的逻辑关系不能颠倒。
	assert(phead->next != phead);
	LTNode* tail = phead->prev;
	phead->prev = tail->prev;
	tail->prev->next = phead;
	free(tail);//本函数中的所有指针都各得其所,没必要专门置空,释放掉空间即可
}

头插一个节点:需要注意的是,头插节点也需要插在哨兵位节点和原先的头节点之间。

void ListPushFront(LTNode* phead, LTDateType x)
{
	assert(phead);
	LTNode* newnode = BuyListNode(x);
	phead->next->prev = newnode;
	newnode->prev = phead;
	newnode->next = phead->next;
	phead->next = newnode;
}

头删一个节点:

void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next);//和尾删一样,都需要保证双向链表中至少有一个节点
	LTNode* next = phead->next;
	LTNode* nextnext = next->next;
	nextnext->prev = phead;
	phead->next = nextnext;
	free(next);
}

寻找一个值为x的节点:

LTNode* ListFind(LTNode* phead, LTDateType x)
{
	assert(phead);
	assert(phead->next);
	LTNode* cur = phead->next;
	while (cur!=phead)//当cur=phead时,就说明双向链表已经遍历一遍了
	{
		if (cur->data = x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

在特定的位置插入一个值为x的节点:

void ListInsert(LTNode* pos, LTDateType x)
{
	assert(pos);//这次不用断言头节点了,因为插入,头节点为空也无所谓
	LTNode* newnode = BuyListNode(x);
	LTNode* posPrev = pos->prev;//不同于单链表想要找一个节点的话只能从前往后找(向一个方向找),双线链表找一个节点的前一个节点的话直接找这个节点的prev即可
	newnode->next = pos;
	pos->prev = newnode;
	posPrev->next = newnode;
	newnode->prev = posPrev;
}



这篇关于数据结构--双向链表的实现(复习)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程