データ構造（Data Structures）
データ構造（Data Structures）とは
セル(cell)の集合にある構造を与えたもの
セル(cell)とは
データを格納する基本単位（最小単位）、「要素」ともいう
ポインタ（pointer）とは
ポインタには、データのメモリ上の場所を示すアドレスが格納されている。アドレス値が入っていないポインタをヌルポインタという
ヌルポインタ（null pointer）
アドレス値０のポインタ、何もさしていない
リスト（list）
リスト（list）とは
セルが０個以上連結されたデータ構造
リストには、配列と連結リストがある（注意 「リスト＝連結リスト」 と説明される場合が多い）
配列(array)
データがメモリ上連続して格納されている。
連結リスト(linked list)
データがポインタによりつながっており、メモリ上はバラバラに格納されている。
連結リスト 要素（セル）へのアクセス
例 データＣをアクセスする
先頭からポインタをたどってデータＣをアクセスする（順番にアクセスすることからシーケンシャルアクセスという）
配列 要素（セル）へのアクセス
例 データＣをアクセスする
要素番号（添え字）でアクセスするため、1回の命令でアクセスできる（このようなアクセスをランダムアクセスという）
連結リスト 要素（セル）の挿入と削除
例 データAとデータBの間にデータCを挿入する
プログラムではデータの数に関係なく、次の2行で処理できる
- データAのポインタを、データＣのアドレスで置き換える
- データＣのポインタを、データＢのアドレスで置き換える
例 以下のリストからデータBを削除する
プログラムではデータの数に関係なく、次の2行で処理できる
- データAのポインタを、データＣのアドレスで置き換える
- データＢのポインタを、ヌルポインタで置き換える
配列 要素（セル）の挿入と削除
例 データAとデータＢの間にデータＦを挿入する
プログラムでは、
1.データＢから後ろのデータをひとつずつ右側にずらしコピーする（ずらしコピーを行う要素の数だけ命令が実行される）
2.ずらしコピーで空いた場所に、データＦを書き込む
例 データAとデータＢの間にあるデータＦを削除する
プログラムでは、
1.データＢから後ろのデータをひとつずつ左側にずらしコピーする（ずらしコピーを行う要素の数だけ命令が実行される）
2.データＦは、データＢで上書きされる
連結リストの種類
連結リストには、次の3つの種類がある
- 単方向リスト
- 双方向リスト
- 環状リスト
※単方向リストと双方向リストを、線形リストとよぶ
単方向リスト
データを片方にしか、たどれない連結リスト
双方向リスト
データを両方から、たどれる連結リスト
環状リスト
全要素が環状につながっているリスト
例題１ 図は単方向リストを表している。“東京”がリストの先頭であり、そのポインタには次のデータのアドレスが入っている。また、“名古屋”はリストの最後であり、そのポインタには0が入っている。
アドレス150に置かれた“静岡”を、“熱海”と“浜松”の間に挿入する。
例題２ 次のような双方向のポインタをもつリスト構造のデータがある。社員Ｇを社員Ａと社員Ｋの間に追加する。追加後のポインタの値を埋めなさい。
追加前の双方向リストを図で書きなさい
追加後の双方向リストを図で書きなさい
確認問題
１．データ構造（Data Structures）とは、（ a ）の集合にある構造を与えたものである
２．セル(cell)とは、データを格納する（ a ）のことである。
３．（ a ）には、データのメモリ上の場所を示すアドレスが格納されている。
４．アドレス値が入っていないポインタを（ a ）という
５．セルが０個以上連結されたデータ構造を（ a ）という
６．リストには、（ a ）と（ ｂ ）がある（注意 「リスト＝（ ｃ ）」 と説明される場合が多い）
７．配列と連結リストのパフォーマンス比較。セルへのアクセスが高速なのが（ a ）、セルの削除・挿入が高速なのが（ ｂ ）である
８．連結リストには、（ a ）、（ ｂ ）、（ ｃ ）の3種類がある
９．単方向リストの構造を図で書きなさい
１０．双方向リストの構造を図で書きなさい
１１．環状リストの構造を図で書きなさい
基本情報対策問題
１．図は単方向リストを表している。“東京”がリストの先頭であり、そのポインタには次のデータのアドレスが入っている。また、“那須塩原”はリストの最後であり、そのポインタには0が入っている。
アドレス150に置かれた“小山”を、“大宮”と“宇都宮”の間に挿入する。挿入後のポインタの値を記入しなさい。
２．次のような双方向のポインタをもつリスト構造のデータがある。大宮を浦和の次に追加する場合、追加後の表のポインタを埋めなさい。
