//顺序表的各种操作（包括头删，尾删，插入，逆序，摧毁，清空等等）
//头文件
#pragma once
#include <iostream>
using namespace std;
 
template<class Type>
class SeqList
{
public:
	SeqList(size_t sz = INIT_SIZE);
	~SeqList();
public:
	bool isfull() const
	{return size >= capacity; }
	bool isempty() const
	{return (size == 0); }
public:
	void show_list();
	void push_front(const Type &x);
	void push_back(const Type &x);
	void insert_pos(int pos,const Type &x);
	int find(const Type &key);
	void pop_front();
	void pop_back();
	void sort();
	void insert_val(const Type &x);
	void delete_pos(int pos);
	void delete_val(const Type &x);
	int length();
	void clear();
	void destory();
	void reverse();
	void quit_system(int &a);
private:
	enum{ INIT_SIZE = 8 };
	Type *base;
	size_t capacity;
	size_t size;
};
 
 
template<class Type>                        //构造函数
SeqList<Type>::SeqList(size_t sz)
{
	capacity = sz > INIT_SIZE ? sz : INIT_SIZE;
	base = new Type[capacity];
	size = 0;
}
 
template<class Type>                        //析构函数
SeqList<Type>::~SeqList()
{
	delete base;
}
 
template<class Type>                        //显示
void SeqList<Type>::show_list()
{
	if (size == 0)
	{
		cout << "数据表为空。" << endl;
		return;
	}
	for (int i = 0; i<size; ++i)
	{
		cout << base[i] << " ";
	}
	cout << endl;
}
 
template<class Type>                         //头插
void SeqList<Type>::push_front(const Type &x)
{
	if (isfull())
	{
		cout << "顺序表已满，不能插入." << endl;
		return;
	}
	for (int i = size; i > 0; --i)
	{
		base[i] = base[i - 1];
	}
	base[0] = x;
	size++;
}
 
template<class Type>                        //尾插
void SeqList<Type>::push_back(const Type &x)
{
	if (isfull())
	{
		cout << "顺序表已满，不能插入." << endl;
		return;
	}
	base[size] = x;
	size++;
}
 
template<class Type>						//按位置插
void SeqList<Type>::insert_pos(int pos,const Type &x)
{
	if (pos<0 || pos>size)
	{
		cout << "插入的位置不正确。" << endl;
		return;
	}
	if ( isfull() )
	{
		cout << "顺序表已满，不能插入." << endl;
		return;
	}
	for (int i = size; i > pos; --i)
	{
		base[i] = base[i - 1];
	}
	base[pos] = x;
	size++;
}
 
template<class Type>						//查找
int SeqList<Type>::find(const Type &key)
{
	for (int i = 0; i<size; ++i)
	{
		if (base[i] == key)
			return i;
	}
	return -1;
}
 
 
template<class Type>						//头删
void SeqList<Type>::pop_front()
{
	if (isempty())
	{
		cout << "顺序表为空，不能删除。" << endl;
		return;
	}
	for (int i = 0; i < size; ++i)
	{
		base[i] = base[i + 1];
	}
	size--;
}
 
template<class Type>
void SeqList<Type>::pop_back()				//尾删
{
	if (isempty())
	{
		cout << "顺序表为空，不能删除。" << endl;
		return;
	}
	size--;
}
 
template<class Type>						//排序
void SeqList<Type>::sort()
{
	if (isempty())
	{
		return;
	}
	for (int i = 1; i < size; i++)
	{
		for (int j = 0; j < size - i; j++)
		{
			int temp;
			if (base[j]>base[j + 1])
			{
				temp = base[j];
				base[j] = base[j + 1];
				base[j + 1] = temp;
			}
		}
	}
}
 
template<class Type>						//按值插入
void SeqList<Type>::insert_val(const Type &x)
{
	push_back(x);  //尾插
	sort();   //排序
}
 
