不正经

这个屌丝很懒，什么也没留下！

热门标签

C语言初阶数据结构（三）双向链表(保姆级别详细图解，轻松上手，通俗易懂)_c语言双向链表

作者：不正经 | 2024-06-01 01:58:19

踩

c语言双向链表

一、基本结构

二、功能实现以及效果展示

、完整代码

一、基本结构

首先要明白双向链表里面包含什么：“双向”两个方向，用两个指针，一个头指针Prev和一个尾指针next ，如下图结点：

头结点不包含数据，后续结点用data存放数据

二、功能实现以及效果展示

菜单展示：

1.创建结构体变量，成员变量包含头结点prev和数据data以及尾指针next


typedef struct ListNode
{
	struct ListNode* prev;
	struct ListNode* next;
	LTDataType data;
}ListNode;

2.创建新结点newnode，返回newnode的地址

使用malloc创建新结点，然后使其头指针和为指针为NULL


ListNode* BuyListNode(LTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("");
		return;
	}
	else
	{
		newnode->data = x;
		newnode->next = NULL;
		newnode->prev = NULL;
		return newnode;
	}
}

3.初始化双向链表

为了避免使用二级指针，可以在初始化双向链表时，返回头结点的地址。让ListNode*类型的指针plist存放头结点的地址

ListNode* plist = ListInit();

初始化双向链表：


ListNode* ListInit()
{
	ListNode* phead = BuyListNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

要让头结点的头指针和尾指针指向自己

4.打印结点数据

定义一个指针cur，用来指向头结点的后继节点，然后从该位置开始打印，每次打印完该结点的数据后，就使指针cur指向下一个结点，直到cur指向的结点是头结点时结束


void ListPrint(ListNode* phead)
{
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

5.头插数据

定义头结点的后继节点为First,这样就避免了在插入数据时考虑指针顺序，创建一个新结点newnode，然后让newnode的尾结点指向First，再让First的头指针指向newnode，再连接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;
	/*ListInsert(phead->next, x);*/
 
}

头插法以及打印数据效果展示

6.尾插数据

头结点的前驱结点就是尾结点，所以，直接定义一个指向头结点的指针tail 然后创建一个新结点，存放要插入的数据，直接将newnode和tail 以及 newnode和头结点相连


void ListPushBack(ListNode* phead,LTDataType x)
{
	//头结点phead的前驱结点就是尾结点
	assert(phead);
	ListNode* tail = phead->prev;
	ListNode*newnode= BuyListNode(x);
	newnode->prev = tail;
	tail->next = newnode;
	phead->prev = newnode;
	newnode->next = phead;
	/*ListInsert(phead, x);*/
}

尾插数据效果展示

7.头删数据

创建一个指针Second，让该指针先存放第二个结点的地址，避免第一个结点Frist被释放后，第二个结点找不到，先让头结点的尾结点指向Second，然后让Second的头指针指向头结点，然后释放第一个结点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);
	First = NULL;
	//ListErase(phead->next);
}

头删数据效果展示

8.尾删数据

定义一个指针tail存放头结点的前驱结点也就是尾结点的地址，然后找到tail的前驱结点prev，然后将prev的尾指针指向头结点phead，然后phead的头指针指向prev，释放掉tail即可


void ListPopBack(ListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	ListNode* tail = phead->prev;
	ListNode* prev = tail->prev;
	prev->next = phead;
	phead->prev = prev;
	free(tail);
	tail = NULL;
	/*ListErase(phead->prev);*/
}

尾插数据效果展示

9.查找数据（效果展示与10和11搭配实现）

定义一个指针cur从第一个结点（非头结点）开始查询，如果找到了，就返回该结点的地址，如果找不到就返回NULL


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

10.随机插入数据

一般与查找数据连用，定义一个指针pos接受查询到的数据的地址，然后再pos指向的结点的前面插入一个结点，创建一个新结点newnode，存放要插入的数据，然后找到pos的前驱结点prev，使prev的尾结点指向newnode，newnode的头结点指向prev，然后再将newnode跟pos相连

这里的data那里应该是数据x，之前的应该也是，画到一半才想起来QAQ

