抽象データとしてのリスト構造
配列でリストを作ろうが、単連結リストでリストを作ろうが、別にリストを使う側は意識しないで使えればそれでいい
- ユーザの利点
- リストの実装方法によらず同じコードが使える
- 実装側の利点
- ユーザーからの呼出しだけ維持すればさらに効率的な実装をできる
APIだ！！
抽象データ型の概念と意義
- 内部情報の隠蔽などが可能に
- 仕様と実装が分離
- モジュール化の実現
リストが持つべき基本操作
- リストの初期化
- 先頭の位置を返す
- 終端の位置を返す
- 特定のものの位置を返す
- 特定のものの直前の位置
- 特定のものの直後の位置
- 挿入
- 削除
- 要素の取得
実装例
配列でもやれはする
ノードで実装する場合は内部では添字をずらすことで扱いやすくする(外から触れるときの挙動は変えない)
配列ならずらす操作が
単連結リストならたどる操作は
双方向リストを使えば全てで
バックトラック法
8王妃問題
8×8のチェス盤で8個のクイーンを互いに取り合わないで配置する
←全探索は非効率的すぎる
条件を満たすもののみ効率的に列挙する
バックトラック法
- 条件を満たすように王妃をおいていく
- それ以上はおけないとわかったら1手戻してやり直す
はじめは縦列についてのみ検査、横行についての検査、最後に斜めについての検査を入れる