双向链表-图书馆管理系统函数分析

发布于 2022-05-17  136 次阅读


这两天学习到了C语言的数据结构,学了几天终于明白点了

确实上来是不是很懂,看了好几遍,然后自己跟着敲了一遍,理清了一下逻辑思路(可能有些地方表达的不是很准确)

我们需要利用双向链表,来实现一个图书馆管理系统,也就是增删改查的功能

我们先来简单的介绍一下链表结构

什么是链表

链表是由一系列节点组成的,它在内存中是非连续性的

每个节点包含两个域,一个是数据域,一个是指针域,数据域用来保存用户数据,指针域保存下一个节点的地址

链表有:静态链表 动态链表 单向链表 双向链表 循环链表 单向循环链表 双向循环链表

其与数组各有优缺点,数组在数据量庞大的情况下,增删改比较麻烦,因为需要让所有的数据进行移动

而链表就很好的解决了这个办法,但是其在内存上是非连续性空间,所以查询效率上比数组要慢一点

咱们简单的来看一下链表图解(我的理解就是一堆指针将不连续的内存空间数据相连起来)

而链表的增删改就比较轻松了,只需要修改其指针指向即可达到我们的要求

场景描述

我们有一个图书馆,他馆藏10W本书籍

如果我们用数组来表示,太繁琐了,而且后续的增删改很不方便,增加删除需要移动其他的数据,因此链表的结构,就很适合此类场景

说了那么多 我们先来看一下图书馆管理系统的代码吧

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>



int nBookNodeCount = 0;
struct BookNode* ndHeaderNode = NULL;
//书的节点定义,其包含一个向上的指针和向下的指针
typedef struct BookNode {
	//书节点的向上指针
	struct BookNode* Blink;
	//书节点的向下指针
	struct BookNode* Flink;
	//书籍名字
	char BookName[50];
	//书籍价格
	float BookPrice;
	//书籍编号
	int BookNumber;
};


//增加书籍的函数
struct BookNode* BookAddNode(struct BookNode* NowNode, char* BookName, int BookNumber, float BookPrice);
//查询书籍函数
void SerachNode(struct BookNode* HeaderNode, char* BookName);
//修改书籍函数
void ChangeNode(struct BookNode* HeaderNode, char* BookName, float BookPrice);
//删除书籍函数
void DeleteNode(struct BookNode* HeaderNode, char* BookName);




int main()
{
	while (true)
	{
		int BookSystemChoice = 0;
		char szBookName[50];
		float szBookPrice;
		int szBookNumber;
		float szNewBookPrice;
		printf("欢迎来到图书管理系统\n");
		printf("请选择要使用的功能:\n");
		printf("1.增加图书信息\n");
		printf("2.查询图书信息\n");
		printf("3.修改图书信息\n");
		printf("4.删除图书信息\n");
		scanf_s("%d", &BookSystemChoice);
		switch (BookSystemChoice)
		{
			case 1:
				memset(szBookName,0,50);
				printf("请输入书名:");
				scanf("%s", szBookName);
				printf("请输入定价:");
				scanf("%f", &szBookPrice);
				printf("请输入图书编号:");
				scanf("%d", &szBookNumber);
				ndHeaderNode = BookAddNode(ndHeaderNode, szBookName, szBookNumber, szBookPrice);
				break;
			case 2:
				memset(szBookName, 0, 50);
				printf("请输入查询书名:");
				scanf("%s", szBookName);
				SerachNode(ndHeaderNode, szBookName);
				break;
			case 3:
				memset(szBookName, 0, 50);
				printf("请输入修改的书名:");
				scanf("%s", szBookName);
				printf("请输入修改的定价:");
				scanf_s("%f", &szNewBookPrice);
				ChangeNode(ndHeaderNode, szBookName, szNewBookPrice);
				break;
			case 4:
				memset(szBookName, 0, 50);
				printf("请输入要删除的书:");
				scanf("%s", szBookName);
				DeleteNode(ndHeaderNode, szBookName);
				break;
		}

	}

	
	return 0;
}
//添加书籍函数方法
struct BookNode* BookAddNode(struct BookNode* NowNode, char* BookName, int BookNumber, float BookPrice)
{
	struct BookNode* NewBookNode = NULL;
	struct BookNode* TempBookNode = NULL;
	struct BookNode* HeadBookNode = NowNode;
	NewBookNode = (struct BookNode*)malloc(sizeof(struct BookNode));
	if (NewBookNode == NULL) 
	{
		printf("新节点内存申请失败!");
		return NewBookNode;
	}
	if (NowNode == NULL)
	{
		NowNode = NewBookNode;
		NowNode->Blink = NULL;
		NowNode->Flink = NULL;
	}
	else
	{
		while (HeadBookNode->Flink != NULL)
		{
			TempBookNode = HeadBookNode;
			HeadBookNode = HeadBookNode->Flink;
		} 
		HeadBookNode->Flink = NewBookNode;
		HeadBookNode->Blink = TempBookNode;	
	}
	strcpy(NewBookNode->BookName, BookName);
	NewBookNode->BookPrice = BookPrice;
	NewBookNode->BookNumber = BookNumber;
	NewBookNode->Flink = NULL;
	nBookNodeCount++;
	return NowNode;
}

