データ構造と アルゴリズム 第五回 知能情報学部 新田直也
連結リスト(復習) 各要素がリンクでつながっているリスト n番目の要素には先頭からn回リンクをたどらなければたどり着かない． 先頭 5 2 7 3 11 5 2 7 3 11 5 2 7 3 11 5 2 7 3 11
連結リストによるリストの実装(復習) read, write: O(n) insert: O(n) delete: O(n) 先頭 5 2 3 11 7 先頭 5 2 7 3 11
連結リストのプログラム(1) C言語での実装には構造体とポインタを用いる． Webページを考えて見ればよい． Javaではクラスとその参照だけで実装できる． Webページを考えて見ればよい．
連結リストのプログラム(2) struct CELL { int value; struct CELL *next; } 内容 1ページに相当 (構造体) 次ページのアドレス (ポインタ) CELL value next
連結リストのプログラム(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
連結リストのプログラム(4) 先頭の要素を示すポインタ(リンク): ポインタを使ったアクセス: struct CELL *header; *((*header).next) header (*header).value (*header).next (*(*header).next).value (*(*header).next).next
連結リストのプログラム(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
連結リストの 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は? 新しいページのURLを r とすると… r->next = p->next; p->next = r; p *p *(p->next) p->value p->next
連結リストの 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) deleteは? 削除ページの直前のページのURLを p とすると… p->next = (p->next)->next; p *p *(p->next) p->value p->next (p->next)->next
連結リストの delete (2) リンクを切っただけではページは削除されない．ページ自体を削除するには? → free 関数 void free(void *p); p から始まるメモリを解放する． r = (p->next)->next ; free(p->next); p->next = r;