实验一线性表应用类实验

《实验一线性表应用类实验》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、实验一线性表应用类实验一、问题定义及需求分析1.问题描述对线性表中的前M个元素和盾N个元素整体互换。2.实验耍求设汁元素整体互换的模拟程序。a.采用顺序表存储结构实现。b.采用链表存储结构实现。3.输入形式输入数字M,N。4.输入值的范围M和N都是由1至丨J表长maxlen-1(1)高效算法:M+N=50(2)低效算法:M+N<=505.输出形式互换过与互换前的线性表(含有元素位置以及元素数据)6.测试数据顺序表：(1)高效算法：M:45,N:5(2)低效算法：M:45,N:5二、概要设计1.抽象数据类型的定义：structList{

2、intdata[maxlen];intlistlen;Jseqlist;//顺序表2.主程序流程图:(1)高效算法:开始结火(2)低效算法：开始结束3.W数执行情况说明：(1)低效算法(Dintmain()载入顺序表，接受屏幕输入的M和N的值。并且调用change(&seqlist.data[O],seqlist.listlen,x,y)，输出换前换后的结果。(Dintchange(&seqlist.data[O],seqlist.listlen,x,y)运用~个辅助空间ptr,使前m个元素与后n个元素整体互换，ptr为数组头指针，l

3、ength为数组长度。含冇判断流程，使得不符合输入要求的数据M和N被排除。(2)高效算法(Dintmain()载入顺序表，接受屏幕输入的M和N的值，并且调用change(&seqlist.data[O],seqlist.listlen,x,y),输出换前换后的结果。②intListChange(int*ptr,intlength)给定头指针和序列长度，执行逆置功能③intchange(int*ptr,intlength,intm,intn)调用ListChange(int*ptr,intlength),先将前M个和后N个元素整体的进行

4、逆置处理，再分别对前M个和后N个元素进行逆置处理。三、详细设计(1)低效算法：intchange(int*ptr,intlength,intm,intn)//—个辅助空间使前m个元素与后n个元素幣体互换，ptr为数组头指针，length为数组长度{if(M+N>表长最大值)return-1;if(前后调换数据个数相M)//中间数据不用移动{只需耍把前后的元素一一对应地调换就可以}elseif(M比N大)//m〉n，

5、间数据整体前移{前后元素对皮调换屮间数据整体前移}}else//m

6、移intmain(){存入50个数据元素接受梆幕输入M和N的值判断M和N的值是否符合要求输入互换后的结果}(2)尚效算法：intListChange(int*ptr,intlength)//给定头指针和序列长度，逆置{执行对定K的顺序表的逆置功能}intchange(int*ptr,intlength,intm,intn){if(m+n!=50)return-1;n=50-m;对整个顺序表逆置对第一个数据到第m个数据进行逆置对于后n个数据进行逆置}intmain(){存入50个数据元素接受屏幕输入M和N的值判断M和N的值是否符合耍求输

7、入互换后的结果}四、调试分析1.在程序验收之前，使用顺序表储存结构实现屮我只做了用低效算法实现互换的程序，算法时间复杂度为O(n2)o在程序验收后，我重新添加Y用高效算法实现元素互换的程序，算法时间复杂度为O(n＞。五、使用说明：按照程序屮屏幕提示输入M和N的值并回车查看输出结果六、测试结果(1)低效算法将前x-换刖个数与后y个数交换位置(M+N<=50)，请分别输入^1和心M55换后[0]45[1]46[2][3][H][5]0[6]1[7]ro12OLJ[9][10]5[11]6[12]7[13]8[14]9[15]1O[16]1

8、1[17]12[18]13[19]14[20]15[21]16[22]17[23]18[24】19[25]20[26]21[27]22[28]23[29]2M[30]25[31]26[32]27[33]28[34]29[35]30[36]31[37]32[38]33[39]3磚[HO]35[m]36[M2]37[科3]38[叫4]39[H5]40[H6]41[47]42[43]43[科3](2)高效算法■G:数据结构数据结构实验theformerone-s个数与后从个数交换位置（M+N=50），请分别瑜入M和N:换前换后[o]5

9、[1]6[2]7[3]8[9[5]10[6]11[7]12[3]13[9]14[IO]15[11]16[12]17[13]18[1H]19[15]20[16]21[17]22[IS]23[13]2H[20]25[21]2