1. 首页
  2. 文章中心
  3. 数据结构与算法

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

51 阅读 0 评论
我是靠谱客的博主 精明大地，最近开发中收集的这篇文章主要介绍【数据结构与算法】双向链表C语言描述【数据结构与算法】双向链表，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

链表的分类

  1. 单向、双向
  2. 带头单链表、不带头链表
  3. 循环、非循环

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

  1. 无头单向非循环链表

    在这里插入图片描述

  2. 带头双向循环链表

    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;
}

清理数据结点

  1. 指针cur指向当前要清理的结点，next用于保存下一个待清理结点的地址

    在这里插入图片描述

  2. 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;
}

链表的打印

​ 思路：

  1. 结束条件和单链表不一样，单链表是在打印结点指向NULL时结束打印，但现在是循环链表，不存在指向NULL的问题，因此，结束条件可改为当cur(进行结点打印的指针)等于phead时结束打印

  2. 头结点phead是哨兵位结点，不储存信息，因此从phead的下一个指针开始打印

链表的打印代码
assert(phead);
ListNode* cur = phead->next;

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

尾插

在这里插入图片描述

  1. 进行尾插，首先要找到尾结点，由上图可知双链表头结点的prev指针指向的就是尾结点

    ListNode* tail = phead->prev;

  2. 尾结点找到后，我们来插入新的结点，首先我们将新结点和尾结点进行链接，如下图红色箭头

    在这里插入图片描述

    tail->next = newnode;
newnode->prev = tail;

  3. 头结点与新结点链接

    在这里插入图片描述

    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;
}

尾删

思路：

  1. 确定尾结点

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

    在这里插入图片描述

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

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

    在这里插入图片描述

  3. 删除尾结点

    在这里插入图片描述

尾删代码

//尾删
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;
	}
}

头插

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

在这里插入图片描述

思路：

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

    在这里插入图片描述

  2. 新结点与phead链接

    在这里插入图片描述

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

  3. 新结点与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;
}

头删

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

在这里插入图片描述

  1. 创建两个指针first和second

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

    在这里插入图片描述

  2. 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();
}

最后

以上就是精明大地为你收集整理的【数据结构与算法】双向链表C语言描述【数据结构与算法】双向链表的全部内容，希望文章能够帮你解决【数据结构与算法】双向链表C语言描述【数据结构与算法】双向链表所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(34)

相关文章

【数据结构】插入类排序直接插入排序希尔排序
【数据结构】插入类排序直接插入排序希尔排序
数据结构——插入排序（直接插入排序，希尔排序java）二.希尔排序
数据结构——插入排序（直接插入排序，希尔排序java）二.希尔排序
【Java数据结构和算法】006-链表：双向链表目录0、警醒自己一、双向链表概述二、双链表应用实例
【Java数据结构和算法】006-链表：双向链表目录0、警醒自己一、双向链表概述二、双链表应用实例
数据结构与算法学习：3.双向链表1 双链表2.双向链表的相关操作及实现3 完整代码和运行测试4 总结
数据结构与算法学习：3.双向链表1 双链表2.双向链表的相关操作及实现3 完整代码和运行测试4 总结
【数据结构与算法】双向链表C语言描述【数据结构与算法】双向链表
【数据结构与算法】双向链表C语言描述【数据结构与算法】双向链表
Python全栈（二）数据结构和算法之5.双向链表的实现和栈的实现一、双向链表的定义、判断是否为空、长度&遍历
Python全栈（二）数据结构和算法之5.双向链表的实现和栈的实现一、双向链表的定义、判断是否为空、长度&遍历
Python数据结构与算法系列三：链表1. 链表定义2. 单向链表3. 双向链表4. 单向循环链表
Python数据结构与算法系列三：链表1. 链表定义2. 单向链表3. 双向链表4. 单向循环链表
数据结构与算法学习五：双链表的增、删、改、查前言一、双链表的应用实例二、单链表的缺点分析三、双链表增删改查思路四、代码实现4.1 项目结构
数据结构与算法学习五：双链表的增、删、改、查前言一、双链表的应用实例二、单链表的缺点分析三、双链表增删改查思路四、代码实现4.1 项目结构

评论列表共有 0 条评论

立即
投稿
返回
顶部