3.5 まとめ¶
1. 重要なポイント¶
- データ構造は論理構造と物理構造の2つの観点から分類できます。論理構造はデータ間の論理的関係を記述し、物理構造はデータがメモリにどのように格納されるかを記述します。
- よく使用される論理構造には、線形構造、木、ネットワークがあります。通常、論理構造に基づいてデータ構造を線形（配列、連結リスト、スタック、キュー）と非線形（木、グラフ、ヒープ）に分けます。ハッシュ表の実装は線形と非線形の両方のデータ構造を含む場合があります。
- プログラムが実行中の際、データはメモリに格納されます。各メモリ空間には対応するアドレスがあり、プログラムはこれらのアドレスを通じてデータにアクセスします。
- 物理構造は連続空間格納（配列）と離散空間格納（連結リスト）に分けることができます。すべてのデータ構造は配列、連結リスト、またはその両方の組み合わせを使用して実装されます。
- コンピュータの基本データ型には、整数（
byte、short、int、long）、浮動小数点数（float、double）、文字（char）、ブール値（bool）が含まれます。データ型の値の範囲は、そのサイズと表現に依存します。 - 符号絶対値、1の補数、2の補数は、コンピュータで整数をエンコードする3つの方法であり、相互に変換することができます。符号絶対値の最上位ビットは符号ビットで、残りのビットは数値の値を表します。
- 整数はコンピュータで2の補数によってエンコードされます。この表現の利点には、(i)コンピュータが正と負の整数の加算を統一できる、(ii)減算用の特別なハードウェア回路を設計する必要がない、(iii)正と負の0の曖昧さがない、があります。
- 浮動小数点数のエンコーディングは、1つの符号ビット、8つの指数ビット、23の仮数ビットで構成されます。指数ビットのため、浮動小数点数の範囲は整数よりもはるかに大きくなりますが、精度を犠牲にします。
- ASCIIは最初期の英語文字セットで、1バイトの長さで計127文字です。GBKは人気のある中国語文字セットで、2万文字以上の中国語文字を含みます。Unicodeは世界の様々な言語の文字を含む完全な文字セット標準を提供することを目的とし、文字エンコーディング方法の不一致による文字化け問題を解決します。
- UTF-8は最も人気があり一般的なUnicodeエンコーディング方法です。これは可変長エンコーディング方法で、優れた拡張性と空間効率を持ちます。UTF-16とUTF-32は固定長エンコーディング方法です。中国語文字をエンコードする際、UTF-16はUTF-8よりも少ない空間を使用します。JavaやC#などのプログラミング言語はデフォルトでUTF-16エンコーディングを使用します。
2. Q & A¶
Q: なぜハッシュ表は線形と非線形の両方のデータ構造を含むのですか？
ハッシュ表の基礎構造は配列です。ハッシュ衝突を解決するために、「チェイン法」を使用する場合があります（後の節「ハッシュ衝突」で説明）：配列の各バケットは連結リストを指し、その長さが特定の閾値より大きくなると木（通常は赤黒木）に変換される可能性があります。 格納の観点から、ハッシュ表の基礎構造は配列で、各バケットには値、連結リスト、または木が含まれる場合があります。したがって、ハッシュ表は線形データ構造（配列、連結リスト）と非線形データ構造（木）の両方を含む場合があります。
Q: char型の長さは1バイトですか？
char型の長さは、プログラミング言語のエンコーディング方法によって決まります。例えば、Java、JavaScript、TypeScript、C#はすべてUTF-16エンコーディング（Unicodeコードポイントを保存するため）を使用するため、char型の長さは2バイトです。
Q: 配列ベースのデータ構造を「静的データ構造」と呼ぶことに曖昧さはありませんか？スタックもプッシュやポップなどの「動的」操作を実行できます。
スタックは動的なデータ操作を実装できますが、データ構造は依然として「静的」です（長さが固定）。配列ベースのデータ構造は動的に要素を追加または削除できますが、その容量は固定されています。スタックサイズが事前に割り当てられたサイズを超える場合、古い配列は新しく作成されたより大きな配列にコピーされます。
Q: スタック（キュー）を構築する際、そのサイズが指定されていないのに、なぜ「静的データ構造」なのですか？
高級プログラミング言語では、スタック（キュー）の初期容量を手動で指定する必要はありません。このタスクはクラス内で自動的に完了されます。例えば、JavaのArrayListの初期容量は通常10です。さらに、拡張操作も自動的に完了されます。詳細については、後続の「リスト」の章を参照してください。
Q: 符号絶対値を2の補数に変換する方法は「最初に否定してから1を加える」ですので、2の補数を符号絶対値に変換することはその逆操作「最初に1を減算してから否定する」であるべきです。 しかし、2の補数も「最初に否定してから1を加える」を通じて符号絶対値に変換できます。なぜですか？
A: これは、符号絶対値と2の補数間の相互変換が「補数」の計算と等価だからです。まず補数を定義します：\(a + b = c\)と仮定すると、\(a\)は\(b\)の\(c\)に対する補数と言い、逆に\(b\)は\(a\)の\(c\)に対する補数と言います。
長さ\(n = 4\)の二進数\(0010\)が与えられた場合、この数が符号絶対値（符号ビットを無視）の場合、その2の補数は「最初に否定してから1を加える」ことで得られます：
符号絶対値と2の補数の和が\(0010 + 1110 = 10000\)であることを観察します。つまり、2の補数\(1110\)は符号絶対値\(0010\)の\(10000\)に対する「補数」です。これは、上記の「最初に否定してから1を加える」が\(10000\)に対する補数の計算と等価であることを意味します。
では、\(1110\)の\(10000\)に対する「補数」は何でしょうか？「最初に否定してから1を加える」ことで計算できます：
言い換えると、符号絶対値と2の補数は互いに\(10000\)に対する「補数」であるため、「符号絶対値から2の補数」と「2の補数から符号絶対値」は同じ操作（最初に否定してから1を加える）で実装できます。
もちろん、「最初に否定してから1を加える」の逆操作を使用して2の補数\(1110\)の符号絶対値を求めることもできます。つまり、「最初に1を減算してから否定する」：
要約すると、「最初に否定してから1を加える」と「最初に1を減算してから否定する」は両方とも\(10000\)に対する補数を計算しており、等価です。
本質的に、「否定」操作は実際には\(1111\)に対する補数を求めることです（符号絶対値 + 1の補数 = 1111が常に成り立つため）。そして1の補数に1を加えることは\(10000\)に対する2の補数と等しくなります。
上記では\(n = 4\)を例に取りましたが、任意の桁数の任意の二進数に一般化できます。