第３回 配列とリスト

Transcription

1 連結リスト Algorithms and Data Structures on C

2 この回の要点 連結リストによるリスト 連結リストの構造 連結リストの利点と欠点 C 言語による連結リストの実現 ヘッダファイルによるソースファイルの分割

3 連結リスト (linked list) リストの実現の一種 リストに含まれる各要素をリンクによって連結した構造 リンクとは 他のデータへの参照のこと 各要素は 自分から次のデータへのリンクを持つ その要素が連なった構造が連結リスト 個人データ A さん B さん C さん F さん リンク 参照 名前 年齢 連結リスト D さん NULL E さん

4 連結リストの利点と欠点 利点 データの挿入 削除が簡単 =O(1) サイズが可変 ( メモリの上限はある ) 欠点 要素 k にアクセスするのにリンクをたどる必要がある = O(N) データ以外にリンク分のメモリが必要 挿入 削除

5 双方向連結リスト (double linked list) 前後の要素へのリンクを持つ連結リスト 要素を逆順にたどることが可能 2 つのリンクを持つためのメモリが必要 個人データ () A さん B さん C さん F さん 次へ 前へ 参照 参照 NULL 名前 年齢 双方向連結リスト (List) D さん NULL E さん

6 個人情報型 メンバー next char *name 名前 prev int age 年齢 name *prev,*next 前後のリンク age 関数 * make(const char*,int) の生成 void free(*) の破棄 void insertbefore(*,*) 前に挿入 void insertafter(*,*) 後に挿入 void remove(*) 削除 void print(*) 表示 参照 参照

7 .h #ifndef h #define h /*** *** 個人情報 ***/ #include <stdio.h> #include <stdlib.h> #include <string.h> ヘッダファイルの重複読み込みを回避 // 個人情報型の宣言 typedef struct tag { struct tag *prev,*next; // 前後の個人情報へのリンク char *name; // 名前 int age; // 年齢 ; 続く

8 .h // プロトタイプ宣言 *make(const char *n,int a); void free( *pd); void insertbefore( *pd1, *pd2); // 生成 // 破棄 // pd1 の前に pd2 を接続 void insertafter( *pd1, *pd2); void remove( *pd); void print( *pd); // pd1 の後に pd2 を接続 // pd を取り外す // 表示 #endif // h ここまでが 1 回しか読み込まれない

9 .cc /*** *** の実装 ***/ #include ".h" // 個人情報の生成 *make(const char *n,int a){ *pd=(*)malloc(sizeof()); pd->prev=pd->next=null; pd->name=(char*)malloc(strlen(n)+1); strcpy(pd->name,n); pd->age=a; return pd; // 個人情報の破棄 void free( *pd){ free(pd->name); free((void*)pd); 続く

10 .cc // 個人情報 pd1 の前に個人情報 pd2 を接続 void insertbefore( *pd1, *pd2){ if(pd1==null pd2==null) return; if(pd1->prev) pd1->prev->next=pd2; pd2->prev=pd1->prev; pd2->next=pd1; pd1->prev=pd2; 前に挿入 pd1 pd2 pd1 続く

11 .cc // 個人情報 pd1 の後ろに個人情報 pd2 を接続 void insertafter( *pd1, *pd2){ if(pd1==null pd2==null) return; if(pd1->next) pd1->next->prev=pd2; pd2->prev=pd1; pd2->next=pd1->next; pd1->next=pd2; 後に挿入 pd1 pd1 pd2 続く

12 .cc // 個人情報 pd を取り外す void remove( *pd){ if(pd==null) return; if(pd->prev) pd->prev->next=pd->next; if(pd->next) pd->next->prev=pd->prev; pd->prev=pd->next=null; 削除 pd // 個人情報を表示する void print( *pd){ printf("%s(%d)",pd->name,pd->age);

