【数据结构与算法】双向链表C语言描述

admin • 2021-12-18 20:31 • C/C++

【数据结构与算法】双向链表

链表的分类

单向、双向
带头单链表、不带头链表
循环、非循环

在我们平时的学习中，最常用的两种链表：

无头单向非循环链表
带头双向循环链表

head的是哨兵位头结点，不存储数据

下文主要讲解第二种带头双向链表

创建结构体

双向链表中，每个结点除了包含下个节点的地址外，还包含前一个结点的地址，因此我们需要分别创建两个指针next和prev

创建结构体代码

typedef int LTDataType;

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

链表初始化

方法一：要完成初始化，我们需要把phead的地址传给相应的初始化函数，只有址传递才能改变phead的值，下面例子则是错误的：

下面我们来看看调用部分的phead和传入函数后的phead的地址是否相同

调用部分的phead地址如下

传入函数后的phead的地址如下

可见此时phead的地址不一样，因此无法对传入的phead指针变量进行修改，正确的操作应该是传入phead的地址，如下图

此时传入的即为指针变量的地址，可以实现对传入指针变量的修改（初始化）了

初始化函数代码(方法一)

//初始化链表
void ListInit(ListNode** pphead)
{
	*pphead = BuyListNode(0);
	(*pphead)->next = *pphead;
	(*pphead)->prev = *pphead;

	return pphead;
}

**方法二：**这种方法比较简单，不用传入二级指针，直接返回初始化函数创建的头结点赋值给phead即可完成初始化

ListNode* phead = ListInit();

初始化函数代码(方法二)

//初始化链表
ListNode* ListInit()
{
	ListNode* phead = BuyListNode(0);
	phead->next = phead;
	phead->prev = phead;

	return phead;
}

清理数据结点

指针cur指向当前要清理的结点，next用于保存下一个待清理结点的地址
cur==phead的时候的时候，结束清理，且对phead初始化,以确保头结点继续使用

phead->next = phead;
phead->prev = phead;

清理数据结点代码

void ListClear(ListNode* phead)
{
	assert(phead);

	//清理所有数据结点，保留头结点，可以继续使用
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}

	phead->next = phead;
	phead->prev = phead;
}

销毁链表

上面我们讲的是对链表的结点进行清理，但如果这个链表不再使用时，需要将头结点也一起销毁

销毁链表代码

//销毁链表
void ListDestroy(ListNode* phead)
{
	assert(phead);

	ListClear(phead);
	free(phead);
}

创建新结点

ListNode* BuyListNode(LTDataType x)
{
	ListNode*node = (ListNode*)malloc(sizeof(ListNode));
	//初始化
	node->next = NULL;
	node->prev = NULL;
	node->data = x;

	return node;
}

链表的打印

思路：

结束条件和单链表不一样，单链表是在打印结点指向NULL时结束打印，但现在是循环链表，不存在指向NULL的问题，因此，结束条件可改为当cur(进行结点打印的指针)等于phead时结束打印
头结点phead是哨兵位结点，不储存信息，因此从phead的下一个指针开始打印

链表的打印代码

assert(phead);
ListNode* cur = phead->next;

while (cur != phead) //结束条件
{
	print("%d ", cur->data);
	cur = cur->next;
}

尾插

进行尾插，首先要找到尾结点，由上图可知双链表头结点的prev指针指向的就是尾结点
```
ListNode* tail = phead->prev;
```
尾结点找到后，我们来插入新的结点，首先我们将新结点和尾结点进行链接，如下图红色箭头
```
tail->next = newnode;
newnode->prev = tail;
```

头结点与新结点链接

newnode->next = phead;
phead->prev = newnode;

尾插代码

//尾插
void ListPushBack(ListNode* phead, LTDataType x)
{
	assert(phead); //断言，头指针不指向NULL

	ListNode* tail = phead->prev;
	ListNode* newnode = BuyListNode(x);
	
	//进行结点的链接
	tail->next = newnode;
	newnode->prev = tail;

	newnode->next = phead;
	phead->prev = newnode;
}

