住所録プログラムの作成 （その2）
リスト構造
リスト構造
現在までは住所録のデータを格納するのに配列を用いてきた。配列中に新たな要素を追加したり、消去する場合、それ以降の要素をシフトさせる作業が必要となる。
これに対し、住所録など、多くの同じ形式のデータを取り扱う場合、リスト構造が有効である。これは配列とは異なり、データの追加や削除が容易に行なえるという特徴がある。
一般にリストは同じ型をもつ複数のセルが数珠繋ぎになっているものをいう。セルにはデータ部分と次のセルを示すポインタからなる。実現方法として、各セルが自分自身の型へのポインタを持ち、そのポインタには次のセルのポインタが格納される。
リストを実現するには構造体の自己参照で実現できる。このような構造体の宣言は、
| struct
personal{ int no; char name[256]; char furigana[256]; int age; int year; int month; int day; char address[256]; /* 次のセルへのポインタ */ struct personal *next; }; |
のようにする。
実際にリストを作成するには以下の手順が必要である。
以下のプログラムは100個のセルを持ったリストを作成し、データにセル番号×2を代入するプログラムである。
| #include<stdio.h> struct list{ int data; /* 次のセルへのポインタ */ struct list *next; }; struct list *add_sel() { struct list *buf; /* セルのメモリ確保 */ buf = (struct list *)malloc(sizeof(struct list)); return(buf); } void print_list(struct list *start) { struct list *buf; /* 注目セルをスタートセルにする */ buf = start; /* buf->nextがNULLになるまでループ*/ while(buf->next != NULL){ printf(" %d\n", buf->data); /* 注目セルを次に進める */ buf = buf->next; } } main() { /* スタート位置のポインタ */ struct list *start; /* 現在位置(注目セル)のポインタ */ struct list *buf; int i; /* スタートのセルの作成 */ start = add_sel(); start->next = NULL; /* 注目セルをスタートセルにする */ buf = start; for(i = 0; i < 100; i++){ /* 注目セルにデータを代入 */ buf->data = i * 2; /* 注目セルの後ろに新しいセルを作成 */ buf->next = add_sel(); /* 注目セルを次に進める */ buf = buf->next; buf->next = NULL; } print_list(start); } |
リスト中のある位置に新たなセルを挿入する場合は、挿入位置が示すポインタを新しいセルを示すようにし、新しいセルが示す場所を挿入位置が示していた場所にすればよい。この様子は以下の図である。
また、これをプログラムで作成すると以下のようになる。
| /* *sel 挿入位置 *new 挿入するセル */ void insert_sel(struct list *sel, struct list *new) { struct list *buf; buf = sel->next; sel->next = new; new->next = buf; } |
リスト中のある位置のセルを消去する場合は、消去位置の一つ前のセルが示すポインタを、消去位置が示すポインタにすればよい。すなわち、5番目のセルを消去したい場合は、4番目のセルの示すポインタを5番目のセルが示すポインタにすればよい。この様子は以下の図である。
また、これをプログラムで作成すると以下のようになる。消去位置の一つ前のセルを引数とすることに注意すること。
| /* *sel 消去位置の一つ前 */ void delete_sel(struct list *sel) { struct list *buf; buf = sel->next; sel->next = buf->next; free(buf); } |
基本的に以上のような操作で、リストの結合、リストの分割も簡単に行える。