首页 > 资讯 > 后端开发 > 其他教程 >C语言中双链表的基本操作

110

分享到

C语言中双链表的基本操作

C语言双链表双链表的基本操作 C语言双链表操作 2023-02-05 15:02:28 110人浏览泡泡鱼

摘要

目录带头结点的双向循环链表基本操作创建销毁打印尾插法尾删头插头删查找元素位置任意位置插入任意位置删除完整代码及测试总结带头结点的双向循环链表链表结构如下：每个节点都有一个数据域和

带头结点的双向循环链表

链表结构如下：

每个节点都有一个数据域和两个指针域，这两个指针分别指向链表的前驱节点和后继节点，头节点的前驱节点是链表的最后一个节点，链表最后一个节点的后继节点是头节点。

正因为如此，带头结点的双向循环链表没有空节点，在进行遍历时，循环条件也与单链表不同：

单链表用cur->next为空判断当前节点是否为最后一个节点，带头的双向循环链表则需判断cur->next是否等于头节点。

定义：

typedef int DataType;
typedef struct Listnode
{
	DataType data;//数据域
	struct ListNode* next;//指向下一个节点
	struct ListNode* prev;//指向前一个节点
}ListNode;

基本操作

创建

创建链表需要先申请一段内存，然后再进行赋值，这里BuyListNode函数用于申请内存空间，在插入节点时，也需要调用BuyListNode函数。

申请节点：

static ListNode* BuyListNode(int x)
{
	ListNode* newNode = NULL;
	newNode = (ListNode*)malloc(sizeof(ListNode));//为节点动态申请一段内存
	if (NULL == newNode)
	{
		assert(0);
		return NULL;
	}
	//为申请的节点赋值
	newNode->data = x;
	newNode->next = NULL;
	newNode->prev = NULL;
	return newNode;
}

创建链表：

ListNode* ListCreate()
{
	ListNode*head=BuyListNode(0);//调用申请节点的函数
	//为头节点指针域赋值，链表为空时，prev和next都指向头节点
	head->next = head;
	head->prev = head;
	return head;
}

销毁

使用链表时会申请内存空间，所使用完毕后要进行释放，避免内存泄漏，这里销毁链表用了头删的思想，每次删除链表中的第一个节点并释放空间，具体过程如图：

循环执行上述过程，直到链表为空，最后再释放头节点空间。

程序如下：

void ListDestory(ListNode** plist)
{
	assert(plist);
	ListNode* cur = (*plist)->next;
	while (cur!=(*plist))
	{
		(*plist)->next = cur->next;
		free(cur);
		cur = (*plist)->next;
	}
	free(*plist);
	*plist = NULL;
}

这里需要注意的是，销毁链表要改变链表头结点的指向，所以传参时需要传二级指针。在对带头结点的双链表的操作中，只有销毁会改变指向头结点的指针plist的指向，所以只有销毁时需要传二级指针，其余操作传一级指针即可。

打印

链表打印的思想比较简单，只需要遍历打印即可。

程序：