//查询书籍函数方法
void SerachNode(struct BookNode* HeaderNode, char* BookName)
{
	if (HeaderNode == NULL)
	{
		printf("头节点为空!此库中没有书籍!\n");
	}
	for (size_t i = 0; i < nBookNodeCount; i++)
	{
		if (strcmp(HeaderNode->BookName, BookName) == 0)
		{
			printf("书名:%s\n", HeaderNode->BookName);
			printf("书价:%f\n", HeaderNode->BookPrice);
			printf("书号:%d\n", HeaderNode->BookNumber);
		}
		else
		{
			printf("查询不到此信息!\n");
		}
		HeaderNode = HeaderNode->Flink;
	}
	/*while方法
	while (HeaderNode->Flink != NULL)
	{
		HeaderNode = HeaderNode->Flink;
		if (strcmp(HeaderNode->BookName,BookName) == 0)
		{
			printf("书名:%s\n", HeaderNode->BookName);
			printf("书价:%f\n", HeaderNode->BookPrice);
			printf("书号:%d\n", HeaderNode->BookNumber);
		}
	}*/

}

//修改书籍函数方法
void ChangeNode(struct BookNode* HeaderNode, char* BookName, float BookPrice)
{
	if (HeaderNode == NULL)
	{
		printf("头节点为空!此库不存在信息!\n");
		return;
	}
	if (strcmp(HeaderNode->BookName, BookName) == 0)
	{
		HeaderNode->BookPrice = BookPrice;
	}
	while (HeaderNode->Flink !=NULL)
		HeaderNode = HeaderNode->Flink;
	{
		if(strcmp(HeaderNode->BookName,BookName) == 0)
		{
			HeaderNode->BookPrice = BookPrice;
			printf("修改成功!\n");
			return;
		}
		
	}
	printf("修改失败!\n");
		return;


}
//删除书籍函数方法
void DeleteNode(struct BookNode* HeaderNode, char* BookName)
{
	struct BookNode* TempNode = NULL;
	TempNode = HeaderNode;
	for (size_t i = 0; i < nBookNodeCount; i++)
	{
		if (strcmp(TempNode->BookName,BookName) == 0)
		{
			//删除头节点的方法
			if (TempNode = HeaderNode)
			{
				TempNode = HeaderNode->Flink;
				free(HeaderNode);
				ndHeaderNode = TempNode;
				HeaderNode = ndHeaderNode;
				nBookNodeCount--;
				printf("删除成功!\n");
				return;
			}
			//删除尾节点
			if (TempNode->Flink == NULL) 
			{
				TempNode->Blink->Flink = NULL;
				free(TempNode);
				nBookNodeCount--;
				printf("删除成功!\n");
				return;
			}
			TempNode->Blink->Flink = TempNode->Flink;
			TempNode->Flink->Blink = TempNode->Blink;
			free(TempNode);
			nBookNodeCount--;
			printf("删除成功!\n"); 
			return;
		}
                      TempNode = TempNode->Flink;
	}
	
}

