一維數(shù)組A[m+n]固棚，前m項(xiàng)和后n項(xiàng)分別為線性表（a1,a2,...,am）和（b1,b2,...,bn），現(xiàn)要求將其交換位置哥倔，變?yōu)椋╞1,b2,...,bn,a1,a2,...,am）。
本人代碼片段如下：
void ExchangeAB(SeqList &L, int m, int n){
if (m < 1 || n < 1) {
return;
}
int p = m, q = n, t; //p為每次交換的左邊數(shù)列元素?cái)?shù)，q為每次交換的右邊數(shù)列元素?cái)?shù)番甩；
int left = 0, right = m + n - 1; //每次交換的左邊界和右邊界
while (q > 0 && p > 0 && left < right) { //當(dāng)數(shù)列未交換完畢
if (p > q) { //若左邊比右邊長(zhǎng)
for (int i = left; i < left + q; i++) {
t = L.data[i];
L.data[i] = L.data[i + p];
L.data[i + p] = t;
}
left += q; //修改左邊界
p -= q; //修改左邊數(shù)列長(zhǎng)度
} else { //若左邊比右邊短
for (int i = left; i < left + p; i++) {
t = L.data[i];
L.data[i] = L.data[i + q];
L.data[i + q] = t;
}
right -= p; //修改右邊界
q -= p; //修改右邊數(shù)列長(zhǎng)度
}
}
}
該算法時(shí)間復(fù)雜度僅有O(n)，利用分治法思想完成届搁，僅需遍歷一遍數(shù)列即可缘薛。
完整可運(yùn)行代碼如下：
#include <iostream>
#define MaxSize 50
using namespace std;
typedef struct {
int data[MaxSize];
int length;
}SeqList;
void OutputList(SeqList &L){
for (int i = 0; i < L.length; i++) {
cout << L.data[i];
}
}
void CreateList(SeqList &L){
int l;
cout << "Please enter the length:";
cin >> l;
L.length = l;
for (int i = 0;i<L.length;i++) {
cout << "Please enter the num" << i << ":";
cin >> L.data[i];
}
}
void ExchangeAB(SeqList &L, int m, int n){
if (m < 1 || n < 1) {
return;
}
int p = m, q = n, t, left = 0, right = m + n - 1;
while (q > 0 && p > 0 && left < right) {
if (p > q) {
for (int i = left; i < left + q; i++) {
t = L.data[i];
L.data[i] = L.data[i + p];
L.data[i + p] = t;
}
left += q;
p -= q;
} else {
for (int i = left; i < left + p; i++) {
t = L.data[i];
L.data[i] = L.data[i + q];
L.data[i + q] = t;
}
right -= p;
q -= p;
}
}
}
int main(int argc, char *argv[]) {
SeqList L;
CreateList(L);
ExchangeAB(L, 3, 9); //自已設(shè)定m與n的值
OutputList(L);
}