# 顺序表的基本原理

当构建一个线性结构时应满足以下条件
1.唯一的首元素与唯一的尾元素
2.除第一个元素外,其余每个元素只有一个头元素
3.除最后一个元素外,其余每个元素只有一个尾元素
此外,线性表的顺序表示指的是用一组连续地址依次储存元素,
并且顺序表的存储空间大小是被限制的。
倘若构建一个具有线性结构的顺序表时,
应具有以下线性结构的基本功能
1.首部插入
2.尾部插入
3.选择插入
4.长度获取
5.首部弹出
6.尾部弹出
7.元素搜查
8.元素删除
9.选择删除
10.元素排序
11.顺序逆转
12.元素清除
13.空间销毁
等操作。

# 顺序表的基本创建

SeqList_.h(头文件)
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#define MAX_SPACE 8// 方便初始容量设定
// 字符形式
#define END_F ']'// 结束标志符
#define D_FORM "%c"// 字符输出格式
#define DEBUG_CHAR
typedef char DateType;
//// 整型形式
//#define END_F -1 // 结束标志数
//#define D_FORM "% d"// 整型输出格式
//#define DEBUG_INT
//typedef int DateType;
struct Link_List
{
	DateType* Data_List;// 指向一段连续的空间 (数组)
	int max_space;
	int size;
};
void Initial_SeqList(struct Link_List* List);
void Show_Menu();
void push_back(struct Link_List* List, const DateType element);
void push_front(struct Link_List* List, const DateType element);
void pop_back(struct Link_List* List);
void pop_front(struct Link_List* List);
void Show_SeqList(const struct Link_List* List);
int get_length(const struct Link_List* List);
int find(const struct Link_List* List, const DateType element);
void insert_pos(struct Link_List* List, const DateType element, const int pos);
void delete_val(struct Link_List* List, const DateType element);
void delete_pos(struct Link_List* List, const int pos);
void sort(struct Link_List* List, int (*cp)(void*, void*));
void reverse(struct Link_List* List);
void clean(struct Link_List* List);
void destroy(struct Link_List* List);
SeqList_functions.c
#include"SeqList_.h"
// 分配顺序表空间与数值初始化
void Initial_SeqList(struct Link_List* List)
{
	assert(NULL != List);
	List->Data_List = (DateType*)malloc(sizeof(DateType) * MAX_SPACE);
	List->max_space = MAX_SPACE;
	List->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_SeqList******[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] destory_space*\n");
	printf(" [0]  quit_system ******                  *\n");
	printf("*******************************************\n");
}
// 顺序表末端插入
void push_back(struct Link_List* List,const DateType element)
{
	assert(NULL != List);
	if (List->size == List->max_space)
	{
#ifdef DEBUG_INT
		printf("空间已满,值%d未插入\n", element);
#endif
#ifdef DEBUG_CHAR
		printf("空间已满,值%c未插入\n", element);
#endif
		return;
	}
	List->Data_List[List->size++] = element;
}
// 顺序表前端插入
void push_front(struct Link_List* List,const DateType element)
{
	assert(NULL != List);
	if (List->size == List->max_space)
	{
#ifdef DEBUG_INT
		printf("空间已满,值%d未插入\n", element);
#endif
#ifdef DEBUG_CHAR
		printf("空间已满,值%c未插入\n", element);
#endif
	}
	else
	{
		int i = 0;
		// 先扩容再后移
		for (i = (++List->size) - 1; i > 0; --i)
			(List->Data_List)[i] = (List->Data_List)[i - 1];
		(List->Data_List)[0] = element;
	}
}
// 顺序表末端弹出一位元素
void pop_back(struct Link_List* List)
{
	assert(NULL != List);
	if (!(List->size))
		return;
	else
	{
		#ifdef DEBUG_INT
			printf("值%d已弹出\n", (List->Data_List)[(List->size) - 1]);
		#endif
		#ifdef DEBUG_CHAR
			printf("值%c已弹出\n", (List->Data_List)[(List->size) - 1]);
		#endif
		--List->size;
	}
}
// 顺序表头部弹出一位元素
void pop_front(struct Link_List* List)
{
	assert(NULL != List);
	if (!(List->size))
		return;
	else if (1 == List->size)
	{
		#ifdef DEBUG_INT
			printf("值%d已弹出\n", (List->Data_List)[0]);
		#endif
		#ifdef DEBUG_CHAR
			printf("值%c已弹出\n", (List->Data_List)[0]);
		#endif
		--List->size;
	}
	else
	{
		int i = 0;
		#ifdef DEBUG_INT
			printf("值%d已弹出\n", (List->Data_List)[0]);
		#endif
		#ifdef DEBUG_CHAR
			printf("值%c已弹出\n", (List->Data_List)[0]);
		#endif
		// 前移覆盖后缩容
		for (i = 0; i < List->size - 1; ++i)
		{
			(List->Data_List)[i] = (List->Data_List)[i + 1];
		}
		--List->size;
	}
}
// 展示当前存储空间
void Show_SeqList(const struct Link_List* List)
{
	assert(NULL != List);
	if (!(List->size))
		return;
	else
	{
		int i = 0;
		printf("SeqList内存储值>:\n");
		for (i = 0; i < List->size; ++i)
		{
			if (i == List->size - 1)
			{
				#ifdef DEBUG_INT
					printf("%d\n", (List->Data_List)[i]);
				#endif
				#ifdef DEBUG_CHAR
					printf("%c\n", (List->Data_List)[i]);
				#endif
			}
			else
			{
				#ifdef DEBUG_INT
					printf("%d-", (List->Data_List)[i]);
				#endif
				#ifdef DEBUG_CHAR
					printf("%c-", (List->Data_List)[i]);
				#endif
			}
		}
	}
}
// 获取当期存储空间的长度
int get_length(const struct Link_List* List)
{
	assert(NULL != List);
	printf("当前储存长度为%d\n", List->size);
	return List->size;
}
// 特定元素位置查找
int find(const struct Link_List* List,const DateType element)
{
	assert(NULL != List);
	if (!(List->size))
		return -1;
	else
	{
		int i = 0;
		for (i = 0; i < List->size - 1; ++i)
		{
			if (element == (List->Data_List)[i])
			{
				#ifdef DEBUG_INT
					printf("%d为第%d个元素\n", element, i + 1);
				#endif
				#ifdef DEBUG_CHAR
					printf("%c为第%d个元素\n", element, i + 1);
				#endif
				return i;
			}
		}
#ifdef DEBUG_INT
		printf("未找到%d元素\n", element);2
#endif
#ifdef DEBUG_CHAR
		printf("未找到%c元素\n", element);
#endif
		return -1;
	}
}
// 特定元素的特定位置插入
void insert_pos(struct Link_List* List,const DateType element,const int pos)
{
	assert(NULL != List);
	// 满了不能插入
	if (List->size == List->max_space)
		return;
	else if (pos < 0 || pos > List->size)// 插入位置不在允许范围内
		return;
	else
	{
		int i = 0;
		int j = 0;
		// 先扩容再后移最后插入
		for (i = 0; i < (List->size) - 1; ++i)
		{
			if (pos - 1 == i)
			{
				(List->size)++;
				for (j = (List->size) - 1; j > i; --j)
				{
					(List->Data_List)[j] = (List->Data_List)[j - 1];
				}
				(List->Data_List)[i] = element;
				#ifdef DEBUG_INT
					printf("%d插入成功\n", element);
				#endif
				#ifdef DEBUG_CHAR
					printf("%c插入成功\n", element);
				#endif
			}
		}
	}
}
// 删除顺序表中特定值的所有元素
void delete_val(struct Link_List* List,const DateType element)
{
	assert(NULL != List);
	if (!(List->size))
		return;
	else
	{
		int i = 0;
		// 先判断值,倘若值为 element,前移覆盖再后退
		while (i < List->size)
		{
			int j = 0;
			if (element == List->Data_List[i])
			{
				for (j = i; j < List->size - 1; ++j)
				{
					List->Data_List[j] = List->Data_List[j + 1];
				}
				--List->size;
				--i;
			}
			++i;
		}
		#ifdef DEBUG_INT
			printf("值为%d的元素已删除成功\n",element);
		#endif
		#ifdef DEBUG_CHAR
			printf("值为%c的元素已删除成功\n", element);
		#endif
	}
}
// 删除顺序表中的特定位置
void delete_pos(struct Link_List* List,const int pos)
{
	assert(NULL != List);
	if (!(List->size))
		return;
	else if (pos < 0 || pos > List->size)
		return;
	else
	{
		int i = 0;
		int j = 0;
		// 前移覆盖再缩容
		for (i = 0; i < List->size; ++i)
		{
			if (pos - 1 == i)
			{
				for (j = i; j < (List->size); ++j)
				{
					(List->Data_List)[j] = (List->Data_List)[j + 1];
				}
				--List->size;
				printf("第%d位的元素已删除成功\n",pos);
				break;
			}
		}
	}
}
// 顺序表中的万能冒泡排序
void sort(struct Link_List* List, int (*cp)(void*, void*))
{
	assert(NULL != List);
	if (!(List->size))
		return;
	else if (1 == List->size)
		return;
	else
	{
		int i = 0;
		int j = 0;
		for (i = 0; i < (List->size) - 1; ++i)
		{
			int trans = 0;
			for (j = 0; j < (List->size) - i - 1; ++j)
			{
				if (1 == cp(&((List->Data_List)[j]), &((List->Data_List)[j + 1])))
				{
					trans = (List->Data_List)[j];
					(List->Data_List)[j] = (List->Data_List)[j + 1];
					(List->Data_List)[j + 1] = trans;
				}
			}
		}
	}
}
// 值交换逆转
void reverse(struct Link_List* List)
{
	assert(NULL != List);
	if (!(List->size))
		return;
	else if (1 == List->size)
		return;
	else
	{
		int i = 0;
		int num = 0;
		int j = List->size - 1;
		int mid = List->size / 2;
		for (i = 0; i < mid; ++i)
		{
			num = (List->Data_List)[i];
			(List->Data_List)[i] = (List->Data_List)[j];
			(List->Data_List)[j--] = num;
		}
	}
}
// 清空顺序表
void clean(struct Link_List* List)
{
	assert(NULL != List);
	List->size = 0;
}
// 摧毁当前顺序表空间内存
void destroy(struct Link_List* List)
{
	assert(NULL != List);
	free(List->Data_List);
	List->Data_List = NULL;
	List->size = 0;
}
SeqList_main.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList_.h"
static int cmp(void* data1, void* data2)
{
	DateType* d1;
	DateType* d2;
	d1 = (DateType*)data1;
	d2 = (DateType*)data2;
	if (*d1 > *d2)
		return 1;
	else if (*d1 < *d2)
		return -1;
	else
		return 0;
}
int main()
{
	int option = 0;
	struct Link_List LL;
	Initial_SeqList(&LL);
	Show_Menu();
	// 逗号表达式,都先执行一遍,但取值为最后一位
	while (printf("选择为>:"), scanf("%d", &option), printf("\n"), option)
	{
		DateType element = 0;
		int pos = 0;
		
		getchar();// 截断只读缓存区的换行符
		switch (option)
		{
		case 1:
			printf("输入的值为>:");
			while (scanf(D_FORM, &element),  END_F != element)
				push_back(&LL, element);
			break;
		case 2:
			printf("输入的值为>:");
			while (scanf(D_FORM, &element), END_F != element)
				push_front(&LL, element);
			break;
		case 3:
			pop_back(&LL);
			break;
		case 4:
			pop_front(&LL);
			break;
		case 5:
			Show_SeqList(&LL);
			break;
		case 6:
			get_length(&LL);
			break;
		case 7:
			printf("查找的值>:");
			scanf(D_FORM, &element);
			find(&LL, element);
			break;
		case 8:
			printf("插入值与插入位置>:");
			scanf(D_FORM "%d", &element, &pos);
			insert_pos(&LL, element, pos);
			break;
		case 9:
			printf("需删除的值为>:");
			scanf(D_FORM, &element);
			delete_val(&LL, element);
			break;
		case 10:
			printf("删除的元素位置>:");
			scanf("%d", &pos);
			delete_pos(&LL, pos);
			break;
		case 11:
			sort(&LL, cmp);
			break;
		case 12:
			reverse(&LL);
			break;
		case 13:
			clean(&LL);
			break;
		case 14:
			destroy(&LL);
			break;
		default: printf("输入值不在选择范围\n");
		}
		Show_Menu();
	}
	destroy(&LL);
	printf("已退出");
	return 0;
}