数据结构——线性表

#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
数据结构——线性表

推荐阅读更多精彩内容