其实细心的UU可以观察到，头插数据和尾插数据都可以调用随机插入函数，只是头插数据的时候pos是phead->next 尾插数据时pos就是phead

头插 ListInsert(phead->next, x);

尾插 ListInsert(phead, x);


void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* newnode = BuyListNode(x);
	ListNode* prev = pos->prev;
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}

随机插入效果展示

11.随机删除数据

定义一个pos指针接受查询到的数据的地址，然后在定义一个指针prev指向pos的前驱结点，定义一个指针next指向pos的后继结点，然后让prev的尾指针指向next，再让next的头指针指向prev，最后释放掉pos即可

其实头删数据、尾删数据都可以通过随机删除实现

头删数据：ListErase(phead->next)

尾删数据：Li


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

stErase(phead->prev);

随机删除效果展示

12.修改数据

先找到想要修改的数据，然后再将要修改的数据输入即可


printf("请输入你想要修改的数据:\n");
			scanf("%d", &x);
			ListNode * pos2 = ListFind(plist, x);
			if (pos2 == NULL)
			{
				printf("该数据不存在，请重新进行操作!\n");
			}
			else
			{
				printf("该数据存在，请输入数据进行修改:\n");
				scanf("%d", &x);
				pos2->data = x;
				printf("修改成功!\n");
			}
			break;

效果展示

13.计算链表数据个数

定义一个指针cur指向头结点的后继结点，定义一个变量count计算数据个数，让cur依次向后移动，每次让count++；直到cur指向头结点时结束


int ListSize(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;
	int count = 0;
	while (cur != phead)
	{
		count++;
		cur = cur->next;
	}
	return count;
}

效果展示

14.销毁双向链表

定义一个指针cur指向第一个结点，然后从第一个结点开始释放，每次定义一个指针next指向cur的后一个结点，然后将cur释放，再将next的地址给cur，直到只剩下头结点，最后将头结点也释放


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

如有问题评论就好，看到就会回嗷~ UU们如有帮助，点点赞呐~

头文件：List.h（函数声明）


//头文件
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 
typedef int LTDataType;
typedef struct ListNode
{
	struct ListNode* prev;
	struct ListNode* next;
	LTDataType data;
}ListNode;
 
//初始化双向链表
ListNode* ListInit();
//打印双向链表
void ListPrint(ListNode* phead);
//销毁双向链表
void ListDestory(ListNode* phead);
//尾插法
void ListPushBack(ListNode* phead, LTDataType x);
//头插法
void ListPushFront(ListNode* phead, LTDataType x); 
//尾删
void ListPopBack(ListNode* phead);
//头删
void ListPopFront(ListNode* phead);
//查找数据
ListNode*ListFind(ListNode* phead, LTDataType x);
//随机插入数据
void ListInsert(ListNode* pos, LTDataType x);
//随机删除数据
void ListErase(ListNode* pos);
//计算双向链表中的数据个数
int ListSize(ListNode* phead);

源文件List.c(函数功能实现)


#include"List.h"
 
//创建新结点
ListNode* BuyListNode(LTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("");
		return;
	}
	else
	{
		newnode->data = x;
		newnode->next = NULL;
		newnode->prev = NULL;
		return newnode;
	}
}
 
//初始化双向链表
ListNode* ListInit()
{
	ListNode* phead = BuyListNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}
 
//打印双向链表
void ListPrint(ListNode* phead)
{
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
 
//尾插法
void ListPushBack(ListNode* phead,LTDataType x)
{
	//头结点phead的前驱结点就是尾结点
	assert(phead);
	ListNode* tail = phead->prev;
	ListNode*newnode= BuyListNode(x);
	newnode->prev = tail;
	tail->next = newnode;
	phead->prev = newnode;
	newnode->next = phead;
	/*ListInsert(phead, x);*/
}
 
//头插法
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;
	/*ListInsert(phead->next, x);*/
 
}
 
//尾删
void ListPopBack(ListNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
	ListNode* tail = phead->prev;
	ListNode* prev = tail->prev;
	prev->next = phead;
	phead->prev = prev;
	free(tail);
	tail = NULL;
	/*ListErase(phead->prev);*/
}
 
