数据结构的课件实验一线性表的顺序表示和实现

实验一 线性表的顺序表示和实现实验内容 1.线性表的顺序存储结构C语言中的顺序表存储结构描述： 线性表的顺序存储结构 #define MAXSIZE 100 /*顺序表允许的最大空间量*/typedef struct ElemType elemMAXSIZE; /* ElemType为抽象数据类型*/ int length; /*当前顺序表长度*/ SqList; 2.顺序表的基本操作 （1）初始化操作：为顺序表分配一个预定义大小的数组空间，并将线性表的当前长度length设为0。（2）清空操作：将顺序表的长度设为0，是表为空表（3）销毁操作：将顺序表所占用的空间释放（4）定位操作：根据给定的数据元素e，在顺序表中找出和e相等的数据元素的位序，如果这样的数据元素不存在，则返回0（5）插入操作：在顺序表的第i个数据元素前插入一个新的数据元素e，注意，在插入前必须判断i的值域，而在插入操作后必须使顺序表的长度增1.（6）删除操作：删除顺序表中第i个数据元素，并且用e返回其值。注意，在删除操作前必须判断i的值域，而在删除操作后必须使顺序表的长度减1。（7）输出操作：即将顺序表中各个元素按下标次序输出。3.顺序表操作实现的操作步骤（1）实现将顺序表的存储结构和基本操作程序代码。（2）实现main主函数。4.程序代码完整清单#include #include #define MaxSize 50 /*顺序表允许的最大空间量*/typedef char ElemType; /*顺序表中元素类型为char*/typedef struct ElemType elemMaxSize; int length; SqList; /*顺序表结构定义 */基本操作函数声明 void InitList(SqList *&L); /*初始化线性表*/ void DestroyList(SqList *L); /*销毁线性表*/ int ListEmpty(SqList *L); /*清空线性表*/int ListLength(SqList *L); /*求表长*/void DispList(SqList *L); /*输出表*/int GetElem(SqList *L,int i,ElemType &e); /*取表中元素*/ int LocateElem(SqList *L, ElemType e); /*定位表中元素*/ int ListInsert(SqList *&L,int i,ElemType e); /*插入元素*/int ListDelete(SqList *&L,int i,ElemType &e); /*删除表中元素*/void main()SqList *L;ElemType e;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个元素n); ListDelete(L,3,e);printf(11)输出顺序表L:);DispList(L);printf(12)释放顺序表Ln);DestroyList(L);void InitList(SqList *&L) /*初始化线性表 操作结果：构造一个空的顺序线性表*/L=(SqList *)malloc(sizeof(SqList);L-length=0;void DestroyList(SqList *L) /*释放线性表 操作结果：释放空间*/free(L);int ListEmpty(SqList *L) /*清空线性表 操作结果：将L置为空表*/return(L-length=0);int ListLength(SqList *L) /*求表长 操作结果：返回表中元素个数*/return(L-length);void DispList(SqList *L) /*输出表 操作结果：若顺序表非空，则输出顺序表中所有*/ /*元素的值，否则为空操作*/int i;if (ListEmpty(L) return;for (i=0;ilength;i+)printf(%c,L-elemi);printf(n);int GetElem(SqList *L,int i,ElemType &e) /*取表中元素 操作结果：用e返回L中的第i*/ /*个元素的值*/if (iL-length)return 0;e=L-elemi-1;return 1;int LocateElem(SqList *L, ElemType e) /*定位表中元素 操作结果：返回L中第1个*/ /* 与e相等的元素位序*/int i=0;while (ilength & L-elemi!=e) i+;if (i=L-length)return 0;elsereturn i+1;int ListInsert(SqList *&L,int i,ElemType e) /*向表中插入元素 操作结果：在L 中第i个*/ /*位置前插入新的数据元素e，L的长度加1*/int j;if (iL-length+1)return 0;i-;/*将顺序表位序转化为elem下标*/for (j=L-length;ji;j-)/*将elemi及后面元素后移一个位置*/L-elemj=L-elemj-1;L-elemi=e;L-length+;/*顺序表长度增1*/return 1;int ListDelete(SqList *&L,int i,ElemType &e) /*将表中元素删除 操作结果：将L 中第i /*个位置的元素删除，L的长度减1int j;if (iL-length)return 0;i-;/*将顺序表位序转化为elem下标*/e=L-elemi;for (j=i;jlength-1;j+)L-elemj=L-elemj+1;L-length-;return 1;5. 运行结果清单(1)初始化顺序表L(2)依次采用尾