1. 顺序表とリンクリスト

コースの内容#

イントロダクション#

【基本データ構造】コースの概要
- 赤色を重点的に把握する！
三つの等式
- プログラム = アルゴリズム + データ構造
- プログラム設計 = アルゴリズム + データ構造 + プログラミングパラダイム
- データ構造 = 構造の定義 + 構造の操作
アルゴリズムとデータ構造を通じて、コンピュータがリソースを効果的に利用し、計算リソースをより価値あるものにする

順序表#

【より高度な配列の機能】

構造の定義#

空間は連続しており、任意のタイプの同じ要素を格納できる
- 順序表には順序表を格納することもできる
size：順序表の空間サイズ
length：格納されている要素の数
data_type：格納されている要素のタイプ

構造の操作#

挿入
- 👇👇👇
- 空のまま挿入することはできず、連続している必要がある
- 挿入位置以降のすべての要素を 1 つ後ろに移動する
  - 後ろから移動し、各要素を 1 つ後ろに移動する
- 変更する必要がある属性：length + 1
  - size を変更する必要がある場合は、以下を参照して拡張する
削除
- 👇👇👇
- 実際には削除されず、システムにこのアドレスのストレージ領域が使用可能であることを伝える
- 後ろのすべての要素をまとめて 1 つ前に移動する
  - 削除する位置の値が上書きされる
  - 最後の値はどのように上書きされるか？
    - 単に 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
  - 新しいリストに保存し、ヘッドインサート法を使用する
  - インデックス = 0 の位置にノードを挿入し続ける
  - 不足：スペースの浪費、手間がかかる
- 方法 2
  - インプレース反転、2 つの変数を使用して逆にする、ヘッドインサート法でもある
  - 前提：各操作がメモリリークを引き起こさないようにする
  - NULL アドレスは最後にあり、反転しない
コードデモは後で

単方向循環リスト#

ヘッドは常にテールノードのアドレスを記録する～

インデックス = 0 にノードを挿入する必要がある場合
- 🆒ヘッドがテールノードを記録している場合、ヘッドが指すテールノードの後に直接挿入するだけでよい
- ❌ヘッドがまだ最初のノードのアドレスを記録している場合、機能しません。なぜなら
  - インデックス = 0 のノードの前のノードを見つけるために、リスト全体を走査する必要があるかもしれない
  - 単方向リストの場合とは異なり、ヘッドの後ろ、インデックス = 0 のノードの前に挿入することができるからです
テールにノードを挿入する場合
- ヘッドが新しいテールノード【8】を指すように変更する必要がある！

コードデモ#

順序表#

初期化、破棄
- malloc を使用して空間を割り当て、この構造を初期化する
- 構造から外側に向かって free し、ポインタを null に設定する
拡張操作
- realloc の戻り値を一時変数に割り当て、null が返される場合にデータが失われるのを防ぐ
- realloc が成功したら、元のアドレスの空間は自動的に free される
- スペースを半分に減らす拡張空間を設計することもできるが、スペースが全く残っていない場合は失敗フラグ 0 を返す
- 詳細はコメントを参照してください
挿入、削除
- 操作できない場合に注意する
- 挿入時に満員になった場合、拡張操作を行う
印刷：ユーザーフレンドリー
main 関数のテスト：rand ()、神秘的なモジュロ演算（データの取得、さまざまな例のシミュレーション、操作数の決定）、空間のクリアを忘れない

リンクリスト#

一部の結果

ダミーヘッドノードは、最初のノードの挿入と削除を容易にするために使用されます
- 通常の変数でヘッドを定義することは、
  - ダミーヘッドノードは比較的固定されており、随時 free する必要はないため
  - 通常の変数はポインタ変数よりも安定しており、malloc する必要はないため

考えるポイント#

⭐データ構造の初期化 [例：リンクリスト、リンクリストノード] 時になぜ動的メモリ割り当て [malloc など] を使用し、通常の変数を定義しないのですか？
- まず、盲点を排除する：ポインタは malloc が返すアドレスのみを受け入れることができるわけではなく、ポインタは通常の変数を指すこともできる
- キーポイント：【malloc で割り当てられたメモリはヒープスペースにあり、通常の変数はスタックスペースに定義される】
- スタックスペース：サイズはわずか 8MB で、関数から出ると変数は自動的に解放される
- ヒープスペース：大容量のメモリを割り当てることができる；変数の寿命が長く、通常は手動で解放する必要がある
❓ダミーヘッドノードを通常の変数とポインタ変数のどちらで定義するかの違い
- 個人的な理解では、ポインタ変数を使用するのは malloc が返すアドレスを受け入れるため
- ダミーヘッドノードは単に指示する役割であり、大容量のスペースは必要ないため、malloc する必要はなく、通常の変数で十分です

ヒント#

プログラミングの学習は言語に限定されません
課題の練習問題