■2分木ソート(平成 11 年秋午後問7) 次のCプログラムの説明及びプログラムを読んで、設問に答えよ。 次に、再帰的な関数 BinTreeSort を呼び出して2分木の要素を身長の昇順に整列する。 引数は、ルートの要素番号である。 関数 BinTreeSort の原型(プロトタイプ)は、次のとおりである。 〔プログラムの説明〕 次の STUDENT 構造体の配列 Stu を、身長 Height をキーとして昇順に整列して出力する。 typedef struct { char Name[64] ; int Age ; float Height ; float Weight ; } STUDENT ; STUDENT Stu[MAXNUM] ; /* /* /* /* 名前 年齢 身長 体重 */ */ */ */ void BinTreeSort( int Root ) ; 最後に、再帰的な関数 DisplayData を呼び出し、2分木をたどって構造体配列の内容を身長の昇順に出力する。 引数は、ルートの要素番号である。 関数 DisplayData の原型は、次のとおりである。 void DisplayData( int Root ) ; 配列のデータを入れ替えずに、順番を表す2分木を作成する。 2分木を表すため、次の配列変数を定義する。 int Lower[MAXNUM], Upper[MAXNUM] ; 図1は、要素を昇順に整列したとき、要素番号が 3,1,0,5,2,4 の順番になる場合を示す。 このとき、配列 Lower、Upper の内容は図2のようになる。 値が -1 のときは、次に接続する要素がないことを示す。 要素番号 ����� � ルート � ルート � � � � � ����� 要素番号 � � �� �� � � � � � � � ����� �� �� � �� #include �� � �� �� �� �� �� �� void void � �� �� � �� �� 最初に、構造体配列 Stu の定義に現れた順に要素を Upper 側に接続し、図3に示す2分木を作成する。 ルート � � � � <stdio.h> BinTreeSort( int Root ) ; DisplayData( int Root ) ; #define MAXNUM 5 図2 図1の 2 分木を表す配列の内容 図1 要素の接続状態の例 ルート 〔プログラム〕 �� �� ��� �� 図2 図1の 2 分木を表す配列の内容 図1 要素の接続状態の例 � ����� � � � � 図3 整列前の接続状態 図3 整列前の接続状態 � � � � typedef struct { char Name[64] ; int Age ; float Height ; float Weight ; } STUDENT ; /* /* /* /* 名前 年齢 身長 体重 STUDENT Stu[MAXNUM] = { { " 相川 太郎 ", 19, 162.5, { " 伊藤 四郎 ", 14, 158.0, { " 加藤 五郎 ", 18, 182.0, { " 田中 三郎 ", 12, 148.0, { " 山中 次郎 ", 16, 178.5, */ */ */ */ 65.4 48.4 82.5 46.8 70.0 }, }, }, }, } } ; int Upper[MAXNUM], Lower[MAXNUM] ; www.e-publishing.jp main( ) { int Index ; for( Index = 0 ; Index < MAXNUM ; Index++ ) { Upper[Index] = Index + 1 ; Lower[Index] = -1 ; } Upper[MAXNUM - 1] = -1 ; BinTreeSort( 0 ) ; DisplayData( 0 ) ; } 設問 プログラム中の に入れる正しい答えを、解答群の中から選べ。 解答群 ア -1 イ Data エ Lower[Root] オ Next キ Upper[Data] ク Upper[Root] ウ Lower[Data] カ Root void BinTreeSort( int Root ) { int Data, Next ; Data = Upper[Root] ; if ( Data == -1 ) return ; Upper[Root] = -1 ; while( Data != -1 ) { Next = a ; if ( Stu[Data].Height >= Stu[Root].Height ) { b Upper[Data] = ; Upper[Root] = Data ; } else { Upper[Data] = Lower[Root] ; c Lower[Root] = ; } Data = Next ; } Data if ( Data if ( = Upper[Root] Data != -1 ) = Lower[Root] Data != -1 ) ; BinTreeSort( Data ) ; ; BinTreeSort( Data ) ; } 【課題1】 問題文のプログラムでは、2分木データの初期設定を次のように行った。 Lower[0]=-1, Upper[0]=1; Lower[1]=-1, Upper[1]=2; Lower[2]=-1, Upper[2]=3; Lower[3]=-1, Upper[3]=4; Lower[4]=-1, Upper[4]=-1; 同様に、次に示す2分木データの場合を初期設定し、実行しなさい。 � void DisplayData( int Root ) { if ( Root == -1 ) return ; DisplayData( d �������� DisplayData( Upper[Root] ) ; � 伊藤 相川 �������� � ������ �������� ) ; printf(" 名前 :%s 年齢 :%d 身長 :%f 体重 :%f\n" , Stu[Root].Name, Stu[Root].Age, Stu[Root].Height, Stu[Root].Weight ) ; ������ ������ � � 田中 ������ �� �� 加藤 �� �� �������� ������ �� 山中 �� } 【課題2】 いろいろな2分木データに関して初期設定し、実行してみなさい。 (もし、身長の昇順にならなかった場合には、その原因を突き止め、プログラムを改良しなさい。) www.e-publishing.jp ■平成 11 秋午後問7解答例 2分木構造に格納した要素に関して、要素のメンバ:身長の昇順に整列して出力するプログラムである。 空欄a、b、cを有する部分の各文に次のように番号を付した上で、プログラム内容をみていこう。 01 02 03 04 05 06 07 08 void BinTreeSort( int Root ) { int Data, Next ; ���� ���� ��� ��������� ������ Data = Upper[Root] ; if ( Data == -1 ) return ; Upper[Root] = -1 ; while( Data != -1 ) { a ������ ����������� 09 Next = 10 if ( Stu[Data].Height >= Stu[Root].Height ) { 11 Lower[Root] = b ���� ④ メンバ ������ の大小比較 ��� ��������� ; c ������ ������ ����������� ����������� ③ ���� ; } Data = Next ; } 空欄a 文番号 05 で、Data=Upper[Root]; としたので、次は、Next=Upper[Data]; とする必要がある。 空欄aの答え:キ 空欄b 文番号 10 の if( Stu[Data].Height >= Stu[Root].Height ) が「真」のときは、比較要素を次段の Upper 側に進めて同様の処理を行う。 要素番号 ����� ����� ���� ������ ���� ����������� ����������� �������������� ���������������� ���� ����������� ����������� �������������� ���������������� void BinTreeSort( int Root ) { int Data, Next ; Data = Upper[Root] ; /* ① */ if ( Data == -1 ) return ; Upper[Root] = -1 ; /* ② */ while( Data != -1 ) { /* 要素が無くなるまで繰り返す */ Next = Upper[Data] ; /* ③ */ /* Next = 空欄 a */ if ( Stu[Data].Height >= Stu[Root].Height ) { /* ④ *//* 比較要素の Height が昇順なら */ /*** 次の比較要素に処理を進める ***/ Upper[Data] = Upper[Root] ; /* Upper[Data] = 空欄 b */ Upper[Root] = Data ; } else { /* 比較要素の Height が昇順に無いなら */ /*** これまで Upper 側だったものを、Lower 側のものと置き換える ***/ Upper[Data] = Lower[Root] ; Lower[Root] = Data ; /* Lower[Root] = 空欄 c */ } Data = Next ; } Data = Upper[Root] ; /*** Upper 側 - 部分木に対して BinTreeSort を行う ***/ if ( Data != -1 ) BinTreeSort( Data ) ; つまり、これまで、Upper[Data] であったものを、新たに Upper[Root] として同様の処理を行う。 空欄bの答え:ク 空欄c 文番号 10 の if( Stu[Data].Height >= Stu[Root].Height ) が「偽」のときは、これまで Upper 側 であったものを、Lower 側のものに置き換えて処理を行う。 空欄cの答え:イ 空欄d 関数:DisplayData( ) の基本構造は、次のようになっている。 DisplayData( 空欄d ); printf("………"); ① ���� Upper[Root] = Data ; } else { Upper[Data] = Lower[Root] ; 16 ����������� ② ��に ���� ; Upper[Data] = 12 13 14 15 17 18 19 本問は、2分木の要素に関して、二つの要素間の処理を、再帰により全要素に拡大していくものである。 従って、基本は二つの要素(本問では、それを Root と Data としている。)間の処理である。 それら二つの要素の接続状態、それを表す配列の内容、及び、それがプログラム中のどこに対応するかを示す。 ← Root、つまり、ノード部分に位置する要素を表示する。 DisplayData(Upper[Root]); ← Upper 側 - 部分木の表示を再帰処理に託す。 DisplayData(Upper[Root]); は、Upper 側 - 部分木の表示を再帰処理に託すものである。 Data = Lower[Root] ; /*** Lower 側 - 部分木に対して BinTreeSort を行う ***/ if ( Data != -1 ) BinTreeSort( Data ) ; 従って、DisplayData( 空欄d ); では、Lower 側 - 部分木の表示を再帰処理に託す。 空欄dの答え:エ } www.e-publishing.jp /******* H11aki07.c *******/ /******* 2分木構造に格納した要素を、そのメンバ:Height の昇順に整列して表示する *******/ #include <stdio.h> void void void BinTreeSort( int Root ) { int Data, Next ; BinTreeSort( int Root ) ; DisplayData( int Root ) ; Data = Upper[Root] ; if ( Data == -1 ) return ; Upper[Root] = -1 ; #define MAXNUM 5 typedef struct { char Name[64] ; int Age ; float Height ; float Weight ; } STUDENT ; /* /* /* /* 名前 年齢 身長 体重 STUDENT Stu[MAXNUM] = { { " 相川 太郎 ", 19, 162.5, { " 伊藤 四郎 ", 14, 158.0, { " 加藤 五郎 ", 18, 182.0, { " 田中 三郎 ", 12, 148.0, { " 山中 次郎 ", 16, 178.5, while( Data != -1 ) { /* 要素が無くなるまで繰り返す */ Next = Upper[Data] ; /* Next = 空欄 a */ if ( Stu[Data].Height >= Stu[Root].Height ) { /* 比較要素の Height が昇順にあるなら */ /*** 次の比較要素に処理を進める ***/ Upper[Data] = Upper[Root] ; /* Upper[Data] = 空欄 b */ Upper[Root] = Data ; } */ */ */ */ 65.4 48.4 82.5 46.8 70.0 /* 2分木の要素を身長の昇順に整列する */ else { /* 比較要素の Height が昇順に無いなら */ /*** これまで Upper 側だったものを、Lower 側のものと置き換える ***/ Upper[Data] = Lower[Root] ; Lower[Root] = Data ; /* Lower[Root] = 空欄 c */ } Data = Next ; }, }, }, }, } } ; } Data = Upper[Root] ; /* Upper 側 - 部分木に対して BinTreeSort を行う */ if ( Data != -1 ) BinTreeSort( Data ) ; int Upper[MAXNUM], Lower[MAXNUM] ; main( ) { int Index ; Data = Lower[Root] ; /* Lower 側 - 部分木に対して BinTreeSort を行う */ if ( Data != -1 ) BinTreeSort( Data ) ; } /*** 2 分木の初期設定 ***/ for( Index = 0 ; Index < MAXNUM ; Index++ ) { Upper[Index] = Index + 1 ; Lower[Index] = -1 ; } Upper[MAXNUM - 1] = -1 ; /*** 関数呼出し ***/ BinTreeSort( 0 ) ; DisplayData( 0 ) ; void DisplayData( int Root ) { if ( Root == -1 ) return ; DisplayData( Lower[Root] ) ; printf(" 名前 :%s 年齢 :%d 身長 :%f 体重 :%f\n" , Stu[Root].Name, Stu[Root].Age, Stu[Root].Height, Stu[Root].Weight ) ; DisplayData( Upper[Root] ) ; } /* 引数として Root の要素番号を渡す */ /* Lower 側 - 部分木を表示する */ /* 節(ノード)の要素を表示する */ /* Upper 側 - 部分木を表示する */ } 【実行結果】 2分木データの初期設定によって、次に示すような接続状態、配列内容になる。 float 型で指定 ���� � ������ 相川 �������� � �� ������ 伊藤 �������� � �� ������ 加藤 �������� � �� ������ 田中 �������� � �� ������ �� 山中 �� 要素番号 ����� ����� ���� ������ � �� � 相川太郎 ����� � �� � 伊藤四郎 ����� � �� � 加藤五郎 ����� � �� � 田中三郎 ����� � �� �� 山中次郎 ����� 名前 : 田中 名前 : 伊藤 名前 : 相川 名前 : 山中 名前 : 加藤 三郎 四郎 太郎 次郎 五郎 年齢 :12 年齢 :14 年齢 :19 年齢 :16 年齢 :18 身長 :148.000000 身長 :158.000000 身長 :162.500000 身長 :178.500000 身長 :182.000000 double 型で指定 体重 :46.799999 体重 :48.400002 体重 :65.400002 体重 :70.000000 体重 :82.500000 名前 : 田中 名前 : 伊藤 名前 : 相川 名前 : 山中 名前 : 加藤 三郎 四郎 太郎 次郎 五郎 年齢 :12 年齢 :14 年齢 :19 年齢 :16 年齢 :18 身長 :148.000000 身長 :158.000000 身長 :162.500000 身長 :178.500000 身長 :182.000000 体重 :46.800000 体重 :48.400000 体重 :65.400000 体重 :70.000000 体重 :82.500000 問題文では、身長、体重のデータの型は float で宣言しているが、float ではデータを格納する領域が多くないため、 10 進データを2進データに変換する際、誤差が生じる場合がある。そのため、変換された2進データを 10 進データで表示する と、上記の左側 - 実行結果に示すように正確に表示されない場合が出てくる。 身長、体重のデータ型を double で宣言すれば、上記右側 - 実行結果のように改善される。 ������������������ ��� と ������ は省略してある。 www.e-publishing.jp
© Copyright 2025 ExpyDoc