木構造の実装

Transcription

1 汎用的構造と反復子 Algorithms and Data Structures on C

2 この回の要点 汎用的構造とは これまでのリストでは何か問題か? 解決する方法は? 反復子とは 何をするものか? どのように使うか? 実装コード ListNode 型 List 型 ListIterator 型

3 個人情報 PD 型 ( 第 4 回で作成 ) 個人情報 名前 (char *name) 年齢 (int age) リストとしての構造 前の要素 (PD *prev) 次の要素 (PD *next) typedef struct PDtag { struct PDtag *prev; struct PDtag *next; char *name; int age; PD; ListPD 型 PD 型 個人情報のリスト構造 NULL 前 次 前 次 前 次 NULL 太郎 (21) first 次郎 (18) 三郎 (15) last

4 残念なこと データと構造とが混在している 別なデータのリスト構造を使いたいときは もう一度同様な型を書く必要がある リスト構造に対する操作も再度作り直し p1 の前に p2 を接続 insertbefore(pd *p1,pd *p2); p1 の後に p2 を接続 insertafter(pd *p1,pd *p2); pd を削除 remove(pd *pd); など 本来 リスト構造と中のデータは関係ない リストでは数珠つなぎになっていること が重要 データと構造を分離できると便利 構造に対する操作は流用できる

5 これまでのリスト構造 ( 問題あり ) PD 型 ListNodePD 型に変更 リストにつながれることを前提とした個人情報の型 個人情報 ( 名前と年齢 ) の他に前後のリンクを持つ ListPD 型 ListNodePD 型のデータが一列につながった構造 処理 データが個人情報であることが前提 print(list*) 関数で すべての個人情報が表示される

6 リスト内容の表示 (1) /*** *** 個人情報リストのテスト ***/ #include "ListPD.h" TestListPD.cc addtop(lp,makelistnodepd(" 近藤 ",41)); printf("**before** n"); print(lp); remove(lp,pd); printf("**after** n"); print(lp); int main(void){ printf("2 番目は "); ListPD *lp=makelistpd(); print(get(lp,1)); printf(" です n"); この部分 ListNodePD *pd; add(lp,makelistnodepd(" 山田 ",19)); add(lp,pd=makelistnodepd(" 森 ",50)); free(lp); すべての要素を表示する add(lp,makelistnodepd(" 田中 ",23)); print(lp);

7 リスト内容の表示 (2) // 表示 void print(listpd *lp){ ListNodePD *p=lp->first; printf("listpd:(%d): n",lp->size); for(int i=1;p;p=p->next,i++){ printf("%d:",i); print(p); printf(" "); printf(" n"); ListPD.cc 先頭のノードから始めて 次々にノードをたどりながら そのノードを表示する 要素の反復が関数の中で行われている

8 リスト内容の表示 (3) // 個人情報を表示する void print(listnodepd *pd){ printf("%s(%d)",pd->name,pd->age); ListNodePD.cc 個人情報として表示する $ ListTestPD ListPD:(3): 1: 山田 (19) 2: 森 (50) 3: 田中 (23) **before** ListPD:(4): 1: 近藤 (41) 2: 山田 (19) 3: 森 (50) 4: 田中 (23) **after** ListPD:(4): 1: 近藤 (41) 2: 山田 (19) 3: 田中 (23) 2 番目は山田 (19) です

9 問題点は? リストをたどる目的は表示だけではない 全員の点数を +5 点したい 鹿児島市内に居住する人の名前を表示したい 20 歳の人にメールを出したい すべてのインベーダとの衝突判定をしたい その都度 print() と同様な関数を書く? 非効率的 データ構造の内部に立ち入ることになる 汎用性の低下

10 リスト構造の見直し 中に入っているデータには興味はない 順に並んでいることが本質 データとして void* を持てば 何でも入れられる 最小限持つべき機能 リストの先頭や末尾に要素を追加できる 要素を取り出すことができる 要素を削除できる List 型 NULL 要素数がわかる ListNode 型 前 次 前 次 汎用的リスト構造 前 次 NULL void* first void* void* last

11 新しいリスト構造 List データ型は構造とデータを分離 リンクノードを表す ListNode 型 構造 ( 前後の腕 ) はそのまま データは void* のポインタ リンクリストを表す List 型 先頭要素 first 末尾要素 last 要素数 size 反復子 ListIterator 型 リストの中の要素を次々に取り出すための型 ListIterator void* first last ListNode void* ListNode void* ListNode void* ListNode void* ListNode void*

12 反復子 (Iterator) とは ある構造の中のデータを順に取り出す仕組み for 文でループを組むのと似ている データそのものを取り出すので どんな処理でも可能 使用方法 1. 反復子を生成する 2. ループ条件で反復子が次の要素を持つかどうかをチェック 3. 次の要素を持つなら それを取り出して処理する 疑似コード Iterator it=makeiterator(set); while(hasnext(it)){ data *d=next(it); // d を処理 set の中の要素の反復子を生成する 次の要素がある間 要素を取り出して処理する

13 ListNode.h #ifndef ListNode h #define ListNode h /*** *** 双方向リンクリストのノード ***/ #include <stdio.h> #include <stdlib.h> // ノード型 typedef struct ListNodeTag { struct ListNodeTag *prev,*next; void *data; 実際のデータ ListNode; // プロトタイプ宣言 ListNode *makelistnode(void*); void free(listnode*); void insertbefore(listnode*,listnode*); void insertafter(listnode*,listnode*); void remove(listnode*); void *get(listnode*); #endif // ListNode h

14 ListNode.cc /*** *** ListNode の実装 ***/ #include "ListNode.h" 入れるデータは // 生成 ListNode *makelistnode(void *d){ void* 型 ListNode *n=(listnode*)malloc(sizeof(listnode)); n->data=d; return n; // 破棄 void free(listnode *n){ if(n->data) free(n->data); free((void*)n); 続く

15 ListNode.cc // 前に挿入 void insertbefore(listnode *n1,listnode *n2){ if(n1==null n2==null) return; if(n1->prev) n1->prev->next=n2; n2->prev=n1->prev; n2->next=n1; n1->prev=n2; // 次に挿入 void insertafter(listnode *n1,listnode *n2){ if(n1==null n2==null) return; if(n1->next) n1->next->prev=n2; n2->prev=n1; n2->next=n1->next; n1->next=n2; 続く

16 ListNode.cc // 取り外す void remove(listnode *n){ if(n==null) return; if(n->prev) n->prev->next=n->next; if(n->next) n->next->prev=n->prev; n->prev=n->next=null; // データを取り出す void *get(listnode *n){ return n->data;

17 List.h #ifndef List h #define List h /*** *** リスト ***/ #include "ListNode.h" // リスト型 typedef struct { ListNode *first,*last; int size; List; // プロトタイプ宣言 List *makelist(); void free(list*); void addtop(list*,void*); void add(list*,void*); void remove(list*,void*); void *getfirst(list*); void *getlast(list*); void *get(list*,int); int getsize(list*); #endif // List h

18 List.cc /*** *** List の実装 ***/ #include "List.h" // 生成 List *makelist(){ List *l=(list*)malloc(sizeof(list)); l->first=l->last=null; l->size=0; return l; // 破棄 // 中の要素も破棄する void free(list *l){ ListNode *n=l->first,*nn; while(n){ nn=n->next; free(n); n=nn; free((void*)l); 続く

19 List.cc // 先頭に追加 void addtop(list *l,void *d){ ListNode *n=makelistnode(d); if(l->first==null) l->first=l->last=n; else{ insertbefore(l->first,n); l->first=n; l->size++; // 末尾に追加 void add(list *l,void *d){ ListNode *n=makelistnode(d); if(l->last==null) l->first=l->last=n; else{ insertafter(l->last,n); l->last=n; l->size++; データは void* データは void* 続く

20 List.cc // データ d のノードを取り出す ( 線形探索 ) 内部使用のみ ListNode *find(list *l,void *d){ for(listnode *n=l->first;n;n=n->next) if(get(n)==d) return n; return NULL; // リストから取り外す void remove(list *l,void *d){ ListNode *n=find(l,d); if(n==l->first) l->first=l->first->next; if(n==l->last) l->last=l->last->prev; if(n) remove(n); l->size--; データは void* データは void* // i 番目の要素 void *get(list *l,int i){ ListNode *n=l->first; for(int j=0;j<i && n;j++) n=n->next; return (n)?get(n):null; // 要素数 int getsize(list *l){ return l->size;

21 ListIterator.h #ifndef ListIterator h #define ListIterator h /*** *** リストの反復子 ***/ #include "List.h" // 反復子型 typedef struct { List *list; ListNode *next; ListIterator; // 反復対象のリスト // 次に返すノード // プロトタイプ宣言 ListIterator *makelistiterator(list*); void free(listiterator*); ListNode *hasnext(listiterator*); void *next(listiterator*); データは void* #endif // ListIterator h

22 ListIterator.cc /*** *** ListIterator の実装 ***/ #include "ListIterator.h" // 生成 ListIterator *makelistiterator(list *l){ ListIterator *it=(listiterator*)malloc(sizeof(listiterator)); it->list=l; it->next=null; // 反復未開始状態 return it; // 破棄 void free(listiterator *it){ free((void*)it); 続く

23 ListIterator.cc // 次の要素があるか // 次の要素がないときはNULLが返る ListNode *hasnext(listiterator *it){ if(it->next==null) // 反復未開始なら return it->next=it->list->first; // 先頭要素 return it->next=it->next->next; // そうでないなら次の要素 // 次の要素 void *next(listiterator *it){ return get(it->next);

24 PD.h #ifndef PD h #define PD h /*** *** 個人情報 ***/ #include <stdio.h> #include <stdlib.h> #include <string.h> // 個人情報型 typedef struct { char *name; int age; PD; 前後の腕がない! // プロトタイプ宣言 PD *makepd(const char*,int); PD *makepd(char*,int); void free(pd*); void print(pd*); #endif // PD h

25 PD.cc /*** *** PD の実装 ***/ #include "PD.h" // 生成 PD *makepd(const char *n,int a){ return makepd((char*)n,a); PD *makepd(char *n,int a){ PD *pd=(pd*)malloc(sizeof(pd)); int l=strlen(n); pd->name=(char*)malloc(l+1); strcpy(pd->name,n); pd->age=a; return pd; 続く

26 PD.cc // 破棄 void free(pd *pd){ free(pd->name); free((void*)pd); // 表示 void print(pd *pd){ printf("%s(%d)",pd->name,pd->age);

27 TestList.cc /*** List のテスト ***/ #include "PD.h" #include "List.h" #include "ListIterator.h" // 全部のデータを表示する void print(list *list){ printf("list(%d): n",getsize(list)); int i=1; for(listiterator *it=makelistiterator(list);hasnext(it);i++){ PD *pd=(pd*)next(it); printf("%d:",i); print(pd); printf("-"); printf(" n"); 続く

28 TestList.cc int main(void){ List *list=makelist(); PD *pd; add(list,makepd(" 山田 ",21)); add(list,pd=makepd(" 斎藤 ",34)); add(list,makepd(" 森 ",50)); addtop(list,makepd(" 近藤 ",18)); add(list,makepd(" 山下 ",33)); printf("*** Before *** n"); print(list); remove(list,pd); printf("*** After *** n"); print(list); pd=(pd*)get(list,2); printf("2 番は ");print(pd);printf(" です "); free(list);

29 TestList の実行結果 $ TestList *** Before *** List(5): 1: 近藤 (18)-2: 山田 (21)-3: 斎藤 (34)-4: 森 (50)-5: 山下 (33)- *** After *** List(4): 1: 近藤 (18)-2: 山田 (21)-3: 森 (50)-4: 山下 (33)- 2 番は森 (50) です

30 課題 次ページは 20 人分の名前と 4 科目の点数である 名前と 4 科目の点数を持つデータ型 PScore を作り それを List に入れて 科目ごとの上位 3 名の名前と点数を出力するプログラム PScoreTop3.cc を示せ (PScore は PD を参考に作ること ) 作成方法 : 作成した 3 つのコード PScore.h,PScore.cc,PScoreTop3.cc をワードに添付して示すこと 実行結果も示すこと 提出方法 : メールで メールの本文中にも学籍番号を氏名を明記すること 提出先 :fuchida@ibe.kagoshima-u.ac.jp メールタイトル : アルゴリズム課題 厳守! 期限 :2017 年 11 月 26 日 ( 日 ) 24:00

31 成績データ (CSV 形式 ) pscore-data.csv Luke,79,80,91,67 Conrad,60,88,89,97 Cecil,74,70,72,60 Percival,60,64,99,96 Nicholas,71,79,61,65 Andy,60,82,62,84 Ernest,77,80,75,70 Le Roy,98,78,77,60 Marcus,89,63,65,65 Lew,78,89,87,69 Boniface,84,70,63,69 Robert,76,94,98,92 Ewan,82,90,71,84 Guinnens,82,62,84,72 Rex,77,84,80,78 Duke,60,66,76,83 Stephan,67,62,60,87 Clifton,84,85,82,75 Tecwen,74,73,79,67 Adele,81,74,96,85