实验一线性表应用类实验

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.抽象数据类型的定义：struct List int datamaxlen; int lis

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

3、 main()载入顺序表，接受屏幕输入的M和N的值，并且调用change(&seqlist.data0, seqlist.listlen, x, y)，输出换前换后的结果。int ListChange(int* ptr, int length)给定头指针和序列长度，执行逆置功能int change(int* ptr, int length, int m, int n)调用ListChange(int* ptr, int length)，先将前M个和后N个元素整体的进行逆置处理，再分别对前M个和后N个元素进行逆置处理。三、 详细设计 （1） 低效算法：int change(int* pt

4、r, int length, int m, int n) /一个辅助空间使前m个元素与后n个元素整体互换，ptr为数组头指针，length为数组长度 if(M+N>表长最大值) return -1; if(前后调换数据个数相同) /中间数据不用移动 只需要把前后的元素一一对应地调换就可以 else if(M比N大) /m>n，中间数据整体前移 前后元素对应调换 中间数据整体前移 else /m<n，中间数据整体后移 前后元素对应调换中间数据整体后移 int main()存入50个数据元素接受屏幕输入M和N的值判断M和N的值是否符合要求输入互换后的结果（2） 高效算法：int

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

6、我重新添加了用高效算法实现元素互换的程序，算法时间复杂度为O(n)。五、 使用说明：按照程序中屏幕提示输入M和N的值并回车查看输出结果六、 测试结果（1） 低效算法（2） 高效算法七、 附录(a)高效算法#include <stdio.h>#include <iostream>#include <iomanip> /格式输出, setw()using namespace std;#define maxlen 50struct List int datamaxlen; int listlen; seqlist; /顺序表int ListChange(int*

7、ptr, int length) /给定头指针和序列长度，逆置 int *p, *q, temp; for(p = ptr, q = ptr + length; p < q; p+,q-) temp = *p; *p = *q; *q = temp; return 0;int change(int* ptr, int length, int m, int n) if(m + n !=50) return -1; n = 50 - m; ListChange(&seqlist.data0, 50); ListChange(&seqlist.data0, m); ListCh

8、ange(ptr+m, 50-m); return 1;int main() int i,x,y; seqlist.listlen = 0; for(i=0; i<maxlen; i+) /存入50个数据元素 seqlist.datai = i; seqlist.listlen+; cout<<"将前M个数与后N个数交换位置(M+N=50)，请分别输入M和N: " cin>>x>>y; if(-1 = change(&seqlist.data0, seqlist.listlen, x, y) cout << &q

9、uot;Error! " << endl; /如果m+n>顺序表实际长度，则认为出错 cout<<"换前 换后"<<endl; for(i=0; i<maxlen; i+) cout << "" << setw(2) << i << " : " << seqlist.datai << endl; /设置域宽 return 0;（3） 低效算法#include <stdio.h>#include

10、<iostream>#include <iomanip> /格式输出, setw()using namespace std;#define maxlen 50struct List int datamaxlen; int listlen;seqlist; /顺序表int change(int* ptr, int length, int m, int n) /一个辅助空间使前m个元素与后n个元素整体互换，ptr为数组头指针，length为数组长度 int i,j; int temp; /一个辅助空间 int* mark; if(m+n>length) return

11、-1; if(m = n) /前后调换个数相同，中间数据不用移动 for(i=0; i<m; i+) temp = *ptr; *ptr = *(ptr + length - n); *(ptr + length - n) = temp; ptr+; else if(m > n) /m>n，中间数据整体前移 for(i=0; i<n; i+) temp = *ptr; *ptr = *(ptr + length - n); *(ptr + length - n) = temp; ptr+; mark = ptr; for(j=0; j<m-n; j+) temp

12、= *ptr; for(i=n; i<length-1; i+) *ptr = *(ptr + 1); ptr+; *ptr = temp; ptr = mark; else /m<n，中间数据整体后移 for(i=0; i<m; i+) temp = *ptr; *ptr = *(ptr + length - n); *(ptr + length - n) = temp; ptr+; mark = ptr + length - n; for(j=0; j<n-m; j+) ptr = mark; temp = *ptr; for(i=length-n+m; i>

13、m; i-) *ptr = *(ptr - 1); ptr-; *ptr = temp; mark+; return 0;int main() int i,x,y; seqlist.listlen = 0; for(i=0; i<maxlen; i+) /存入50个数据元素 seqlist.datai = i; seqlist.listlen+; cout<<"将前x个数与后y个数交换位置(M+N<=50)，请分别输入M和N: " cin>>x>>y; if(-1 = change(&seqlist.data0, seqlist.listlen, x, y) cout << "Error! " << endl; /如果m+n>顺序表实际长度，则认为出错