アルゴリズムとデータ構造1 2005年6月17日 酒居敬一([email protected]) http://www.info.kochi-tech.ac.jp/k1sakai/Lecture/ALG/2005/index.html 配列 • 添え字とデータが1対1で対応 • 添え字は連続 1 2 – 添え字が１から始まるとは限らない 3 • データの挿入や削除は面倒 4 … … 添え字を用いてアクセスする（例では３） n 図2.1.1 教科書28ページ データ数nの配列 二次元配列 • 行と列それぞれをインデックスで指し示す １ ３ ・ ・ ・ ・ ・・・ ｍ ・・・・・・・ ２ ４ ３ ・・・・・・・ １ （３，２） 添え字を 用いて データに アクセス ２ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・・・・・・・・・・・・・・・・・ 図2.1.2 教科書29ページ 2次元配列 三次元配列 １ ２ ３ ・・・・ ・・・・・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・・・・・・・・・ １ ２ ３ ・ ・ ・ ｋ ・ ・ ・ ・ ・ ・ ・ ・ ・ ｍ ・ ・ ・ ・ ・ ・ ・ ・ ・ （３，１，１） 添え字を 用いて データに アクセス 図2.1.3 教科書29ページ 3次元配列 配列上の探索 添え字を用いて 直接アクセス 先頭から 順に調べる 直接探索 線形探索 配列上の探索 半分ずつ調べます 1)半分に分ける 2)前半に存在するか調べる 前半にあれば前半について探索 後半にあれば後半について探索 ※探索のためにデータの整列が必要 二分探索 配列へデータの挿入 P-1 P-1 p p P+1 ｐ番目にデータを挿入 P+1 P+2 P+2 P+3 P+3 ・ ・ ・ ・ 隙間を空けて 突っ込みます ・ ・ ・ ・ n n n+1 n+1 配列からデータの削除 P-1 P-1 p p ｐ番目の データを削除 P+1 P+1 P+2 P+2 P+3 P+3 ・ ・ ・ ・ n n+1 ・ ・ ・ ・ 削除してできた 隙間を詰めます n n+1 メモリと配列 • 計算機のメモリは一種の配列である – プロセッサの命令が扱える単位を要素としている • byte, word, dwordのような整数 • float, double, long doubleのような不動小数点数 • qword, dqwordのようなショートベクタ整数 • プログラミング言語による多彩な要素をもつ配列 – プログラミング言語のコンパイラが変換してくれます • 気にしなくてもいいんですが、場合によります… 補足説明 • Javaにはポインタが陽に説明されていない… – 「～への参照」という形でポインタの存在が見える – NullPointerExceptionでも存在がわかる 配列オブジェクト変数 [実はポインタ変数] 配列オブジェクト変数 [実はポインタ変数] 配列オブジェクト変数 [実はポインタ変数] 配列オブジェクト変数 length: 配列の大きさ length: 配列の大きさ 配列本体へのポインタ length: 配列の大きさ 配列本体へのポインタ length: 配列の大きさ 配列オブジェクト 配列本体へのポインタ 配列本体へのポインタ 配列オブジェクト 配列オブジェクト 配列本体 [メモリ上の領域] 配列本体 [メモリ上の領域] 配列本体 [メモリ上の領域] 配列本体 連結リスト • データをそれぞれの要素に格納 • 要素どおし、つながってリストを形成 先頭 データ データ データ 次 次 次 データを動かすことなく、要素の挿入・削除ができる 連結リスト操作（挿入） 先頭 データ データ データ 次 次 次 データ 次 図2.4.1・2.4.2 教科書41・42ページ 単純な連結リスト（線形リスト）データ挿入 連結リスト操作（削除） 先頭 データ データ データ 次 次 次 図2.4.3 教科書43ページ 単純な連結リスト（線形リスト）データ削除 双方向連結リスト • 連結リストを双方にリンクしたもの データ データ データ 先頭 次 次 次 最後 前 前 前 両方向から探索できる 双方向連結リスト（挿入） データ データ データ 先頭 次 次 次 最後 前 前 前 データ 次 前 図2.4.4・2.4.5 教科書44ページ 双方向連結リスト データ挿入 双方向連結リスト操作（削除） データ データ データ 先頭 次 次 次 最後 前 前 前 図2.4.6 教科書45ページ 双方向連結リスト データ削除 スタック（LIFO） プッシュ ポップ スタックポインタ スタックポインタ 図2.2.1・2.2.2・2.2.3 教科書35・36・37ページ スタック構造（プッシュ・ポップ） 待ち行列（FIFO） データ挿入 データ取得 図2.3.1・2.3.2・2.3.3 教科書38・39ページ 待ち行列（データの挿入・取得）
© Copyright 2024 ExpyDoc
