====== リスト構造 ====== ハッシュテーブルを作る際に、ハッシュ値が被った時の処理を考えると、\\ 自由に要素を追加可能なデータ構造が欲しくなるよね\\ こんなかんじの list[0]:〇→〇 list[1]:〇→〇→〇 list[2]:〇 list[3]:〇→〇 list[4]:〇→〇→〇 list[5]:〇 list[6]:〇→〇 list[7]:〇 そうだ、そんなときはリスト構造を使おう！\\ リスト構造は、データをアドレスでつないだ構造をしています。\\ 一番オーソドックスなリスト構造（単方向リスト）\\ h:head\\ t:tail\\ 　[ h ]→ [ 1 ]→ [ 3 ]→ [ 5 ]→ [ 7 ]→ [ t ]\\ \\ データ単体は以下のような形になります。\\ 118　　　　　　　アドレス　　 [ 9 ]→NULL [ データ値]→NULL 　　　　　　　　　　　　　　　↑Next（次のデータのアドレス、初期値はNULL） * NULL: * 何も指さないアドレス。数値みたいに0とかで初期化しようと思っても、0番地にもデータが入ってるかもしれないので、0は使えない。。。 * そのために、どこにも属してないよってアドレスを表すものが必要。ってことで用意されたのがNULL リスト型のデータを1個だけ作ると、どこかのアドレスにこんな感じのデータが１個作られます。\\ アドレス　　 [ データ値]→NULL 　　　　　 ↑Next（次のデータのアドレス、初期値はNULL） たとえば、アドレス0x022にデータが作られて、データ値を3で初期化して使おうとすると以下のようになります。\\ 値は 022　　 [ 3 ]→NULL 　　　　　 ↑Next（次のデータのアドレス、初期値はNULL） ---- ここから書きかけ 　head:ヘッド（データがここからつなっていく、「はじめ」を表すデータのアドレス） tail:テール（データの終わりを表すでーたのアドレス） 　データ：　アドレス部　データ部 ネクス部 でできているよ 　　アドレス部：データ自身のアドレス 　　　データ部：格納したい値 　　ネクスト部：次のデータのアドレス 　整数 [ 1,3,5,7 ] がリストになっているイメージ 　h→1→3→5→7→t アクセス法 　①headのデータアドレスを取得 ②headのnextを見る（最初のデータにアクセスできる） 　③nextのデータのnextを見る（次のデータにアクセスできる） 　④　… 　⑤nextがtailになったらそれ以上データはないよ 　 　今見ているアドレスを変数にしてたどっていく 031 013 A15 FF2 109 BAD アドレス（16進） 　[ h ]→ [ 1 ]→ [ 3 ]→ [ 5 ]→ [ 7 ]→ [ t ] 013 A15 FF2 109 BAD 　 ↑iterator 　Crr = head if(Crr.next != tail) Crr = Crr.next if(crr.data == 5)5の時の処理 データの追加 031 013 A15 FF2 109 BAD アドレス（16進） 　[ h ]→ [ 1 ]→ [ 3 ]→ [ 5 ]→ [ 7 ]→ [ t ] 013 A15 FF2 109 BAD 　headとtailのアドレスは知っているとき、 　リスト構造のデータを用意 整数データ 9 を追加 　 118 　[ 9 ]→NULL (NULLはどこにもつながっていないよというアドレス（数値でいう0）） 　nextがtailになっているデータにつなぐ！ if(Crr.next == tail) Crr.next = 118 (Crr:109 Crr.next:118) Crr = Crr.next (Crr:118 Crr.next:NULL) Crr.next = tail (Crr:118 Crr.next:tail) ==== リスト構造の種類 ==== 呼ばれ方\\ ネットを見るといろいろ表記ゆれがありますが、基本的に以下のものは同じリスト構造を指します。\\ *リスト構造 *リンクリスト *リンクトリスト *連結リスト *リスト リスト構造の種類\\ * 単方向リスト * リンクの方向が一方向に決まっているもの * 前方リンクと後方リンクがある * 単方向循環リスト * リンクの最後のデータと最初のデータが円環状につながっているもの、一方向にしかたどれない * 前方リンクと後方リンクがある * 双方向リスト * リンクの方向が前後方向のもの、データをたどるときに1個前と1個先のデータへリンクされている * 双方向循環リスト * 循環リスト ==== 配列VSリスト ==== 配列とリストの違い ==== イテレータを使って、nextのデータにアクセスしていくソースコード ==== #include #include using std::cout; using std::cin; using std::endl; using std::list; //STLのlistを使うよっていうinclude //テンプレート（いろんな方に対応できる便利な奴） int main() { //intのリストを作りたいな list ilist; //floatのリストを作りたいな //list flist; int indata; do{ cout << "整数を入力："; cin >> indata; if(indata != -1) ilist.push_back(indata); else break; }while(true); list::iterator theI = ilist.begin(); cout << *theI << endl; //*theI theIのアドレスの中身のデータを取り出す theI = std::next(theI); //theI++ cout << *theI << endl; //cout << ilist[2] << endl; ランダムアクセスはできん！ }