# 双链表的基本原理

当构建一个线性结构时应满足以下条件
1.唯一的首元素与唯一的尾元素
2.除第一个元素外,其余每个元素只有一个头元素
3.除最后一个元素外,其余每个元素只有一个尾元素
此外,单链表的储存结构的特点是用任意的储存单元来链接储存的数据元素,
每一个链表节点中都存有当前链表节点的`数据`以及下一位链表节点的`地址`
但想要形成一个双向的链表,这往往是不够的,
为此,还需在单链表的基础上额外增加一个能指向上一位节点的链表指针。
倘若构建一个具有线性结构的双链表时,
应具有以下线性结构的基本功能
1.首部插入
2.尾部插入
3.选择插入
4.长度获取
5.首部弹出
6.尾部弹出
7.元素搜查
8.元素删除
9.选择删除
10.元素排序
11.顺序逆转
12.元素清除
13.空间销毁
等操作。

# 双链表的基本创建 (整型版本)

  • 部分实现函数与单链表基本一致,往日若有空再补
Double_Link_Node_.h(头文件)
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int Element;
struct Double_Link_Node
{
	Element element;
	struct Double_Link_Node* pre;
	struct Double_Link_Node* next;
};
struct Double_Link_Pointer
{
	int size;
	struct Double_Link_Node* head;
	struct Double_Link_Node* tail;
};
void Initial_Node(struct Double_Link_Pointer* L_Node);
void Show_Menu();
void push_back(struct Double_Link_Pointer* L_Node, Element element);
void push_front(struct Double_Link_Pointer* L_Node, Element element);
void pop_back(struct Double_Link_Pointer* L_Node);
void pop_front(struct Double_Link_Pointer* L_Node);
void Show_DList_Node(struct Double_Link_Pointer* L_Node);
int get_length(struct Double_Link_Pointer* L_Node);
//struct Double_Link_Node* find(struct Double_Link_Pointer* L_Node, Element element);
//void insert_pos(struct Double_Link_Pointer* L_Node, Element element, int pos);
//void delete_val(struct Double_Link_Pointer* L_Node, Element element);
//void delete_pos(struct Double_Link_Pointer* L_Node, int pos);
//void sort(struct Double_Link_Pointer* L_Node);
//void reverse(struct Double_Link_Pointer* L_Node);
//void clean(struct Double_Link_Pointer* L_Node);
//void destroy_space(struct Double_Link_Pointer* L_Node);
Double_Link_functions.c
#include"Double_Link_Node_.h"
void Initial_Node(struct Double_Link_Pointer* L_Node)
{
	L_Node->head = NULL;
	L_Node->tail = NULL;
	L_Node->size = 0;
}
void Show_Menu()
{
	printf("\n********************************************\n");
	printf(" [1]  push_back  ********[2]  push_front   *\n");
	printf(" [3]  pop_back   ********[4]  pop_front    *\n");
	printf(" [5]  Show_Node  ********[6]  get_length   *\n");
	printf(" [7]  find       ********[8]  insert_pos   *\n");
	printf(" [9]  delete_val ********[10] delete_pos   *\n");
	printf(" [11] sort       ********[12] reverse      *\n");
	printf(" [13] clear      ********[14] destroy_space*\n");
	printf(" [0]  quit_system                          *\n");
	printf("********************************************\n");
}
void push_back(struct Double_Link_Pointer* L_Node, Element element)
{
	struct Double_Link_Node* P_Node = (struct Double_Link_Node*)malloc(sizeof(struct Double_Link_Node));
	P_Node->element = element;
	P_Node->next = NULL;
	if (!(L_Node->size))
	{
		P_Node->pre = NULL;
		L_Node->head = P_Node;
		L_Node->tail = P_Node;
		L_Node->size++;
	}
	else
	{
		P_Node->pre = L_Node->tail;
		L_Node->tail->next = P_Node;
		L_Node->tail = P_Node;
		L_Node->size++;
	}
	printf("值%d已插入\n", element);
}
void push_front(struct Double_Link_Pointer* L_Node, Element element)
{
	struct Double_Link_Node* P_Node = (struct Double_Link_Node*)malloc(sizeof(struct Double_Link_Node));
	P_Node->element = element;
	P_Node->next = NULL;
	if (!(L_Node->size))
	{
		P_Node->pre = NULL;
		L_Node->head = P_Node;
		L_Node->tail = P_Node;
		L_Node->size++;
	}
	else
	{
		P_Node->next = L_Node->head;
		L_Node->head->pre = P_Node;
		P_Node->pre = NULL;
		L_Node->head = P_Node;
		L_Node->size++;
	}
	printf("值%d已插入\n", element);
}
void pop_back(struct Double_Link_Pointer* L_Node)
{
	if (!(L_Node->size))
		printf("存储空间内未有存储值\n");
	else
	{
		struct Double_Link_Node* P_Node = L_Node->tail->pre;
		printf("值%d已弹出\n", L_Node->tail->element);
		free(L_Node->tail);
		L_Node->size--;
		L_Node->tail = P_Node;
		if (!(L_Node->size))
			L_Node->head = NULL;
		else
			L_Node->tail->next = NULL;
	}
}
void pop_front(struct Double_Link_Pointer* L_Node)
{
	if (!(L_Node->size))
		printf("存储空间内未有存储值\n");
	else
	{
		struct Double_Link_Node* P_Node = L_Node->head->next;
		printf("值%d已弹出\n", L_Node->head->element);
		free(L_Node->head);
		L_Node->head = NULL;
		L_Node->size--;
		L_Node->head = P_Node;
		if (!(L_Node->size))
			L_Node->tail = NULL;
	}
}
void Show_DList_Node(struct Double_Link_Pointer* L_Node)
{
	if (!(L_Node->size))
	{
		printf("空间内无储存值\n");
	}
	else
	{
		struct Double_Link_Node* P_Node = L_Node->head;
		while (P_Node)
		{
			if (!(P_Node->next))
			{
				printf("%d->NULL", P_Node->element);
				break;
			}
			printf("%d->", P_Node->element);
			P_Node = P_Node->next;
		}
	}
}
int get_length(struct Double_Link_Pointer* L_Node)
{
	printf("当前空间链表长度为%d\n", L_Node->size);
	return L_Node->size;
}
Double_Link_main.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Double_Link_Node_.h"
int main()
{
	int option = 0;
	int pos = 0;
	Element element = 0;
	struct Double_Link_Pointer DLP;
	Initial_Node(&DLP);
	Show_Menu();
	while (printf("选择为>:"), scanf("%d", &option), option)
	{
		switch (option)
		{
		case 1:
			printf("插入值为(数字-1终止)>:");
			while (scanf("%d", &element), -1 != element)
			{
				push_back(&DLP, element);
			}
			break;
		case 2:
			printf("插入值为(数字-1终止)>:");
			while (scanf("%d", &element), -1 != element)
			{
				push_front(&DLP, element);
			}
			break;
		case 3:
			pop_back(&DLP);
			break;
		case 4:
			pop_front(&DLP);
			break;
		case 5:
			Show_DList_Node(&DLP);
			break;
		case 6:
			get_length(&DLP);
			break;
		//case 7:
		//	printf ("查找的值为>:");
		//	scanf("%d", &element);
		//	find(&DLP, element);
		//	break;
		//case 8:
		//	printf ("插入值与位置>:");
		//	scanf("%d %d", &element, &pos);
		//	insert_pos(&DLP, element, pos);
		//	break;
		//case 9:
		//	printf ("需要删除的元素值>:");
		//	scanf("%d", &element);
		//	delete_val(&DLP, element);
		//	break;
		//case 10:
		//	printf ("需要删除的元素位置>:");
		//	scanf("%d", &pos);
		//	delete_pos(&DLP, pos);
		//	break;
		//case 11:
		//	sort(&DLP);
		//	break;
		//case 12:
		//	reverse(&DLP);
		//	break;
		//case 13:
		//	clean(&DLP);
		//	break;
		//case 14:
		//	destroy_space(&DLP);
		//	break;
		default: printf("输入值不在选择范围\n");
		}
		Show_Menu();
	}
	//destroy_space(&DLP);
	printf("已退出\n");
	return 0;
}