(7) Bidirectional linked list

source ：http://c.biancheng.net/view/3342.html
The list we have learned so far , Whether it's a dynamic linked list or a static linked list , Each node in the table contains only one pointer （ The cursor ）, And they all point to the direct successor nodes , This kind of linked list is usually called one-way linked list （ Or single linked list ）.

Although using a single linked list can 100% Solve the logical relationship as “ one-on-one ” Data storage problem , But when solving some special problems , Single linked list is not the most efficient storage structure . for instance , If the algorithm needs to find a large number of forward nodes of a specified node , Using a single linked list is undoubtedly disastrous , Because a single linked list is more suitable for “ Before and after ” look for , and “ From back to front ” Finding is not its strength .

In order to solve similar problems efficiently , In this section, learn about the two-way linked list （ Double linked list for short ）.

Understand two-way linked list from name , That is, the linked list is “ two-way ” Of , Pictured 1 Shown ：

Schematic diagram of two-way linked list structure

two-way , It means that the logical relationship between nodes is bidirectional , But usually the header pointer is set to only one , Unless the actual situation requires .

From the picture 1 Can be seen in , Each node in the bidirectional linked list contains the following 3 Some information （ Pictured 2 Shown ）：

1. Pointer to the domain ： Used to point to the direct predecessor node of the current node ;
2. Data fields ： Used to store data elements .
3. Pointer to the domain ： Used to point to the immediate successor of the current node ;

therefore , The node structure of double linked list uses C Language is realized as ：

typedef struct line{
    struct line * prior; // Point directly forward 
    int data;
    struct line * next; // Point to the direct successor 
}line;

Through the two-way linked list to achieve the library management system . The main function is to add, delete, modify and query .

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

int nCount = 0;

// Book structure 
typedef struct Node {
	struct Node * Blink;
	struct Node * Flink;
	char BookName[50];
	float BookPrice;
	int BookNumber;
};

struct Node * ndHeaderNode = NULL;

// Add book functions 
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;
}
// Functions for querying books 
void QueryNode(struct Node * HeaderNode, char * BookName)
{
	if (HeaderNode == NULL)
	{
		printf("ERROR:HeaderNode == NULL\n");
		return;
	}
	if (strcmp(HeaderNode->BookName, BookName) == 0)
	{
		printf(" Title ：%s\n", HeaderNode->BookName);
		printf(" pricing ：%f\n", HeaderNode->BookPrice);
		printf(" Book number ：%d\n", HeaderNode->BookNumber);
		return;
	}
	while (HeaderNode->Flink != NULL)
	{
		HeaderNode = HeaderNode->Flink;
		if (strcmp(HeaderNode->BookName, BookName) == 0)
		{
			printf(" Title ：%s\n", HeaderNode->BookName);
			printf(" pricing ：%f\n", HeaderNode->BookPrice);
			printf(" Book number ：%d\n", HeaderNode->BookNumber);
			return;
		}
	}
	printf("Can Not Found!\n");
}
// Modify book information 
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;
}
// Delete book functions 
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(" Please enter the function you want to use :\n");
		printf("1. Add book information \n");
		printf("2. Search for book information \n");
		printf("3. Modify book information \n");
		printf("4. Delete book information \n");
		scanf("%d", &ReadFlag);
		switch (ReadFlag)
		{
		case 1:
			//memset(szBookName, 0 ,50);
			printf(" Please enter the title of the book ：");
			scanf("%s", szBookName);
			printf(" Please enter the pricing  ：");
			scanf("%f", &fBookPrice);
			printf(" Please enter the book number ：");
			scanf("%d", &nBookNumber);
			// New function 
			ndHeaderNode = AppendNode(ndHeaderNode, szBookName, nBookNumber, fBookPrice);
			break;
		case 2:
			printf(" Please enter the title of the book ：");
			scanf("%s", szBookName);
			// Query function 
			QueryNode(ndHeaderNode, szBookName);
			break;
		case 3:
			printf(" Please enter the title of the book ：");
			scanf("%s", szBookName);
			printf(" Please enter the new pricing ：");
			scanf("%f", &fNewBookPrice);
			//code  Modified function 
			ModifyNode(ndHeaderNode, szBookName, fNewBookPrice);
			break;
		case 4:
			printf(" Please enter the title of the book ：");
			scanf("%s", szBookName);
			// Delete function 
			DeleteNode(ndHeaderNode, szBookName);
			break;
		}
	}
}
int main()
{
	Start();
	return 0;
}