# 静态链表的基本原理

当构建一个线性结构时应满足以下条件
1.唯一的首元素与唯一的尾元素
2.除第一个元素外,其余每个元素只有一个头元素
3.除最后一个元素外,其余每个元素只有一个尾元素
此外,由于C语言中有指针操作能过直接操作计算机内存,
但有些编程语言是没有指针概念的,
因此倘若想在没有指针操作下,要创建一个链表就只能通过模拟链表的概念来完成了,
就如接下来通过链表数组来实现的一个单链表结构。
倘若构建一个具有线性结构的静态链表时,
应具有以下线性结构的基本功能
1.首部插入
2.尾部插入
3.选择插入
4.长度获取
5.首部弹出
6.尾部弹出
7.元素搜查
8.元素删除
9.选择删除
10.元素排序
11.顺序逆转
12.元素清除
13.空间销毁
等操作。

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

  • 额外用了 C++ 的 & 别名操作 (多个不同的变量指向同一块地址空间)
  • 部分函数实现重复性太高,以后有空再补
Static_L_Node_.h(头文件)
#pragma once
#include<stdio.h>
#include<assert.h>
#define MAX_SPACE 12
typedef int Element;
static struct Static_Link_Node
{
	int element;
	int index;
};
// 重定义的静态链表结构体为一个静态链表结构体数组
typedef struct Static_Link_Node SL_Node[MAX_SPACE];
void Initial_Node(SL_Node& L_Node);
void Show_Menu();
void push_back(SL_Node& L_Node, Element element);
void push_front(SL_Node& L_Node, Element element);
void pop_back(SL_Node& L_Node);
void pop_front(SL_Node& L_Node);
int get_sl_length(SL_Node& L_Node);
void Show_SL_Node(SL_Node& L_Node);
Static_L_Node_functions.cpp
#include"Static_L_Node_.h"
void Initial_Node(SL_Node& L_Node)
{
	int i = 0;
	L_Node[0].element = 0;
	for (i = 1; i < MAX_SPACE; i++)
	{
		L_Node[i - 1].index = i;
	}
	L_Node[MAX_SPACE - 1].index = 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(SL_Node& L_Node, Element element)
{
	assert(-1 != L_Node[0].index);
	if (!(L_Node[0].element))
	{
		L_Node[++L_Node[0].element].element = element;
		L_Node[0].index = 1;
		L_Node[L_Node[0].element].index = -1;
	}
	else if (MAX_SPACE - 1 == L_Node[0].element)
		printf("存储空间已满\n");
	else
	{
		int i = 0;
		while (-1 != L_Node[i].index)
		{
			i = L_Node[i].index;
		}
		L_Node[i].index = ++L_Node[0].element;
		L_Node[L_Node[0].element].element = element;
		L_Node[L_Node[0].element].index = -1;
	}	
}
void push_front(SL_Node& L_Node, Element element)
{
	assert(-1 != L_Node[0].index);
	if (!(L_Node[0].element))
	{
		L_Node[++L_Node[0].element].element = element;
		L_Node[0].index = L_Node[0].element;
		L_Node[L_Node[0].element].index = -1;
	}
	else if (MAX_SPACE - 1 == L_Node[0].element)
		printf("存储空间已满\n");
	else
	{
		L_Node[++L_Node[0].element].element = element;
		L_Node[L_Node[0].element].index = L_Node[0].index;
		L_Node[0].index = L_Node[0].element;
	}
}
void pop_back(SL_Node& L_Node)
{
	assert(-1 != L_Node[0].index);
	if (0 == L_Node[0].element)
		printf("存储空间未有存储值\n");
	else
	{
		int i = 0;
		int P_i = 0;
		while (-1 != L_Node[i].index)
		{
			P_i = i;
			i = L_Node[i].index;
		}
		L_Node[0].element--;
		printf("值%d已弹出\n", L_Node[i].element);
		if (!(L_Node[0].element))
			return;
		L_Node[P_i].index = -1;
	}
}
void pop_front(SL_Node& L_Node)
{
	assert(-1 != L_Node[0].index);
	if(!(L_Node[0].element))
		printf("存储空间未有存储值\n");
	else
	{
		L_Node[0].element--;
		if (!(L_Node[0].element))
			return;
		L_Node[0].index = L_Node[L_Node[0].index].index;
	}
}
void Show_SL_Node(SL_Node& L_Node)
{
	assert(-1 != L_Node[0].index);
	if (!(L_Node[0].element))
		printf("静态链表空间未有存储值\n");
	else
	{
		int i = 0;
		
		i = L_Node[i].index;
		while (-1 != L_Node[i].index)
		{
			printf("%d->", L_Node[i].element);
			i = L_Node[i].index;
		}
		printf("%d->NULL(-1)", L_Node[i].element);
	}
}
int get_sl_length(SL_Node& L_Node)
{
	assert(-1 != L_Node[0].index);
	printf("存储空间长度为%d\n", L_Node[0].element);
	return L_Node[0].element;
}
Static_Link_Node_main.cpp
#define _CRT_SECURE_NO_WARNINGS 1
#include"Static_L_Node_.h"
int main()
{
	int option = 0;
	int pos = 0;
	Element element = 0;
	SL_Node S_Link_Node;
	Initial_Node(S_Link_Node);
	Show_Menu();
	while (printf("选择为>:"), scanf("%d", &option), option)
	{
		switch (option)
		{
		case 1:
			printf("插入值为(数字-1终止)>:");
			while (scanf("%d", &element), -1 != element)
			{
				push_back(S_Link_Node, element);
			}
			break;
		case 2:
			printf("插入值为(数字-1终止)>:");
			while (scanf("%d", &element), -1 != element)
			{
				push_front(S_Link_Node, element);
			}
			break;
		case 3:
			pop_back(S_Link_Node);
			break;
		case 4:
			pop_front(S_Link_Node);
			break;
		case 5:
			Show_SL_Node(S_Link_Node);
			break;
		case 6:
			get_sl_length(S_Link_Node);
			break;
		//case 7:
		//	printf ("查找的值为>:");
		//	scanf("%d", &element);
		//	find(S_Link_Node, element);
		//	break;
		//case 8:
		//	printf ("插入值与位置>:");
		//	scanf("%d %d", &element, &pos);
		//	insert_pos(S_Link_Node, element, pos);
		//	break;
		//case 9:
		//	printf ("需要删除的元素值>:");
		//	scanf("%d", &element);
		//	delete_val(S_Link_Node, element);
		//	break;
		//case 10:
		//	printf ("需要删除的元素位置>:");
		//	scanf("%d", &pos);
		//	delete_pos(S_Link_Node, pos);
		//	break;
		//case 11:
		//	sort(S_Link_Node);
		//	break;
		//case 12:
		//	reverse(S_Link_Node);
		//	break;
		//case 13:
		//	clean(S_Link_Node);
		//	break;
		//case 14:
		//	destroy_space(S_Link_Node);
		//	break;
		default: printf("输入值不在选择范围\n");
		}
		Show_Menu();
	}
	//destroy_space(S_Link_Node);
	printf("已退出\n");
	return 0;
}