コンテンツにスキップ
日本語版のレビュアーを募集しています。詳しくは こちら をご覧ください。

# 3.6 演習

## 3.6.1 確認問題

### 1. 身近な場面にあるデータの関係

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

1. 生徒が一列に並び、それぞれが自分の前と後ろにいる人だけに注目する。
2. 学校が「学校 → 学年 → クラス」という階層で管理されている。
3. 都市の道路が複数の交差点を結び、1 つの交差点から複数の別の交差点へ行けるほか、道路が環状につながることもある。

解答

1. 線形構造です。列の先頭と最後にいる人を除き、それぞれの人は前後の 1 人ずつとだけ隣り合い、関係が一本の線に沿って並んでいます。

2. 木構造です。各クラスはいずれか 1 つの学年に属し、各学年はさらに学校に属しており、関係が上から下へ階層的に広がっています。

3. 網状構造です。1 つの交差点を複数の交差点と結ぶことができ、経路が環状につながる場合もあるため、1 つの順序や厳密な階層では表せません。

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

### 2. 論理的な順序をメモリに保存する方法

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

- 方法 A：`A、B、C` を、それぞれ番号 `20、21、22` のメモリ領域に置く。
- 方法 B：`A、B、C` を、それぞれ番号 `20、7、31` のメモリ領域に置き、`A` に `B` の位置、`B` に `C` の位置を記録する。

1. どちらが連続した領域への保存で、どちらが分散した領域への保存ですか？
2. 2 つの方法は、それぞれ配列と連結リストのどちらに近いですか？
3. 方法 B のメモリ領域の番号は大きさの順に並んでいません。それでも `A → B → C` という論理的な順序を表せるのはなぜですか？

解答

1. 方法 A は連続したメモリ領域を使っているため、連続した領域への保存です。方法 B のノードは別々の場所に分散しているため、分散した領域への保存です。

2. 方法 A は配列に、方法 B は連結リストに近いです。

3. 論理的な順序を決めるのはノード間に記録された接続関係であり、メモリ領域の番号の大小ではありません。 `A` に記録された位置から `B` を見つけ、さらに `B` に記録された位置から `C` を見つけられるため、`A、B、C` の順にアクセスできます。

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

### 3. 宿題の記録におけるデータ型と構造

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

`[true, false, true, true]`

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

解答

1. 各要素は「はい」か「いいえ」だけを表すため、ブール型 `bool` が適しています。

2. これらの要素は座席順に並んで線形構造を作っており、配列で保存できます。

3. 変わるのは内容の型です。要素がブール値から整数に変わります。一方、構成方法は変わりません。 データは引き続き座席順に一列に並び、配列という線形構造を使えます。

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

## 3.6.2 プログラミング演習

### 1. 二進表現に含まれる 1 の個数

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

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

解法のヒント

1. n & 1 で n の最下位ビットを取り出し、そのビットが 1 かどうかを判定できます
2. 1 ビット右へシフトすると、現在の最下位ビットが取り除かれます。多くの言語では演算子 >> を使います
3. 各ビットを調べて右へシフトする方法を完成させたら、n & (n - 1) が n の最も右にある 1 を 0 に変えることも確認してみましょう

LeetCode

##### ご意見、ご質問、ご提案があればぜひコメントしてください