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

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

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;

3、//构造一个空的线性表LintInitList(SqList&L){L.elem=(ElemType*)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*newele

6、m=(ElemType*)realloc(L.elem,(L.listsize+CREMENTSIZE)*sizeof(ElemType));//存储空间已满，增加分配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中删

7、除第i个元素，并用e返回其值intListDelete(SqList&L,inti,ElemType&e)专业整理知识分享完美WORD格式{if(i<1

8、

9、i>L.len)return-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);//构造线性

10、表printf("请输入原始数据(字符串个数0~99)：L=");//数据初始化gets(L.elem);for(j=1;L.elem[j-1]!='';j++)L.len=j;//获取表长L.lenL.elem[j]='';printf("操作：插入（I）还是删除(D)?");//判断进行插入还是删除操作AGAIN:cin>>ch;if(ch=='I'){cout<<"插在第几个元素之前:";//插入操作cin>>i;cout<<"输入要插入的新元素:";cin>>e;cout<

11、tInsert(L,%d,%c)",L.elem,i,e);state=ListInsert(L,i,e);}elseif(ch=='D'){cout<<"删除第几个元素：";//删除操作cin>>i;cout<

12、L.elem);//输出结果if(ch=='D'&&state!=-1)cout<<",e="<