汎用的構造と反復子

汎用的構造と
反復子
この回の要点
• 汎用的構造とは
• これまでのリストでは何か問題か？
• 解決する方法は？
• 反復子とは
• 何をするものか？
• どのように使うか？
• 実装コード
• ListNode型
• List型
• ListIterator型
個人情報 PD型
• 個人情報
typedef PDtag {
struct PDtag *prev;
struct PDtag *next;
char *name;
int age;
} PD;
• 名前(char *name)
• 年齢(int age)
• リストとしての構造
• 前の要素(PD *prev)
• 次の要素(PD *next)
ListPD型
個人情報のリスト構造
PD型
NULL
前
次
太郎（21）
first
前
次
次郎（18）
前
次
三郎（15）
last
NULL
残念なこと
• データと構造とが混在している
• 別なデータのリスト構造を使いたいときは、もう一度同
様な型を書く必要がある。
• リスト構造に対する操作も再度作り直し。
• p1の前にp2を接続 insertBefore(PD *p1,PD *p2);
• p1の後にp2を接続 insertAfter(PD *p1,PD *p2);
• pdを削除 remove(PD *pd); など
• 本来、リスト構造と中のデータは関係ない
• データと構造を分離できると便利。
• 構造に対する操作は流用できる。
リスト構造の見直し
• 中に入っているデータには興味はない
• 順に並んでいることが本質
• データとして void* を持てば、何でも入れられる
• 最小限持つべき機能
•
•
•
•
リストの先頭や末尾に要素を追加できる
要素を取り出すことができる
要素を削除できる
要素数がわかる
List型
汎用的リスト構造
ListNode型
NULL
前
次
void*
first
前
次
void*
前
次
void*
last
NULL
これまでのリスト構造
• PD型→ListNodePD型に変更
• リストにつながれることを前提とした個人情報の型
• 個人情報（名前と年齢）の他に前後のリンクを持つ
• ListPD型
• PD型のデータが一列につながった構造
• 処理
• データが個人情報であることが前提
• print(List*)関数で、すべての個人情報が表示される。
リスト内容の表示（1）
/***
ListTestPD.cc
*** 個人情報リストのテスト
addTop(lp,makeListNodePD("近藤",41));
***/
printf("**before**¥n"); print(lp);
#include "ListPD.h"
remove(lp,pd);
printf("**after**¥n"); print(lp);
int main(void){
printf("2番目は");
ListPD *lp=makeListPD();
print(get(lp,1));
この部分
printf("です。¥n");
ListNodePD *pd;
freeListPD(lp);
add(lp,makeListNodePD("山田",19));
add(lp,pd=makeListNodePD("森",50));
add(lp,makeListNodePD("田中",23));
print(lp);
}
すべての要素
を表示する
リスト内容の表示（2）
// 表示
ListPD.cc
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");
}
そのノードを表示する
リスト内容の表示（3）
// 個人情報を表示する
ListNodePD.cc
void print(ListNodePD *pd){
printf("%s(%d)",pd->name,pd->age);
}
$ 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()と同様な関数を書く？
• 非効率的
• データ構造の内部に立ち入ることになる
• 汎用性の低下
新しいリスト構造
List
ListNode
first →
void*
• データ型は構造とデータを分離
• リンクノードを表すListNode型
ListNode
void*
• 構造（前後の腕）はそのまま
• データは void* のポインタ
• リンクリストを表すList型
• 先頭要素first
• 末尾要素last
• 要素数size
ListNode
void*
ListIterator
ListNode
void*
• 反復子ListIterator型
• リストの中の要素を次々に
取り出すための型
void*
last →
ListNode
void*
反復子（Iterator）とは
• ある構造の中のデータを順に取り出す仕組み
• for文でループを組むのと似ている
• データそのものを取り出すので、どんな処理でも可能
• 使用方法
1.
2.
3.
反復子を生成する。
ループ条件で反復子が次のようを持つかどうかをチェック
次の要素を持つなら、それを取り出して処理する
• 疑似コード
Iterator it=makeIterator(set);
while(hasNext(it)){
data *d=next(it);
// dを処理
}
反復子を生成する
次の要素がある間、
要素を取り出して処理する
ListNode.h
#ifndef __ListNode__h
#define __ListNode__h
// プロトタイプ宣言
/***
ListNode *makeListNode(void*);
*** 双方向リンクリストのノード
void freeListNode(ListNode*);
***/
void insertBefore(ListNode*,ListNode*);
#include <stdio.h>
void insertAfter(ListNode*,ListNode*);
#include <stdlib.h>
void remove(ListNode*);
void *get(ListNode*);
// ノード型
typedef struct ListNodeTag {
struct ListNodeTag *prev,*next;
void *data;
} 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 freeListNode(ListNode *n){
if(n->data)
free(n->data);
free(n);
}
続く
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
// プロトタイプ宣言
/***
List *makeList();
*** リスト
void freeList(List*);
***/
void addTop(List*,void*);
#include "ListNode.h"
void add(List*,void*);
void remove(List*,void*);
// リスト型
void *getFirst(List*);
typedef struct {
void *getLast(List*);
ListNode *first,*last
void *get(List*,int);
int size
int getSize(List*);
} 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 freeList(List *l){
ListNode *n=l->first,*nn;
while(n){
nn=n->next;
freeListNode(n);
n=nn;
}
free(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++;
}
続く
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; }
ListIterator.h
#ifndef __ListIterator__h
#define __ListIterator__h
/***
*** リストの反復子
***/
#include "List.h"
// 反復子型
typedef struct {
List *list;
ListNode *next;
} ListIterator;
// 反復対象のリスト
// 次に返すノード
// プロトタイプ宣言
ListIterator *makeListIterator(List*);
void freeListIterator(ListIterator*);
ListNode *hasNext(ListIterator*);
void *next(ListIterator*);
#endif // __ListIterator__h
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 freeListIterator(ListIterator *it){
free(it);
}
続く
ListIterator.cc
// 次の要素があるか
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 freePD(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 freePD(PD *pd){
free(pd->name);
free(pd);
}
// 表示
void print(PD *pd){
printf("%s(%d)",pd->name,pd->age);
}
ListTest.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");
}
続く
ListTest.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("です");
freeList(list);
}
TestListの実行結果
$ ListTest
*** 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)です
課題141201
• 国語、算数、理科、社会の4科目の点数と名前を
持つデータ型PScoreを作り、それをListに入れて各
科目の平均点を計算するプログラム
ProcessPScore.ccを示せ。
（PScoreはPDを参考に作ること）
• 作成方法：
• 作成した3つのコード PScore.h,PScore.cc,ProcessPScore.ccをワードに添付し
て示すこと。
• 提出方法：
• メールで。
• メールの本文中にも学籍番号を氏名を明記すること。
• 提出先：[email protected]
• メールタイトル：”アルゴリズム課題141201” ←厳守！
• 期限：2014年12月7日（日）

Download Report