数据结构实验线性表及其应用

1、计算机系数据结构实验报告（1）实验目的：帮助学生掌握线性表的基本操作在顺序和链表这两种存储结构上的实现，尤以链表的 操作和应用作为重点。问题描述：1、构造一个空的线性表 L。2、 在线性表L的第i个元素之前插入新的元素 e；3、在线性表L中删除第i个元素，并用e返回其值。实验要求：1、 分别利用顺序和链表存储结构实现线性表的存储，并设计出在不同的存储结构中线 性表的基本操作算法。2、在实验过程中，对相同的操作在不同的存储结构下的时间复杂度和空间复杂度进行 分析。算法分析：由于两种存储结构都用来创建线性结构的数据表，可采用相同的输出模式和整体结构类似的算法，如下：实验内容和过程：顺序存储结构线性

2、表程序清单：顺序存储结构线性表的插入删除#in elude #in elude using namespace std;# define LISTSIZE 100# define CREMENTSIZE10/定义数据元素类型为字符型typedef char ElemType; typedef struct ElemType *elem; int len;int listsize;/数据元素首地址当前元素个数当前存储最大容量SqList;/ 构造一个空的线性表 Lint InitList(SqList &L)=(ElemType *)malloc(LISTSIZE*sizeof(ElemType

3、); if (! exit(-2); / 分配空间失败 =0;=LISTSIZE;/ 在顺序线性表 L 中第 i 个位置之前插入新的元素 e int ListInsert(SqList &L,int i,ElemType e)if (i+1) return -1; /i if =值不合法ElemType *newelem=(ElemType *)realloc,+CREMENTSIZE)*sizeof(ElemType);/ 存储空间已满，增加分配if(!newelem) exit (-2); / =newelem; +=CREMENTSIZE;分配失败ElemType *q=&i-1) ;f

4、or (ElemType *p=&);p=q;-p) *(p+1)=*p; /插入位置及其后的元素后移q=e; +;return 1;/在顺序线性表L中删除第i个元素，并用e返回其值int ListDelete(SqList &L,int i,ElemType&e)if (i return -1; /i ElemType *p=&i-1);值不合法e=*p; ElemType*q=+;for (+p;pch;if(ch=I)couti; coute;coutendl;printf( 输入数据： L=(%s)state=ListInsert (L,i,e);else if (ch=D)couti

5、;coutendl;printf( 输入数据： L=(%s)state=ListDelete(L,i,e);else goto AGAIN;/coutendl 正确结果： ; if(state=-1) coutERROR,; printf(L=(%s) ,;/ListInsert(L,%d,%c),i,e);/ 删除操作DeleteList(L,%d,e),i);操作指示符输入错误处理输出结果if(ch=D&state!=-1) cout,e=e;链式存储结构线性表程序清单：/ 单链存储结构线性表的插入删除 #include 定义数据元素类型为字符型获取第 i 个元素的值寻找第 i 个元素寻找

6、失败#include using namespace std;#define null 0typedef char ElemType;/typedef struct LNodeElemType data; struct LNode *next;LNode,*LinkList;int GetElem(LinkList L,int i,ElemType &e) / LinkList p;int j; p=L-next; j=1; while(p&jnext; +j; / if(!p|ji) return -1;/e=p-data; return 1; int ListInsert(LinkList

7、 &L,int i,ElemType e)/ 在带头结点的单链线性表 L 中第 i 个元素之前插入元素 e LinkList p,s; int j;p=L;j=0; while(p&jnext;+j; if(!p|ji-1) return -1; s=(LinkList) malloc( sizeof(LNode); s-data=e;s-next=p-next; p-next=s;return 1;int ListDelete(LinkList&L,int i,ElemType&e)/ 在带头结点的单链线性表 L 中, 删除第 i 个元素，并由 e 返回其值 LinkList p,q; in

8、t j;p=L;j=0;while(p-next&jnext;+j;if(!(p-next)|ji-1) return -1; q=p-next;p-next=q-next; e=q-data;free(q);return 1;int newdata(LinkList&L,char *ch)int k;printf( 请输入原始数据 ( 字符串个数 099) ： L=); / 数据初始化 gets(ch);ListInsert(L,k+1, chk); /返回链表中的元素个数将初始for (k=0;chk!=0;k+) 化数据插入链表 L 中 coutOKCH;if(CH=I)couti; c

9、oute;coutendl;printf( 输入数据： L=(%s) ListInsert(L,%d,%c),ch,i,e); state=ListInsert(L,i,e);+;else if (CH=D)couti;coute ndl;prin tf(输入数据：L=(%s)state=ListDelete(L,i,e);else goto AGAIN;/coute ndl正确结果：; if(state=-1) coutERROR,; cout=m;m+)/GetElem(L,m,f);coutf;DeleteList(L,%d,e),ch,i);操作指示符输入错误处理/输出结果输出数据co

10、ut);删除操作反馈eif(CH=D&state!=-1) cout,e= LiStIriEet ,EHROR-L=CEHIKHOPp&eeas fruited uith i*etui*n value 0 ies：s any key to Eoratiraue _L = (ABCEHKNPQTU) List In sert(L, 4, u)C:Us ersAd minist rato rD m kto p；未命答 2exeL = () ListDelete (L, 1, e)L = (DEFILMNORU) ListDelete_Sq(L, 5, e)L = (CD) ListDelete S

11、q(L, 1, e)测试过程中所注意到的问题主要还是输出与输入界面的问题，通过灵活使用cout和cin函数来不断改进。另外，在用户端看来在设计算法时程序的可重复性未考虑，显得不够人性化。时间复杂度分析：假定线性表有n个节点，顺序存储结构下，插入程序段以*(p+1)=*p作为基本操作的原操作， 并讨论在最坏情况下的时间复杂度，记T(n)=0(n);删除程序段以*(p-1)=*(p)作为基本操作的原操作，并讨论在最坏情况下的时间复杂度，记T (n)=O(n)。链式存储结构下，插入程序段以 p=p- next作为基本操作的原操作，并讨论在最坏情况下的时间复杂度，记 T(n)=O(n);删除程序段以p

12、=p-next作为基本操作的原操作，并讨论在最坏情况下的时间复 杂度，记 T (n)=O(n)。总结和感想：改进设想在于减少中间变量，优化数据初始化操作，和增加程序可重复性。具体操作完成估计就该把上述程序全面修改了，还包括算法的修改和增进。从完成该实验的过程中， 出现的问题很多，一方面由于对 C语言的不够熟悉，在语法和语句 执行效率上总是不尽人意，另一方面由于在设计算法时考虑不全面， 在后来写入程序时屡屡 修改，使程序设计效率大大降低。基于上述两点，今后需全面复习 C语言以效后计，并做好在设计算法方面的工作。思考题：实现链表的逆置算法：以上述链式存储结构线性表程序做基础，可省略数据初始化和输入输出等操作，