实验一线性表应用类实验
一、 问题定义及需求分析
1. 问题描述
对线性表中的前M 个元素和后N 个元素整体互换。
2. 实验要求
设计元素整体互换的模拟程序。
a. 采用顺序表存储结构实现。
b. 采用链表存储结构实现。
3. 输入形式
输入数字M ，N 。
4. 输入值的范围
M 和N 都是由1到表长maxlen-1
（1）高效算法：M+N=50
（2）低效算法：M+N
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 个元素进行逆置处理。
三、详细设计
（1） 低效算法：
int change(int* ptr, int length, int m, int n) //一个辅助空间使
前m 个元素与后n 个元素整体互换，ptr 为数组头指针，length
为数组长度
{
if(M+N>表长最大值)
return -1;
if(前后调换数据个数相同) //中间数据不用移动
{
只需要把前后的元素一一对应地调换就可以
}
else if(M比N 大) //m>n，中间数据整体前移
{
前后元素对应调换
中间数据整体前移
}
}
else //m
{
前后元素对应调换
中间数据整体后移
}
int main()
{
存入50个数据元素
接受屏幕输入M 和N 的值
判断M 和N 的值是否符合要求
输入互换后的结果
}
（2） 高效算法：
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 的值并回车查看输出结果
六、 测试结果
（1） 低效算法
（2） 高效算法
七、 附录
(a)高效算法
#include
#include
#include //格式输出, setw()
using namespace std;
#define maxlen 50
struct List
{
int data[maxlen];
int listlen;
} seqlist; //顺序表
int ListChange(int* ptr, int length) //给定头指针和序列长度，逆置
{
int *p, *q, temp;
for(p = ptr, q = ptr + length; p
{
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.data[0], 50);
ListChange(&seqlist.data[0], m);
ListChange(ptr+m, 50-m);
return 1;
}
int main()
{
int i,x,y;
seqlist.listlen = 0;
for(i=0; i
{
seqlist.data[i] = i;
seqlist.listlen++;
}
cout
入M 和N: ";
cin>>x>>y;
if(-1 == change(&seqlist.data[0], seqlist.listlen, x, y))
cout 顺序表实际长度，则认为出错
cout
for(i=0; i
cout
//设置域宽
return 0;
}
（3） 低效算法
#include
#include
#include //格式输出, setw()
using namespace std;
#define maxlen 50
struct List
{
int data[maxlen];
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 -1;
if(m == n) //前后调换个数相同，中间数据不用移动
{
for(i=0; i
{
temp = *ptr;
*ptr = *(ptr + length - n);
*(ptr + length - n) = temp;
ptr++;
}
}
else if(m > n) //m>n，中间数据整体前移
{
for(i=0; i
{
temp = *ptr;
*ptr = *(ptr + length - n);
*(ptr + length - n) = temp;
ptr++;
}
mark = ptr;
for(j=0; j
{
temp = *ptr;
for(i=n; i
{
*ptr = *(ptr + 1);
ptr++;
}
*ptr = temp;
ptr = mark;
}
}
else //m
{
for(i=0; i
{
temp = *ptr;
*ptr = *(ptr + length - n);
*(ptr + length - n) = temp;
ptr++;
}
mark = ptr + length - n;
for(j=0; j
{
ptr = mark;
temp = *ptr;
for(i=length-n+m; i>m; i--)
{
*ptr = *(ptr - 1);
ptr--;
}
*ptr = temp;
mark++;
}
}
return 0;
}
int main()
{
int i,x,y;
seqlist.listlen = 0;
for(i=0; i
{
seqlist.data[i] = i;
seqlist.listlen++;
}
cout
cin>>x>>y;
if(-1 == change(&seqlist.data[0], seqlist.listlen, x, y))
cout 顺序表实际长度，则认为出错，函数返回-1
cout
for(i=0; i
cout
return 0;
} //
实验一线性表应用类实验
一、 问题定义及需求分析
1. 问题描述
对线性表中的前M 个元素和后N 个元素整体互换。
2. 实验要求
设计元素整体互换的模拟程序。
a. 采用顺序表存储结构实现。
b. 采用链表存储结构实现。
3. 输入形式
输入数字M ，N 。
4. 输入值的范围
M 和N 都是由1到表长maxlen-1
（1）高效算法：M+N=50
（2）低效算法：M+N
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 个元素进行逆置处理。
三、详细设计
（1） 低效算法：
int change(int* ptr, int length, int m, int n) //一个辅助空间使
前m 个元素与后n 个元素整体互换，ptr 为数组头指针，length
为数组长度
{
if(M+N>表长最大值)
return -1;
if(前后调换数据个数相同) //中间数据不用移动
{
只需要把前后的元素一一对应地调换就可以
}
else if(M比N 大) //m>n，中间数据整体前移
{
前后元素对应调换
中间数据整体前移
}
}
else //m
{
前后元素对应调换
中间数据整体后移
}
int main()
{
存入50个数据元素
接受屏幕输入M 和N 的值
判断M 和N 的值是否符合要求
输入互换后的结果
}
（2） 高效算法：
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 的值并回车查看输出结果
六、 测试结果
（1） 低效算法
（2） 高效算法
七、 附录
(a)高效算法
#include
#include
#include //格式输出, setw()
using namespace std;
#define maxlen 50
struct List
{
int data[maxlen];
int listlen;
} seqlist; //顺序表
int ListChange(int* ptr, int length) //给定头指针和序列长度，逆置
{
int *p, *q, temp;
for(p = ptr, q = ptr + length; p
{
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.data[0], 50);
ListChange(&seqlist.data[0], m);
ListChange(ptr+m, 50-m);
return 1;
}
int main()
{
int i,x,y;
seqlist.listlen = 0;
for(i=0; i
{
seqlist.data[i] = i;
seqlist.listlen++;
}
cout
入M 和N: ";
cin>>x>>y;
if(-1 == change(&seqlist.data[0], seqlist.listlen, x, y))
cout 顺序表实际长度，则认为出错
cout
for(i=0; i
cout
//设置域宽
return 0;
}
（3） 低效算法
#include
#include
#include //格式输出, setw()
using namespace std;
#define maxlen 50
struct List
{
int data[maxlen];
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 -1;
if(m == n) //前后调换个数相同，中间数据不用移动
{
for(i=0; i
{
temp = *ptr;
*ptr = *(ptr + length - n);
*(ptr + length - n) = temp;
ptr++;
}
}
else if(m > n) //m>n，中间数据整体前移
{
for(i=0; i
{
temp = *ptr;
*ptr = *(ptr + length - n);
*(ptr + length - n) = temp;
ptr++;
}
mark = ptr;
for(j=0; j
{
temp = *ptr;
for(i=n; i
{
*ptr = *(ptr + 1);
ptr++;
}
*ptr = temp;
ptr = mark;
}
}
else //m
{
for(i=0; i
{
temp = *ptr;
*ptr = *(ptr + length - n);
*(ptr + length - n) = temp;
ptr++;
}
mark = ptr + length - n;
for(j=0; j
{
ptr = mark;
temp = *ptr;
for(i=length-n+m; i>m; i--)
{
*ptr = *(ptr - 1);
ptr--;
}
*ptr = temp;
mark++;
}
}
return 0;
}
int main()
{
int i,x,y;
seqlist.listlen = 0;
for(i=0; i
{
seqlist.data[i] = i;
seqlist.listlen++;
}
cout
cin>>x>>y;
if(-1 == change(&seqlist.data[0], seqlist.listlen, x, y))
cout 顺序表实际长度，则认为出错，函数返回-1
cout
for(i=0; i
cout
return 0;
} //