好像在神人劉汝佳的書中有提到「鍵結結構-例題-移動小球」寫過一次,有移前及移後,
這題只是移後,應較簡單,程式要找一下再後補,找到了:
輸入第1行2個數字 ,球數n、指令數m ,指令兩種 A x y及B x y,將x移至y之前及之後
以下為移動小球的程式碼,而 NPSC 2004 國中 E排排站只有將 x 移至 y之後,應直接改一下即可
// 提升程式設計的邏輯思考力 p6-7~6-9 例6.2.1 移動小球 解法 B 鏈式串列
// 指令 A x y 將x移至y之前, B x y 將x移至y之後
#include <iostream>
using namespace std;
const int MaxN = 500000 ; // 最多 50 萬 顆球
int lt[MaxN+1]; // 左 link
int rt[MaxN+1]; // 右 link
int n; // 小球 的數量
int main( )
{
int m; // 指令數 <= 100000
cin >> n >> m; // 輸入球數 、指令數
int i ,f=1,r=n;
lt[1]=-1; for(i=2; i<=n; ++i) lt[i]=i-1; // 左鍵
rt[n]=-1; for(i=n-1; i>=1; --i) rt[i]=i+1; // 右鍵
char c; // 指令
int x,y; //移動的球號、目標的球號
int a , b;
while( m-- )
{
cin >> c >> x >> y;
// 將 x 移出
a=lt[x] ; b=rt[x]; // x 的左a 及 右b
if(a<0) lt[b]=-1, f=b;
else if(b<0) rt[a]=-1 , r=a;
else lt[b]=a , rt[a]=b;
// 將 x 插入 y 之左 或 之右
if( c == 'A' ) { // 將 x 插入 y 之左
a=lt[y] ;
lt[x] = a; lt[y] = x;
rt[x] = y;
if(a==-1) f=x; else rt[a] = x;
} else { // 將 x 插入 y 之右
b=rt[y];
lt[x] = y;
if(b==-1) r=x; else lt[b] = x;
rt[x] = b; rt[y] = x;
}
}
cout << f;
while( rt[f]>0 )
{
f = rt[f];
cout << " " << f ;
}
cout << endl;
return 0;
}
/*
6 2
A 1 4
B 3 5
6 3
B 1 6
B 2 1
A 5 2
-----------
2 1 4 5 3 6
3 4 6 1 5 2
*/