尾删

思路：

确定尾结点

ListNode* tail = phead->prev;
ListNode* tailPrev = tail->prev;

tailPrev指向的结点与头结点进行链接

phead->prev = tailPrev;
tailPrev->next = phead;

删除尾结点

尾删代码


//尾删
void ListPopBack(ListNode* phead)
{
	assert(phead);
	if (phead->next == phead) //判断是否只有哨兵位头结点
	{
		return phead;
	}
	else
	{
		ListNode* tail = phead->prev;
		ListNode* tailPrev = tail->prev;

		phead->prev = tailPrev;
		tailPrev->next = phead;
		free(tail);

		return phead;
	}
}

头插

头插是指在哨兵位头结点的后面插入

思路：

定义first指针用于储存原链表中phead的后一个结点

新结点与phead链接

phead->next = newnode;
newnode->prev = phead;

新结点与first链接,头插结束

newnode->next = first;
first->prev = newnode;

头插代码

//头插
void ListPushFront(ListNode* phead, LTDataType x)
{
	assert(phead);

	ListNode* first = phead->next;
	ListNode* newnode = BuyListNode(x);

	phead->next = newnode;
	newnode->prev = phead;

	newnode->next = first;
	first->prev = newnode;
}

头删

把哨兵位结点的后一个结点删除

创建两个指针first和second

ListNode* first = phead->next;
ListNode* second = first->next;

phead与second链接,删除first

phead->next = second;
second->prev = phead;
free(first);

头删代码

//头删
void ListPopFront(ListNode* phead)
{
	assert(phead);
	assert(phead->next!=phead);

	ListNode* first = phead->next;
	ListNode* second = first->next;

	phead->next = second;
	second->prev = phead;
	free(first);
}

链表的查找

查找只要对链表遍历即可,逻辑和打印链表相似，直接上代码

链表的查找代码

//查找
ListNode* ListFind(ListNode* phead, int x)
{
	assert(phead);
	ListNode* cur = phead->next;

	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}

	return NULL;
}

插入（任意结点）

要在给定结点的前面插入（例如在d2前插入），就要先得到这个给定结点的位置，那么用查找函数确定这个结点的位置pos

后面的插入和前面所提到到两种插入大同小异，这里就不赘述了

插入（任意结点）代码

//插入（任意位置）
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* posPrev = pos->prev;
	ListNode* newnode = BuyListNode(x);

	posPrev->next = newnode;
	newnode->prev = posPrev;
    
	newnode->next = pos;
	pos->prev = newnode;
}

删除（任意结点）

删除（任意结点）代码

//删除（任意位置）
void ListErase(ListNode* pos)
{
	assert(pos);
	ListNode* posPrev = pos->prev;
	ListNode* posNext = pos->next;

	free(pos);
	posPrev->next = posNext;
	posNext->prev = posPrev;
}

双链表完整代码

List.h文件

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>

typedef int LTDataType;

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

//void ListInit(ListNode** phead);
ListNode* ListInit();
void ListClear(ListNode* phead);
void ListDestroy(ListNode* phead);
ListNode* BuyListNode(LTDataType x);
void ListPrint(ListNode* phead);

void ListPushBack(ListNode* phead, LTDataType x);
void ListPopBack(ListNode* phead);
void ListPushFront(ListNode* phead, LTDataType x);
void ListPopFront(ListNode* phead);

ListNode* ListFind(ListNode* phead, int x);
void ListInsert(ListNode* pos, LTDataType x);
void ListErase(ListNode* pos);

List.c文件

#include "List.h"

//初始化链表
ListNode* ListInit()
{
	ListNode* phead = BuyListNode(0);
	phead->next = phead;
	phead->prev = phead;

	return phead;
}

//创建新结点
ListNode* BuyListNode(LTDataType x)
{
	ListNode*node = (ListNode*)malloc(sizeof(ListNode));
	node->next = NULL;
	node->prev = NULL;
	node->data = x;

	return node;
}

