顺序表ADT模板设计及简单应用：将顺序表中前 m 个元素和后 n 个元素进行互换

问题描述

目的：使用STL中的vector模板，设计并实现顺序表应用场合的一些简单算法设计。

应用1：试设计一个算法，用尽可能少的辅助空间将顺序表中前 m 个元素和后 n 个元素进行互换，即将线性表(a1,a2,…,am,b1,b2,…,bn) 改变成(b1,b2,…,bn,a1,a2,…,am)。

参考函数原型：template
void Exchange( vector &A,int m )；// 本算法实现顺序表中前 m 个元素和后 n 个元素的互换

输入说明

第一行：待处理顺序表的长度

第二行：待处理顺序表的数据元素（数据元素之间以空格分隔）

第三行：逆置位置m

输出说明

第一行：待处理顺序表的遍历结果

第二行：逆置结果

输入范例

10
13 5 27 9 32 123 76 98 54 87
5

输出范例

13 5 27 9 32 123 76 98 54 87 

123 76 98 54 87 13 5 27 9 32 

思路分析

• 尽可能少的辅助空间，就以为者要用最少的空间复杂度去实现，不能创建大量的元素
• 最简单的方法就是设置一个元素，进行交换。
• 一个次反转，为原序的逆序，然后再反转，就是原序

伪代码

void realExchange(vector<Elemtype> &A,int left,int right)
{ 
	//swap reverse the element between left and right
	Elemtype temp;
	while(left <= eight)
	{ 
		temp = A[left];
		A[left] = A[right];
		A[left] = temp;
		left ++;
		right --;
	}
}

template<class Elemtype>
void Exchange(vector<Elemtype>& A,int m)
{ 
    //reverse the whole vector
    realExchange(A,0,A.size());
    //reverse the element between 0 and m
    realExchange(A,0,m);
    //reverse the elements between m and A.size()
    realExchange(A,m,A.size());
}

错误出现

• 错误用例（花了一分，心疼啊）
  
• 分析：显而易见的，没有料想到不同的数据类型，只是在整型中不断尝试，没有发现问题
• 修改：将int修改成string，然后就通过了。这里如果是数字也是可以看成字符型的输入的，但是如果声明为的整型，就完全识别不了字符串型。
  

分析与总结

• 对于vector，首先要考虑到对于的索引的限制，给出的索引是否合理，越界或者的小于零
• 不要仅仅局限于一种数据类型的，既然已经要求了多种数据类型的，那就试试看别的数据类型