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

安河桥畔 2023-03-20 我要评论

带头结点的双向循环链表

链表结构如下：

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

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

单链表用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;
}

测试结果：

总结

以上为个人经验，希望能给大家一个参考，也希望大家多多支持。