C++顺序表操作代码示范_OC/C/C++

C++顺序表操作代码演示
/*
*建立一个顺序表，插入n个元素并输出
*Author :CplusHua PurpleHua
*Date:2012-10-06
*/
#include<iostream>
#include "malloc.h"
#include <stdio.h>
#define ElemType int //宏定义
#define LIST_INT_SIZE 10 //改为1，改用ListInsert增加空间
using namespace std;
//定义一个顺序表
struct  SqList{
	ElemType * elem;
	int length;
	int listsize;
}L={NULL,0,0};
//返回状态定义
//这里修改了课本里的宏定义，全部在一个enum中定义完毕，
//让所有的函数返回一个枚举类型的结果
enum Status
{
	OK,FAILED,EMPTY,NOTINIT,OVERFLOW1//OVERFLOW在visual studio无法使用，改为OVERFLOW1
};
//初始化一个顺序表，成功返回OK,n是申请空间的大小
Status InitList_Sq(SqList &L,int n=LIST_INT_SIZE)
{
	if(L.elem) free(L.elem);//如果已经建立顺序表，则释放重新建立
	if(0==n)return FAILED;
	L.elem=(ElemType *)malloc(n*sizeof(ElemType));//为指针申请空间
	if(!L.elem) exit(OVERFLOW1);
	L.length=0;
	L.listsize=n;
	return OK;
}
//在线性表第i个元素之前插入一个元素
Status ListInsert_Sq(SqList &L,int i,ElemType e)
{//如果LIST_INT_SIZE设置为100，则在此加入判断，L.lisesize>100时增加空间
	if(L.length<=0||i<=0)return FAILED;//空表，返回失败
	if(!L.elem) return NOTINIT;//顺序表未初始化
	if(i>L.length) return OVERFLOW1;//溢出，返回溢出（输入越界）
	if(L.length>=L.listsize)
	{
		//每插入一个元素重新申请增加空间
		ElemType *newbase=(ElemType *)realloc(L.elem,(L.listsize+1)*sizeof(ElemType));
		L.elem=newbase;
		L.listsize++;
	}
	int *p,*q;
	p=L.elem+L.length;//最后一个位置
	q=L.elem+i-1;//要插入元素的位置
	for(;p>q;p--)
		*p=*(p-1);
	*q=e;
	L.length++;
return OK;
}
//删除顺序表中的元素
Status ListDelete_Sq(SqList &L,int i,ElemType *e=0)
{
	if(L.length<0||i>L.length||i<=0) return FAILED;
	if(!L.elem) return NOTINIT;//顺序表未初始化
	if(0==L.length) return EMPTY;
	int *p;
	p=L.elem+i-1;//定位到要删除的元素位置
	if(e)
		*e=*p;//返回要删除元素的值
	for(;p<=L.elem+L.length;p++)
	{
		*p=*(p+1);
	}
	L.length--;
	return OK;
 
}
//要输入元素的线性表L，要输入的元素个数n
Status ListInput_Sq(SqList &L,int n)
{
	int *p=L.elem;
	for(int i=0;i<n;i++)
	{
		cin>>*(p++);
		L.length++;
	}
	return OK;
}
//顺序输出顺序表中的元素
Status ListOutput_Sq(SqList &L)
{
	if(!L.elem) return NOTINIT;//顺序表未初始化
	int *p;
	p=L.elem;
	cout<<"顺序表中的元素为:";
	for(int i=0;i<L.length;i++)
	{
		cout<<*(p++)<<" ";
	}
	cout<<endl;
	return OK;
}
//查找最大元素
Status ListMax_Sq(SqList &L,ElemType *e)
{
	if(!L.elem) return NOTINIT;//顺序表未初始化
	int max;
	int *p;
	p=L.elem;
	max=*p;
	for(int i=0;i<L.length;i++)
	{
		if(max<*p)
			max=*p;
		p++;//最后溢出了会怎样？
	}
	*e=max;
	return OK;
}
//升序排序
Status ListSort_Sq(SqList &L)
{
	if(!L.elem) return NOTINIT;//顺序表未初始化
	int tmp;
	int i,j;
	int *p;
	p=L.elem;
	for(i=0;i<L.length-1;i++)
	{
		for(j=0;j<L.length-i-1;j++)
		{
			if(*(p+j)>*(p+j+1))
			{
				tmp=*(p+j);
				*(p+j)=*(p+j+1);
				*(p+j+1)=tmp;
			}
		}
	}
	return OK;
}
//逆序（使用一个暂存空间）
Status ListRevorder_Sq(SqList &L)
{
	if(!L.elem) return NOTINIT;//顺序表未初始化
	int tmp;
	int *p;
	p=L.elem;
	for(int i=0;i<L.length/2;i++)
	{
		tmp=*(p+i);
		*(p+i)=*(p+L.length-i-1);
		*(p+L.length-i-1)=tmp;
	}
	return OK;
}
//逆序（不使用暂存空间）
Status ListRevorder1_Sq(SqList &L)
{
	if(!L.elem) return NOTINIT;//顺序表未初始化
	int *p;
	p=L.elem;
	for(int i=0;i<L.length/2;i++)
	{
		*(p+i)=(*(p+L.length-i-1))^(*(p+i));
		*(p+L.length-i-1)=(*(p+L.length-i-1))^(*(p+i));
		*(p+i)=(*(p+L.length-i-1))^(*(p+i));
	}
	return OK;
}
//主函数
int main()
{
	int opt;
   // SqList L;
   // L.elem=NULL;//初始化
	int i,res,e,n;
	n=0;
	while(1)
	{
 
		if(n)
		{
			while(getchar()!='\n'&&getchar()!=' ');
			while(getchar()!='\n'&&getchar()!=' ');
		}
		cout<<"************请输入您要进行的操作的编号************"<<endl<<endl;
		cout<<"1.建立一个顺序表,输入n个数字元素并输出"<<endl;
		cout<<"2.查找线性表中的最大元素并输出"<<endl;
		cout<<"3.在线性表的第i个元素前插入一个正整数x"<<endl;
		cout<<"4.删除线性表中的第j个元素"<<endl;
		cout<<"5.将线性表中的元素按升序排列"<<endl;
		cout<<"6.将线性表中的元素就地逆序（只允许用一个暂存单元）"<<endl;
		cout<<"7.将线性表中的元素就地逆序（不使用暂存单元）"<<endl;
		cout<<"8.退出"<<endl<<endl;
		cout<<"***************************************************"<<endl;
		cin>>opt;
		switch (opt)
		{
			case 1:
			cout<<"***************请输入要输入元素的个数**************"<<endl;
			cin>>n;
			InitList_Sq(L,n);//建立顺序表
			cout<<"*****************请输入线性表元素******************"<<endl;
			ListInput_Sq(L,n);//进入输入元素的函数
			ListOutput_Sq(L);//输出顺序表中的元素
			break;
			case 2:
			if(!L.elem)
			{
				cout<<"顺序表未初始化，请初始化顺序表！"<<endl<<endl;
				break;
			}
			ListMax_Sq(L,&e);
			cout<<"最大元素为:"<<e<<endl;
			break;
			case 3:
			if(!L.elem)
			{
				cout<<"顺序表未初始化，请初始化顺序表！"<<endl<<endl;
				break;
			}
			cout<<"请分别输入要插入的元素和要插入元素的位置"<<endl;
			cout<<"元素：";
			cin>>e;
			cout<<"位置：";
			cin>>i;
			ListInsert_Sq(L,i,e);
			ListOutput_Sq(L);//输出顺序表中的元素
			break;
			case 4:
			if(!L.elem)
			{
				cout<<"顺序表未初始化，请初始化顺序表！"<<endl<<endl;
				break;
			}
			cout<<"请输入要删除的元素的位置"<<endl;
 
			cin>>i;//位置
			ListDelete_Sq(L,i,&res);
			cout<<"删除的元素为:"<<res<<endl;
			ListOutput_Sq(L);//输出顺序表中的元素
			break;
			case 5:
			if(!L.elem)
			{
				cout<<"顺序表未初始化，请初始化顺序表！"<<endl<<endl;
				break;
			}
			ListSort_Sq(L);//升序排序
			ListOutput_Sq(L);//输出顺序表中的元素
			break;
			case 6:
			if(!L.elem)
			{
				cout<<"顺序表未初始化，请初始化顺序表！"<<endl<<endl;
				break;
			}
			ListRevorder_Sq(L);//使用一个暂存空间逆序
			ListOutput_Sq(L);//输出顺序表中的元素
			break;
			case 7:
			if(!L.elem)
			{
				cout<<"顺序表未初始化，请初始化顺序表！"<<endl<<endl;
				break;
			}
			ListRevorder1_Sq(L);//不使用暂存空间逆序
			ListOutput_Sq(L);//输出顺序表中的元素
			break;
			case 8:
				return 0;
			default:
				cout<<"ERROR"<<endl;
		}
	}
	return 0;
}