順序表ADT模板設計及簡單應用：將順序表中前 m 個元素和後 n 個元素進行互換（資料結構OJ練習）（樣例4553 WA）

順序表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，首先要考慮到對於的索引的限制，給出的索引是否合理，越界或者的小於零
• 不要僅僅侷限於一種資料型別的，既然已經要求了多種資料型別的，那就試試看別的資料型別