顺序表的基本操作

（1）输出顺序表中的所有元素；
（2）按序号查找指定元素，即输出顺序表中的第i个元素；
（3）按值查找指定元素，即输出顺序表中值为x的元素的序号；
（4）在指定位置插入元素，即在第i个元素前面插入值为x的元素；
（5）删除指定元素，即删除第i个元素；
（6）删除顺序表中所有值在[x,y]范围内的元素，要求时间复杂度达到O(n)；
（7）单值化操作，即删除表中重复元素中的多余元素，只保留其中序号最小的一个，例如，顺序表(2,4,4,3,2,4)单值化后的结果为(2,4,3)；
（8）简单划分操作，即将顺序表 (a1，a2，… ，an) 重新排列为以指定元素a1为界的两部分：a1前面的值均小于等于a1，a1后面的值均大于a1；
（9）采用直接插入法将顺序表排列为升序序列，参见教材P236对直接插入排序法基本操作步骤的讲解；
（10）销毁顺序表并退出。

#include
#include

using namespace std;

typedef int Status;
typedef int ElemType;
#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define OVERFLOW -2
//定义线性表结构
typedef struct {
	ElemType* Link;
	int length;
}Sqlist;


Status Init(Sqlist& QL);
Status Create(Sqlist& QL, int length);

Status Display(const Sqlist& QL);
Status GetElem(const Sqlist& QL, ElemType& e, int index);
Status LocateElem(const Sqlist& QL, ElemType e, int& index);
Status Insert(Sqlist& QL, ElemType e, int index);
Status Delete(Sqlist& QL, int index);
Status DeleteAll(Sqlist& QL, ElemType value, ElemType value2);
Status Uniform(Sqlist& QL);
Status Division(Sqlist& QL, int index);
Status InsertSort(Sqlist& QL);
Status Destroy(Sqlist& QL);
Status GetLength(const Sqlist& QL, ElemType& e);
Status IsEmpty(const Sqlist& QL);
Status IsFull(const Sqlist& QL);

