C语言数据结构-双向链表

2023-12-13 17:34:50

文章目录

1 双向链表的结构
2 双向链表的实现
3 完整代码

1 双向链表的结构

在这里插入图片描述

带头链表的头结点,实际是"哨兵位",哨兵位节点不存储任何有效元素,只是站在这里"放哨的".
哨兵位的意义:遍历循环链表避免死循环.

2 双向链表的实现

笔者在删除,插入数据时,画好图后,也好了代码,但是在调试中多次出现代码位置出错,导致写的代码的含义不符合预期.
所以说思路一定要清晰,多多检查调试

2.1 定义双向链表的数据结构

typedef int ListDataType;

typedef struct ListNode
{
	ListDataType data;		//整型数据
	struct ListNode* next;	//前驱指针
	struct ListNode* pre;	//后驱指针

}ListNode;

2.2 打印链表

链表的第一个数据是phead->next,哨兵位不存储数据
循环链表中,遍历一遍,碰到phead为止

void ListPrint(ListNode* phead)
{
	ListNode* cur = phead->next;	//头结点,哨兵位的下一位
	while (cur != phead)//双向循环链表,循环到哨兵位为止
	{
		printf("%d-> ", cur->data);
		cur = cur->next;
	}
}

在这里插入图片描述

2.3 初始化链表

定义一个双向循环链表后,初始化链表,此时只有一个phead(哨兵位),前驱指针和后驱指针都指向phead自己
哨兵位的数据(data)在应用中不使用,就设置成-1了,与笔者之后使用的正整数形成差异

ListNode* ListInit()
{
	ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
	if (phead == NULL)
	{
		perror("malloc error");
		return;
	}
	phead->data = -1;
	phead->next = phead->pre = phead;
	return phead;
}

在这里插入图片描述

调试中发现,phead,phead->next,phead->pre地址相同,data都是笔者设置的-1.

2.4 销毁链表

遍历一遍链表进行销毁,cur碰到phead哨兵位为止
释放cur前,记录下cur->next,释放cur后,把cur->next赋值给cur,以此避免销毁cur后,cur->next不能指向下一个节点的情况
最后再把哨兵位释放,置空.

void ListDestory(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;	//头结点,哨兵位的下一位
	while (cur!=phead)
	{
		//释放cur前,记录下cur->next,释放cur后,把cur->next赋值给cur
		ListNode* NEXT = cur->next;
		free(cur);
		cur = NEXT;
	}
	//释放哨兵位
	free(phead);
	phead = NULL;
}

在这里插入图片描述

2.5 尾插,头插

先写一个创建内存空间的函数,创建node后,画图示意头插和尾插
一定注意编写代码的顺序,看看笔者注释所说的

//插入数据前创建内存空间
ListNode* ListBuyNode(ListDataType x)
{
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	node->data = x;
	node->next = node->pre = NULL;

	return node;
}

void ListPushBack(ListNode* phead, ListDataType x)
{
	assert(phead);
	ListNode* node = ListBuyNode(x);

	//先处理新节点前驱指针和后驱指针
	node->pre = phead->pre;
	node->next = phead;
	//再处理原链表最后一个节点和phead
	phead->pre->next = node;
	phead->pre = node;
}

void ListPushFront(ListNode* phead, ListDataType x)
{
	assert(phead);
	ListNode* node = ListBuyNode(x);
	//先处理新节点前驱指针和后驱指针
	node->pre = phead;
	node->next = phead->next;
	//再处理phead和原链表第一个节点(phead->next)
	phead->next->pre = node;
	phead->next = node;

}

初始化成功,我们插入一个数据"1",成功插入

2.6 尾删,头删

删除链表至少有除哨兵位的一个数据,换句话说,链表不能只有一个哨兵位

在这里插入图片描述

void ListPopBack(ListNode* phead)
{
	assert(phead);
	//链表不能只有一个哨兵位
	assert(phead->next != phead);
	ListNode* del = phead->pre;
	//删除节点的前驱指针
	del->pre->next = phead;
	//phead的前驱指针
	phead->pre = del->pre;
}

void ListPopFront(ListNode* phead)
{
	assert(phead && phead->next != phead);
	ListNode* del = phead->next;

	del->next->pre = phead;
	phead->next = del->next;

	free(del);
	del = NULL;

}

在这里插入图片描述

2.7 根据头次出现数据找下标

这个Find()函数在笔者的多篇博客都有提到缺点,但是我们主要实现功能,笔者在力扣题写过找多个相同元素,删多个相同元素的题

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

	return NULL;
}

在这里插入图片描述

2.8 定点前插入

在这里插入图片描述

void ListInsert(ListNode* pos, ListDataType x)
{
	assert(pos);
	ListNode* node= ListBuyNode(x);
	//先处理node
	node->next = pos;
	node->pre = pos->pre;
	//在处理pos->pre和pos
	pos->pre->next= node;
	node->next->pre = node;

}

在这里插入图片描述

2.9 删除pos位置

在这里插入图片描述

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

在这里插入图片描述

2.10 定点后插入

在这里插入图片描述

void ListInsertAfter(ListNode* pos, ListDataType x)
{
	assert(pos);
	ListNode* node = ListBuyNode(x);
	//node的prev 和 next
	node->next = pos->next;
	node->pre = pos;

	//pos的next 和 pos->next的prev
	pos->next = node;
	node->next->pre = node;
}

在这里插入图片描述

3 完整代码

3.1 List.h

#define _CRT_SECURE_NO_WARNINGS
#include<stdbool.h>
#include<stddef.h>
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

//0 定义双向循环链表节点结构
typedef int ListDataType;

typedef struct ListNode
{
	ListDataType data;
	struct ListNode* next;	//前驱指针
	struct ListNode* pre;	//后驱指针

}ListNode;

