线性顺序表——数据结构_第1页
线性顺序表——数据结构_第2页
线性顺序表——数据结构_第3页
线性顺序表——数据结构_第4页
线性顺序表——数据结构_第5页
已阅读5页,还剩11页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

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);

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论