线性表的顺序存储

【核心代码】

#define MAXSIZE 100
typedef int ElemType;
#include<stdlib.h>
typedef int Status;
#define OK 1
#define OVERFLOW -2
#define ERROR 0
#define INFEASIBLE -1
#include<iostream>
using namespace std;


//顺序表的存储结构
template<class ElemType>
typedef struct
{
ElemType *elem;
int length;
}SqList;


//构造一个空的线性表L
Status InitList(SqList &L) 
{
	L.elem=new ElemType[MAXSIZE];
	if(!L.elem)             
		exit(OVERFLOW);      //存储分配失败退出
	L.length=0;
	return OK;
}


//通过输入创建数据
Status Input(SqList &L,int e)
{
	int i;
	if(e<1||e>100)
		exit(OVERFLOW);
	else
		for(i=0;i<e;i  )
			L.length=L.length 1;
}


//判断L是否为空表
Status ListEmpty(SqList L)
{
	if(L.length==0)
		return OK;
	else
		return ERROR;
}


//取出第i个位置的数据
Status GetElem(SqList L,int i,ElemType &e)
{
	if(i<1||i>L.length)
		return ERROR;       //判断i值是否合理，若不合理，返回ERROR
	e=L.elem[i-1];          //elem[i-1]单元存储第i个数据元素
	return OK;
}


//取出第i个位置的数据的直接前驱数据
Status PriorElem(SqList L,ElemType cur_e,ElemType &pre_e)
{
	int i=2;
	ElemType *p=L.elem 1;
	while(i<=L.length&&*p!=cur_e)
	{
		p  ;
		i  ;
	}
	if(i>L.length)
		return INFEASIBLE;           //操作失败，pre_e无定义
	else
	{
		pre_e=*--p;
		return OK;                   //若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱
	}
}



//取出第i个位置的数据的直接后继数据
Status NextElem(SqList L,ElemType cur_e,ElemType &next_e)
{
	int i=1;
	ElemType *p=L.elem;
	while(i<L.length&&*p!=cur_e)
	{
		i  ;
		p  ;
	}
	if(i==L.length)
		return INFEASIBLE;            //操作失败，next_e无定义
	else
	{
		next_e=*  p;
		return OK;                    //若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继
	}
}


//查找数据返回在线性表中的位置
int LocateElem(SqList L,ElemType e)
{	
	int i;
	for(i=0;i<L.length;i  )
		if(L.elem[i]==e)
			return i 1;         //查找成功，返回序号i 1
	return 0;                   //查找失败，返回0

}


//在指定位置插入数据,i值的合法范围是1≤i≤L.length 1
Status ListInsert(SqList &L,int i,int j,ElemType e)
{
	if((i<1)||(i>L.length 1))
		return ERROR;                //i值不合法
	if(L.length==MAXSIZE)
		return ERROR;                //当前存储空间已满
	for(j=L.length-1;j>=i-1;j--) 
		L.elem[j 1]=L.elem[j];       //插入位置及之后的元素后移
	L.elem[i-1]=e;                   //将新元素e放入第i个位置
	  L.length;                      //表长 1
	return OK;

}


//删除指定位置数据
Status ListDelete(SqList &L,int i,int j)
{
	if((i<1)||(i>L.length))
		return ERROR;                //i值不合法
	for(j=i;j<=L.length-1;j  )
		L.elem[j-1]=L.elem[j];       //被删除元素之后的元素前移
	--L.length;                      //表长-1
	return OK;
}


//按值删除数据（先调用查找函数找到位置，再按位置删除）
Status ValueDelete(SqList &L,int i,int j,ElemType e)
{
 LocateElem(L,e);
 ListDelete(L,i,j);
 return 0;
}


//输出线性表中的数据
Status Output(SqList &L)
{
	int i;
	for(i=0;i<L.length;i  )
		cout<<L.elem[i];
	return 0;
}


int main()
{	int a[MAXSIZE]={1,2,3,4,5,6,7,8};
	int i,e,j,cur_e,pre_e,next_e;
	SqList L;
	InitList(L);
	cout<<"输入数据:"<<endl;
	Input(L,e);
	ListEmpty(L);
	switch(i)
	{
	case 1:
		cout<<"取出第i个位置的数据的直接前驱数据"<<endl;
		PriorElem(L,cur_e,pre_e);
		break;
	case 2:
		cout<<"取出第i个位置的数据的直接后继数据"<<endl;
		NextElem(L,cur_e,next_e);
		break;
	case 3:
		cout<<"查找数据返回在线性表中的位置"<<endl;
		LocateElem(L,e);
		break;
	case 4:
		cout<<"在指定位置插入数据"<<endl;
		ListInsert(L,i,j,e);
		break;
	case 5:
		cout<<"删除指定位置数据"<<endl;
		 ListDelete(L,i,j);
		break;
	case 6:
		cout<<"按值删除数据"<<endl;
		ValueDelete(L,i,j,e);
		break;
	default:
		cout<<"退出"<<endl;
	}
	Output(L);
	return 0;
}