[数据结构与算法]双链表的增删查改实现（c语言描述）

内容导读

1.什么是双链表

1.1 双链表概述

1.2循环链表

1.3?双链表的优点

2.双链表的定义以及常见功能的实现

2.0双链表定义以及常见功能头文件

2.1双链表定义（声明）

2.2双链表内存申请及扩容

2.3双链表初始化

2.4双链表的打印

2.5双链表的插入与删除操作理论

?2.6双链表头插操作代码实现

2.7双链表尾插操作代码实现

?2.8双链表的位置pos（已知）前插入操作代码实现

2.9双链表的头删操作代码实现

2.10双链表尾删操作代码实现

?2.11双链表的位置pos（已知）删除操作代码实现

?2.12双链表的元素查找，若找到目的值i则返回其地址pos，否则返回NULL

2.13双链表的元素查找修改，若找到目的值i则将i修改成e，并返回其地址，否则返回NULL

终：代码合集

1.什么是双链表

1.1 双链表概述

在线性表的链式存储结构中，每个物理结点增加一个指向后继结点的指针域（后指针）和一个指向前驱结点的指针域（前指针） ->双链表。

?举个栗子：带头结点双链表结构

1.2循环链表

循环链表是另一种形式的链式存储结构形式。?

所以说双链表的形式就会有多种啦，比如循环双链表，带头结点的双链表，带头结点的循环双链表，带头结点的双链表等等。不过本质都是一样的，只需要学会任意一种，其他的只要注意一些不同的细节也能轻松实现。

1.3?双链表的优点

• 从任一结点出发可以快速找到其前驱结点和后继结点；
• 从任一结点出发可以访问其他结点。

双链表相比于单链表来说，双链表能够从任何一个结点访问其他任意结点，而单链表只能单方向访问下一个结点。虽然双链表的结构较比与单链表要复杂，但是双链表的操作要相比于单链表简单。

在本文中，双链表所有实现方式以带头结点的循环双链表为基础实现。

2.双链表的定义以及常见功能的实现

2.0双链表定义以及常见功能头文件

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int ListType;
typedef struct ListNode		//声明双链表结点结构
{
	ListType data;		//存储数据：data
	struct ListNode* prev;	//指向前驱结点：前指针
	struct ListNode* next;	//指向后继结点：后指针
}ListNode;
//实现双链表增删查改接口
//双链表的初始化
ListNode* ListInit();
//双链表的打印
void ListPrint(ListNode* phead);
//双链表的头插
void ListPushFront(ListNode* phead,ListType x);
//双链表的头删
void ListPopFront(ListNode* phead);
//双链表的尾插
void ListPushBack(ListNode* phead, ListType x);
//双链表的尾删
void ListPopBack(ListNode* phead);
//双链表结点的扩容
ListNode* BuyListNode(ListType x);
//双链表的位置pos（已知）前插入
void ListInsert( ListNode* pos, ListType x);
//双链表的位置pos（已知）删除
void ListErase( ListNode* pos);
//双链表的元素查找，若找到目的值i则返回其地址pos，否则返回NULL
ListNode* ListFind(ListNode* phead, ListType i);
//双链表的元素查找修改，若找到目的值i则将i修改成e，并返回其地址，否则返回NULL
ListNode* ListReplace(ListNode* phead, ListType i, ListType e);

2.1双链表定义（声明）

对于双链表，采用类似于单链表的类型定义，其结点类型ListNode声明如下：

typedef int ListType;
typedef struct ListNode		//声明双链表结点结构
{
	ListType data;		//存储数据：data
	struct ListNode* prev;	//指向前驱结点：前指针
	struct ListNode* next;	//指向后继结点：后指针
}ListNode;

2.2双链表内存申请及扩容

//双链表结点申请及扩容
ListNode* BuyListNode(ListType x)
{
	ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));    //新结点内存申请
	if (newNode == NULL) {
		printf("申请内存失败！");
		return NULL;
	}
	newNode->next = NULL;
	newNode->prev = NULL;
	newNode->data = x;
	return newNode;            //将新申请的结点的前后指针置空，存入数据，返回新结点的地址
}

2.3双链表初始化

//双链表的初始化
ListNode* ListInit()
{
	ListNode* phead = BuyListNode(0);        //申请新结点作为头指针
	phead->next = phead;        //初始化的双链表前后指针均指向本身
	phead->prev = phead;

	return phead;            //返回指针地址
}

2.4双链表的打印

需要打印双链表中的每个数据，就需要遍历整个双链表，需要遍历双链表，那就要找到遍历双链表的条件，由于我是以带头结点的循环双链表为基础，那么遍历终结的条件不是指向NULL，而是指向头结点地址，因为当遍历完一次后，指针就会指向初始结点。

