データ構造こうぞうポータル

1導入どうにゅう

この講義群こうぎぐんでは、データ構造こうぞうが提供ていきょうする操作そうさと、その操作そうさを実現じつげんする実装じっそうを区別くべつし、用途ようとに適てきした構造こうぞうを選択せんたくする基準きじゅんを説明せつめいする。

2抽象ちゅうしょうデータ型がたと実装じっそう

抽象ちゅうしょうデータ型がた（abstract data type; ADT）は、保持ほじする値あたいと利用可能りようかのうな操作そうさの契約けいやくを規定きていする。実装じっそうは、その契約けいやくを配列はいれつ、連結れんけつリスト、木きなどによって実現じつげんする具体的方法ぐたいほうほうである。同一どういつのADTでも、実装じっそうによって時間計算量じかんけいさんりょうと空間計算量くうかんけいさんりょうは異ことなる。

各講義かくこうぎでは、操作そうさの事前条件じぜんじょうけんと事後条件じごじょうけん、空からの構造こうぞうに対たいする挙動きょどう、実装上じっそうじょうの前提ぜんてい、計算量けいさんりょうの順じゅんに確認かくにんする。

3学習順序がくしゅうじゅんじょ

1. スタックとキューでは、LIFOとFIFOという取出順序とりだしじゅんじょを定義ていぎし、DFSとBFSの候補管理こうほかんりへ接続せつぞくする。
2. ハッシュ表ひょうでは、鍵かぎによる検索けんさくと衝突処理しょうとつしょりを扱あつかう。
3. 木きとヒープでは、階層構造かいそうこうぞうと優先度ゆうせんどに基もとづく操作そうさを扱あつかう。
4. 素集合そしゅうごうデータ構造こうぞうでは、集合しゅうごうの併合へいごうと所属判定しょぞくはんていを扱あつかう。