二分木ソート - e-publishing.jp会社ロゴ

■２分木ソート（平成 11 年秋午後問７）
次のＣプログラムの説明及びプログラムを読んで、設問に答えよ。
次に、再帰的な関数 BinTreeSort を呼び出して２分木の要素を身長の昇順に整列する。
引数は、ルートの要素番号である。
関数 BinTreeSort の原型（プロトタイプ）は、次のとおりである。
〔プログラムの説明〕
次の STUDENT 構造体の配列 Stu を、身長 Height をキーとして昇順に整列して出力する。
typedef struct {
char
Name[64] ;
int
Age ;
float Height ;
float Weight ;
} STUDENT ;
STUDENT Stu[MAXNUM] ;
/*
/*
/*
/*
名前
年齢
身長
体重
*/
*/
*/
*/
void
BinTreeSort( int Root ) ;
最後に、再帰的な関数 DisplayData を呼び出し、２分木をたどって構造体配列の内容を身長の昇順に出力する。
引数は、ルートの要素番号である。
関数 DisplayData の原型は、次のとおりである。
void
DisplayData( int Root ) ;
配列のデータを入れ替えずに、順番を表す２分木を作成する。
２分木を表すため、次の配列変数を定義する。
int Lower[MAXNUM], Upper[MAXNUM] ;
図１は、要素を昇順に整列したとき、要素番号が 3，1，0，5，2，4 の順番になる場合を示す。
このとき、配列 Lower、Upper の内容は図２のようになる。
値が -1 のときは、次に接続する要素がないことを示す。
要素番号 ��
�
ルート
�
ルート � �
� �
�
��
要素番号
�
�
��
��
�
� �
�
�
�
�
��
��
��
�
��
#include
��
�
��
��
��
��
��
��
void
void
�
��
��
�
��
��
最初に、構造体配列 Stu の定義に現れた順に要素を Upper 側に接続し、図３に示す２分木を作成する。
ルート
�
�
�
�
<stdio.h>
BinTreeSort( int Root ) ;
DisplayData( int Root ) ;
#define MAXNUM 5
図２図１の 2 分木を表す配列の内容
図１要素の接続状態の例
ルート
〔プログラム〕
��
��
��
��
図２図１の 2 分木を表す配列の内容
図１要素の接続状態の例
�
��
�
�
�
�
図３整列前の接続状態
図３整列前の接続状態
�
�
�
�
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 ) ;
}
【課題１】
問題文のプログラムでは、２分木データの初期設定を次のように行った。
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;
同様に、次に示す２分木データの場合を初期設定し、実行しなさい。
�
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 ) ;
��
��
�
�
田中 ��
��
��
加藤
��
��
��
��
山中
��
}
【課題２】
いろいろな２分木データに関して初期設定し、実行してみなさい。
（もし、身長の昇順にならなかった場合には、その原因を突き止め、プログラムを改良しなさい。）
www.e-publishing.jp
■平成 11 秋午後問７解答例
２分木構造に格納した要素に関して、要素のメンバ：身長の昇順に整列して出力するプログラムである。
空欄ａ、ｂ、ｃを有する部分の各文に次のように番号を付した上で、プログラム内容をみていこう。
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 ;
}
空欄ａ
文番号 05 で、Data=Upper[Root]; としたので、次は、Next=Upper[Data]; とする必要がある。
空欄ａの答え：キ
空欄ｂ
文番号 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] として同様の処理を行う。
空欄ｂの答え：ク
空欄ｃ
文番号 10 の if( Stu[Data].Height >= Stu[Root].Height ) が「偽」のときは、これまで Upper 側
であったものを、Lower 側のものに置き換えて処理を行う。空欄ｃの答え：イ
空欄ｄ
関数：DisplayData( ) の基本構造は、次のようになっている。
DisplayData( 空欄ｄ );
printf("………"); ①
��
Upper[Root] = Data ;
}
else {
Upper[Data] = Lower[Root] ;
16
��
② ��に
��
;
Upper[Data] =
12
13
14
15
17
18
19
本問は、２分木の要素に関して、二つの要素間の処理を、再帰により全要素に拡大していくものである。
従って、基本は二つの要素（本問では、それを Root と Data としている。）間の処理である。
それら二つの要素の接続状態、それを表す配列の内容、及び、それがプログラム中のどこに対応するかを示す。
← Root、つまり、ノード部分に位置する要素を表示する。
DisplayData(Upper[Root]); ← Upper 側 - 部分木の表示を再帰処理に託す。
DisplayData(Upper[Root]); は、Upper 側 - 部分木の表示を再帰処理に託すものである。
Data = Lower[Root] ;
/*** Lower 側 - 部分木に対して BinTreeSort を行う ***/
if ( Data != -1 ) BinTreeSort( Data ) ;
従って、DisplayData( 空欄ｄ ); では、Lower 側 - 部分木の表示を再帰処理に託す。空欄ｄの答え：エ
}
www.e-publishing.jp
/******* H11aki07.c *******/
/******* ２分木構造に格納した要素を、そのメンバ：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
/* ２分木の要素を身長の昇順に整列する */
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 側 - 部分木を表示する */
}
【実行結果】
２分木データの初期設定によって、次に示すような接続状態、配列内容になる。
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 進データを２進データに変換する際、誤差が生じる場合がある。そのため、変換された２進データを 10 進データで表示する
と、上記の左側 - 実行結果に示すように正確に表示されない場合が出てくる。
身長、体重のデータ型を double で宣言すれば、上記右側 - 実行結果のように改善される。
��
�� と �� は省略してある。
www.e-publishing.jp

Download Report