线性顺序表——数据结构

1、/头文件#include <stdio.h>#include <stdlib.h>/预定义常量和类型:函数结果状态代码#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 Stat

2、us;typedef int ElemType;typedef 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) print

3、f("分配失败n"); exit(OVERFLOW); /存储分配失败 L.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/函数Destro

4、yList的主要功能是销毁线性表L。Status DestroyList(SqList &L)if(exist(L)/判断线性表是否存在 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) /重置为空

5、表return OK;else return ERROR;/重置线性表，成功返回OK，失败返回ERROR/函数ListEmpty的主要功能是判断线性表是否为空表。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

6、L.length ;/返回元素个数elsereturn -1;/检验线性表元素个数，成功返回数字，失败返回-1./函数GetElem的主要功能是返回线性表中指定位置的数据元素。 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

7、ERROR;/成功返回 OK, 失败返回ERROR/函数compare的主要功能是判断线性表中有与输入元素相同的数值，函数默认程序compare(ElemType e1, ElemType e2) if(e1=e2)return OK; /相等，返回OKelsereturn ERROR;/不相等，返回ERROR /函数返回值是一个执行成功与否的状态标志/函数LocateElem的主要功能是返回满足函数compare()的数据元素位序。int LocateElem(SqList L,ElemType e, Status(*compare)(ElemType,ElemType) int i; El

8、emType *p; i=1 ;/i的处值为第1个元素的位序 p=L.elem; /p的初值为第1个元素的存储位置 while(i<=L.length&&!(*compare)(*p+,e)+i; if(i<=L.length) return i; else return ERROR; /在顺序线性表L中查找第一个与e满足compare()的元素的位序 /若找到，则返回其在L中的位序，否则返回ERROR/函数PriorElem的主要功能是返回指定元素的前驱。Status PriorElem(SqList L,ElemType cur_e,ElemType &

9、pre_e) int i=0; /初始化元素下标 while(i<L.length) /循环条件if(L.elemi=cur_e)/若L.elemi的元素值与cur_e相等if(i>0)/判断i值是否合法 pre_e=L.elemi-1; return pre_e;/满足条件，用pre_e返回元素cur_e前驱的值 else return -1; i+;/循环条件不满足，继续循环if(i>=L.length)return ERROR;/不满足循环条件，无法继续实行return OK;/操作成功，返回OK/返回给定元素的前驱，成功则返回OK,由pre_e带回前驱值，失败则返回E

10、RROR/函数NextElem的主要功能是返回元素元素的后继。Status NextElem(SqList L,ElemType cur_e,ElemType &next_e)int i=0;while(i<L.length)/循环条件if(L.elemi=cur_e)/若L.elemi的元素值与cur_e相等if(i!=L.length-1)/判断i值是否合法 next_e=L.elemi+1; return next_e;/满足条件，用next_e返回元素cur_e后继的值 else return -1; i+;/循环条件不满足，继续循环if(i>=L.length)r

11、eturn ERROR;/不满足循环条件，无法继续实行return OK;/操作成功，返回1 /若cur_e是L的数据元素，且不是最后一个，则用next_e返回他的后继，若失败，则next_e无定义/函数visit的主要功能是判断是依次输出线性表的元素的值Status visit(ElemType e) printf("%d ",e); return OK;/输出完成，返回OK/函数ListInsert的主要功能是向线性表中插入新的元素。Status ListInsert(SqList &L, int i, ElemType e)/参数L表示的是一个已经初始化的线性

12、表变量/e表示待插入的数据/函数返回值是一个执行成功与否的状态标志 /i的合法值为1<=i<=ListLength_Sq(L)+1ElemType *newbase,*q,*p;if(i<1|i>L.length+1) return ERROR; /i值不合法if(L.length>=L.listsize) /当前存储空间已满，增加分配newbase=(ElemType *)realloc(L.elem,(L.listsize +LINSTINCREMENT)*sizeof(ElemType);if(!newbase)exit(OVERFLOW);/存储分配失败L

13、.elem=newbase;/新基址L.listsize+=LINSTINCREMENT;/增加存储容量q=&(L.elem i-1); /q为插入位置 for(p=&(L.elemL.length-1);p>=q;-p) *(p+1)=*p; /插入位置及之后的元素后移*q=e; /插入e+L.length ;/表长增加1return OK;/插入成功，返回OK/ListInsert/函数ListDelete的主要功能是删除线性表中的元素。Status ListDelete(SqList &L,int i,ElemType &e)/线性表L已存在且非空，

14、在顺序线性表L中删除第i个元素，并用e返回其值，L的长度-1 /i的合法值为1<=i<=LIstLength_Sq(L) ElemType *q,*p;if(i<1)|(i>L.length)return ERROR; /i值不合法p=&(L.elemi-1); /p为被删除元素的位置 e=*p; /被删除元素的值赋给e q=L.elem+L.length-1; /表尾元素的位置 for(+p;p<=q;+p) *(p-1)=*p; /被删除之后的元素往前移 -L.length; /表长减一 return OK;/ListDelete/函数ListTrav

15、erse的主要功能是对每个元素调用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+); /对每个数据元素调用visit() return OK;/操作成功 /顺序线性表L已存在,依次对L的每个数据元素调用函数visit(),一旦visit()失败，则操作失败int main()SqList L;ElemType e,cur_e,pr

16、e_e,next_e;int i,j,n;InitList(L);printf("输入元素的个数为:");scanf("%d",&n);while(n<=0)/n的合法值为n>0printf("输入错误,请重新输入n");printf("输入元素的个数为:");scanf("%d",&n);printf("请输入%d个元素:",n);/输入元素for(i=1;i<=n;i+)scanf("%d",&e);ListI

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

18、的合法值为0<i<L.length+1printf("输入错误,请重新输入n");printf("请输入元素的序数为:");scanf("%d",&i);GetElem(L,i,e);printf("第%d个的元素的值为%dn",i,e);printf("n");/函数LocateElem和函数compare()的应用，查找第一个与e满足函数compare()的元素的位序 printf("请输入数据元素e:");scanf("%d",&

19、amp;e);printf("第一个与e满足关系的元素的位序为:%dn",LocateElem(L,e,(*compare); printf("n");/函数priorElem的应用，输出某数据元素的前驱printf("请输入数据元素cur_e:");scanf("%d",&cur_e);if(PriorElem(L,cur_e,pre_e)!=-1) printf("%d的前驱为:%dn",cur_e,PriorElem(L,cur_e,pre_e);else printf("

20、;线性表L中没有数据元素%d的前驱n",cur_e);printf("n");/函数NextElem的应用,输出某元素的后继printf("请输入数据元素cur_e:");scanf("%d",&cur_e);if(NextElem(L,cur_e,next_e)!=-1) printf("%d的后继为:%dn",cur_e,NextElem(L,cur_e,next_e);else printf("线性表L中没有数据元素%d的后继n",cur_e);printf("

21、n");/函数ListInsert的应用，插入元素printf("请输入要插入的数据元素的位置i:");scanf("%d",&i); printf("请输入要插入的数据元素e:");scanf("%d",&e); if(i>=1&&i<=L.length) ListInsert(L,i,e); printf("插入新的数据元素后的线性表L中的数据元素为:"); for(i=0;i<L.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;i<L.le