#include <stdio.h>
#include <stdlib.h>
//以下为函数运行结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define LIST_INIT_SIZE 5 //线性表存储空间的初始分配量
#define LISTINCREMENT 1 //线性表存储空间分配增量
typedef int Status; //函数类型，其值为为函数结果状态代码
typedef int ElemType; //假设数据元素为整型
typedef struct
{
ElemType *elem; //存储空间基址
int length; //当前长度
int listsize; //当前分配的存储容量
}Sqlist;
//实现线性表的顺序存储结构的类型定义
static Sqlist L;//为了引用方便，定义为全局变量
static ElemType element;
///////////////////////////////////////
//函数名：InitList()
//参数：SqList L
//初始条件：无
//功能：构造一个空线性表
//返回值：存储分配失败：OVERFLOW
// 存储分配成功：OK
///////////////////////////////////////
Status InitList(Sqlist L)
{
L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(L.elem==NULL)
exit(OVERFLOW);
else
{
L.length=0;
L.listsize=LISTINCREMENT;
return OK;
}
}
///////////////////////////////////////
//函数名：DestroyList()
//参数：SqList L
//初始条件：线性表L已存在
//功能：销毁线性表
//返回值：L.elem==NULL:ERROR
// L.elem!=NULL:OK
///////////////////////////////////////
Status DestroyList(Sqlist L)
{
if(L.elem==NULL)
return ERROR;
else
free(L.elem);
return OK;
}
///////////////////////////////////////
//函数名：ClearList()
//参数：SqList L
//初始条件：线性表L已存在
//功能：清空线性表
//返回值：L.elem==NULL:ERROR
// L.elem!=NULL:OK
///////////////////////////////////////
Status ClearList(Sqlist L)
{
if(L.elem==NULL)
exit(ERROR);
int i;
ElemType *p_elem=L.elem;
for(i=0;i<L.length;i++)
{
*L.elem=NULL;
L.elem++;
}
L.elem=p_elem;
return OK;
}
///////////////////////////////////////
//函数名：ListEmpty()
//参数：SqList L
//初始条件：线性表L已存在
//功能：判断线性表是否为空
//返回值：空：TRUE
// 非空：FALSE
///////////////////////////////////////
Status ListEmpty(Sqlist L)
{
int i;
ElemType *p_elem=L.elem;
for(i=0;i<L.length;i++)
{
if(*L.elem!=0)
{
L.elem=p_elem;
return FALSE;
}
L.elem++;
}
return TRUE;
}
///////////////////////////////////////
//函数名：ListLength()
//参数：SqList L
//初始条件：线性表L已存在
//功能：返回线性表长度
//返回值：线性表长度(L.length)
///////////////////////////////////////
int ListLength(Sqlist L)
{
return L.length;
}
///////////////////////////////////////
//函数名：GetElem()
//参数：SqList L,int i,ElemType *element
//初始条件：线性表L已存在，1<=i<=ListLength(L)
//功能：用e返回线性表中第i个元素的值
//返回值：(i<1)||(i>ListLength(L))：OVERFLOW
// 1<=i<=ListLength(L)：OK
///////////////////////////////////////
Status GetElem(Sqlist L,int i)
{
int j;
ElemType *p_elem=L.elem;
if(i<1||i>L.length)
return OVERFLOW;
for(j=1;j<=i;j++)
L.elem++;
element=*L.elem;
L.elem=p_elem;
return OK;
}
///////////////////////////////////////
//函数名：LocateElem()
//参数：Sqlist L,ElemType element
//初始条件：线性表L已存在
//功能：返回顺序表L中第1个与element相等的元素
//返回值：若在L中存在于element相等的元素：其位序
// 若在L中不存在与element相等的元素：0
///////////////////////////////////////
int LocationElem(Sqlist L,ElemType element)
{
int i;
ElemType *p_elem=L.elem;
for(i=1;i<L.length;i++)
{
if(*L.elem==element)
{
L.elem=p_elem;
return i;
}
else
L.elem++;
}
return 0;
}
///////////////////////////////////////
//函数名：PriorElem()
//参数：Sqlist L,ElemType cur_e,ElemType *pre_e
//初始条件：线性表L已存在，i>1&&i<=L.length，LocationElem()存在
//功能：用pre_e返回线性表中cur_e的前驱
//返回值：i<=1||i>L.length：OVERFLOW
// i>1&&i<=L.length：OK
///////////////////////////////////////
Status PriorElem(Sqlist L,ElemType cur_e,ElemType *pre_e)
{
ElemType *p_elem=L.elem;
int i,j;
i=LocationElem(L,cur_e);
if(i<=1||i>L.length)
exit(OVERFLOW);
for(j=1;j<i;j++)
{
if(j==(i-1))
{
pre_e=L.elem;
L.elem=p_elem;
return OK;
}
else
L.elem++;
}
}
///////////////////////////////////////
//函数名：NextElem()
//参数：Sqlist L,ElemType cur_e,ElemType *next_e
//初始条件：线性表L已存在，i>=1&&i<L.length，LocationElem()存在
//功能：用next_e返回线性表中cur_e的后继
//返回值：i<1||i>=L.length：OVERFLOW
// i>=1&&i<L.length：OK
///////////////////////////////////////
Status NextElem(Sqlist L,ElemType cur_e,ElemType *next_e)
{
ElemType *p_elem;
int i,j;
i=LocationElem(L,cur_e);
if(i<1||i>=L.length)
exit(OVERFLOW);
for(j=1;j<i;j++)
{
if(j==(i-1))
{
next_e=L.elem;
L.elem=p_elem;
return OK;
}
else
L.elem++;
}
}
///////////////////////////////////////
//函数名：ListInsert()
//参数：SqList L,int i,ElemType e
//初始条件：线性表L已存在，1<=i<=ListLength(L)+1
//功能：在线性表中第i个数据元素之前插入数据元素e
//返回值：失败：ERROR
// 成功：OK
///////////////////////////////////////
Status ListInsert(Sqlist L,int i,ElemType e)
{
int *q=&(L.elem[i-1]);
ElemType *newbase,*p;
if(i<1||i>(L.length+1))
return ERROR;
if(L.length>=L.listsize)
{
newbase=(ElemType*)realloc(L.elem,L.listsize+LISTINCREMENT*sizeof(ElemType));
if(newbase==NULL)
exit(OVERFLOW);
L.elem=newbase;
L.listsize+=LISTINCREMENT;
}
for(p=&(L.elem[L.length-1]);p>=q;--p)
*(p+1)=*p;
*q=e;
++L.length;
return OK;
}
///////////////////////////////////////
//函数名：ListDelete()
//参数：SqList L,int i,Elemtype e
//初始条件：线性表L已存在，1<=i<=ListLength(L)
//功能：将线性表L中第i个数据元素删除
//返回值：失败：ERROR
// 成功：OK
///////////////////////////////////////
Status ListDelet(Sqlist L,int i,ElemType e)
{
if(i<1||(i>L.length))
return ERROR;
ElemType *p,*q;
p=&(L.elem[i-1]);
e=*p;
q=L.elem+L.length-1;
for(++p;p<=q;++p)
*(p-1)=*p;
--L.length;
return OK;
}
