数据结构实验线性表与应用

《数据结构实验线性表与应用》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

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

2、：顺序存储结构线性表程序清单：//顺序存储结构线性表的插入删除#include技术资料专业分享WORD文档可编辑#includeusingnamespacestd;#defineLISTSIZE100#defineCREMENTSIZE10typedefcharElemType;//定义数据元素类型为字符型typedefstruct{ElemType*elem;//数据元素首地址intlen;//当前元素个数intlistsize;//当前存储最大容量}SqList;//构造一个空的线性表LintInitList(SqList&L){L.elem=(El

3、emType*)malloc(LISTSIZE*sizeof(ElemType));if(!L.elem)exit(-2);//分配空间失败L.len=0;L.listsize=LISTSIZE;}//在顺序线性表L中第i个位置之前插入新的元素eintListInsert(SqList&L,inti,ElemTypee){if(i<1

4、

5、i>L.len+1)return-1;//i值不合法if(L.len>=L.listsize){ElemType*newelem=(ElemType*)realloc(L.elem,(L.listsize+CREMENTSIZE)*sizeof(ElemTyp

6、e));//存储空间已满，增加分配if(!newelem)exit(-2);//分配失败L.elem=newelem;L.listsize+=CREMENTSIZE;}ElemType*q=&(L.elem[i-1]);for(ElemType*p=&(L.elem[L.len-1]);p>=q;--p)*(p+1)=*p;//插入位置及其后的元素后移*q=e;++L.len;return1;}//在顺序线性表L中删除第i个元素，并用e返回其值intListDelete(SqList&L,inti,ElemType&e)技术资料专业分享WORD文档可编辑{if(i<1

7、

8、i>L.len)ret

9、urn-1;//i值不合法ElemType*p=&(L.elem[i-1]);e=*p;ElemType*q=L.elem+L.len-1;for(++p;p<=q+1;++p)*(p-1)=*p;//被删除元素之后的元素前移--L.len;return1;}intmain(){SqListL;chare,ch;inti,j,state;InitList(L);//构造线性表printf("请输入原始数据(字符串个数0~99)：L=");//数据初始化gets(L.elem);for(j=1;L.elem[j-1]!='';j++)L.len=j;//获取表长L.lenL.elem[j]=

10、'';printf("操作：插入（I）还是删除(D)?");//判断进行插入还是删除操作AGAIN:cin>>ch;if(ch=='I'){cout<<"插在第几个元素之前:";//插入操作cin>>i;cout<<"输入要插入的新元素:";cin>>e;cout<>i;cout<

11、teList(L,%d,e)",L.elem,i);state=ListDelete(L,i,e);}elsegotoAGAIN;//操作指示符输入错误处理cout<