咳咳,好像不是很规范,接下来是我自己的函数分析(部分描述不是很准确)

增加书籍函数方法分析

首先我们来理解一下增加书籍的函数

其定义的结构体中参数为NowNode,也就是当前的节点

然后是书名,书价,书号

结构体中定义了几个参数

第一个是新节点,也就是我们要添加的书籍新节点指针NewBookNode

第二个是临时节点,TempBookNode

第三个是头节点,HeadBookNode,它的值为当前节点

然后我们为新节点malloc出一个内存空间

然后第一个判断的新节点内存是否申请出来了

然后做第二个判断,如果当前节点为空,就把新节点置为当前节点,同时保险起见,将新节点的上一个节点和下一个节点置空(当前节点为空说明此时此链表为空链表)

如果当前节点不为空

做一个while循环

循环条件是头节点的下一个节点不为空(当前节点不为空证明此链表不是空链表,那么我们需要遍历出链表中的最后一个节点,以便我们将新节点插入到最后节点的尾部)

也就是说,循环最后可以得到最后一个头节点

此时的HeadBookNode就是此链表的最后一个头节点

那么我们用临时节点TempBookNode来接收此时的HeadBookNode

然后HeadBookNode指向它的下一个节点

while循环结束后,HeadBookNode的下一个节点就是我们的新节点NewBookNode,也就是此时新节点成功的链接到了链表的最后一个位置的下一个

同时,HeadBookNode的上一个节点,是临时节点TempBookNode

此时链表的节点指针,我们已经设置OK了

然后插入数据域

利用strcpy函数,将新节点中的BookName,赋值

同时赋值Price,Number完成增加书籍的操作

然后将新节点的下一个节点置为空

(同时我们做了一个节点计数器,nBookNodeCount,用来计算节点数量)

查找书籍函数方法分析

参数为头节点,以及书名作为查询的依据

这里可以用两个方法,如果没有前面的节点计数器,我们就用while循环的方法

While:

循环条件为头节点的下一个节点不为空,那么也就是遍历所有的节点

同时将头节点置为它下一个节点,依次来遍历

然后if条件判断,用strcmp对比函数,来对比输入的书名是否一样,如果一样打印其信息

for:

利用节点计数器,已知其由多少个节点,与while一样做if判断打印

并且需要将头节点置为它下一个节点(因为指针并不会自己往下遍历)

修改书籍函数方法分析

修改函数参数为头节点,书籍名称,书籍价格,通过书籍名称查找修改书籍价格

首先做if判断,如果头节点为空,则直接返回

然后首先做第一个头节点处理

如果头节点中的书名和输入的书名相同,则修改其价格

然后做while循环,循环条件为头节点的下一个节点不为空,而头节点我们已经处理了,所以只需要从第二个节点开始

HeaderNode = HeaderNode->Flink

然后做判断,如果相同修改其定价

删除书籍函数方法分析

参数为头节点和书籍名字,通过书籍名字来删除

先定义一个临时节点TempNode,将其置为空

然后临时节点等于头节点

然后做for循环,循环条件是i小于节点总数

然后作比较,如果书名相同进入if内部执行

如果TempNode等于头节点,则将TempNode作为头节点的下一个节点

同时释放掉头节点,然后为了更清晰,我们用一个全局变量ndHeaderNode来接收TempNode,同时将头节点再次赋值为ndHeaderNode

同时因为删除了一个节点,节点计数器-1

删除尾节点:

临时节点的下一个为空,则是尾节点

同时TempNode的上一个的下一个,也就是本身置空

释放掉TempNode,节点计数器-1

如果是中间的节点需要删除

那么TempNode的上一个节点的下一个节点就是TempNode的下一个节点

TempNode下一个节点的上一个节点就是TempNode的上一个节点

同时free释放掉TempNode,节点计数器-1

记住后面的TempNode = TempNode->Flink,让其指向下一个,否则永远都只在一个节点中操作

总结

部分描述可能不是很准确,大致的意思是那个

而且代码存在优化空间,只不过我改了几个地方总是会报错,也是刚开始学习这门编程语言,所以肯定存在不足和提升空间

后面我也会优化一下代码结构

以上就是我个人的代码分析