プログラミング演習 Ⅲ Linked List P. Ravindra S. De Silva e-mail: ravi@cs.tut.ac.jp, Room F-413 URL: www.icd.cs.tut.ac.jp/~ravi/prog3/index_j.html
連結リストとは? 一つひとつの要素がその前後の要素との参照関係をもつデータ構造 A B C D 連結リストを使用する利点 - 通常の配列はサイズが固定されている : データの挿入や削除をしたいときはデータを移動させる必要がある 連結リストならば必要なサイズ分だけ追加することができる : 挿入や削除をしてもデータを移動させる必要はない Page 2
単方向リスト 単方向リストは 連続ノードからなるデータ構造の基本的な概念である 各ノードは次を格納する 要素 次のノードへのリンク 要素 次 ノード A B C D Page 3
連結リストの実装 任意のデータフィールド群を持ち 1 つか 2 つの参照 ( リンク ) により次 ( および前 ) のノードを指している struct list { int data; struct list *next; } data next 次を参照するポインタをリンクと呼ぶ どの構造体も後続の領域へ導くリンクでつながる この後続を参照するポインタは メモリ内のそれぞれの場所を示すアドレス または特別な値 NULL を含む Page 4 4
例 struct list { int data; struct list *next; } struct list a, b, c; a.data = 1; b.data = 2; c.data = 3; a.next = b.next = c.next = NULL; a 1 b c NULL 2 NULL 3 NULL データ次データ次データ次 Page 5
例 ( つづき ) struct list { int data; struct list *next; } struct list a, b, c; a.data = 1; b.data = 2; c.data = 3; a.next = b.next = c.next = NULL; a.next = &b; b.next = &c; a 1 b 2 c 3 Page 6
動的メモリ操作 struct node{ int data; struct node *next; }; struct node *ptr; ptr data next ptr = (struct node *) /*type casting */ malloc(sizeof(struct node)); Page 7
Free 操作 関数 free はメモリを解放する - 換言すると メモリをシステムに返すことで 将来的にそのメモリを解放することができる free(ptr); ptr? Page 8
連結リストのノード 例 3 つのデータ領域をもったノード : struct student{ char name[20]; int id; double grdpts; struct student *next_student; } Name id grdpts next_student Page 9
連結リストの基本的な操作 ノードを追加する ノードを削除する ノードを検索する リストの走査 : カウント処理や統計的な処理に便利 Page 10
空の連結リストにノードを追加する pnew phead 処理前 : 39 pnew -> next = phead; // リンクを設定 NULL phead = pnew;// point list to first node ppre 処理後 : pnew 39 phead ppre Page 11
連結リストの先頭にノードを追加する 処理前 : pnew 39 phead 75 124 処理後 : ppre pnew -> next = phead; phead = pnew; // 先頭ノードのリストを参照 pnew 39 phead 75 124 ppre Page 12
連結リストの中間にノードを追加する 処理前 : pnew 64 pnew -> next = ppre -> next; ppre -> next = pnew; 55 124 ppre 処理後 : pnew 64 ppre 55 124 Page 13
連結リストの終端にノードを追加する 処理前 : pnew 144 pnew -> next = NULL; ppre -> next = pnew; 55 124 ppre 処理後 : pnew 144 ppre 55 124 Page 14
連結リストにノードを挿入する 先頭 (phead) と前 (ppre) のポインタを与えて データが挿入される (item). 新しいノードのためのメモリが確保され (pnew) リンクが適切につながる Page 15 // 連結リストにノードを挿入する struct node *pnew; pnew = (struct node *) malloc(sizeof(struct node)); pnew -> data = item; if (ppre == NULL){ // 先頭ノードの前に追加するもしくか空の場合 pnew -> next = phead; phead = pnew; } else { // 中間か終端に追加する pnew -> next = ppre -> next; ppre -> next = pnew; }
連結リストからノードを削除する いくつかのリンクを変更しリストからノードを理論的に取り除くことで リストから物理的にノードを削除することができる リスト中の任意のノードを削除することができる リスト中のノードを削除して空のリストとなった場合は 先頭ポインタはヌルに設定される 理論的にノードを削除する : 消したいノード (pcur) とその前にあるノード (ppre) を考える. 前のノードのリンクの指し示すノード (ppre->next) を, 消したいノードの次のノード (pcur -> next) にする. free 関数を使って消したノードの領域を解放する. Page 16
連結リストから一番目のノードを削除する 処理前 : phead = pcur -> next; free(pcur); phead 75 124 ppre pcur 処理後 : phead Recycled 124 ppre pcur Page 17
連結リストからノードを削除する 一般的な場合 処理前 : 75 96 124 ppre -> next = pcur -> next; free(pcur); ppre pcur 処理後 : Recycled 75 124 ppre pcur Page 18
連結リストからノードを削除する ノードの先頭 (phead), 消したいノード (pcur), 消したいノードの一つ前のノード (ppre) を用意する.pCur を消し,pCur の為に確保された領域を解放するという処理は, 以下のようになる. // 連結リストからノードを削除する if (ppre == NULL) // リストの最初のノードだった場合の削除 phead = pcur -> next; else // リストの最初のノード以外の場合の削除 ppre -> next = pcur -> next; free(pcur). Page 19
連結リストの検索 連結リストの挿入や削除の操作はどちらも, 特定の, 挿入先のノードや消したいデータに一致するノードを検索しなければならない. // 連結リストからノードを検索する ppre = NULL; pcur = phead; // 目的の値が見つかるまで あるいはデータの終端にたどり着くまで繰り返す while (pcur!= NULL && pcur -> data!= target) { ppre = pcur; pcur = pcur -> next; } // 目的の値が見つかったら あるいはデータの終端に来たらどうするか if (pcur!= NULL) found = 1; else found = 0; Page 20
連結リストの走査 リストの走査はリストにある全てのデータを処理する. したがって, 全てのノードにあるデータは処理される. // 連結リストの走査 Struct node *pwalker; pwalker = phead; printf( リストに含まれているのは : n ); while (pwalker!= NULL){ printf( %d, pwalker -> data); pwalker = pwalker -> next; } Page 21
Page 22 応用
多項式 一つの連結リストで表される多項式 以下の多項式を表現したい em em A( x) = a x + a x +... + a x 1 2 0 m 1 m 2 0 e 以下のような 0 でない係数 a i と負でない乗数 e i の場合 e m-1 > e m-2 > > e 1 > e 0 0. それぞれの項を係数と乗数, 次の項へのポインタを含むノードとして表す. Page 23
宣言 typedef struct poly_node *poly_pointer; typedef struct poly_node { int coef; int expon; poly_pointer link; }; poly_pointer a, b, c; em em A( x) = a x + a x +... + a x 1 2 0 m 1 m 2 0 e Page 24 coef expon link
例 : 多項式を表現する a 14 8 a = 3x + 2x + 1 3 14 2 8 1 0 null 14 10 6 b = 8x 3x + 10x b 8 14-3 10 10 6 null Page 25
多項式の加算 二つの多項式を足すには, 多項式 a と多項式 b で示されているノードで始まるそれぞれの項を調べる. 二つの項の乗数が等しい場合, 二つの係数を足し, 結果の多項式に新しい項を作る. 今調べている a の項の乗数が,b の項の乗数よりも少ない場合,b の項を複製し, 結果の多項式に加える. そして,b の項を次の項へ進める.(a->expon > b->expon の場合も, 同様に行う.) Page 26
例 : 多項式の加算 (a) a->expon == b->expon 3 14 2 8 1 0 a 8 14-3 10 10 6 b 11 14 d a->expon == b->expon Page 27
例 : 多項式の加算 (b) a->expon < b->expon 3 14 2 8 1 0 a 8 14-3 10 10 6 b 11 14-3 10 d a->expon < b->expon Page 28
例 : 多項式の加算 (c) a->expon > b->expon 3 14 2 8 1 0 a 8 14-3 10 10 6 11 14-3 10 2 8 b a->expon > b->expon Page 29
サンプルコード Program 4.10 : 2 つの多項式を加算する poly_pointer padd(poly_pointer a, poly_pointer b) { poly_pointer front, rear, temp; int sum; rear =(poly_pointer)malloc(sizeof(poly_node)); if (IS_FULL(rear)) { fprintf(stderr, The memory is full n ); exit(1); } front = rear; while (a && b) { switch (COMPARE(a->expon, b->expon)) { Page 30
サンプルコード ( つづき ) case -1: /* a->expon < b->expon */ attach(b->coef, b->expon, &rear); b= b->link; break; case 0: /* a->expon == b->expon */ sum = a->coef + b->coef; if (sum) attach(sum,a->expon,&rear); a = a->link; break; b = b->link; case 1: /* a->expon > b->expon */ } } attach(a->coef, a->expon, &rear); a = a->link; for (; a; a = a->link) attach(a->coef, a->expon, &rear); for (; b; b=b->link)attach(b->coef, b->expon, &rear); rear->link = NULL; temp = front; front = front->link; free(temp); return front; } Page 31
サンプルコード for (; a; a = a->link) attach(a->coef, a->expon, &rear); for (; b; b=b->link)attach(b->coef, b->expon, &rear); rear->link = NULL; temp = front; front = front->link; free(temp); return front; } 余分な先頭ノードを削除する Page 32