template<class Type>						//按位置删除
void SeqList<Type>::delete_pos(int pos)
{
	if (isempty())
	{
		cout << "顺序表为空，不能删除。" << endl;
		return;
	}
	if (pos < 0 || pos >= size)
	{
		cout << "删除的位置不正确。" << endl;
		return;
	}
	for (int i = pos; i < size; ++i)
	{
		base[i] = base[i + 1];
	}
	size--;
}
 
template<class Type>						//按值删除
void SeqList<Type>::delete_val(const Type &x)
{
	if (isempty())
	{
		cout << "顺序表为空，不能删除。" << endl;
		return;
	}
	int pos=find(x);  
	if (pos == -1)
	{
		cout << "未找到该数。" << endl;
		return;
	}
	delete_pos(pos);
}
 
template<class Type>						//求长度
int SeqList<Type>::length()
{
	return size;
}
 
template<class Type>						//清除表
void SeqList<Type>::clear()
{
	size = 0;
}
 
template<class Type>						//摧毁表
void SeqList<Type>::destory()
{
	base = NULL;
}
 
 
template<class Type>						//逆序
void SeqList<Type>::reverse()
{
	for (int i = 0,j = size - 1; i < size / 2; i++,j--)
	{
		int temp = base[i];
		base[i] = base[j];
		base[j] = temp;
	}
}
 
template<class Type>						//退出
void SeqList<Type>::quit_system(int &a)
{
	a = 0;
}
 
 
 
//主函数
#include"SeqList.h"
 
void main()
{
	SeqList<int> mylist;
	int select = 1;
	int Item;
	int pos;
	while (select)
	{
		cout << "************************************************************************" << endl;
		cout << "*      [1] show_list                         [2] quit_system           *" << endl;
		cout << "*      [3] push_front                        [4] push_back             *" << endl;
		cout << "*      [5] pop_front                         [6] pop_back              *" << endl;
		cout << "*      [7] insert_pos                        [8] insert_val            *" << endl;
		cout << "*      [9] delete_pos                        [10] delete_val           *" << endl;
		cout << "*      [11] find                             [12] length               *" << endl;
		cout << "*      [13] clear                            [14] destory              *" << endl;
		cout << "*      [15] reverse(逆序)                    [16] sort(顺序)           *" << endl;
		cout << "************************************************************************" << endl;
		cout << "请选择功能：";
		cin >> select;
		switch (select)
		{
		case 1:
			mylist.show_list();
			break;
		case 2:
			mylist.quit_system(select);
			break;
		case 3:
			cout << "请输入您要插入的数(以-1结束)：";
			while (cin >> Item,Item != -1)
			{
				mylist.push_front(Item);
			}
			break;
		case 4:
			cout << "请输入您要插入的数(以-1结束)：";
			while (cin >> Item,Item !=-1)
			{
				mylist.push_back(Item);
			}
			break;
		case 5:
			mylist.pop_front();
			break;
		case 6:
			mylist.pop_back();
			break;
		case 7:
			cout << "请输入您要插入的位置：";
			cin >> pos;
			cout << "请输入您要插入的值：";
			cin >> Item;
			mylist.insert_pos(pos,Item);
			break;
		case 8:
			cout << "请输入要插入的数：";
			cin >> Item;
			mylist.insert_val(Item);
			break;
		case 9:
			cout << "请输入要删的位置：";
		    cin >> pos;
			mylist.delete_pos(pos);
			break;
		case 10:
			cout << "请输入要删的值:";
			cin >> Item;
			mylist.delete_val(Item);
			break;
		case 11:
			cout << "请输入要查找的数：";
			cin >> Item;
			pos = mylist.find(Item);
			if (pos != -1)
			{
				cout << "该数为第" << pos << "个数" << endl;
			}
			cout << "未找到该数。"<<endl;
			break;
		case 12:
			cout <<"该顺序表长度为："<< mylist.length() << endl;
			break;
		case 13:
			mylist.clear();
			break;
		case 14:
			mylist.destory();
			break;
		case 15:
			mylist.reverse();
			break;
		case 16:
			mylist.sort();
			break;
		default:
			break;
		}
 
	}
}