プログラム再構成に関する特許申請について

データ構造と
アルゴリズム
第五回
知能情報学部
新田直也
連結リスト(復習)

各要素がリンクでつながっているリスト
先頭
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
連結リストのプログラム(1)

C言語での実装には構造体とポインタを用いる．


Javaではクラスとその参照だけで実装できる．
Webページを考えて見ればよい．
連結リストのプログラム(2)
struct CELL {
int value;
struct CELL *next;
}
CELL
value
next
内容
次ページのアドレス
(ポインタ)
1ページに相当
(構造体)
連結リストのプログラム(3)

ポインタの復習:

p がポインタ(アドレス)なら，*p は pが示す先を表す．
*p
<html>
<body>
<H1>5</H1>
<A HREF=“…”>次へ</A>
</body>
</html>
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)．
リストを順に表示するプログラム:
p
*p
(*p).value
struct CELL *header;
(*p).next
struct CELL *p;
for (p = header; p != NULL; p = (*p).next ) {
printf(“%d\n”, (*p).value);
}

略記法：

(*p).next は p->next と書ける．
( (*p).value も同様．)
連結リストの read, write

read と write
struct CELL *header;
int read(int n) {
struct CELL *p;
p = header;
for (; n > 0; n--) {
if (p == NULL) {
return ERR;
}
p = p->next;
}
return p->value;
}
struct CELL *header;
void write(int n, int e) {
struct CELL *p;
p = header;
for (; n > 0; n--) {
if (p == NULL) {
return;
}
p = p->next;
}
p->value = e;
}
連結リストの insert (1)

insertは?
p
*(p->next)
*p
p->value
p->next
新しいページのURLを r とすると…
r->next = p->next;
p->next = r;
連結リストの insert (2)

新しいページをどうやって作る? そのURLは?
→ malloc 関数

void *malloc(int n);
n バイトのメモリを確保し，その先頭アドレスを返す．
struct CELL *ｒ;
r = malloc(sizeof(struct CELL));
CELL構造体1つ分のメモリサイズ
連結リストの insert (3)

insert
void insert(int n, int e) {
struct CELL *p;
struct CELL *r;
r = malloc(sizeof(struct CELL));
r->value = e;
if (n == 0) {
r->next = header;
header = r;
} else {
n--;
p = header;
for (; n > 0; n--) {
if (p == NULL) return;
p = p->next;
}
r->next = p->next;
p->next = r;
}
}
連結リストの insert (4)

バグを含んだ insert
void insert(int n, int e) {
struct CELL *p;
struct CELL c;
c.value = e;
if (n == 0) {
c.next = header;
header = &c;
} else {
n--;
p = header;
for (; n > 0; n--) {
if (p == NULL) return;
p = p->next;
}
c.next = p->next;
p->next = &c;
}
}
復帰時に c が消えてしまう！
連結リストの delete(1)

p
deleteは?
*(p->next)
*p
p->value
p->next
(p->next)->next
削除ページの直前のページのURLを p とすると…
p->next = (p->next)->next;
連結リストの delete (2)

リンクを切っただけではページは削除されない．
ページ自体を削除するには?
→ free 関数

void free(void *p);
p から始まるメモリを解放する．
r = (p->next)->next ;
free(p->next);
p->next = r;

Download Report