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