データ構造と
アルゴリズム
第四回
知能情報学部
新田直也
抽象データ型
データ構造とそれを操作するアルゴリズムを外から
見えないように一まとめに（カプセル化）したもの．
データ抽象とも呼ばれる(厳密には異なる概念)．
メーラーソフトで考えてみよう．
受信する
メールを読む
メールを書く
アドレスを登録する
ユーザは操作の種類
(インタフェース)のみを
知っている．
操作の中身（アルゴリズム）や
データの保存形式（データ構造）
を知らなくても使える．
リスト
リスト: 抽象データ型の1つ(データの有限列)
5
7
3 11
リストのインターフェース
2
k番目の位置に要素を追加: insert(k, e)
k番目の位置の要素を削除: delete(k)
k番目の位置の要素を読む: read(k)
k番目の位置の要素に書く: write(k, e)
リストを実装可能なデータ構造は何通りもある．
配列，連結リスト，…
配列によるリストの実装(1)
まずは簡単なものから…
int list[1000];
int num = 0;
int read(int k) {
if (k < num) return list[k];
return ERR;
}
void write(int k, int e) {
if (k < num) list[k] = e;
}
配列によるリストの実装(2)
続き…
void insert(int k, int e) {
if (k <= num) {
for (int n = num - 1; n >= k; n--) {
list[n+1] = list[n];
}
list[k] = e;
num++;
}
}
deleteは…?
リストを配列で実装した場合の計算量
データのサイズ: 配列の要素数(num)．
(最悪)時間計算量
read: 2ステップ → O(1)
write: 2ステップ → O(1)
insert: k が 0 の場合最悪．
(2×num + 3)ステップ → O(num)
void insert(int k, int e) {
if (k <= num) {
for (int n = num - 1; n >= k; n--) {
list[n+1] = list[n];
}
list[k] = e;
num++;
}
}
連結リスト
各要素がリンクでつながっているリスト
先頭
5
2
7
3
11
n番目の要素には先頭からn回リンクをたどらなければた
どり着かない．
5
2
7
3
11
5
2
7
3
11
5
2
7
3
11
連結リストによるリストの実装
read, write: O(n)
insert: O(n)
先頭
5
2
3
11
7
3
7
delete: O(n)
先頭
5
2
11
リストの実装のまとめ
同じ抽象データ型でも内部のデータ構造が変わると操作す
るアルゴリズムもその計算量も変わる．
リストの場合:
リストの
配列による
インタフェース 実装
read
O(1)
連結リストによ
る実装
O(n)
write
O(1)
O(n)
insert
O(n)
O(n)
delete
O(n)
O(n)
連結リストのプログラム(1)
C言語での実装には構造体とポインタを用いる．
Javaではクラスとその参照だけで実装できる．
Webページを考えて見ればよい．
連結リストのプログラム(2)
struct CELL {
int value;
struct CELL *next;
}
CELL
value
next
内容
次ページのアドレス
(ポインタ)
1ページに相当
(構造体)
連結リストのプログラム(3)
ポインタの復習:
p がポインタ(アドレス)なら，*p は pが示す先を表す．
*p
p
構造体の復習:
s がメンバ m を持つ構造体なら，s.m は s のメンバ m を示す．
s
s.value
s.next
連結リストのプログラム(4)
先頭の要素を示すポインタ(リンク):
struct CELL *header;
ポインタを使ったアクセス:
*header
*(*header).next
header
(*header).value
(*header).next
(*(*header).next).value
(*(*header).next).next
連結リストのプログラム(5)
リストの最後は?
next が何も指さない(NULL)．
リストを順に表示するプログラム:
struct CELL *header;
for (p = header; p != NULL; p = (*p).next ) {
printf(“%d\n”, (*p).value);
}
略記法：
(*p).next は p->next と書ける．
( (*p).value も同様．)
© Copyright 2024 ExpyDoc