//0 打印链表
void ListPrint(ListNode* phead);

//1 初始化链表
ListNode* ListInit();

//2 销毁链表
void ListDestory(ListNode* phead);

//3 尾插,头插
void ListPushBack(ListNode* phead, ListDataType x);
void ListPushFront(ListNode* phead, ListDataType x);

//4 尾删,头删
void ListPopBack(ListNode* phead);
void ListPopFront(ListNode* phead);

//5 根据数找到第一次出现的下标
ListNode* ListFind(ListNode* phead, ListDataType x);
  
//6 定点前插入
void ListInsert(ListNode* pos, ListDataType x);

//7 删除pos位置
void ListErase(ListNode* pos);

//8 定点后插入
void ListInsertAfter(ListNode* pos, ListDataType x);

3.2 Lish.c

#include "List.h"

void ListPrint(ListNode* phead)
{
	ListNode* cur = phead->next;
	while (cur != phead)//双向循环链表,循环到哨兵位为止
	{
		printf("%d-> ", cur->data);
		cur = cur->next;
	}
}

ListNode* ListInit()
{
	ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
	if (phead == NULL)
	{
		perror("malloc error");
		return;
	}
	phead->data = -1;
	phead->next = phead->pre = phead;
	return phead;
}

void ListDestory(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;	//头结点,哨兵位的下一位
	while (cur!=phead)
	{
		//释放cur前提前记录下cur->next,释放cur后,把cur->next赋值给cur
		ListNode* NEXT = cur->next;
		free(cur);
		cur = NEXT;
	}
	//释放哨兵位
	free(phead);
	phead = NULL;
}

//插入数据前创建内存空间
ListNode* ListBuyNode(ListDataType x)
{
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	node->data = x;
	node->next = node->pre = NULL;

	return node;
}

void ListPushBack(ListNode* phead, ListDataType x)
{
	assert(phead);
	ListNode* node = ListBuyNode(x);

	//先处理新节点前驱指针和后驱指针
	node->pre = phead->pre;
	node->next = phead;
	//再处理原链表最后一个节点和phead
	phead->pre->next = node;
	phead->pre = node;
}

void ListPushFront(ListNode* phead, ListDataType x)
{
	assert(phead);
	ListNode* node = ListBuyNode(x);
	//先处理新节点前驱指针和后驱指针
	node->pre = phead;
	node->next = phead->next;
	//再处理phead和原链表第一个节点(phead->next)
	phead->next->pre = node;
	phead->next = node;

}

void ListPopBack(ListNode* phead)
{
	assert(phead);
	//链表不能只有一个哨兵位
	assert(phead->next != phead);
	ListNode* del = phead->pre;
	//删除节点的前驱指针
	del->pre->next = phead;
	//phead的前驱指针
	phead->pre = del->pre;
}

void ListPopFront(ListNode* phead)
{
	assert(phead && phead->next != phead);
	ListNode* del = phead->next;

	del->next->pre = phead;
	phead->next = del->next;

	free(del);
	del = NULL;

}

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

	return NULL;
}

void ListInsert(ListNode* pos, ListDataType x)
{
	assert(pos);
	ListNode* node= ListBuyNode(x);
	//先处理node
	node->next = pos;
	node->pre = pos->pre;
	//在处理pos->pre和pos
	pos->pre->next= node;
	node->next->pre = node;

}

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

void ListInsertAfter(ListNode* pos, ListDataType x)
{
	assert(pos);
	ListNode* node = ListBuyNode(x);
	//node的prev 和 next
	node->next = pos->next;
	node->pre = pos;

	//pos的next 和 pos->next的prev
	pos->next = node;
	node->next->pre = node;
}

3.3 test.c

#include"List.h"

void test1()
{
	ListNode* plist = ListInit();
}

void test2()
{
	ListNode* plist = ListInit();;
	ListPushBack(plist, 1);
	ListPushBack(plist, 4);
	ListPushBack(plist, 7);

	ListPrint(plist);  //1->4->7->
	ListDestory(plist);
}

void test3()
{
	ListNode* plist = ListInit();;
	ListPushFront(plist, 1);
	ListPushFront(plist, 4);
	ListPushFront(plist, 7);

	ListPrint(plist);//7->4->1->
	ListDestory(plist);
}

void test4()
{
	ListNode* plist = ListInit();;
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPushBack(plist, 5);
	ListPushBack(plist, 6);
	ListPushBack(plist, 7);
	ListPushBack(plist, 8);
	ListPushBack(plist, 9);
	ListPrint(plist);
	printf("\n");

	ListPopBack(plist);
	ListPopBack(plist);
	ListPopFront(plist);
	ListPopFront(plist);

	ListPrint(plist);
	ListDestory(plist);
}

void test5()
{
	ListNode* plist = ListInit();;
	ListPushBack(plist, 1);
	ListPushBack(plist, 2);
	ListPushBack(plist, 3);
	ListPushBack(plist, 4);
	ListPushBack(plist, 5);
	ListPrint(plist);
	printf("\n");

	//测试指定位置
	ListNode* Find1 = ListFind(plist, 2);
	ListNode* Find2 = ListFind(plist, 4);
	ListInsert(Find1, 10);
	ListInsertAfter(Find2, 20);
	ListPrint(plist);
	printf("\n");

	ListErase(Find1);
	ListPrint(plist);
	ListDestory(plist);
}

int main()
{
	//test1();
	//test2();
	//test3();
	//test4();
	test5();


	return 0;
}

笔者在删除,插入数据时,画好图后,也好了代码,但是在调试中多次出现代码位置出错,导致写的代码的含义不符合预期.
所以说思路一定要清晰,多多检查调试

文章来源:https://blog.csdn.net/m0_73678713/article/details/134907222
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！