（7）双向链表

来源：http://c.biancheng.net/view/3342.html
目前我们所学到的链表，无论是动态链表还是静态链表，表中各节点中都只包含一个指针（游标），且都统一指向直接后继节点，通常称这类链表为单向链表（或单链表）。

虽然使用单链表能 100% 解决逻辑关系为 “一对一” 数据的存储问题，但在解决某些特殊问题时，单链表并不是效率最优的存储结构。比如说，如果算法中需要大量地找某指定结点的前趋结点，使用单链表无疑是灾难性的，因为单链表更适合 “从前往后” 找，而 “从后往前” 找并不是它的强项。

为了能够高效率解决类似的问题，本节来学习双向链表（简称双链表）。

从名字上理解双向链表，即链表是 “双向” 的，如图 1 所示：

双向链表结构示意图

双向，指的是各节点之间的逻辑关系是双向的，但通常头指针只设置一个，除非实际情况需要。

从图 1 中可以看到，双向链表中各节点包含以下 3 部分信息（如图 2 所示）：

1. 指针域：用于指向当前节点的直接前驱节点；
2. 数据域：用于存储数据元素。
3. 指针域：用于指向当前节点的直接后继节点；

因此，双链表的节点结构用 C 语言实现为：

typedef struct line{
    struct line * prior; //指向直接前趋
    int data;
    struct line * next; //指向直接后继
}line;

通过双向链表实现图书管理系统。主要实现的功能是增删改查。

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

int nCount = 0;

//书籍结构
typedef struct Node {
	struct Node * Blink;
	struct Node * Flink;
	char BookName[50];
	float BookPrice;
	int BookNumber;
};

struct Node * ndHeaderNode = NULL;

//增加书籍的函数
struct Node * AppendNode(struct Node * CurrentNode, char * BookName, int BookNumber, float BookPrice)
{
	struct Node * pNewNode = NULL;
	struct Node * pTempNode = NULL;
	struct Node * pHeadNode = CurrentNode;
	pNewNode = (struct Node *)malloc(sizeof(struct Node));
	if (pNewNode == NULL)
	{
		printf("memory malloc failed!\n");
		return pNewNode;
	}
	if (CurrentNode == NULL)
	{
		CurrentNode = pNewNode;
		CurrentNode->Blink = NULL;
		CurrentNode->Flink = NULL;
	}
	else
	{
		while (pHeadNode->Flink != NULL)
		{
			pTempNode = pHeadNode;
			pHeadNode = pHeadNode->Flink;
		}
		pHeadNode->Flink = pNewNode;
		pHeadNode->Blink = pTempNode;
	}
	strcpy(pNewNode->BookName, BookName);
	pNewNode->BookPrice = BookPrice;
	pNewNode->BookNumber = BookNumber;
	pNewNode->Flink = NULL;
	nCount++;
	return CurrentNode;
}
//查询书籍的函数
void QueryNode(struct Node * HeaderNode, char * BookName)
{
	if (HeaderNode == NULL)
	{
		printf("ERROR:HeaderNode == NULL\n");
		return;
	}
	if (strcmp(HeaderNode->BookName, BookName) == 0)
	{
		printf("书名：%s\n", HeaderNode->BookName);
		printf("定价：%f\n", HeaderNode->BookPrice);
		printf("书号：%d\n", HeaderNode->BookNumber);
		return;
	}
	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);
			return;
		}
	}
	printf("Can Not Found!\n");
}
//修改书籍信息
void ModifyNode(struct Node * HeaderNode, char * BookName, float BookPrice)
{
	if (HeaderNode == NULL)
	{
		printf("ERROR:HeaderNode == NULL\n");
		return;
	}
	if (strcmp(HeaderNode->BookName, BookName) == 0)
	{
		HeaderNode->BookPrice = BookPrice;
		printf("ModifyNode Success!\n");
		return;
	}
	while (HeaderNode->Flink != NULL)
	{
		HeaderNode = HeaderNode->Flink;
		if (strcmp(HeaderNode->BookName, BookName) == 0)
		{
			HeaderNode->BookPrice = BookPrice;
			printf("ModifyNode Success!\n");
			return;
		}
	}

	printf("ModifyNode Failed!\n");
	return;
}
//删除书籍的函数
void DeleteNode(struct Node * HeaderNode, char * BookName)
{
	struct Node * pNode = NULL;
	pNode = HeaderNode;
	for (size_t i = 0; i < nCount; i++)
	{
		if (strcmp(pNode->BookName, BookName) == 0)
		{
			if (pNode == HeaderNode)
			{
				pNode = HeaderNode->Flink;
				free(HeaderNode);
				ndHeaderNode = pNode;
				HeaderNode = ndHeaderNode;
				nCount--;
				return;
			}
			if (pNode->Flink == NULL)
			{
				pNode->Blink->Flink = NULL;
				free(pNode);
				nCount--;
				printf("Delete Success!\n");
				return;
			}

			pNode->Blink->Flink = pNode->Flink;
			pNode->Flink->Blink = pNode->Blink;
			free(pNode);
			nCount--;
			printf("Delete Success!\n");
			return;
		}
	}
}
void Start()
{
	while (1)
	{
		int ReadFlag = 0;
		char szBookName[50];
		float fBookPrice = 0;
		float fNewBookPrice = 0;
		int nBookNumber = 0;
		printf("请输入需要使用的功能:\n");
		printf("1.添加书籍信息\n");
		printf("2.查询书籍信息\n");
		printf("3.修改书籍信息\n");
		printf("4.删除书籍信息\n");
		scanf("%d", &ReadFlag);
		switch (ReadFlag)
		{
		case 1:
			//memset(szBookName, 0 ,50);
			printf("请输入书名：");
			scanf("%s", szBookName);
			printf("请输入定价 ：");
			scanf("%f", &fBookPrice);
			printf("请输入书号：");
			scanf("%d", &nBookNumber);
			//新增函数
			ndHeaderNode = AppendNode(ndHeaderNode, szBookName, nBookNumber, fBookPrice);
			break;
		case 2:
			printf("请输入书名：");
			scanf("%s", szBookName);
			//查询函数
			QueryNode(ndHeaderNode, szBookName);
			break;
		case 3:
			printf("请输入书名：");
			scanf("%s", szBookName);
			printf("请输入新的定价：");
			scanf("%f", &fNewBookPrice);
			//code 修改的函数
			ModifyNode(ndHeaderNode, szBookName, fNewBookPrice);
			break;
		case 4:
			printf("请输入书名：");
			scanf("%s", szBookName);
			//删除函数
			DeleteNode(ndHeaderNode, szBookName);
			break;
		}
	}
}
int main()
{
	Start();
	return 0;
}