实验一线性表应用类实验.docx

《实验一线性表应用类实验.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、ntlistlen;}seqlist;//顺序表2.主程序流程图：（1）高效算法：（2）低效算法：3.函数执行情况说明：（1）低效算法①intmain()载入顺序表，接受屏幕输入的M和N的值。并且调用change(&seqlist.data[0],seqlist.listlen,x,y)，输出换前换后的结果。②intchange(&seqlist.data[0],seqlist.listlen,x,y)运用一个辅助空间ptr，使前m个元素与后n个元素整体互换，ptr为数组头指针，length为数组长度。含有判断流程，使得不符合输入要求的数据M和N被排除。（2）高效

3、算法①intmain()载入顺序表，接受屏幕输入的M和N的值，并且调用change(&seqlist.data[0],seqlist.listlen,x,y)，输出换前换后的结果。②intListChange(int*ptr,intlength)给定头指针和序列长度，执行逆置功能③intchange(int*ptr,intlength,intm,intn)调用ListChange(int*ptr,intlength)，先将前M个和后N个元素整体的进行逆置处理，再分别对前M个和后N个元素进行逆置处理。一、详细设计（1）低效算法：intchange(int*ptr,i

4、ntlength,intm,intn)//一个辅助空间使前m个元素与后n个元素整体互换，ptr为数组头指针，length为数组长度{if(M+N>表长最大值)return-1;if(前后调换数据个数相同)//中间数据不用移动{只需要把前后的元素一一对应地调换就可以}elseif(M比N大)//m>n，中间数据整体前移{前后元素对应调换中间数据整体前移}}else//m

5、ge(int*ptr,intlength)//给定头指针和序列长度，逆置{执行对定长的顺序表的逆置功能}intchange(int*ptr,intlength,intm,intn){if(m+n!=50)return-1;n=50-m;对整个顺序表逆置对第一个数据到第m个数据进行逆置对于后n个数据进行逆置}intmain(){存入50个数据元素接受屏幕输入M和N的值判断M和N的值是否符合要求输入互换后的结果}一、调试分析1.在程序验收之前，使用顺序表储存结构实现中我只做了用低效算法实现互换的程序，算法时间复杂度为O(n2)。在程序验收后，我重新添加了用高效算法实现

6、元素互换的程序，算法时间复杂度为O(n)。二、使用说明：按照程序中屏幕提示输入M和N的值并回车查看输出结果三、测试结果（1）低效算法（1）高效算法一、附录(a)高效算法#include#include#include//格式输出,setw()usingnamespacestd;#definemaxlen50structList{intdata[maxlen];intlistlen;}seqlist;//顺序表intListChange(int*ptr,intlength)//给定头指针和序列长度，逆置{int

7、*p,*q,temp;for(p=ptr,q=ptr+length;p

8、i