#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status; //定义函数结果的状态码
typedef int ElemType;
//--------------线性表的动态分配存储结构-----------------------
#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量
#define LISTINCREMENT 10 //线性表存储空间的分配增量
typedef struct {
ElemType * elem; //存储空间基址
int length;
int listsize; //当前分配的存储容量
}SqList;
//---------------顺序表的基本操作--------------------------------
Status InitList(SqList &L);
//操作结果：构造一个空的线性表L。
Status DestroyList(SqList &L);
//初始条件：线性表L已存在。
//操作结果：销毁线性表L。
Status ClearList(SqList &L);
//初始条件：线性表L已存在。
//操作结果：将L重置为空表。
bool ListEmpty(SqList L);
//初始条件：线性表L已存在。
//操作结果：若L为空表，则返回TRUE，否则返回FALSE。
int ListLength(SqList L);
//初始条件：线性表L已存在。
//操作结果：返回L中数据元素的个数。
Status GetElem(SqList L, int i, ElemType &e);
//初始条件：线性表L已存在，1<=i<=ListLength(L)。
//操作结果：用e返回L中第i个数据元素的值。
int LocateElem(SqList L, int e, bool (*equal)(ElemType, ElemType));
//初始条件：线性表L已存在，compare()是数据元素判定函数。
//返回L中第一个与e满足关系compare()的数据元素的位序。若这样的数据元素不存在，则返回值为0.
Status PriorElem(SqList L, ElemType cur_e, ElemType &pre_e);
//初始条件：线性表L已存在。
//操作结果：若cur_e是L中的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。
Status NextElem(SqList L, ElemType cur_e, ElemType &next_e);
//初始条件：线性表L已存在。
//操作结果：若cur_e是L中的数据元素，且不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。
Status ListInsert(SqList &L, int i, ElemType e);
//初始条件：线性表L已存在，1<=i<=ListLength(L)+1.
//操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1.
Status ListDelete(SqList &L, int i, ElemType &e);
//初始条件：线性表L已存在且非空，1<=i<=ListLength(L).
//操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1.
Status ListTraverse(SqList L, bool (*visit)(ElemType));
//初始条件：线性表L已存在
//操作结果：依次对L的每个元素调用函数visit().一旦visit()失败,则操作失败。
void MergeList_Sq(SqList La,SqList Lb,SqList &Lc);
//---------------顺序表的功能实现---------------------------------
Status InitList(SqList &L) //构造一个空的顺序表
{
L.elem=(ElemType*)malloc(LIST_INIT_SIZE* sizeof (ElemType));
if (!L.elem) exit(OVERFLOW); //存储分配失败
L.length=0; //空表长度为0
L.listsize=LIST_INIT_SIZE; //初始存储容量
return OK;
}//InitList
Status DestroyList(SqList &L) //线性表存在，销毁线性表
{
free(&L);
return OK;
}//DestroyList
Status ClearList(SqList &L) //将L置为空表
{
L.length=0; //长度为0位空表
return OK;
}//ClearList
bool ListEmpty(SqList L) //判断是否为空表，是返回true否返回false
{
if(!L.length) return TRUE;
else
return FALSE;
}//ListEmpty
int ListLength(SqList L) //返回线性表的长度即返回线性表数据元素个数
{
return L.length;
}//ListLength
Status GetElem(SqList L, int i, ElemType &e) //用e返回第i个元素的值
{
if (i<1||i>L.length) return ERROR; //判断输入是否合法
e=L.elem[i-1];
return OK;
}//GetElem
int LocateElem(SqList L, int e, bool (*equal)(ElemType, ElemType)) //返回L中第一个与e满足关系compare()的数据元素的位序
{
int i=1;
while(i<=L.length && !(equal(L.elem[i-1],e))) ++i;
if (i <= L.length) return i;
else return 0;
}//LocateElem
Status PriorElem(SqList L, ElemType cur_e, ElemType &pre_e) //返回前驱
{
int i=1;
while(i <= L.length && !(cur_e==L.elem[i-1])) ++i;
if(i<2 || i>L.length)
return ERROR;
pre_e = L.elem[i-2];
return OK;
}//PriorElem
Status NextElem(SqList L, ElemType cur_e, ElemType &next_e) //返回后继
{
int i=1;
while(i <= L.length && !(cur_e==L.elem[i-1])) ++i;
if(i>L.length-1)
return ERROR;
next_e = L.elem[i];
return OK;
}//NextElem
Status ListInsert(SqList &L, int i, ElemType e) //在顺序表中第i个位置插入e，L的长度增加1
{
ElemType* p;
ElemType* q;
ElemType* newbase;
if(i<1||i>L.length+1) return ERROR; //判断i的值是否合法
if(L.length>=L.listsize)
{
newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)* sizeof (ElemType));
if (!newbase) exit(OVERFLOW);
L.elem=newbase;
L.listsize+=LISTINCREMENT;
}
q=&(L.elem[i-1]);
for(p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p;
*p=e;
++L.length;
return OK;
}//ListInsert
Status ListDelete(SqList &L, int i, ElemType &e) //删除第i个元素，并返回e
{
ElemType* p,*q;
if(i<1||i>L.length) return ERROR;
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;
}//ListDelete
Status ListTraverse(SqList L, bool (*visit)(ElemType)) //对L中每个元素调用函数visit
{
int i=1;
while (i<=L.length && (visit(L.elem[i-1]))) ++i;
return OK;
}
github代码:https://github.com//badcyc/dataStruct
网友评论