ロビーサーバーとネットワークに使われるデータ構造の構築ノードライブラリとキューの構築 04a1016 大嶽優データ構造論 ► データ構造とは、使用するデータの形態を定義し、扱う方法という意味である。 ► サーバーでは多くのデータが行き来し、管理しなくてはならないので効率的なデータ構造が必要不可欠である。連結リストとノード Node1 Node2 link Node3 link Node4 link Node5 link ・データが連結されて、鎖のようにつながったものを定義します・ノードはデータの最小最小単位であり、リンクでつながれているとします。・メモリ構造ではなくそれぞれに付加されたアドレスによって連結される。スタックとキュー s4 s3 ●スタック LIFO(last Input First Out)構造 s2 s1 s4 s3 s2 s1 ●キュー FIFO(First Input First Out)構造ノードライブラリ struct NODE { void int NODE NODE }; *data; size; *prv; *next; date:データの内容 size:データのサイズ、チェックなどに使える prv:前のノードのポインタ next:後のノードのポインタノード生成ノードにメモリ割り当てノードがNULLか N ノード初期化次のノードとリンク前のノードノードリターン Y 終了ノードを連結から取り出す Y 前と次のノードがNULLか？終了 N 前のノードがNULLか？ Y N Prvの次のノードにNextを連結一番前のノードを検索 NEXTノードが NULLか？ N NextのPrvに連結一番前のノードをリターン Y ノードの間に1つのノードを挿入 Y 引数ノードのNEXT, PrvをNULLに指定前のノードが NULLか？ N 次のノードに前のノードの NEXTを指定前のノードのNEXTに引数ノードを指定 Y 次のノードが NULLか？ N 次のノードのPRVに引数ノードを指定引数ノードのNEXTに次のノードを指定引数ノードのPrvに前のNEXTを指定キューライブラリキューの設計 struct QUEUE { NODE NODE int }; *head; *tail; count; Head:キューの連結リストの先頭のノードへのポインタ Tail:末尾のノードへのポインタ Int:ノードの個数（誤り検出用キューのリセット関数キューがNULLか？終了ＮＹキューカウンタ＞０か？キューの先頭が NULLか？ＹＮ次のノードを先頭ノードのＮｅｘｔに指定キューカウンタを0に指定先頭ノードリセット終了Ｎ先頭ノード解除キューカウンタ＜０ならばＹキューの先頭をＮｅｘｔにキューカウンタ＝０キューカウンタ-1 終了キューの末尾をＮＵＬＬ指定キューに1つのノードを挿入Ｎキューの末尾と先頭がＮＵＬＬか？キューの末尾がＮＵＬＬではなく、先頭がＮＵＬＬか？キューの末尾のノード検索Ｙキューの先頭ノード検索Ｎノード生成ＹノードがＮＵＬＬか？終了ＮＹキューの先頭がＮＵＬＬか？ＮＮデータがあるか？Ｙノードにデータコピーキューカウンタ＋＋生成されたノードを先頭に指定ノードのデータをＮＵＬＬに指定キューの最初のノードをピックＹキューがＮＵＬＬか？終了Ｎノードの戻り値にキューの先頭を指定Ｎキューの先頭がＮＵＬＬか？Ｙノードの戻り値は先頭ノード、キューの先頭は戻り値を指定Ｙノードの戻り値がＮＵＬＬか？ＮＹキューの末尾と先頭をＮＵＬＬに指定キューの末尾がノードの戻り値か？Ｎキューカウンター１ノードリターンキューの先頭ノード指定動作テスト ► キューから先頭ノードをピックする関数とデータをピックする関数をテストする。 ► 1000000個のデータを格納し、110000個のデータを出力する。 ► 正確性を確かめるためにテキストデータで出力し、確認する。まとめ ► データ構造は、考えは簡単だが設計するとなると構造化や一般化が非常に難しいことがわかった。 ► ポインタを多用するため、十分なテストを行わないと思いがけないエラーが出てくる可能性がある。 ► 今回のライブラリを生かせるようなデータベースとの連携をする方法も考えたい。