实验一线性表应用类实验教程.docxVIP

实验一 线性表应用类实验 问题定义及需求分析 1.问题描述 对线性表中的前M个元素和后N个元素整体互换。 2.实验要求 设计元素整体互换的模拟程序。 a.采用顺序表存储结构实现。 b.采用链表存储结构实现。 3.输入形式 输入数字M，N。 4.输入值的范围 M和N都是由1到表长maxlen-1 （1）高效算法：M+N=50 （2）低效算法：M+N=50 5.输出形式 互换过与互换前的线性表（含有元素位置以及元素数据） 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 50 struct List { int data[maxlen]; int listlen; } seqlist; //顺序表 int ListChange(in