//顺序表的各种操作（包括头删，尾删，插入，逆序，摧毁，清空等等）
 
//头文件
#ifndef _SEQLIST_H
#define _SEQLIST_H
 
 
#include<stdio.h>
 
 
 
 
typedef int ElemType;
 
 
#define INIT_SIZE  8
 
 
typedef struct SeqList
{
	ElemType *base;
	size_t    capacity;
	size_t    size;
}SeqList;
 
 
int isempty(SeqList *list);
int isfull(SeqList *list);
 
 
void InitList(SeqList *list);
void push_back(SeqList *list,ElemType x);
void show_list(SeqList *list);
void push_front(SeqList *list,ElemType x);
void pop_back(SeqList *list);
void pop_front(SeqList *list);
void insert_pos(SeqList *list,ElemType x,int pos);
void quit_system(SeqList *list,int *x);
int find(SeqList *list,ElemType x);
int length(SeqList *list);
void insert_val(SeqList *list,ElemType x);
void sort(SeqList *list);
void delete_pos(SeqList *list,int pos);
void delete_val(SeqList *list,ElemType x);
void clear(SeqList *list);
void destory(SeqList *list);
void reverse(SeqList *list);
 
 
#endif
 
//函数文件
#include"SeqList.h"
 
 
int i;
int isempty(SeqList *list)          //检测表是否满
{
	return list->size == 0;
}
int isfull(SeqList *list)          //检测表是否空
{
	return list->size >= list->capacity;
}
 
 
void InitList(SeqList *list)        //表初始化
{
	list->capacity = INIT_SIZE;
	list->base = (ElemType *)malloc(sizeof(ElemType)*list->capacity);
	list->size = 0;
}
 
 
void push_back(SeqList *list,ElemType x)     //尾插
{
	if (isfull(list))
	{
		printf("顺序表已满,不能插入!\n") ;
		return;
	}
	list->base[list->size] = x;
	list->size++;
}
 
 
 
 
void show_list(SeqList *list)                //显示
{
	if (list->size == 0)
	{
		printf("顺序表为空。\n");
		return;
	}
	for (i = 0; i<list->size; ++i)
	{
		printf("%d ",list->base[i]);
	}
	printf("\n");
}
 
 
void push_front(SeqList *list,ElemType x)    //头插
{
	if (isfull(list))
	{
		printf("顺序表已满,不能插入!\n");
		return;
	}
	for (i = list->size; i > 0; i--)
	{
		list->base[i] = list->base[i - 1];
	}
	list->base[0] = x;
	(list->size)++;
}
 
 
void pop_front(SeqList *list)                 //头删
{
	if (isempty(list))
	{
		printf("顺序表为空，不能删除\n");
		return;
	}
	for (i = 0; i < list->size; i++)
	{
		list->base[i] = list->base[i + 1];
	}
	(list->size)--;
}
 
 
void pop_back(SeqList *list)                 //尾删
{
	if (isempty(list))
	{
		printf("顺序表为空，不能删除\n");
		return;
	}
	list->size--;
}
 
 
void insert_pos(SeqList *list,int pos)   ////按位置插
{
	if (pos<0 || pos>list->size)
	{
		printf("插入的位置不正确。\n ");
		return;
	}
	if (isempty(list))
	{
		printf("顺序表已满，不能插入.\n");
		return;
	}
	for (i = list->size; i > pos; i--)
	{
		list->base[i] = list->base[i - 1];
	}
	list->base[pos] = x;
	list->size++;
}
 
 
void quit_system(SeqList *list,int *x)    //退出
{
	*x = 0;
}
 
 
int find(SeqList *list,ElemType x)       //查找
{
	for (i = 0; i < list->size; i++)
	{
		if (list->base[i]==x)
			return i;	
	}
	return -1;
}
 
 
int length(SeqList *list)                 //求长度
{
	return list->size;
}
 
 
void insert_val(SeqList *list,ElemType x)    //按值插入
{
	push_back(list,x);
	sort(list);
}
 
 
void sort(SeqList *list)                  //排序
{
	if (isempty(list))
	{
		return;
	}
	for (int i = 1; i < list->size; i++)
	{
		for (int j = 0; j < list->size - i; j++)
		{
			int temp;
			if (list->base[j]>list->base[j + 1])
			{
				temp = list->base[j];
				list->base[j] = list->base[j + 1];
				list->base[j + 1] = temp;
			}
		}
	}
}
 
 
void delete_pos(SeqList *list,int pos)     //按位置删除
{
	if (isempty(list))
	{
		printf( "顺序表为空，不能删除。\n" );
		return;
	}
	if (pos < 0 || pos >= list->size)
	{
		printf("删除的位置不正确。\n");
		return;
	}
	for (int i = pos; i < list->size; ++i)
	{
		list->base[i] = list->base[i + 1];
	}
	list->size--;
}
 
 
void delete_val(SeqList *list,ElemType x)   //按值删除
{
	if (isempty(list))
	{
		printf( "顺序表为空，不能删除。\n");
		return;
	}
	int pos = find(list,x);
	if (pos == -1)
	{
		printf("未找到该数。\n");
		return;
	}
	delete_pos(list,pos);
}
 
 
void clear(SeqList *list)                 //清空
{
	list->size = 0;
}
 
 
void destory(SeqList *list)               //摧毁表
{
	list->base = NULL;
}
 
 
void reverse(SeqList *list)              //逆序
{
	for (int i = 0,j = list->size - 1; i < list->size / 2; i++,j--)
	{
		int temp = list->base[i];
		list->base[i] = list->base[j];
		list->base[j] = temp;
	}
}
 
