【剣指Offer面接問題】九度OJ 1524:複雑なチェーンテーブルのコピー

タイトルリンクアドレス:http://ac.jobdu.com/problem.php?pid=1524
タイトル1524:複雑なチェーンテーブルのコピー
時間制限:1秒メモリ制限:128メガ特殊判定:Noコミット:751解決:359問題説明:複雑なチェーンテーブルを入力します(各ノードにノード値があり、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 5 0 2 0サンプル出力:1 3 2 5 3 4 5 0
構想分析:
ACという問題には、いろいろな方法があります.直接チェーンテーブルノードポインタ配列が実現され、pSiblingポインタがあるノードSを指すと、チェーンテーブルノードポインタ配列からSノードのアドレスを取り出し、pSiblingポインタに値を付与する.もちろん私たちはやはり本の2つの方法を学ぶべきです.
コード:

/********************************* 
【  Offer   】   OJ1524：       
Author:     Date：2015 
Email:[email protected] 
**********************************/
#include 
#include   
#include 
#include 
#include 
#include 
#include  
using namespace std;  
#define MAX 1005

//         
typedef struct LinkNode
{
  int data;
  LinkNode * next;                //                 
  LinkNode * pSibling;        //     
}LinkNode;

LinkNode * nodeArray[MAX];  //        ，              

//           
LinkNode * createComplexLinklist(int n)
{
   LinkNode * head = (LinkNode *)malloc(sizeof(LinkNode));   //       
   head -> data = 0;             
   head -> next = NULL;
   LinkNode * p = head;          
   LinkNode * s = NULL;          //    
   int i,data,Ti;               
   //               
   for(i = 1;i <= n;i++)     // 1    
   {
     scanf("%d",&data);
     s = (LinkNode *)malloc(sizeof(LinkNode));
     s -> data = data;
     s -> next = p -> next;
     p -> next = s;            
     p = s;                     
     nodeArray[i] = s;    //                    
   }
   //             
   p = head -> next;
   for(i = 1;i <= n;i++)
   {
      scanf("%d",&Ti);
      if(0 != Ti)
      {
          p -> pSibling = nodeArray[Ti];
      }
      else
      {
          p -> pSibling = head;     
      }
      p = p -> next;
   }
   return head;
}

/**
*        
*  @param head         
*  @return void
*/
void printComplexLinklist(LinkNode * head)
{
    LinkNode * p = head -> next;
    while(p != NULL)
    {
      printf("%d %d
",p -> data,p -> pSibling -> data);
      p = p -> next;
    }
}

int main()
{
    int n;
    LinkNode * head = NULL;
    while(scanf("%d",&n)!= EOF )
    {
      head = createComplexLinklist(n);
      printComplexLinklist(head);
    }
    return 0;
}


/**************************************************************
    Problem: 1524
    Language: C++
    Result: Accepted
    Time:40 ms
    Memory:1160 kb
****************************************************************/