汎用的構造と
反復子
この回の要点
• 汎用的構造とは
• これまでのリストでは何か問題か？
• 解決する方法は？
• 反復子とは
• 何をするものか？
• どのように使うか？
• 実装コード
• ListNode型
• List型
• ListIterator型
個人情報 PD型（第4回で作成）
• 個人情報
• 名前(char *name)
• 年齢(int age)
• リストとしての構造
• 前の要素(PD *prev)
• 次の要素(PD *next)
typedef struct PDtag {
struct PDtag *prev;
struct PDtag *next;
char *name;
int age;
} PD;
太郎（21）
前
次
次郎（18）
前
次
三郎（15）
前
次
NULL
NULL
個人情報のリスト構造
PD型
ListPD型
first
last
残念なこと
• データと構造とが混在
している
• 別なデータのリスト構造を使いたいときは、
もう一度同
様な型を書く必要がある
。
• リスト構造に対する操作も再度作り直し。
• p1の前にp2を接続 insertBefore(PD *p1,PD *p2);
• p1の後にp2を接続 insertAfter(PD *p1,PD *p2);
• pdを削除 remove(PD *pd); など
• 本来、リスト構造と中のデータは関係ない
• リストでは数珠つなぎになっていること、が重要
• データと構造を分離できると便利。
• 構造に対する操作は流用できる。
これまでのリスト構造（問題あり）
• PD型→
ListNodePD型に変更
• リストにつながれることを前提とした個人情報の型
• 個人情報（名前と年齢）の他に前後のリンクを持つ
• ListPD型
• ListNodePD型のデータが一列につながった構造
• 処理
• データが
個人情報である
ことが前提
• print(List*)関数で、すべての
個人情報が表示
される。
リスト内容の表示（1）
/*** *** 個人情報リストのテスト ***/ #include "ListPD.h" int main(void){ ListPD *lp=makeListPD(); ListNodePD *pd; add(lp,makeListNodePD("山田",19)); add(lp,pd=makeListNodePD("森",50)); add(lp,makeListNodePD("田中",23)); print(lp); addTop(lp,makeListNodePD("近藤",41)); printf("**before**¥n"); print(lp); remove(lp,pd); printf("**after**¥n"); print(lp); printf("2番目は"); print(get(lp,1)); printf("です。¥n"); free(lp); }この部分
すべての要素 を表示するTestListPD.cc
リスト内容の表示（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
要素の反復が関数の中で
行われている
リスト内容の表示（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)です。問題点は？
• リストをたどる目的は表示だけではない
• 全員の点数を＋５点したい
• 鹿児島市内に居住する人の名前を表示したい
• 20歳の人にメールを出したい
• すべてのインベーダとの衝突判定をしたい
• ・・・
• その都度、print()と同様な関数を書く？
• 非効率的
• データ構造の内部に立ち入ることになる
• 汎用性の低下
リスト構造の見直し
• 中に入っているデータには興味はない
• 順に並んでいることが本質
• データとして void* を持てば、何でも入れられる
• 最小限持つべき機能
• リストの先頭や末尾に要素を追加できる
• 要素を取り出すことができる
• 要素を削除できる
• 要素数がわかる
void*
前
次
void*
前
次
void*
前
次
NULL
NULL
汎用的リスト構造
ListNode型
List型
first
last
新しいリスト構造
• データ型は
構造とデータを分離
• リンクノードを表す
ListNode型
• 構造（前後の腕）はそのまま
• データは void* のポインタ
• リンクリストを表す
List型
• 先頭要素first
• 末尾要素last
• 要素数size
• 反復子
ListIterator型
• リストの中の要素を次々に
取り出すための型
first →
last →
List
ListIterator
ListNode
void*
ListNode
void*
ListNode
void*
ListNode
void*
ListNode
void*
void*
反復子（Iterator）とは
• ある構造の中のデータを順に取り出す仕組み
• for文でループを組むのと似ている
• データそのものを取り出すので、どんな処理でも可能
• 使用方法
1.
反復子を生成する。
2.
ループ条件で反復子が次の要素を持つかどうかをチェック
3.
次の要素を持つなら、それを取り出して処理する
• 疑似コード
Iterator it=
makeIterator(set)
;
while(
hasNext(it)
){
data *d=
next(it)
;
// dを処理
}
次の要素がある間、
要素を取り出して処理する
setの中の要素の
反復子を生成する
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 実際のデータ
ListNode.cc
/***
*** ListNodeの実装
***/
#include "ListNode.h"
// 生成
ListNode *makeListNode(
void *d
){
ListNode *n=(ListNode*)malloc(sizeof(ListNode));
n->data=d;
return n;
}
// 破棄
void free(ListNode *n){
if(n->data)
free(n->data);
free((void*)n);
}
続く
入れるデータは
void*型
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;
}
続く
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;
}
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
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); }続く
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*
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--; } // 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; }
データはvoid*
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*); #endif // __ListIterator__hデータはvoid*
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);
}
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);
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前後の腕がない！
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; }
続く
PD.cc
// 破棄 void free(PD *pd){ free(pd->name); free((void*)pd); } // 表示 void print(PD *pd){ printf("%s(%d)",pd->name,pd->age); }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"); }
