簡易データベース 情報画像工学実験 I : 実験２ 担当：関屋大雄（工学部１号棟５１５室） E-mail : sekiya@faculty.chiba-u.jp TA:　 山下哲孝 (M2) : n_yamashita@graduate.chiba-u.jp 　　　　横手俊倫(M1) : yokote@graduate.chiba-u.jp

目的 再帰的データ構造の理解 線形リスト構造 二分木構造 ファイルポインタの操作の理解 デバッグ方法の練習 情報画像工学実験I 実験2

課題 第１週 第２週 第３週 線形リスト構造の理解 二分探索木の理解 構造体ファイル入出力・ データベース処理プログラムの作成 　　　データベース処理プログラムの作成 情報画像工学実験I 実験2

再帰的データ構造 自己参照構造体を基本に構成されるデータ構造 自己参照構造体 リスト構造 木構造 構造体のメンバとして自分自身と同じ構造体へのポインタを持つ構造体 情報画像工学実験I 実験2

リスト構造 typedef struct _list{ struct _list *next; //構造体のメンバとして自分自身と同じ構造体へのポインタ datatype data; } listelem, *list; head : NULL (リスト構造の末尾の目印) 情報画像工学実験I 実験2

リストの操作 list head=NULL; list p; p=(list)malloc(sizeof(listelem)); //領域確保 p->data = ・・・ p->next = head; head = p; 空のリストの作成 情報画像工学実験I 実験2

リストの操作 list p; p=(list)malloc(sizeof(listelem)); //領域確保 p->data = ・・・ p->next = head; head = p; 新しい構造体の作成、領域確保 *p *p 情報画像工学実験I 実験2

リストの操作 list head=NULL; list p; p=(list)malloc(sizeof(listelem)); //領域確保 p->data = ・・・ p->next = head; head = p; データ登録 ・・・ ・・・ 情報画像工学実験I 実験2

リストの操作 list head=NULL; list p; p=(list)malloc(sizeof(listelem)); //領域確保 p->data = ・・・ p->next = head; head = p; ・・・ ・・・ 情報画像工学実験I 実験2

リストへの挿入 list insert(list head, int key, int val) //keyのあとにvalを挿入 { list elem, cur; elem = (list)malloc(sizeof(listelem)); elem->data = val; for(cur = head; cur!= NULL; cur = cur->next){ if(key == cur->data){ elen->next = cur->next; cur->next = elem; return head; } elem->next = head; head = elem; head 5 2(key) 3 情報画像工学実験I 実験2

リストへの挿入 list insert(list head, int key, int val) //keyのあとにvalを挿入 { list elem, cur; elem = (list)malloc(sizeof(listelem)); elem->data = val; for(cur = head; cur!= NULL; cur = cur->next){ if(key == cur->data){ elen->next = cur->next; cur->next = elem; return head; } elem->next = head; head = elem; *elem head 4(val) 5 2(key) 3 情報画像工学実験I 実験2

リストへの挿入 list insert(list head, int key, int val) //keyのあとにvalを挿入 { list elem, cur; elem = (list)malloc(sizeof(listelem)); elem->data = val; for(cur = head; cur!= NULL; cur = cur->next){ if(key == cur->data){ elen->next = cur->next; cur->next = elem; return head; } elem->next = head; head = elem; elem head cur 4(val) cur 5 2(key) 3 情報画像工学実験I 実験2

リストへの挿入 list insert(list head, int key, int val) //keyのあとにvalを挿入 { list elem, cur; elem = (list)malloc(sizeof(listelem)); elem->data = val; for(cur = head; cur!= NULL; cur = cur->next){ if(key == cur->data){ elem->next = cur->next; cur->next = elem; return head; } elem->next = head; head = elem; elem head 4(val) cur 5 2(key) 3 情報画像工学実験I 実験2

リストへの挿入 list insert(list head, int key, int val) //keyのあとにvalを挿入 { list elem cur; elem = (list)malloc(sizeof(listelem)); elem->data = val; for(cur = head; cur!= NULL; cur = cur->next){ if(key == cur->data){ elen->next = cur->next; cur->next = elem; return head; } elem->next = head; head = elem; *elem head 4(val) cur 5 3 6 (In case of no key) その他の例外処理を考えること 情報画像工学実験I 実験2

リストからの削除 list delete(list head, int key)//keyを削除 { list cur, prev; for(cur = head; cur != NULL; cur = cur->next){ if(key == cur->data){ if(cur == head) head = cur->next; else prev->next = cur->next; free(cur); return head; } prev = cur; return NULL; head 5 2(key) 3 情報画像工学実験I 実験2

リストからの削除 list delete(list head, int key)//keyを削除 { list cur, prev; for(cur = head; cur != NULL; cur = cur->next){ if(key == cur->data){ if(cur == head) head = cur->next; else prev->next = cur->next; free(cur); return head; } prev = cur; return NULL; head cur 5 2(key) 3 情報画像工学実験I 実験2

リストからの削除 list delete(list head, int key)//keyを削除 { list cur, prev; for(cur = head; cur != NULL; cur = cur->next){ if(key == cur->data){ if(cur == head) head = cur->next; else prev->next = cur->next; free(cur); return head; } prev = cur; return NULL; head prev cur 5 2(key) 3 情報画像工学実験I 実験2

リストからの削除 list delete(list head, int key)//keyを削除 { list cur, prev; for(cur = head; cur != NULL; cur = cur->next){ if(key == cur->data){ if(cur == head) head = cur->next; else prev->next = cur->next; free(cur); return head; } prev = cur; return NULL; head prev cur 5 2(key) 3 情報画像工学実験I 実験2

リストからの削除 list delete(list head, int key)//keyを削除 { list cur, prev; for(cur = head; cur != NULL; cur = cur->next){ if(key == cur->data){ if(cur == head) head = cur->next; else prev->next = cur->next; free(cur); return head; } prev = cur; return NULL; head prev cur 5 2(key) 3 情報画像工学実験I 実験2

リストからの削除 list delete(list head, int key)//keyを削除 { list cur, prev; for(cur = head; cur != NULL; cur = cur->next){ if(key == cur->data){ if(cur == head) head = cur->next; else prev->next = cur->next; free(cur); return head; } prev = cur; return NULL; head prev cur 5 3 情報画像工学実験I 実験2

今週のレポート 線形リスト構造において データ（整数型）の挿入 データの削除 昇順、降順の出力 を可能とするプログラムの作成。 情報画像工学実験I 実験2