int main()
{
	int index, length;
	ElemType e;
	//创建顺序表并初始化
	Sqlist L;
	Init(L);
	cout << "请您输入线性表的长度";
	cin >> length;
	Create(L, length);
	cout << "----------------------------------------n";
	int key = 1;
	while (key != 10)
	{
		
		cout << "欢迎使用线性表n"
		     << "请您输入您要执行的操作n"
			 << "1 输出顺序表中所有元素n"
			 << "2 按序号查找指定元素，即输出顺序表的第i个元素n"
			 << "3 按值查找指定元素，即输出顺序表中值为x的元素的序号n"
			 << "4 在指定位置插入元素，即在第i个元素前面插入值为x的元素；n"
			 << "5 删除指定元素，即删除第i个元素；n"	
			 << "6 删除顺序表中所有值在[x,y]范围内的元素n"
			 << "7 单值化操作,即删除表中重复元素中的多余元素，只保留其中序号最小的一个；n"
			 << "8 简单划分操作，即将顺序表 (a1，a2，... ，an) 重新排列为以指定元素"
			 << "a1为界的两部分。a1前面的值均小于等于a1，a1后面的值均大于a1n"
			 << "9 升序排序。n"
			 << "10 销毁顺序表并退出。n"
			 << "----------------------------------------n";

		cin >> key;
		switch (key)
		{
		case 1:
			Display(L); 
			break;
		case 2:
			cout << "请您输入您想要取的元素下标__bb";
			cin >> index;
			if (GetElem(L, e, index)) {
				cout <<"第" << index <<"个元素为" <> e;
			if (LocateElem(L, e, index)) {
				cout << "您查找的元素下标在:" << index << endl;
			}
			break;
		case 4:
			cout << "请您输入您要插入的位置和元素,以空格分割__bb";
			cin >> index >> e;
			Insert(L, e, index);
			cout << "在" << index << "位置插入" << e << "之后的结果n";
			Display(L); 
			break;
		case 5:
			cout << "请您输入您要删除的位置__bb";
			cin >> index;
			Delete(L, index);
			cout << "在" << index << "位置删除元素之后的结果n";
			Display(L);
			break;
		case 6:
			ElemType value1, value2;
			cout << "请您输入要删除的值范围[x,y],以空格分开";
			cin >> value1 >> value2;
			DeleteAll(L, value1, value2);
			cout << "删除" << value1 << "和" << value2 << "之间的值之后的结果n";
			Display(L);
			break;
		case 7:
			Uniform(L);
			cout << "单值化之后的结果n";
			Display(L);
			break;
		case 8:
			cout << "请您输入指定元素的下标";
			cin >> index;
			Division(L, index);
			cout << "以" << index << "为下标简单划分之后的结果n";
			Display(L);
			break;
		case 9:
			InsertSort(L);
			cout << "升序排序之后的结果n";
			Display(L);
			break;
		case 10:
			Destroy(L);
			cout << "Bye!n"; break;
		default:
			cout << "请您输入正确的操作n";
			break;
		}

		cout << "----------------------------------------n";
	}
	return 0;
}


Status Init(Sqlist& QL)
{
	QL.Link = new ElemType[MAXSIZE];
	if (!QL.Link)
	{
		return OVERFLOW;
	}
	QL.length = 0;
	return OK;
}

Status Create(Sqlist& QL, int length)
{
	QL.length = length;
	if (QL.length > MAXSIZE)
	{
		cout << "溢出n";
		QL.length = 0;
		return OVERFLOW;
	}

	if (QL.length < 0)
	{
		cout << "输入长度不可以为负数n";
		QL.length = 0;
		return ERROR;
	}

	cout << "请输入顺序表内的元素";
	for (int i = 0; i < QL.length; i++)
	{
		cin >> QL.Link[i];
	}
	return OK;
}

Status IsEmpty(const Sqlist& QL)
{
	if (QL.length == 0)
	{
		cout << "顺序表为空n";
		return true;
	}
	else
	{
		return false;
	}
}

Status IsFull(const Sqlist& QL)
{
	if (QL.length == MAXSIZE)
	{
		cout << "顺序表已满n";
		return true;
	}
	else
	{
		return false;
	}
}

Status Display(const Sqlist& QL)
{
	if (IsEmpty(QL))
	{
		return ERROR;
	}

	for (int i = 0; i < QL.length; i++)
	{
		cout << QL.Link[i] << ' ';
	}
	cout << endl;
	return OK;
}

Status GetElem(const Sqlist& QL, ElemType& e, int index)
{

	if (index > QL.length)
	{
		cout << "超过顺序表长度n";
		return ERROR;
	}

	if (index < 0)
	{
		cout << "下标不应该为负数n";
		return ERROR;
	}

	//这里想要想要取得的元素是客户指出的，但是顺序表中的首个元素是从0开始
	e = QL.Link[index - 1];
	return OK;
}

Status LocateElem(const Sqlist& QL, ElemType e, int& index)
{
	if (IsEmpty(QL))
	{
		return ERROR;
	}

	for (int i = 0; i < QL.length; i++)
	{
		if (QL.Link[i] == e)
		{
			index = i + 1;
			return OK;
		}
	}

	cout << "未找到该元素n";
	return ERROR;
}

Status Insert(Sqlist& QL, ElemType e, int index)
{
	if (IsFull(QL))
	{
		return ERROR;
	}

	if (index < 0 || index>QL.length + 1)
	{
		cout << "插入位置不合理n";
		return ERROR;
	}
	QL.Link[QL.length] = 0;
	for (int k = QL.length; k >= index; k--)
	{
		QL.Link[k] = QL.Link[k - 1];
	}
	QL.Link[index - 1] = e;
	QL.length++;
	return OK;
}

Status Delete(Sqlist& QL, int index)
{
	if (IsEmpty(QL))
	{
		return ERROR;
	}

	if (index > QL.length || index <= 0)
	{
		cout << "删除位置不合理n";
		return ERROR;
	}

	for (int k = index - 1; k < QL.length - 1; k++)
	{
		QL.Link[k] = QL.Link[k + 1];
	}
	QL.length--;
	return OK;
}

Status GetLength(const Sqlist& QL, ElemType& e)
{
	e = QL.length;
	return OK;
}

Status DeleteAll(Sqlist& QL, ElemType value1, ElemType value2)
{
	if (IsEmpty(QL))
	{
		return ERROR;
	}

	ElemType temp1 = min(value1, value2);
	ElemType temp2 = max(value1, value2);
	int len;
	int k = 0;
	GetLength(QL, len);
	for (int i = 0; i < len; i++)
	{
		QL.Link[i-k] = QL.Link[i];
		if (QL.Link[i] >= temp1 && QL.Link[i] <= temp2)
		{
			k++;
		}
	}
	QL.length -= k;
	return OK;
}

//将重复的元素只保留第一个元素
Status Uniform(Sqlist& QL)
{
	if (IsEmpty(QL))
	{
		return ERROR;
	}

	int len;
	GetLength(QL, len);

	vector book(len);
	int i,j ,k = 0;
	for (i = 0; i < len; i++)
	{

		QL.Link[i - k] = QL.Link[i];
		for (j = 0; j < book.size(); j++)
		{
			if (QL.Link[i] == book[j])
			{
				k++;
				break;
			}
		}
		if (j == book.size())
		{
			book.push_back(QL.Link[i]);
		}
	}
	QL.length -= k;
	return OK;
}

//前小后大
Status Division(Sqlist& QL, int index)
{
	if (IsEmpty(QL))
	{
		return OK;
	}

	if (index > QL.length)
	{
		cout << "Index超过顺序表长度";
		return ERROR;
	}
	int i = 0, j = QL.length;
	int key = QL.Link[index - 1];
	while (i!=j)
	{
		while(QL.Link[i]
			i++;
		}

		if (i != j)
		{
			QL.Link[j] = QL.Link[i];
			j--;
		}

		while (QL.Link[j] > key && i != j)
		{
			j--;
		}

		if (i != j)
		{
			QL.Link[i] = QL.Link[j];
			i++;
		}
	}
	QL.Link[i] = key;
	return OK;
}

//升序排列
Status InsertSort(Sqlist& QL)
{
	if (IsEmpty(QL))
	{
		return ERROR;
	}

	for (int i = 1; i < QL.length; i++)
	{
		ElemType key = QL.Link[i];
		int j = i-1;
		while (QL.Link[j]>key&&j>=0)
		{
			QL.Link[j+1] = QL.Link[j];
			j--;
		}
		QL.Link[j+1] = key;
	}
	return OK;
}

Status Destroy(Sqlist& QL)
{
	delete[] QL.Link;
	QL.length = 0;
	return OK;
}