3.6 演習¶

3.6.1 確認問題¶

データ同士の関係に基づいて、次の 3 つの場面に「線形構造、木構造、網状構造」のいずれかを選び、理由を説明してください。

解答

線形構造です。列の先頭と最後にいる人を除き、それぞれの人は前後の 1 人ずつとだけ隣り合い、関係が一本の線に沿って並んでいます。
木構造です。各クラスはいずれか 1 つの学年に属し、各学年はさらに学校に属しており、関係が上から下へ階層的に広がっています。
網状構造です。1 つの交差点を複数の交差点と結ぶことができ、経路が環状につながる場合もあるため、1 つの順序や厳密な階層では表せません。

構造を判断するときは、メモリをどれだけ使うかを先に考えるのではなく、まず要素同士の関係を観察します。

論理的な順序 A → B → C を保存するために、次の 2 つの簡略化したメモリ配置を考えます。

解答

方法 A は連続したメモリ領域を使っているため、連続した領域への保存です。方法 B のノードは別々の場所に分散しているため、分散した領域への保存です。
方法 A は配列に、方法 B は連結リストに近いです。
論理的な順序を決めるのはノード間に記録された接続関係であり、メモリ領域の番号の大小ではありません。 A に記録された位置から B を見つけ、さらに B に記録された位置から C を見つけられるため、A、B、C の順にアクセスできます。

このことからも、論理構造と物理構造は、同じデータを異なる視点から捉えたものだと分かります。

ある学習グループが、座席順に 4 人の生徒が宿題を提出したかどうかを記録したところ、次の結果になりました。

[true, false, true, true]

各要素には、どの基本データ型が適していますか？
この 4 つの要素は座席順に一列に並んでいます。どのような論理構造を使っていますか？
今後、各生徒の宿題の点数を [90, 0, 85, 100] と記録するように変えた場合、変わるのはデータの「内容の型」と「構成方法」のどちらですか？理由も説明してください。

解答

各要素は「はい」か「いいえ」だけを表すため、ブール型 bool が適しています。
これらの要素は座席順に並んで線形構造を作っており、配列で保存できます。
変わるのは内容の型です。要素がブール値から整数に変わります。一方、構成方法は変わりません。データは引き続き座席順に一列に並び、配列という線形構造を使えます。

基本データ型は「何を保存するか」を、データ構造は「データをどのように構成するか」を表します。

0 以上の整数 n が与えられます。その二進表現に 1 がいくつ含まれるかを数えてください。

ビット演算を使って求めてください。二進表現を文字列に変換したり、1 を直接数える組み込み関数を使ったりしてはいけません。

解法のヒント