//头删
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);
	First = NULL;
	//ListErase(phead->next);
}
 
//查找数据
ListNode* ListFind(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
 
	}
	return NULL;
}
 
//随机插入数据   在pos的前面插入数据
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* newnode = BuyListNode(x);
	ListNode* prev = pos->prev;
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}
 
//随机删除数据    删除pos位置的数据
void ListErase(ListNode* pos)
{
	assert(pos);
	ListNode* prev = pos->prev;
	ListNode* next = pos->next;
	prev->next = next;
	next->prev = prev;
	free(pos);
	pos = NULL;
}
 
//计算双向链表中的元素个数
int ListSize(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;
	int count = 0;
	while (cur != phead)
	{
		count++;
		cur = cur->next;
	}
	return count;
}
 
//销毁双向链表
void ListDestory(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = NULL;
		cur = next;
	}
	free(phead);
	phead = NULL;
}

源文件text.c（功能测试）


#include"List.h"
void menu()
{
	printf("*******************************************\n");
	printf("**1.尾插数据   2.头插数据\n");
	printf("**3.尾删数据   4.头删数据\n");
	printf("**5.随机插入   6.随机删除\n");
	printf("**7.修改数据   8.求结点个数\n");
	printf("**9.打印链表   0.退出程序\n");
	printf("*******************************************\n");
}
void text()
{
	ListNode* plist = ListInit();
	int input = 0;
	int i = 0;
	LTDataType x = 0;
	do
	{
		menu();
		scanf("%d", &input);
		switch (input)
		{
		case 1:
			printf("请输入你想插入的数据,以-1结束\n");
			do
			{
				scanf("%d", &x);
				if (x != -1)
				{
					ListPushBack(plist, x);
				}
			} while (x != -1);
			printf("插入成功\n");
			break;
		case 2:
			printf("请输入你想插入的数据,以-1结束\n");
			do
			{
				scanf("%d", &x);
				if (x != -1)
				{
					ListPushFront(plist, x);
				}
			} while (x != -1);
			printf("插入成功\n");
			break;
		case 3:
			ListPopBack(plist);
			printf("删除成功!\n");
			break;
		case 4:
			ListPopFront(plist);
			printf("删除成功!\n");
			break;
		case 5:
			printf("请先输入你要插入的位置的当前数据：\n");
			scanf("%d", &x);
			ListNode* pos = ListFind(plist, x);
			if (pos == NULL)
			{
				printf("该数据不存在，请重新选择随机插入选项进行操作!\n");
			}
			else
			{
				printf("该数据存在，请输入您要插入的数据:\n");
				scanf("%d", &x);
				ListInsert(pos, x);
				printf("插入成功!\n");
			}
			break;
		case 6:
			printf("请先输入你要删除的位置的当前数据：\n");
			scanf("%d", &x);
			ListNode* pos1 = ListFind(plist, x);
			if (pos1 == NULL)
			{
				printf("该数据不存在，请重新选择随机删除选项进行操作!\n");
			}
			else
			{
				ListErase(pos1);
				printf("删除成功!\n");
			}
			break;
		case 7:
			printf("请输入你想要修改的数据:\n");
			scanf("%d", &x);
			ListNode * pos2 = ListFind(plist, x);
			if (pos2 == NULL)
			{
				printf("该数据不存在，请重新进行操作!\n");
			}
			else
			{
				printf("该数据存在，请输入数据进行修改:\n");
				scanf("%d", &x);
				pos2->data = x;
				printf("修改成功!\n");
			}
			break;
		case 8:
			 i=ListSize(plist);
			 printf("结点个数为%d个\n", i);
			break;
		case 9:
			ListPrint(plist);
			break;
		case 0:
			printf("退出程序!\n");
			break;
		default:
			printf("输入的数字有误，请重新选择\n");
			break;
		}
	} while (input);
}
int main()
{
	text();
	return 0;
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/不正经/article/detail/655413

C语言初阶数据结构（三）双向链表(保姆级别详细图解，轻松上手，通俗易懂)_c语言双向链表

目录

一、基本结构

二、功能实现以及效果展示

、完整代码