コース内容#
はじめに#
- 【基本データ構造】コース概要
-
- 重点を赤で把握！
-
- 三つの等式
- プログラム = アルゴリズム + データ構造
- プログラム設計 = アルゴリズム + データ構造 + プログラミングパラダイム
- データ構造 = 構造定義 + 構造操作
- アルゴリズムとデータ構造を通じて、コンピュータが資源を合理的に利用し、計算資源をより価値のあるものにする
順序表#
【機能がより高度な配列】
構造定義#
- 空間が連続しており、任意のタイプの同じ要素を格納できる
- 順序表の中にも順序表を格納できる
- size：順序表の空間サイズ
- length：格納されている要素の数
- data_type：格納されている要素のタイプ
構造操作#
- 挿入
-
- 👇👇👇
-
- 空のまま挿入してはいけない、必ず連続している必要がある
- 挿入位置以降のすべての要素を一つ後ろに移動する
- 後ろから移動を開始し、各要素を一つ後ろに移動する
- 変更が必要な属性：length + 1
- size は変更が必要な場合があり、拡張については以下を参照
-
- 削除
-
- 👇👇👇
-
- 本当に削除するのではなく、システムにこのアドレスのストレージ領域が占有され、上書き可能であることを知らせる
- 後ろのすべての要素を一つ前に移動する
- 削除する位置の値が上書きされることになる
- 最後の値はどう上書きするのか？
- 直接 length - 1
- 実際には自由に設計可能
- 変更が必要な属性：length - 1
-
- ⭐追加の拡張操作
- 動的メモリ割り当て関数
- malloc：単に空間を確保するが、値は不確定。例：掃除婦がいない部屋を開ける
- calloc：空間を確保し、初期化する。例：掃除婦が掃除する部屋を開ける
- realloc：空間を再確保する。例：部屋のグレードアップ
- 動的メモリ割り当て関数
void* realloc (void* ptr, size_t size); // 新しく確保された空間の先頭アドレスを返す
3 つのケース【realloc】
- まず、元のアドレスの後ろに直接空間を追加できるか試す、空間の先頭アドレスは変わらない；できない場合、
- 別のアドレスを探し、空間を要求し、元の空間のデータを新しい空間にコピーし、元の空間を free する；できない場合（自分で設計して拡張を減らすことができる）
- 空のアドレスを返し、現在のアドレスをクリアしない
連結リスト#
構造定義#
-
-
プログラム内部 + メモリ内部
- 【プログラム内部】はヘッダポインタのみを公開する
- ヘッダポインタ、小さなグリップ、母鶏：最初のノードのアドレスを記録する
- 老鷹が小さな鶏を捕まえることを連想する
- 【メモリ内部】は接続されたノードである
- ノード：データ領域 + ポインタ領域
- ポインタ領域
- 最後のノードのポインタ領域は NULL
- 単方向連結リストのポインタ領域は「後続」とも呼ばれる；双方向連結リストには「前駆」と「後続」がある
- 【プログラム内部】はヘッダポインタのみを公開する
-
順序表と同様に順序保存構造に属する
- 連結リストは論理的には連続しているが、物理的には必ずしも連続しているわけではない
構造操作#
- 挿入
-
- ①挿入位置の前のノード p に移動する
- ②新しいノード x のポインタ領域を挿入位置のノード p.next に指し示す
- ③p のポインタ領域を新しいノード x に指し示す
- 順序を変えてはいけない！そうでないとメモリリークを引き起こす可能性がある（使用できないものを使用していると思い込む）
-
- 削除
- 削除するノードの位置の前の位置に移動する
- 反転
- 方法 1
- 新しい連結リストに格納し、頭挿入法を使用する
- index = 0 の位置にノードを挿入し続ける
- 不足：空間を無駄にし、面倒
- 方法 2
- 原地で反転し、2 つの変数を使って倒す、これも頭挿入法
- 前提：各操作でメモリリークを引き起こさないこと
- NULL アドレスは最後にあり、反転しない
- 方法 1
- コードのデモは後で
単方向循環連結リスト#
- head は常に尾ノードのアドレスを記録する～
- index = 0 にノードを挿入する必要がある場合
-
- 🆒head が尾ノードを記録している場合、直接head が指す尾ノードの後ろに挿入できる
- ❌head がまだ先頭ノードのアドレスを記録している場合、うまくいかない、なぜなら
- index = 0 のノードの前のノードを見つけるために、全連結リストを遍歴して尾ノードを見つける必要があるかもしれない
- 単方向連結リストのように、head の後ろに直接、index = 0 のノードの前に挿入することはできない
-
- 尾部にノードを挿入する場合
-
- head が新しい尾ノードを指すように変更する必要がある【8】！
-
コードデモ#
順序表#
- 初期化、破棄
- malloc を使用して空間を確保し、この構造を初期化する
- 構造から外に free し、ポインタを空にする
- 拡張操作
- realloc が返すアドレスを中間変数に代入し、NULL が返される状況を避け、元のデータが失われるのを防ぐ
- realloc が成功すると、元のアドレスの空間は自動的に free される
- 確実に空間が全く残らないまで、半分に減少する拡張空間を設計できる、失敗のマーク 0 を返す
- 詳細は多く、注釈を参照
- 挿入、削除
- 操作できない状況に注意
- 満員のときに挿入操作を行い、拡張操作を行う
- 印刷：人間的
- main 関数のテスト：rand () を使用し、魔法のモジュロ操作（データを取得し、さまざまなサンプルをシミュレートし、操作数を決定する）、空間をクリアすることを忘れない
連結リスト#
部分結果
-
-
仮想ヘッダノード、最初のノードの挿入と削除を便利にする
- 普通の変数で head を定義し、❓考慮するのは
- 仮想ヘッダノードは比較的固定されており、随時 free する必要がない
- 普通の変数はポインタ変数よりも安定しており、malloc する必要はない
- 普通の変数で head を定義し、❓考慮するのは
思考点#
- ⭐データ構造 [例えば連結リスト、連結リストノード] を初期化する際、なぜ動的にメモリを確保する [malloc などを使用] のか、普通の変数を定義するのではなく？
- まず、盲点を排除する：ポインタは malloc が返すアドレスしか受け取れないわけではなく、ポインタは普通の変数を指すこともできる
- 重要な点：【malloc で申請したメモリはヒープ空間にあり、普通の変数はスタック空間に定義されている（関数内で定義されている）】
- スタック空間：サイズは 8MB しかない；関数を出ると [スコープ] 変数は自動的に解放される
- ヒープ空間：大きなメモリを割り当て可能；変数のライフサイクルが長い、通常は手動で解放する必要がある
- ❓仮想ヘッダノードを普通の変数とポインタ変数として定義する違い
- 個人的な理解として、ポインタ変数を使用するのは、malloc が返すアドレスを受け取るためである
- しかし、仮想ヘッダノードはここでは指示的な役割を果たすだけで、大きな空間は必要ないので、普通の変数で十分である
ヒント#
-
プログラミングの学習は言語に限らない
-
課後練習問題
-