//主函数
#include"SeqList.h"
 
 
void main()
{
	SeqList mylist;
	InitList(&mylist);
 
 
	int select = 1;
	ElemType Item;
	int pos;
	while (select)
	{
		printf("****************************************************\n");
		printf("*   [1] show_list                 [2] quit_system  *\n");
		printf("*   [3] push_front                [4] push_back    *\n");
		printf("*   [5] pop_front                 [6] pop_back     *\n");
		printf("*   [7] insert_pos                [8] insert_val   *\n");
		printf("*   [9] delete_pos                [10] delete_val  *\n");
		printf("*   [11] find                     [12] length      *\n");
		printf("*   [13] clear                    [14] destory     *\n");
		printf("*   [15] reverse(逆序)            [16] sort(顺序)  *\n");
		printf("****************************************************\n");
		printf("请选择:");
		scanf_s("%d",&select);
		switch (select)
		{
		case 1:
			show_list(&mylist);
			break;
 
 
		case 2:
			quit_system(&mylist,&select);
			break;
 
 
		case 3:
			printf("请输入要插入的值(-1结束):>");
			while (scanf_s("%d",&Item),Item != -1)
			{
				push_front(&mylist,Item);
			}
			break;
 
 
		case 4:
			printf("请输入要插入的值(-1结束):>");
			while (scanf_s("%d",Item != -1)
			{
				push_back(&mylist,Item);
			}
			break;
 
 
		case 5:
			pop_front(&mylist);
			break;
			
 
 
		case 6:
			pop_back(&mylist);
			break;
 
 
		case 7:
			printf("请输入要插入的位置：");
			scanf_s("%d",&pos);
			printf("请输入要插入的值：");
			scanf_s("%d",&Item);
			insert_pos(&mylist,Item,pos);
			break;
 
 
		case 8:
			printf("请输入要插入的数：");
			scanf_s("%d",&Item);
			insert_val(&mylist,Item);
			break;
 
 
		case 9:
			printf("请输入要删的位置：");
			scanf_s("%d",&pos);
			delete_pos(&mylist,pos);
			break;
 
 
		case 10:
			printf("请输入要删的值:");
			scanf_s("%d",&Item);
			delete_val(&mylist,Item);
			break;
 
 
		case 11:
			printf("请输入要查找的数：");
			scanf_s("%d",&Item);
			pos=find(&mylist,Item);
			if (pos != -1)
			{
				printf("该数为第%d个数.\n",pos);
			}
			else
				printf("未找到该数。\n");
			break;
 
 
		case 12:
			printf("该顺序表长度为：%d\n",length(&mylist));
			break;
 
 
		case 13:
			clear(&mylist);
			break;
 
 
		case 14:
			destory(&mylist);
			break;
 
 
		case 15:
			reverse(&mylist);
			break;
 
 
		case 16:
			sort(&mylist);
			break;
 
 
		default:
			break;
		}
	}
}