本文共 1287 字，大约阅读时间需要 4 分钟。

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

问题描述

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

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

参考函数原型：template

输入说明

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

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

第三行：逆置位置m

输出说明

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

第二行：逆置结果

输入范例

1013 5 27 9 32 123 76 98 54 875

输出范例

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

思路分析

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

伪代码

void realExchange(vector
   
     &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
    
     void Exchange(vector
     
      & 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，首先要考虑到对于的索引的限制，给出的索引是否合理，越界或者的小于零
• 不要仅仅局限于一种数据类型的，既然已经要求了多种数据类型的，那就试试看别的数据类型

转载地址：http://jwwvb.baihongyu.com/