实现顺序表的各种基本运算

编写程序，实现顺序表的各种基本运算，要求用菜单组织所有功能，程序界面友好，相应提示信息清晰完整，具有较强的容错性。

要实现的功能有：

（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 
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MaxSize 100

using namespace std;

typedef int Status;
typedef int ElemType;

//定义 
typedef struct 
{
	ElemType *elem;
	int length;
}SqList;

//初始化
Status InitList(SqList &L)        
{
	//构造空的顺序表
	  L.elem = new ElemType[MaxSize];              //为顺序表分配一个MaxSize大小的数组空间 
	  if (!L.elem)                                 //存储分配失败，退出 
	     exit(OVERFLOW);
	  L.length = 0;                                //空表长度为0 
	  return OK;
 } 
 
//创建
Status CreatList(SqList &L, int n)
{
	for (int i = 0; i < n; i++)
	    cin >> L.elem[i];
	L.length = n;
	return OK;
}

//判空
int ListEmpty(SqList L)
{
	return (L.length == 0);
}

//输出
Status DispList(SqList L)
{
	for (int i = 0;i < L.length; i++)
	    cout << L.elem[i] << ' ';
	return OK;
}  

//取值,按位查找 
Status GetElem(SqList L, int i, ElemType &e)
{
	if (i < 1 || i > L.length)
	   return ERROR;
	e = L.elem[i - 1];
	return OK;
}
 
//查找，按值查找 
int LocateElem(SqList L, ElemType e)
{
	for (int i = 0; i < L.length; i++)
	    if (L.elem[i] == e)
	        return i + 1;
	return 0;
}

//插入
Status ListInsert(SqList &L, int i, ElemType e)
{
	if (i < 1 || i > L.length +1)
	    return ERROR;
	if (L.length == MaxSize)
	    return ERROR;
	for (int j = L.length; j >= i; j--)
	    L.elem[j] = L.elem[j - 1];
	L.elem[i - 1] = e;
	L.length++;
	return OK;
} 

//删除
Status ListDelete(SqList &L, int i)
{
	if (i < 1 || i > L.length)
	    return ERROR;                    
	for (int j = i; j <= L.length - 1; j++)
	    L.elem[j - 1] = L.elem[j];
	--L.length;
	return OK;
}
 
//删除线性表中x~y之间的元素 
Status delx_y(SqList &L, ElemType x, ElemType y)
{
	int i, t, k = 0;                            //k用来记录非x,y的元素
    if (x > y)
    {
    	t = x;
    	x = y;
    	y = t;
	}
	for (i = 0; i < L.length; i++)
	    if (L.elem[i] < x || L.elem[i] > y)    //复制不在x,y内的元素
		{
			L.elem[k] = L.elem[i];
			k++;
		 } 
	L.length = k;
	return OK;
}
 
//单值化 *** 作,删除表中重复元素中的多余元素
Status del_x(SqList &L)
{                                               //k记录要保留的元素个数，初值为0 
	if (ListEmpty(L))
	    return ERROR;
	
	SqList T;                                  //新创一个表来存放删除后的数据 
	InitList(T);
	
	int len = 0;                               //初始化 
	for (int i = 0; i < L.length; i ++ )
	{
		ElemType e = L.elem[i];             
		if(!LocateElem(T, e))                  
		{
			T.elem[len ++ ] = e;
			T.length = len;
		}
	}
	
	for (int i = 0; i < len; i ++)
		L.elem[i] = T.elem[i];
	L.length = len;
	
	return OK;
 } 

