实验一线性表应用类实验

实验一线性表应用类实验一、问题定义及需求分析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];intlistlen;}seqlist;//顺序表2.主程序流程图：（1）高效算法：开始存入50个数据元素输入M和N的值M+N=50屏幕输出Error否是输出互换前后的数据信息结束（2）低效算法：开始存入50个数据元素输入M和N的值M+N=50屏幕输出Error否是输出互换前后的数据信息结束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）高效算法①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,intlength,intm,intn)//一个辅助空间使前m个元素与后n个元素整体互换，ptr为数组头指针，length为数组长度{if(M+N表长最大值)return-1;if(前后调换数据个数相同)//中间数据不用移动{只需要把前后的元素一一对应地调换就可以}elseif(M比N大)//mn，中间数据整体前移{前后元素对应调换中间数据整体前移}}else//mn，中间数据整体后移{前后元素对应调换中间数据整体后移}intmain(){存入50个数据元素接受屏幕输入M和N的值判断M和N的值是否符合要求输入互换后的结果}（2）高效算法：intListChange(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)。在程序验收后，我重新添加了用高效算法实现元素互换的程序，算法时间复杂度为O(n)。五、使用说明：按照程序中屏幕提示输入M和N的值并回车查看输出结果六、测试结果（1）低效算法（2）高效算法七、附录(a)高效算法#includestdio.h#includeiostream#includeiomanip//格式输出,setw()usingnamespacestd;#definemaxlen50structList{intdata[maxlen];intlistlen;}seqlist;//顺序表intListChange(int*ptr,intlength)//给定头指针和序列长度，逆置{int*p,*q,temp;for(p=ptr,q=ptr+length;pq;p++,q--){temp=*p;*p=*q;*q=temp;}return0;}intchange(int*ptr,intlength,intm,intn){if(m+n!=50)return-1;n=50-m;ListChange(&seqlist.data[0],50);ListChange(&seqlist.data[0],m);ListChange(ptr+m,50-m);return1;}intmain(){inti,x,y;seqlist.listlen=0;for(i=0;imaxlen;i++)//存入50个数据元素{seqlist.data[i]=i;seqlist.listlen++;}cout将前M个数与后N个数交换位置(M+N=50)，请分别输入M和N:;cinxy;if(-1==change(&seqlist.data[0],seqlist.listlen,x,y))coutError!endl;//如果m+n顺序表实际长度，则认为出错cout换前换后endl;for(i=0;imaxlen;i++)cout[setw(2)i]:seqlist.data[i]endl;//设置域宽return0;}（3）低效算法#includestdio.h#includeiostream#includeiomanip//格式输出,setw()usingnamespacestd;#definemaxlen50structList{intdata[maxlen];intlistlen;}seqlist;//顺序表intchange(int*ptr,intlength,intm,intn)//一个辅助空间使前m个元素与后n个元素整体互换，ptr为数组头指针，length为数组长度{inti,j;inttemp;//一个辅助空间int*mark;if(m+nlength)return-1;if(m==n)//前后调换个数相同，中间数据不用移动{for(i=0;im;i++){temp=*ptr;*ptr=*(ptr+length-n);*(ptr+length-n)=temp;ptr++;}}elseif(mn)//mn，中间数据整体前移{for(i=0;in;i++){temp=*ptr;*ptr=*(ptr+length-n);*(ptr+length-n)=temp;ptr++;}mark=ptr;for(j=0;jm-n;j++){temp=*ptr;for(i=n;ilength-1;i++){*ptr=*(ptr+1);ptr++;}*ptr=temp;ptr=mark;}}else//mn，中间数据整体后移{for(i=0;im;i++){temp=*ptr;*ptr=*(ptr+length-n);*(ptr+length-n)=temp;ptr++;}mark=ptr+length-n;for(j=0;jn-m;j++){ptr=mark;temp=*ptr;for(i=length-n+m;im;i--){*ptr=*(ptr-1);ptr--;}*ptr=temp;mark++;}}return0;}intmain(){inti,x,y;seqlist.listlen=0;for(i=0;imaxlen;i++)//存入50个数据元素{seqlist.data[i]=i;seqlist.listlen++;}cout将前x个数与后y个数交换位置(M+N=50)，请分别输入M和N:;cinxy;if(-1==change(&seqlist.data[0],seqlist.listlen,x,y))coutError!endl;//如果m+n顺序表实际长度，则认为出错，函数返回-1cout换前换后endl;for(i=0;imaxlen;i++)cout[setw(2)i]:seqlist.data[i]endl;//设置域宽return0;}