void ListPrint(ListNode* plist)
{
	assert(plist);
	ListNode* cur = plist->next;
	while (cur != plist)//遍历的循环条件
	{
		printf("%d--->", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

尾插法

步骤

申请新节点newNode
对newNode的prev和next进行赋值
使原链表最后一个节点的next指向新节点
链表头指针的prev指向新节点

void ListPushBack(ListNode* plist, DataType x)
{
	assert(plist);
	ListNode* newNode =BuyListNode(x);
	newNode->prev = plist->prev;
	newNode->next = plist;
	plist->prev->next = newNode;
	plist->prev = newNode;
}

尾删

删除节点时需要先判断链表是否为空，先写出链表判空的方法

链表判空

看plist->next是否等于plist即可判断链表是否为空

static int IsEmpty(ListNode*plist)
{
	assert(plist);
	if (plist->next == plist)
	{
		return 1;//链表为空，返回1
	}
	return 0;//链表非空，返回0
}

尾删法

步骤

用del标记最后一个节点
使del前一个节点的next指向头节点
头结点的prev指向del的前一个节点
释放del的空间
这里中间两步将del节点从链表中移除出来，最后一步则释放内存空间
如图：

程序

void ListPopBack(ListNode * plist)
{
	assert(plist);
	if (IsEmpty(plist))
	{
		return;
	}
	ListNode* del = plist->prev;
	del->prev->next = plist;
	plist->prev = del->prev;
	free(del);
	del = NULL;
}

头插

步骤

申请新节点newNode
使新节点的prev指向头节点
令新节点的next指向原来链表第二个节点
令原来第二个节点的prev指向newNode
令头节点的next指向newNode

程序

void ListPushFront(ListNode* plist, DataType x)
{
	assert(plist);
	ListNode* newNode = BuyListNode(0);
	newNode->prev = plist;
	newNode->next = plist->next;

	plist->next->prev = newNode;
	plist->next = newNode;
}

头删

用del标记链表的第一个节点
令头结点的next指向del->next
原链表中第二个节点的prev指向头节点，成为新的第一个节点
释放删除节点的空间

程序

void ListPopFront(ListNode* plist)
{
	assert(plist);
	if (IsEmpty(plist))//先判空
	{
		return;
	}
	ListNode* del = plist->next;

	plist->next = del->next;
	del->next->prev = plist;

	free(del);
	del = NULL;
}

查找元素位置

对链表进行遍历，比对，找到与目标值相等的数时，返回当前的地址

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

任意位置插入

由于双链表有两个指针域，所以可以在pos位置的前面进行插入

步骤

申请一个新节点newNode
为新节点的prev和next赋值，使其分别指向pos的前一个节点和pos
使原来pos前一个节点的next指向新节点
令pos的prev指向新节点

void ListInsert(ListNode* pos, DataType x)
{
	assert(pos);
	ListNode* newNode = BuyListNode(x);
	//在pos前面插入
	newNode->prev = pos->prev;
	newNode->next = pos;

	pos->prev->next = newNode;
	pos->prev = newNode;
}

任意位置删除

删除给定的节点pos

pos前一个节点的next指向pos的下一个节点
pos下一个节点的prev指向pos的前一个节点
释放pos占用的内存空间

程序

void ListErase(ListNode* pos)
{
	assert(pos);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;	
}

完整代码及测试

work.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<windows.h>
typedef int DataType;
typedef struct ListNode
{
	DataType data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;

ListNode* ListCreate();// 创建返回链表的头结点.
void ListDestory(ListNode** plist);// 双向链表销毁
void ListPrint(ListNode* plist);// 双向链表打印
void ListPushBack(ListNode* plist, DataType x);// 双向链表尾插
void ListPopBack(ListNode* plist);// 双向链表尾删
void ListPushFront(ListNode* plist, DataType x);// 双向链表头插
void ListPopFront(ListNode* plist);// 双向链表头删
ListNode* ListFind(ListNode* plist, DataType x);// 双向链表查找
void ListInsert(ListNode* pos, DataType x);// 双向链表在pos的前面进行插入
void ListErase(ListNode* pos);// 双向链表删除pos位置的节点

work.c

#include"work.h"

//申请节点
static ListNode* BuyListNode(int x)
{
	ListNode* newNode = NULL;
	newNode = (ListNode*)malloc(sizeof(ListNode));//为节点动态申请一段内存
	if (NULL == newNode)
	{
		assert(0);
		return NULL;
	}
	//为申请的节点赋值
	newNode->data = x;
	newNode->next = NULL;
	newNode->prev = NULL;
	return newNode;
}


//创建链表
ListNode* ListCreate()
{
	ListNode*head=BuyListNode(0);//调用申请节点的函数
	//为头节点指针域赋值，链表为空时，prev和next都指向头节点
	head->next = head;
	head->prev = head;
	return head;
}

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

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

//尾插法
void ListPushBack(ListNode* plist, DataType x)
{
	assert(plist);
	ListNode* newNode =BuyListNode(x);
	newNode->prev = plist->prev;
	newNode->next = plist;
	plist->prev->next = newNode;
	plist->prev = newNode;
}

//判断链表是否为空
static int IsEmpty(ListNode*plist)
{
	assert(plist);
	if (plist->next == plist)
	{
		return 1;
	}
	return 0;
}

// 尾删法
void ListPopBack(ListNode * plist)
{
	assert(plist);
	if (IsEmpty(plist))
	{
		return;
	}
	ListNode* del = plist->prev;
	del->prev->next = plist;
	plist->prev = del->prev;
	free(del);
	del = NULL;
}

// 双向链表头插
void ListPushFront(ListNode* plist, DataType x)
{
	assert(plist);
	ListNode* newNode = BuyListNode(0);
	newNode->prev = plist;
	newNode->next = plist->next;

	plist->next->prev = newNode;
	plist->next = newNode;
}

// 双向链表头删
void ListPopFront(ListNode* plist)
{
	assert(plist);
	if (IsEmpty(plist))
	{
		return;
	}
	ListNode* del = plist->next;

	plist->next = del->next;
	del->next->prev = plist;

	free(del);
	del = NULL;
}

// 查找元素位置
ListNode* ListFind(ListNode* plist, DataType x)
{
	assert(plist);
	ListNode* cur = plist->next;
	while (cur != plist)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

// 任意位置插入
void ListInsert(ListNode* pos, DataType x)
{
	assert(pos);
	ListNode* newNode = BuyListNode(x);
	//在pos前面插入
	newNode->prev = pos->prev;
	newNode->next = pos;

	pos->prev->next = newNode;
	pos->prev = newNode;
}

//任意位置删除
void ListErase(ListNode* pos)
{
	assert(pos);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
	
}

main.c

#include"work.h"
int main()
{
	ListNode*plist= ListCreate();//创建一个双向非循环链表

    //尾插五个节点
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPushBack(plist, 5);
	ListPrint(plist);
    //头插一个节点
	ListPushFront(plist, 0);
	ListPrint(plist);
    //尾删一个节点
	ListPopBack(plist);
	ListPrint(plist);
    //头删一个节点
	ListPopFront(plist);
	ListPrint(plist);
    //在元素3前面插入一个节点
	ListInsert(ListFind(plist,3),9);
	ListPrint(plist);
    //删除值为9的节点
	ListErase(ListFind(plist,9));
	ListPrint(plist);
    //销毁链表
	ListDestory(&plist);
	system("pause");
	return 0;
}

测试结果：