线性顺序表——数据结构

1、/头文件#include #include /预定义常量和类型:函数结果状态代码#define OK 1#define ERROR 0#define TURE 1#define FALSE 0 #define INFEASIBLE -1#define OVERFLOW -2/-线性表的动态分配顺序存储结构-#define LIST_INIT_SIZE 100 /线性表存储空间的初始分配量#define LINSTINCREMENT 10 /线性表存储空间的分配增量/数据类型说明,其值是函数结果状态代码typedef int Status;typedef int ElemType;typedef

2、 struct ElemType *elem; /存储空间基址int length; /当前长度int listsize; /当前分配的存储容量（以sizeof(ElemType)为单位SqList; /定义了一个线性表的数据类型/-函数基本操作-/ 函数InitList的主要功能是初始化一个线性表,构造一个空的线性表L。Status InitList(SqList &L) L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType); if(!L.elem) printf(分配失败n); exit(OVERFLOW); /存储分配失败 L

3、.length=0; /空表长度为0L.listsize=LIST_INIT_SIZE; /初始存储容量return OK; /InitList/函数Exist的主要功能是判断线性表L是否存在。Status exist(SqList &L) if(L.elem!=NULL)&(L.listsize=LIST_INIT_SIZE) /检测线性表是否存在 return OK; else return ERROR;/若线性表存在返回OK，否则返回ERROR/函数DestroyList的主要功能是销毁线性表L。Status DestroyList(SqList &L)if(exist(L)/判断线性表

4、是否存在 free(L.elem); /释放空间L.elem =NULL; /将指针赋值为空L.length=-1; /当前长度赋值为-1，标志线性表不存在L.listsize=0; /当前最大容量赋值为0return OK;elsereturn ERROR;/成功释放空间时返回OK，否则返回ERROR/函数ClearList的主要功能是将L重置为空表。Status ClearList(SqList &L)if(!(L.elem=NULL) /重置为空表return OK;else return ERROR;/重置线性表，成功返回OK，失败返回ERROR/函数ListEmpty的主要功能是判断

5、线性表是否为空表。Status ListEmpty(SqList L) if(!exist(L) return ERROR; else if(ClearList(L) return TURE; else return FALSE; return OK;/函数ListLength的主要功能是检测线性表的数据元素个数。 Status ListLength(SqList &L)/返回数据元素个数if(exist(L)/判断线性表是否存在return L.length ;/返回元素个数elsereturn -1;/检验线性表元素个数，成功返回数字，失败返回-1./函数GetElem的主要功能是返回线性

6、表中指定位置的数据元素。 Status GetElem(SqList &L, int i, ElemType &e)/ 线性表已存在，用e返回线性表 L中第i个元素 if ( exist(L) & i 0 & i L.length+1) /判定线性表存在和元素位置 i是否合法e = L.elemi - 1; /将指定位置元素赋给ereturn OK; elsereturn ERROR;/成功返回 OK, 失败返回ERROR/函数compare的主要功能是判断线性表中有与输入元素相同的数值，函数默认程序compare(ElemType e1, ElemType e2) if(e1=e2)retu

7、rn OK; /相等，返回OKelsereturn ERROR;/不相等，返回ERROR /函数返回值是一个执行成功与否的状态标志/函数LocateElem的主要功能是返回满足函数compare()的数据元素位序。int LocateElem(SqList L,ElemType e, Status(*compare)(ElemType,ElemType) int i; ElemType *p; i=1 ;/i的处值为第1个元素的位序 p=L.elem; /p的初值为第1个元素的存储位置 while(i=L.length&!(*compare)(*p+,e)+i; if(i=L.length)

8、return i; else return ERROR; /在顺序线性表L中查找第一个与e满足compare()的元素的位序 /若找到，则返回其在L中的位序，否则返回ERROR/函数PriorElem的主要功能是返回指定元素的前驱。Status PriorElem(SqList L,ElemType cur_e,ElemType &pre_e) int i=0; /初始化元素下标 while(i0)/判断i值是否合法 pre_e=L.elemi-1; return pre_e;/满足条件，用pre_e返回元素cur_e前驱的值 else return -1; i+;/循环条件不满足，继续循环i

9、f(i=L.length)return ERROR;/不满足循环条件，无法继续实行return OK;/操作成功，返回OK/返回给定元素的前驱，成功则返回OK,由pre_e带回前驱值，失败则返回ERROR/函数NextElem的主要功能是返回元素元素的后继。Status NextElem(SqList L,ElemType cur_e,ElemType &next_e)int i=0;while(i=L.length)return ERROR;/不满足循环条件，无法继续实行return OK;/操作成功，返回1 /若cur_e是L的数据元素，且不是最后一个，则用next_e返回他的后继，若失败

10、，则next_e无定义/函数visit的主要功能是判断是依次输出线性表的元素的值Status visit(ElemType e) printf(%d ,e); return OK;/输出完成，返回OK/函数ListInsert的主要功能是向线性表中插入新的元素。Status ListInsert(SqList &L, int i, ElemType e)/参数L表示的是一个已经初始化的线性表变量/e表示待插入的数据/函数返回值是一个执行成功与否的状态标志 /i的合法值为1=i=ListLength_Sq(L)+1ElemType *newbase,*q,*p;if(iL.length+1) r

11、eturn ERROR; /i值不合法if(L.length=L.listsize) /当前存储空间已满，增加分配newbase=(ElemType *)realloc(L.elem,(L.listsize +LINSTINCREMENT)*sizeof(ElemType);if(!newbase)exit(OVERFLOW);/存储分配失败L.elem=newbase;/新基址L.listsize+=LINSTINCREMENT;/增加存储容量q=&(L.elem i-1); /q为插入位置 for(p=&(L.elemL.length-1);p=q;-p) *(p+1)=*p; /插入位置

12、及之后的元素后移*q=e; /插入e+L.length ;/表长增加1return OK;/插入成功，返回OK/ListInsert/函数ListDelete的主要功能是删除线性表中的元素。Status ListDelete(SqList &L,int i,ElemType &e)/线性表L已存在且非空，在顺序线性表L中删除第i个元素，并用e返回其值，L的长度-1 /i的合法值为1=i=LIstLength_Sq(L) ElemType *q,*p;if(iL.length)return ERROR; /i值不合法p=&(L.elemi-1); /p为被删除元素的位置 e=*p; /被删除元素

13、的值赋给e q=L.elem+L.length-1; /表尾元素的位置 for(+p;p=q;+p) *(p-1)=*p; /被删除之后的元素往前移 -L.length; /表长减一 return OK;/ListDelete/函数ListTraverse的主要功能是对每个元素调用visit()函数测试。Status ListTraverse(SqList L,Status(*visit)(ElemType) ElemType *p=L.elem; /p指向第1个元素 int i; for(i=1;i=L.length;i+) /从表L的第1个元素到最后1个元素 visit(*p+); /对每

14、个数据元素调用visit() return OK;/操作成功 /顺序线性表L已存在,依次对L的每个数据元素调用函数visit(),一旦visit()失败，则操作失败int main()SqList L;ElemType e,cur_e,pre_e,next_e;int i,j,n;InitList(L);printf(输入元素的个数为:);scanf(%d,&n);while(n0printf(输入错误,请重新输入n);printf(输入元素的个数为:);scanf(%d,&n);printf(请输入%d个元素:,n);/输入元素for(i=1;i=n;i+)scanf(%d,&e);List

15、Insert(L,i,e);/调用函数ListInsert输入/显示线性表的元素个数,依次显示元素printf(线性表共有%d个元素，线性表中的元素依次为:,ListLength(L); for(i=0;in;i+) printf(%d ,L.elemi); printf(n);/函数GetElem的应用，返回线性表L中第i个元素的值printf(请输入要返回数据元素的位序:);scanf(%d,&i);while(iL.length)/i的合法值为0i=1&i=L.length) ListInsert(L,i,e); printf(插入新的数据元素后的线性表L中的数据元素为:); for(i

16、=0;iL.length;i+) printf(%d ,L.elemi); printf(n);printf(n);/函数ListDelete的应用，删除元素 printf(请输入要删除的数据元素的位置j:); scanf(%d,&j); ListDelete(L,j,e); printf(删除数据元素后的线性表L中的数据元素为:); for(i=0;iL.length;i+) printf(%d ,L.elemi); printf(n); printf(删除的第%d个元素值为:%d,j,e); printf(n);printf(n);/函数ListTraverse和函数visit()的应用，L中的每个元素依次调用visit()printf(此时线性表L中的元素的值为:);ListTraverse(L,visit);printf(n);printf(n);/函数ClearList和函数ListEmpty的应用，将线性表L重置为空表，并且判断操作是否成功 printf(将线性表L重置为空表n);ClearList(L);