2005年度 データ構造とアルゴリズム 第4回 「再帰的データ構造：リスト構造」 西尾 信彦 [email protected] 立命館大学情報理工学部 情報システム学科 typedefを覚えよう • • • • 自分でデータ型の名前をつけられる struct xxxxxは長たらしい typedef 既存の型名 新しい型名； 例えば、 – typedef struct _student student; – typedef struct _list { struct _list *next; int data; } *list, listelem; リストの先頭と最後 • 先頭要素を指すポインタが必要 • リストの最後の要素はどこを指す？ – どこも指さない NULL – 自分を指す – (ダミーの)先頭要素を指す リストへの要素の挿入と削除 • どちらもポインタを指し換えにより実現 • リストと対象要素を与えられて処理する – それだけでは済まない – 一つ前の要素も書き換えないと • どこに入れるかで変わる処理 – 先頭かそれ以外で処理が違うのが気持ち悪い – ダミーの先頭要素を用意すると解消する 二重リンクされたリスト • 次の要素を指すだけでなく、前の要素も指 す • 挿入や削除が対象要素だけでできる • 処理は倍の手間 • 両端はどうする？ – ともにNULL – 両端をつなげて循環リスト リストで実現するデータ構造 • スタック – LIFO Last In First Out • キュー – FIFO First In First Out • デク DEQ – Double Ended Queue スタック • • • • • LIFOのデータ構造 Push：スタックに1つデータを積む Pop：スタックから1つデータを取り出す Top：スタックの一番上にあるデータを見る スタックのデータ構造 – リストそのもの • スタックへの操作を上記の3つに制限する ことによってリストでスタックを実現する キュー • 待ち行列を表現するデータ構造 • FIFO 最初に並んだ人が最初にサービスさ れる • Empty：キューが空かどうか見る • Enqueue：キューに1つデータを追加する • Dequeue：キューから1つデータを取り出す • Peek:キューの先頭のデータを見る デク DEQ • 先頭にも最後にもデータを追加、取り出し できるデータ構造 – 二重リンクされたリストで作成 • • • • Unshift：リストの先頭にデータを追加 Push：リストの末尾にデータを追加 Shift：リストの先頭からデータを取り出す Pop：リストの末尾からデータを取り出す
© Copyright 2024 ExpyDoc