13 双方向リンクリスト List メンバー *first,*last 先頭と末尾の要素 int size 要素数 関数 List* makellist() 生成 void free(list*) 破棄 void addtop(list*,*) 先頭に追加 void add(list*,*) 末尾に追加 void remove(list*,*) 要素を削除 * get(list*,int) 取り出し int getsize(list*) 要素数 void print(list*) 表示 first last

14 List.h #ifndef List h #define List h /*** *** 個人情報のリスト ***/ #include ".h" // 個人情報リスト型の宣言 typedef struct { *first,*last; int size; List; ヘッダファイルの重複読み込みを回避 // 先頭と末尾の要素 // 要素数 続く

15 List.h List *makelist(); // 個人情報リストの生成 void free(list *lp); // 個人情報リストの破棄 void addtop(list *lp, *pd); // リストlpの先頭に個人情報 pdを挿入 void add(list *lp, *pd); // リストlpの末尾に個人情報 pdを追加 void remove(list *lp, *pd); // リストlpの要素 pdを削除 *get(list *lp,int n); // n 番目の要素を得る ( 先頭は0 番 ) int getsize(list *lp); // 要素数 void print(list *lp); // 表示 #endif // List h

16 List.cc /*** *** List の実装 ***/ #include "List.h" // 個人情報リストの生成 List *makelist(){ List *lp=(list*)malloc(sizeof(list)); lp->first=lp->last=null; lp->size=0; return lp; // 個人情報リストの破棄 void free(list *lp){ free((void*)lp); 続く

17 List.cc // リスト lp の先頭に個人情報 pd を挿入 void addtop(list *lp, *pd){ if(lp->first==null) lp->first=lp->last=pd; else{ insertbefore(lp->first,pd); lp->first=pd; lp->size++; first pd 続く last

18 List.cc // リスト lp の末尾に個人情報 pd を追加 void add(list *lp, *pd){ if(lp->last==null) lp->first=lp->last=pd; else{ insertafter(lp->last,pd); lp->last=pd; lp->size++; first last 続く pd

19 List.cc // 要素 pd を削除 void remove(list *lp, *pd){ if(lp->first==pd) lp->first=pd->next; if(lp->last==pd) lp->last=pd->prev; remove(pd); lp->size--; // n 番目の要素を得る ( 先頭は 0 番 ) *get(list *lp,int n){ *p=lp->first; for(int i=0;i<n && p;i++) p=p->next; return p; 続く first last pd

20 List.cc // 要素数 int getsize(list *lp){ return lp->size; // 表示 void print(list *lp){ *p=lp->first; printf("list:(%d): n",lp->size); for(int i=1;p;p=p->next,i++){ printf("%d:",i); print(p); printf(" "); printf(" n");

21 ListTest.cc /*** *** 個人情報リストのテスト ***/ #include "List.h" int main(void){ List *lp=makelist(); *pd; add(lp,make(" 山田 ",19)); add(lp,pd=make(" 森 ",50)); add(lp,make(" 田中 ",23)); print(lp); 続く

22 ListTest.cc addtop(lp,make(" 近藤 ",41)); printf("**before** n"); print(lp); remove(lp,pd); printf("**after** n"); print(lp); printf("2 番目は "); print(get(lp,1)); printf(" です n");

23 課題 小学校の成績管理をするために 児童の成績データを双方向リンクリストに入れて管理する このとき SeisekiData というクラスはどのような構造にすればよいか 考えて示せ ただし 型のみでよい ( 関数は不要 ) 成績は国語 算数 理科 社会の 4 科目 児童の情報は 学年 クラス 名前 作成方法 : 自分で考えたクラス構造を プログラムコードとしてワード文書内に書くこと ワードのファイル名は scxxxxxx-al docx 提出方法 : メールで メールの本文中にも学籍番号を氏名を明記すること 提出先 :fuchida@ibe.kagoshima-u.ac.jp メールタイトル : アルゴリズム課題 厳守! 期限 :2017 年 10 月 30 日 ( 日 ) 24:00

24 連結リスト 終了