数据结构实验(1)线性表及其应用.pdf

文档介绍：该【数据结构实验(1)线性表及其应用 】是由【青山代下】上传分享，文档一共【11】页，该文档可以免费在线阅读，需要了解更多关于【数据结构实验(1)线性表及其应用 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:..计算机系数据结构实验报告(1)实验目的:帮助学生掌握线性表的基本操作在顺序和链表这两种存储结构上的实现,尤以链表的操作和应用作为重点。问题描述:1、构造一个空的线性表L。2、在线性表L的第i个元素之前插入新的元素e;3、在线性表L中删除第i个元素,并用e返回其值。实验要求:1、分别利用顺序和链表存储结构实现线性表的存储,并设计出在不同的存储结构中线性表的基本操作算法。2、在实验过程中,对相同的操作在不同的存储结构下的时间复杂度和空间复杂度进行分析。算法分析:由于两种存储结构都用来创建线性结构的数据表,可采用相同的输出模式和整体结构类似的算法,如下:-1-:..:顺序存储结构线性表程序清单://顺序存储结构线性表的插入删除#include<iostream>#include<>usingnamespacestd;#defineLISTSIZE100#defineCREMENTSIZE10typedefcharElemType;//定义数据元素类型为字符型typedefstruct{ElemType*elem;//数据元素首地址intlen;//当前元素个数intlistsize;//当前存储最大容量}SqList;//构造一个空的线性表L-2-:..intInitList(SqList&L){=(ElemType*)malloc(LISTSIZE*sizeof(ElemType));if(!exit(-2);//分配空间失败=0;=LISTSIZE;}//在顺序线性表L中第i个位置之前插入新的元素eintListInsert(SqList&L,inti,ElemTypee){if(i<1||i>+1)return-1;//i值不合法if>={ElemType*newelem=(ElemType*)realloc,+CREMENTSIZE)*sizeof(ElemType));//存储空间已满,增加分配if(!newelem)exit(-2);//分配失败=newelem;+=CREMENTSIZE;}ElemType*q=&[i-1]);for(ElemType*p=&[]);p>=q;--p)*(p+1)=*p;//插入位置及其后的元素后移*q=e;++;return1;}//在顺序线性表L中删除第i个元素,并用e返回其值intListDelete(SqList&L,inti,ElemType&e){if(i<1||i>return-1;//i值不合法ElemType*p=&[i-1]);e=*p;ElemType*q=+;for(++p;p<=q+1;++p)*(p-1)=*p;//被删除元素之后的元素前移;return1;-3-:..}intmain(){SqListL;chare,ch;inti,j,state;InitList(L);//构造线性表请输入原始数据(字符串个数0~99):://数据初始化gets;获取表长操作:插入(I)还是删除判断进行插入还是删除操作AGAIN:cin>>ch;if(ch=='I'){插在第几个元素之前插入操作输入要插入的新元素cin>>e;cout<<endl;输入数据:L=(%s)state=ListInsert(L,i,e);}elseif(ch=='D'){删除第几个元素:删除操作cin>>i;cout<<endl;输入数据:L=(%s)state=ListDelete(L,i,e);}elsegotoAGAIN;//操作指示符输入错误处理正确结果:输出结果-4-:..}链式存储结构线性表程序清单://-----单链存储结构线性表的插入删除-----#include<iostream>#include<>usingnamespacestd;#definenull0typedefcharElemType;//定义数据元素类型为字符型typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;intGetElem(LinkListL,inti,ElemType&e)//获取第i个元素的值{LinkListp;intj;p=L->next;j=1;while(p&&j<i){p=p->next;++j;//寻找第i个元素}if(!p||j>i)return-1;//寻找失败e=p->data;return1;}intListInsert(LinkList&L,inti,ElemTypee){//在带头结点的单链线性表L中第i个元素之前插入元素eLinkListp,s;intj;p=L;j=0;-5-:..while(p&&j<i-1){p=p->next;++j;}if(!p||j>i-1)return-1;s=(LinkList)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;return1;}intListDelete(LinkList&L,inti,ElemType&e){//在带头结点的单链线性表L中,删除第i个元素,并由e返回其值LinkListp,q;intj;p=L;j=0;while(p->next&&j<i-1){p=p->next;++j;}if(!(p->next)||j>i-1)return-1;q=p->next;p->next=q->next;e=q->data;free(q);return1;}intnewdata(LinkList&L,char*ch){intk;请输入原始数据(字符串个数0~99)::数据初始化gets(ch);ListInsert(L,k+1,ch[k]);//将初始化数据插入链表L中returnk;//返回链表中的元素个数}-6-:..intmain(){char*ch;ch=(char*)malloc(100*sizeof(char));//定义数组用来辅助数据初始化LinkListL;//头指针LNodehead;//头结点L=&head;=null;inti,k,state;chare,CH,f;k=newdata(L,ch);//调用函数使链表数据初始化=k;//将元素个数存入头结点的数据域操作:插入(I)还是删除判断进行插入还是删除操作AGAIN:cin>>CH;if(CH=='I'){插在第几个元素之前插入操作输入要插入的新元素cin>>e;cout<<endl;输入数据:L=(%s)state=ListInsert(L,i,e);++;}elseif(CH=='D'){删除第几个元素:删除操作cin>>i;cout<<endl;输入数据:L=(%s)state=ListDelete(L,i,e);--;}elsegotoAGAIN;//操作指示符输入错误处理正确结果:-7-:..(intm=1;>=m;m++)//一一输出数据{GetElem(L,m,f);cout<<f;}删除操作反馈e}实验结果:由于两个程序的输出模式相同,在此只列一组测试数据:L=()ListInsert(L,1,'k')L=(EHIKMOP)ListInsert(L,9,'t')-8-:..=(ABCEHKNPQTU)ListInsert(L,4,'u')L=()ListDelete(L,1,e)L=(DEFILMNORU)ListDelete_Sq(L,5,e)L=(CD)ListDelete_Sq(L,1,e)-9-:..可编辑可修改cout和cin函数来不断改进。另外,在用户端看来在设计算法时程序的可重复性未考虑,显得不够人性化。时间复杂度分析:假定线性表有n个节点,顺序存储结构下,插入程序段以*(p+1)=*p作为基本操作的原操作,并讨论在最坏情况下的时间复杂度,记T(n)=O(n);删除程序段以*(p-1)=*(p)作为基本操作的原操作,并讨论在最坏情况下的时间复杂度,记T’(n)=O(n)。链式存储结构下,插入程序段以p=p->next作为基本操作的原操作,并讨论在最坏情况下的时间复杂度,记T(n)=O(n);删除程序段以p=p->next作为基本操作的原操作,并讨论在最坏情况下的时间复杂度,记T’(n)=O(n)。总结和感想:改进设想在于减少中间变量,优化数据初始化操作,和增加程序可重复性。具体操作完成估计就该把上述程序全面修改了,还包括算法的修改和增进。从完成该实验的过程中,出现的问题很多,一方面由于对C语言的不够熟悉,在语法和语句执行效率上总是不尽人意,另一方面由于在设计算法时考虑不全面,在后来写入程序时屡屡修改,使程序设计效率大大降低。基于上述两点,今后需全面复****C语言以效后计,并做好在设计算法方面的工作。思考题:实现链表的逆置算法:以上述链式存储结构线性表程序做基础,可省略数据初始化和输入输出等操作,此处只列出实现逆置的用户函数Inversion(),主程序调用该函数并输出即可。intInversion(LNodehead)//形参为链表的头结点-10-:..LinkListp,q,r;p=;q=r=0;//p中存放第一个节点的地址while(p){q=p->next;//q作为中间变量p->next=r;//逆序替换元素的地址域r=p;p=q;//将q值返还给p}return1;}-11-