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

实验一线性表应用类实验问题定义及需求分析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 data[maxlen];int listlen;} seqlist; //顺序表2.主程序流程图：（1）高效算法：（2）低效算法：3.函数执行情况说明：（1）低效算法①int main()载入顺序表，接受屏幕输入的M和N的值。并且调用change(seqlist.data[0], seqlist.listlen, x, y)，输出换前换后的结果。②int change(seqlist.data[0], seqlist.listlen, x, y)运用一个辅助空间ptr，使前m个元素与后n个元素整体互换，ptr为数组头指针，length为数组长度。含有判断流程，使得不符合输入要求的数据M和N被排除。（2）高效算法①int main()载入顺序表，接受屏幕输入的M和N的值，并且调用change(seqlist.data[0], 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个元素进行逆置处理。详细设计低效算法：int change(int* ptr, int length, int m, int n) //一个辅助空间使前m个元素与后n个元素整体互换，ptr为数组头指针，length为数组长度{ if(M+N表长最大值) return -1; if(前后调换数据个数相同) //中间数据不用移动 {只需要把前后的元素一一对应地调换就可以 } else if(M比N大) //mn，中间数据整体前移 {前后元素对应调换中间数据整体前移 } } else //mn，中间数据整体后移 {前后元素对应调换中间数据整体后移}int main(){存入50个数据元素接受屏幕输入M和N的值判断M和N的值是否符合要求输入互换后的结果}高效算法：int 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)。在程序验收后，我重新添加了用高效算法实现元素互换的程序，算法时间复杂度为O(n)。使用说明：按照程序中屏幕提示输入M和N的值并回车查看输出结果测试结果低效算法高效算法附录(a)高效算法#include stdio.h#include iostream#include iomanip //格式输出, setw()using namespace std;#define maxlen 50struct List{ int data[maxlen]; int listlen;} seqlist; //顺序表int ListChange(int* 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