順序表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，首先要考慮到對于的索引的限制，給出的索引是否合理，越界或者的小于零
- 不要僅僅局限于一種資料型別的，既然已經要求了多種資料型別的，那就試試看別的資料型別
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/172859.html
標籤：其他
上一篇：Vi編輯器 終端編輯器命令