剣指OFFERの複雑なチェーンテーブルの複製(九度OJ 1524)
2932 ワード
タイトルの説明:
複雑なチェーンテーブル(各ノードにノード値と2つのポインタがあり、1つは次のノードを指し、もう1つの特殊なポインタはいずれかのノードを指します)を入力します.
入力:
入力には複数のテストサンプルが含まれ、入力はEOFで終了します.各テストケースについて、入力される第1の動作の整数n(1<=n<=1000):nは、入力するチェーンテーブル要素の個数を表す.(ノード番号は1から).チェーンテーブルノードの値を表すn個の数が続く.次にn個の数Tiがあり,Tiはi番目のノードの別のポインタ指向を表す.Ti=0はこのポインタがNULLであることを示す.
出力:
各テストケースに対応して、n行を出力し、各行に2つの数があり、1つ目は現在のノード値、2つ目は現在のノードの特殊なポインタの値を表す.
サンプル入力:
5
1 2 3 4 5
3 5 0 2 0
サンプル出力:
1 3
2 5
3 0
4 2
5 0
問題解決の考え方:
ええ、また投機的に...
原題の意味では、この複雑なチェーンテーブルが与えられているはずです.それから、ノードごとにノードをコピーし、ランダムなポインタをコピーし、ランダムなポインタを移動し、最後にチェーンテーブルをジャンプして接続すればいいです.
コード:
#include <stdio.h>
#include <stdlib.h>
typedef struct list{
int num;
int random_link;
}List;
typedef struct listarr{
List arr[1000];
}ListArr;
int main(){
int n,i;
while(scanf("%d",&n)!=EOF && n>=1 && n<=1000){
ListArr *a = (ListArr *)malloc(sizeof(ListArr));
a->arr[0].num=0;
a->arr[0].random_link=0;
for(i=1;i<=n;i++)
scanf("%d",&a->arr[i].num);
for(i=1;i<=n;i++)
scanf("%d",&a->arr[i].random_link);
for(i=1;i<=n;i++)
printf("%d %d
", a->arr[i].num,a->arr[(a->arr[i].random_link)].num);
}
return 0;
}
/**************************************************************
Problem: 1524
User: xhalo
Language: C
Result: Accepted
Time:40 ms
Memory:912 kb
****************************************************************/