//清理数据结点
void ListClear(ListNode* phead)
{
	assert(phead);

	//清理所有数据结点，保留头结点，可以继续使用
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}

	phead->next = phead;
	phead->prev = phead;
}

//销毁链表
void ListDestroy(ListNode* phead)
{
	assert(phead);

	ListClear(phead);
	free(phead);
}

//打印
void ListPrint(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;

	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("n");
}

//尾插
void ListPushBack(ListNode* phead, LTDataType x)
{
	assert(phead); //断言，头指针不指向NULL

	ListNode* tail = phead->prev;
	ListNode* newnode = BuyListNode(x);
	
	//进行结点的链接
	tail->next = newnode;
	newnode->prev = tail;

	newnode->next = phead;
	phead->prev = newnode;
}

//尾删
void ListPopBack(ListNode* phead)
{
	assert(phead);
	if (phead->next == phead) //判断是否只有哨兵位头结点
	{
		return phead;
	}
	else
	{
		ListNode* tail = phead->prev;
		ListNode* tailPrev = tail->prev;

		phead->prev = tailPrev;
		tailPrev->next = phead;
		free(tail);

		return phead;
	}
}

//头插
void ListPushFront(ListNode* phead, LTDataType x)
{
	assert(phead);

	ListNode* first = phead->next;
	ListNode* newnode = BuyListNode(x);

	phead->next = newnode;
	newnode->prev = phead;

	newnode->next = first;
	first->prev = newnode;
}

//头删
void ListPopFront(ListNode* phead)
{
	assert(phead);
	assert(phead->next!=phead);

	ListNode* first = phead->next;
	ListNode* second = first->next;

	phead->next = second;
	second->prev = phead;
	free(first);
}

//查找
ListNode* ListFind(ListNode* phead, int x)
{
	assert(phead);
	ListNode* cur = phead->next;

	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}

	return NULL;
}

//插入（任意位置）
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* posPrev = pos->prev;
	ListNode* newnode = BuyListNode(x);

	posPrev->next = newnode;
	newnode->prev = posPrev;
	newnode->next = pos;
	pos->prev = newnode;
}

//删除（任意位置）
void ListErase(ListNode* pos)
{
	assert(pos);
	ListNode* posPrev = pos->prev;
	ListNode* posNext = pos->next;

	free(pos);
	posPrev->next = posNext;
	posNext->prev = posPrev;
}

test.c

#include "List.h"

void TestList1()
{
	ListNode* phead = ListInit();
	ListPushBack(phead, 1);
	ListPushBack(phead, 2);
	ListPushBack(phead, 3);
	ListPushBack(phead, 4);

	ListPrint(phead);

	ListPopBack(phead);
	ListPopBack(phead);
	ListPopBack(phead);
	ListPopBack(phead);
	ListPopBack(phead);
	ListPrint(phead);

	ListPushFront(phead, 1);
	ListPushFront(phead, 2);
	ListPushFront(phead, 3);
	ListPushFront(phead, 4);
	ListPushFront(phead, 5);

	ListPrint(phead);

	ListPopFront(phead);
	ListPopFront(phead);
	ListPopFront(phead);
	ListPopFront(phead);
	ListPopFront(phead);
	ListPrint(phead);

	ListDestroy(phead);
}

void TestList2()
{
	ListNode* phead = ListInit();
	ListPushBack(phead, 1);
	ListPushBack(phead, 2);
	ListPushBack(phead, 3);
	ListPushBack(phead, 4);
	ListPrint(phead);

	ListNode* pos = ListFind(phead, 3);

	ListInsert(pos, 30);
	ListPrint(phead);

	pos = ListFind(phead, 3);
	ListErase(pos);
	ListPrint(phead);

	ListDestroy(phead);
}
void main()
{
	//TestList1();
	TestList2();
}

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。

THE END

数据结构算法

二维码

在Win10系统中，把C++程序“消失的”窗口“拽”出来显示

< <上一篇

容器：list用法及示例

下一篇>>

搜索内容