亲宝软件园·资讯

展开

C语言带头双向循环链表的示例代码

南猿北者 人气:0

前言

对于链表来说，不只有单链表这一个品种；

链表有很多种形态

按方向分：单向、双向

按带不带头：带头、不带头

按循环：循环、不循环

1、单向或则双向：

2、带头或者不带头：

3、循环或者不循环：

组合排列一下的话，链表一共有8种形态！！！

今天我们就来学习一下结构最复杂的带头双向循环链表！！！；

虽然名字听上去比较复杂，但是实现起来比单链表（全名：不带头、不循环、单向链表）更加简单，也不需要过多考虑特殊情况；
 

两种链表的比较：（上面是单链表，下面是带头双向循环链表）

结构分析

首先链表的头节点是不存储有效数据的（该节点被称为哨兵位），其次我们只需要知道改头节点的指针就能找到整个链表，并且便于对整个链表进行维护；

当然既然是双向的嘛，那节点一定有个指针域指向前一个节点，另一个指针域指向后一个节点；

那么我们的单个节点的数据结构就是：

现在我们定义了一个plist指针用来维护整个链表，根据上面说的plist就应该用来存储哨兵位的头节点的指针，那么如何表示链表为NULL的情况？

链表为空：

就是:

head->next=head;

head->prev=head;

链表的基本操作实现

创建节点

ListNode* ListCreate(LTDataType x)
{
	ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode));
	if (!NewNode)
		exit(-1);
	NewNode->val = x;
	NewNode->prev = NULL;
	NewNode->next = NULL;
	return NewNode;
}

我们在创建节点的时候就一起将数据域初始化，方标后续操作；

初始化链表

void InitDummyHead(ListNode* pHead)
{
	assert(pHead);
	pHead->prev = pHead;
	pHead->next = pHead;
}

链表销毁

// 双向链表销毁
void ListDestory(ListNode* pHead)
{
	assert(pHead);
	ListNode* cur = pHead->next;
	ListNode* next = NULL;
	while (cur!=pHead)
	{
		next = cur->next;
		free(cur);
		cur = next;
	}
	free(cur);
}

实现思路：

打印链表

除了哨兵位的节点存到是无效数据不打印外，其他节点的数据都要打印：

// 双向链表打印
void ListPrint(ListNode* pHead)
{
	assert(pHead);
	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		ListNode* next = cur->next;
		printf("%d->",cur->val);
		cur = next;
	}
	printf("NULL\n");
}

链表尾插

该链表的尾插，比单链表的尾插简单太多了，不用遍历找尾：

// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
	assert(pHead);
    ListNode* NewNode = ListCreate(x);
	ListNode* tail = pHead->prev;
	tail->next = NewNode;
	NewNode->prev = tail;
	pHead->prev = NewNode;
	NewNode->next = pHead;
}

链表尾删

由于是循环的，哨兵位的前一个节点就是尾节点，同时尾节点的前一个节点我们也不用遍历，可以很轻松的拿到：

// 双向链表尾删
void ListPopBack(ListNode* pHead)
{
	assert(pHead);
	assert(!is_Empty(pHead));//判空
	ListNode* tail = pHead->prev;
	ListNode* prev = tail->prev;
	ListNode* next = pHead;
	free(tail);
	prev->next = next;
	next->prev = prev;
}

链表头插

// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	ListNode* prev = pHead;
	ListNode* cur = pHead->next;
	ListNode* NewNode = ListCreate(x);
	prev->next = NewNode;
	NewNode->prev = prev;
	NewNode->next = cur;
	cur->prev = NewNode;
}

链表头删

// 双向链表头删
void ListPopFront(ListNode* pHead)
{
	assert(pHead);
	assert(!is_Empty(pHead));//判空
	ListNode* prev = pHead;
	ListNode* cur = pHead->next;
	ListNode* next = cur->next;
	free(cur);
	prev->next = next;
	next->prev = prev;
}

链表查找

// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	assert(!is_Empty(pHead));//表都为NULL了，就没办法找了
	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		if (cur->val == x)
			return cur;
		else
			cur = cur->next;
	}
	return NULL;
}

链表pos位置前面去插入

// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);//pos不能为NULL,由于参数限制我们无法对pos判断是否为哨兵位头节点，因此我们假设pos传的都是合法指针和NULL
	ListNode* NewNode = ListCreate(x);
	ListNode* prev = pos->prev;
	NewNode->next = pos;
	pos->prev = NewNode;
	prev->next = NewNode;
	NewNode->prev = prev;
}

删除pos位置

// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
	assert(pos);//由于参数限制，我们无法判断表是否为NULL；
	ListNode* prev = pos->prev;
	ListNode* next = pos->next;
	free(pos);
	prev->next = next;
	next->prev = prev;
}

链表判空

//判断链表是否为NULL
bool is_Empty(ListNode* pHead)
{
	assert(pHead);
	return pHead == pHead->prev;
}

代码复用

我们上面既然实现了在pos位置之前插入和删除pos位置的数据；

那么：

ListInsert(plist,x);//相当于尾插
ListInsert(plist->next, x);//相当于头插
ListErase(plist->next);//相当于头删
ListErase(plist->prev);//相当于尾删;

那么实际上我们只要实现ListInsert、ListErase这两个接口就能快速实现出带头双向循环链表了；

总代码及头文件

头文件的包含：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
// 带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType val;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;

// 创建返回链表的头结点.
ListNode* ListCreate(LTDataType x);
//初始化哨兵位的头节点;
void InitDummyHead(ListNode* pHead);
// 双向链表销毁
void ListDestory(ListNode* pHead);
// 双向链表打印
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, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);
//判断链表是否为NULL
bool is_Empty(ListNode* pHead);

功能代码实现：

#include"DList.h"
ListNode* ListCreate(LTDataType x)
{
	ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode));
	if (!NewNode)
		exit(-1);
	NewNode->val = x;
	NewNode->prev = NULL;
	NewNode->next = NULL;
	return NewNode;
}
void InitDummyHead(ListNode* pHead)
{
	assert(pHead);
	pHead->prev = pHead;
	pHead->next = pHead;
}
// 双向链表销毁
void ListDestory(ListNode* pHead)
{
	assert(pHead);
	ListNode* cur = pHead->next;
	ListNode* next = NULL;
	while (cur!=pHead)
	{
		next = cur->next;
		free(cur);
		cur = next;
	}
	free(cur);
}
// 双向链表打印
void ListPrint(ListNode* pHead)
{
	assert(pHead);
	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		ListNode* next = cur->next;
		printf("%d->",cur->val);
		cur = next;
	}
	printf("NULL\n");
}
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	/*ListNode* NewNode = ListCreate(x);
	ListNode* tail = pHead->prev;
	tail->next = NewNode;
	NewNode->prev = tail;
	pHead->prev = NewNode;
	NewNode->next = pHead;*/
	ListInsert(pHead,x);//函数复用
}
// 双向链表尾删
void ListPopBack(ListNode* pHead)
{
	assert(pHead);
	assert(!is_Empty(pHead));//判空
	/*ListNode* tail = pHead->prev;
	ListNode* prev = tail->prev;
	ListNode* next = pHead;
	free(tail);
	prev->next = next;
	next->prev = prev;*/
	ListErase(pHead->prev);//函数复用
}
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	/*ListNode* prev = pHead;
	ListNode* cur = pHead->next;
	ListNode* NewNode = ListCreate(x);
	prev->next = NewNode;
	NewNode->prev = prev;
	NewNode->next = cur;
	cur->prev = NewNode;*/
	ListInsert(pHead->next,x);//函数复用
}
// 双向链表头删
void ListPopFront(ListNode* pHead)
{
	assert(pHead);
	assert(!is_Empty(pHead));//判空
	/*ListNode* prev = pHead;
	ListNode* cur = pHead->next;
	ListNode* next = cur->next;
	free(cur);
	prev->next = next;
	next->prev = prev;*/
	ListErase(pHead->next);//函数复用
}
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x)
{
	assert(pHead);
	assert(!is_Empty(pHead));//表都为NULL了，就没办法找了
	ListNode* cur = pHead->next;
	while (cur != pHead)
	{
		if (cur->val == x)
			return cur;
		else
			cur = cur->next;
	}
	return NULL;
}
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);//pos不能为NULL,由于参数限制我们无法对pos判断是否为哨兵位头节点，因此我们假设pos传的都是合法指针和NULL
	ListNode* NewNode = ListCreate(x);
	ListNode* prev = pos->prev;
	NewNode->next = pos;
	pos->prev = NewNode;
	prev->next = NewNode;
	NewNode->prev = prev;
}
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos)
{
	assert(pos);//由于参数限制，我们无法判断表是否为NULL；
	ListNode* prev = pos->prev;
	ListNode* next = pos->next;
	free(pos);
	prev->next = next;
	next->prev = prev;
}
//判断链表是否为NULL
bool is_Empty(ListNode* pHead)
{
	assert(pHead);
	return pHead == pHead->prev;
}

加载全部内容
相关教程
猜你喜欢
用户评论