//简单划分操作 
Status PartList(SqList &L)
{
	int i = 0, j = L.length - 1;                //pivot=L.elem[0]为基准 
	ElemType pivot = L.elem[0];
	while (i < j)                               //j从后往前找小于等于基准的元素，前移
	{                                           //i从前往后找大于基准的元素，后移 
	    while (j > i && L.elem[j] > pivot)
		       j--;
		       L.elem[i] = L.elem[j];
		while (i < j && L.elem[i] <= pivot)
		       i++;                         
		       L.elem[j] = L.elem[i];		 
	}
	L.elem[i] = pivot;
	return OK;	
} 

 
//直接插入法 
Status Insert_up(SqList L)
{
	int i, j, t;
	for (i = 1; i< L.length; i++)
	{ 
	    t = L.elem[i];
		j = i - 1;
		while (j >= 0 && t < L.elem[j])
		{
		     L.elem[j + 1] == L.elem[j];
			 j--;	
		}	
		L.elem[j + 1] = t;
	}
	return OK;
}

//销毁
Status DestoryList(SqList &L)
{
	delete []L.elem;
	L.elem = NULL;
	L.length = 0;
	return OK;
}

//菜单 
void menu()
{
		cout << "顺序表操作" << endl;
		cout << "P-输出顺序表中所有元素" << endl;
		cout << "G-输出第i个元素的值" << endl;
		cout << "L-输出值为x的元素的序号" << endl;
		cout << "I-在第i个元素前插入x" << endl;
		cout << "D-删除第i个元素" << endl;
		cout << "M-删除x和y之间的所有元素" << endl;
		cout << "S-单值化" << endl;
		cout << "F-简单划分" << endl;
		cout << "X-直接插入排序" << endl;
		cout << "Q-退出" << endl;
		cout << "请选择" << endl;
 } 

int main()
{
	SqList L;
	
	int num, n , m, x, y, z, i;
	ElemType e;
	char choice;
	
	InitList(L);
	cout << "线性表中元素的个数？" << endl;
	cin >> num;
	cout << "请输入元素：" << endl;
	CreatList(L, num);
		
	while (1)
	{
		menu();
		cin >> choice;
		choice = toupper(choice); 
		switch (choice)
		{
			case 'P':
				if (ListEmpty(L))
				    cout << "线性表为空" << endl;
			    else
			    {
			    	cout << "线性表中的元素为：" <> n;
				m = GetElem(L, n, e);
				if (m == 0)
				   cout << "要查找的元素位置不合法" << endl;
				else
				   cout << "要查找的元素是："  << e << endl;
				break;
				
			case 'L':
				cout << "要查找的元素是：" << endl;
				cin >> x;
				m = LocateElem(L, x);
				if (!m)
				   cout << "要查找的元素不存在" << endl;
				else
				   cout << x << "是表中的第" << m << "个元素" << endl;
				break;
				
			case 'I':
			    cout << "在第几个元素前面插入值为x的元素？" << endl;
				cin >> y >> z;
				m = ListInsert(L, y, z);
				if(!m)
				   cout << "插入位置不合法，插入失败" << endl;
				else
				   cout << "插入成功，线性表元素为: " << endl;
				   DispList(L);
				break;
				
			case 'D':
			    cout << "删除第几个元素？" << endl;
				cin >> i;
				m = ListDelete(L, i);
				if (!m)
				   cout << "删除位置不合法，删除失败" << endl;
				else
				   cout << "插入成功，线性表元素为: " << endl;
				   DispList(L);
				break;
				
			case 'M':
				cout << "要删除的元素值在多少到多少的范围内" << endl;
				cin >> x >> y;
				m = delx_y(L, x, y);
				if (!m)
				   cout << "删除失败" << endl;
				else
				   cout << "删除成功,删除后的表元素为" << endl ;
				   DispList(L); 
				break;
			
			case 'S':
			    m = del_x(L);
			    if (!m)
			       cout << "删除失败" << endl;
				else
				   cout << "删除成功，删除后的元素为" << endl;
				   DispList(L);
				break;
				
			case 'F':
				m = PartList(L);
				cout << "划分完成以后的表元素为："  << endl;
				DispList(L);
			    break;
			
			case 'X':
				m = Insert_up(L);
				cout << "排序完成后的表元素为："  << endl;
				DispList(L);
				break;
				
			case 'Q':
				DestoryList(L);
				exit(OVERFLOW);
			default: cout << " 111"; break; 
		}
	}	
	return 0;
}

运行结果图