//双链表的打印
void ListPrint(ListNode* phead)
{
	assert(phead);            //判断传入的地址是否为空，为空强制结束程序
	ListNode* cur = phead->next;
	while (cur!=phead)
	{
		printf("%d  ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

2.5双链表的插入与删除操作理论

双链表插入操作

?双链表删除操作

?2.6双链表头插操作代码实现

?双链表的头插相当于在第一个数据前插入

//双链表的头插
void ListPushFront(ListNode* phead, ListType x)
{
	assert(phead);
	ListNode* newNode = BuyListNode(x);
	ListNode* next = phead->next;    //保存第一个数据地址
	phead->next = newNode;
	newNode->prev = phead;
	next->prev = newNode;
	newNode->next = next;
}

2.7双链表尾插操作代码实现

双链表的尾插相当于在头结点前插入

//双链表的尾插
void ListPushBack(ListNode* phead, ListType x)
{
	assert(phead);

	ListNode* newNode = BuyListNode(x);
	ListNode* tail = phead->prev;        //保存最后一个数据地址
	phead->prev = newNode;
	newNode->next = phead;
	tail->next = newNode;
	newNode->prev = tail;

}

?2.8双链表的位置pos（已知）前插入操作代码实现

//双链表的位置pos（已知）前插入
void ListInsert(ListNode* pos, ListType x)
{
	assert(pos);

	ListNode* newNode= BuyListNode(x);
	ListNode* posPrev = pos->prev;
	pos->prev = newNode;
	newNode->next = pos;
	posPrev->next = newNode;
	newNode->prev = posPrev;
}

2.9双链表的头删操作代码实现

双链表头删相当于删除第一个数据?

//双链表的头删
void ListPopFront(ListNode* phead)
{
	assert(phead);
	assert(phead->next != NULL);
	ListNode* first = phead->next;
	ListNode* second = first->next;
	phead->next = second;
	second->prev = phead;
	free(first);

}

2.10双链表尾删操作代码实现

双链表尾删相当于删除最后一个数据

//双链表的尾删
void ListPopBack(ListNode* phead)
{
	assert(phead);
	assert(phead->next != NULL);

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

?2.11双链表的位置pos（已知）删除操作代码实现

//双链表的位置pos（已知）删除
void ListErase( ListNode* pos)
{
	assert(pos);

	ListNode* posPrev = pos->prev;
	ListNode* posNext = pos->next;
	posPrev->next = posNext;
	posNext->prev = posPrev;

}

?2.12双链表的元素查找，若找到目的值i则返回其地址pos，否则返回NULL

//双链表的元素查找，若找到目的值i则返回其地址pos，否则返回NULL
ListNode* ListFind(ListNode* phead, ListType i)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead) {
		if (cur->data == i)
			return cur;
		cur = cur->next;
	}
	return NULL;
}

2.13双链表的元素查找修改，若找到目的值i则将i修改成e，并返回其地址，否则返回NULL

//双链表的元素查找修改，若找到目的值i则将i修改成e，并返回其地址，否则返回NULL
ListNode* ListReplace(ListNode* phead, ListType i, ListType e)
{
	assert(phead);

	ListNode* cur = phead->next;
	while (cur != phead) {
		if (cur->data == i)
		{
			cur->data = e;
			return cur;
		}
		cur = cur->next;
			
	}
	return NULL;
}

终：代码合集

#include "List.h"
//双链表的初始化
ListNode* ListInit()
{
	ListNode* phead = BuyListNode(0);
	phead->next = phead;
	phead->prev = phead;

	return phead;
}
//双链表的打印
void ListPrint(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur!=phead)
	{
		printf("%d  ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
//双链表的头插
void ListPushFront(ListNode* phead, ListType x)
{
	assert(phead);
	ListNode* newNode = BuyListNode(x);
	ListNode* next = phead->next;
	phead->next = newNode;
	newNode->prev = phead;
	next->prev = newNode;
	newNode->next = next;
}
//双链表的头删
void ListPopFront(ListNode* phead)
{
	assert(phead);
	assert(phead->next != NULL);
	ListNode* first = phead->next;
	ListNode* second = first->next;
	phead->next = second;
	second->prev = phead;
	free(first);

}
//双链表的尾插
void ListPushBack(ListNode* phead, ListType x)
{
	assert(phead);

	ListNode* newNode = BuyListNode(x);
	ListNode* tail = phead->prev;
	phead->prev = newNode;
	newNode->next = phead;
	tail->next = newNode;
	newNode->prev = tail;

}
//双链表的尾删
void ListPopBack(ListNode* phead)
{
	assert(phead);
	assert(phead->next != NULL);

	ListNode* tail = phead->prev;
	ListNode* tailPrev = tail->prev;
	phead->prev = tailPrev;
	tailPrev->next = phead;
	free(tail);
}
//双链表结点的扩容
ListNode* BuyListNode(ListType x)
{
	ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
	if (newNode == NULL) {
		printf("申请内存失败！");
		return NULL;
	}
	newNode->next = NULL;
	newNode->prev = NULL;
	newNode->data = x;
	return newNode;
}
//双链表的位置pos（已知）前插入
void ListInsert(ListNode* pos, ListType x)
{
	assert(pos);

	ListNode* newNode= BuyListNode(x);
	ListNode* posPrev = pos->prev;
	pos->prev = newNode;
	newNode->next = pos;
	posPrev->next = newNode;
	newNode->prev = posPrev;
}
//双链表的位置pos（已知）删除
void ListErase( ListNode* pos)
{
	assert(pos);

	ListNode* posPrev = pos->prev;
	ListNode* posNext = pos->next;
	posPrev->next = posNext;
	posNext->prev = posPrev;

}
//双链表的元素查找，若找到目的值i则返回其地址pos，否则返回NULL
ListNode* ListFind(ListNode* phead, ListType i)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead) {
		if (cur->data == i)
			return cur;
		cur = cur->next;
	}
	return NULL;
}
//双链表的元素查找修改，若找到目的值i则将i修改成e，并返回其地址，否则返回NULL
ListNode* ListReplace(ListNode* phead, ListType i, ListType e)
{
	assert(phead);

	ListNode* cur = phead->next;
	while (cur != phead) {
		if (cur->data == i)
		{
			cur->data = e;
			return cur;
		}
		cur = cur->next;
			
	}
	return NULL;
}