顺序表的基本操作实验报告

1、精选优质文档-倾情为你奉上精选优质文档-倾情为你奉上专心-专注-专业专心-专注-专业精选优质文档-倾情为你奉上专心-专注-专业实验名称 顺序表的基本操作实验日期2019.9.23实验成绩1、实验目的： 1掌握线性表的顺序存储结构的表示和实现方法。2掌握顺序表基本操作的算法实现。3了解顺序表的应用。2、实验内容： 编写一个程序，实现顺序表的各种基本运算（假设顺序表的元素类型为 char），并在此基础上设计一个主程序完成如下功能：（1）初始化顺序表 L；（2）依次采用尾插法插入 a、b、c、d、e 元素；（3）输出顺序表 L；（4）输出顺序表 L 的长度；（5）判断顺序表 L 是否为空；（6）输出

2、顺序表 L 的第 3 个元素；（7）输出元素 a 的位置（8）在第 4 个元素位置上插入 f 元素（9）输出顺序表 L；（10）删除 L 的第 3 个元素；（11）输出顺序表 L；（12）释放顺序表 L。3、核心算法或代码片段：核心算法：1顺序表插入操作的基本步骤：要在顺序表中第 i 个数据元素之前插入一个数据元素 x，首先要判断插入位置 i 是否合法，假设线性表的长为 n，则 i 的合法值范围： 1in+1，若是合法位置，就再判断顺序表否满，如果满，则增加空间或结束操作，如果不满，则将第 i 个数据元素及其之后的所有数据元素都后移一个位置，此时第 i 个位置已经腾空，再将待插入的数据元素 x

3、 插入到该位置上，最后将线性表的长增加 1。2顺序表删除操作的基本步骤：要删除顺序表中第 i 个数据元素，首先仍然要判断 i 的合法性， i 的合法范围是 1in，若是合法位置，则将第 i 个数据元素之后的所有数据都前移一个位置，最将线性表长减 1。3顺序表查找操作的基本步骤：要在顺序表中查找一个给定值的数据元素则可以采用顺序查找的方法，从表中第 1 个数据元素开始依次将值与给定值进行比较，若相等则返回该数据元素在顺序表中的位置，否则返回 0 值。线性表的动态分配顺序存储结构C语言实现#define MaxSize 50/存储空间的分配量Typedef char ElemType；Typede

4、f struct ElemType dataMaxSize; int length; /表长度（表中有多少个元素）SqList;动态创建一个空顺序表的算法：void InitList(SqList *&L) /初始化线性表 L=(SqList *)malloc(sizeof(SqList); /分配存放线性表的空间 L-length=0; /置空线性表长度为0线性表的插入：status Sqlist_insert(Sqlist &L,int i,Elemtype x) /*在顺序表L中第i个元素前插入新元素x*/ if (iL.length+1) return ERROR; /*插入位置不正确

5、则出错*/ if (L.length=MAXLEN)return OVERFLOW; /*顺序表L中已放满元素，再做插入操作则溢出*/for(j=L.length-1;j=i-1;j-) L.elemj+1=L.elemj; /*将第i个元素及后续元素位置向后移一位*/L.elemi-1=x; /*在第i个元素位置处插入新元素x*/L.length+; /*顺序表L的长度加1*/return OK;线性表的删除：status Sqlist_delete(Sqlist &L,int i,Elemtype &e) /*在顺序表L中删除第i个元素* if (iL.length) return ERR

6、OR; /*删除位置不正确则出错*/ for(j=i;j=L.length-1;j+) L.elemj-1=L.elemj; /*将第i+1个元素及后继元素位置向前移一位*/ L.length-;/*顺序表L的长度减1*/ return OK；线性表元素的查找：int LocateElem(SqList *L, ElemType e) /按元素值查找 int i=0; while (ilength & L-datai!=e) i+; /查找元素e if (i=L-length) /未找到时返回0 return 0; else return i+1; /找到后返回其逻辑序号输出线性表：void

7、DispList(SqList *L) /输出线性表 int i; if (ListEmpty(L) return; for (i=0;ilength;i+) printf(%c ,L-datai); printf(n);输出线性表第i个元素的值：bool GetElem(SqList *L,int i,ElemType &e)/求线性表中某个数据元素值 if (iL-length) return false; /参数错误时返回false e=L-datai-1; /取元素值 return true; /成功找到元素时返回true代码：#include #include #define Max

8、Size 50typedef char ElemType;typedef struct ElemType dataMaxSize; int length; SqList;void InitList(SqList *&L);void DestroyList(SqList *L);bool ListEmpty(SqList *L);int ListLength(SqList *L);void DispList(SqList *L);bool GetElem(SqList *L,int i,ElemType &e);int LocateElem(SqList *L, ElemType e);bool

9、 ListInsert(SqList *&L,int i,ElemType e);bool ListDelete(SqList *&L,int i,ElemType &e);void InitList(SqList *&L)/初始化线性表L=(SqList *)malloc(sizeof(SqList);/分配存放线性表的空间L-length=0;/置空线性表长度为0void DestroyList(SqList *L)/销毁线性表free(L);bool ListEmpty(SqList *L)/判线性表是否为空表return(L-length=0);int ListLength(SqLis

10、t *L)/求线性表的长度return(L-length);void DispList(SqList *L)/输出线性表int i;if (ListEmpty(L) return;for (i=0;ilength;i+)printf(%c ,L-datai);printf(n);bool GetElem(SqList *L,int i,ElemType &e)/求线性表中某个数据元素值if (iL-length)return false;/参数错误时返回falsee=L-datai-1;/取元素值return true;/成功找到元素时返回trueint LocateElem(SqList *

11、L, ElemType e)/按元素值查找int i=0;while (ilength & L-datai!=e)i+;/查找元素eif (i=L-length)/未找到时返回0return 0;elsereturn i+1;/找到后返回其逻辑序号bool ListInsert(SqList *&L,int i,ElemType e)/插入数据元素int j;if (iL-length+1)return false;/参数错误时返回falsei-;/将顺序表逻辑序号转化为物理序号for (j=L-length;ji;j-)/将datai及后面元素后移一个位置L-dataj=L-dataj-1;

12、L-datai=e;/插入元素eL-length+;/顺序表长度增1return true;/成功插入返回truebool ListDelete(SqList *&L,int i,ElemType &e)/删除数据元素int j;if (iL-length)/参数错误时返回falsereturn false;i-;/将顺序表逻辑序号转化为物理序号e=L-datai;for (j=i;jlength-1;j+)/将datai之后的元素前移一个位置L-dataj=L-dataj+1;L-length-;/顺序表长度减1return true;/成功删除返回truevoid main()SqList

13、 *L;ElemType e;printf(顺序表的基本运算如下:n);printf( (1)初始化顺序表Ln);InitList(L);printf( (2)依次采用尾插法插入a,b,c,d,e元素n);ListInsert(L,1,a);ListInsert(L,2,b);ListInsert(L,3,c);ListInsert(L,4,d);ListInsert(L,5,e);printf( (3)输出顺序表L:);DispList(L);printf( (4)顺序表L长度=%dn,ListLength(L);printf( (5)顺序表L为%sn,(ListEmpty(L)?空:非空);GetElem(L,3,e);printf( (6)顺序表L的第3个元素=%cn,e);printf( (7)元素a的位置=%dn,LocateElem(L,a);printf( (8)在第4个元素位置上插入f元素n);ListInsert(L,4,f);printf( (9)输出顺序表L:);DispList(L);printf( (10)删除L的第3个