列印

請 登入 或 註冊帳號.
一小時 一天 一週 一個月 永遠
請輸入帳號, 密碼以及預計登入時間

[rscpp]

好像在神人劉汝佳的書中有提到「鍵結結構-例題-移動小球」寫過一次，有移前及移後，
這題只是移後，應較簡單，程式要找一下再後補，找到了：
輸入第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
*/