稿
目
次
稿
目
次
リスト構造
このセクションのソース
いきなりですが、みなさんは小学校や中学校のとき家庭訪問を経験なさったでしょうか？私の時は、訪問にきた先生を次の家まで案内していました。先生は全ての家がどこにあるのか知っているわけでもなく、私も知っているのは次の家がどこにあるのかだけです。にもかかわらず先生が全ての家を回ることができたのは、行く先々の家で次に行くべき家を知ることができたからに他なりません。みなさんの家庭訪問はどうだったでしょうか？もし私と違う方式でしたら、ちょっと私の方式を頭に思い浮かべてください。
さて本題ですが、この章でやりたいのは構造体を家に見立てた家庭訪問です。まずは最初のサンプルを見てみましょう。
/*01*/ #include <stdio.h>
/*02*/ #include <stdlib.h>
/*03*/ #include <string.h>
/*04*/
/*05*/ typedef struct home HOME;
/*06*/
/*07*/ struct home{
/*08*/ char name[256];
/*09*/ HOME *next_home;
/*10*/ };
/*11*/
/*12*/ main()
/*13*/ {
/*14*/ HOME *MakeNewList(char *name);
/*15*/ HOME *AddNextHome(HOME *home, char *name);
/*16*/ void DeleteList(HOME *first_home);
/*17*/
/*18*/ HOME *first_home;
/*19*/ HOME *home;
/*20*/
/*21*/ first_home = MakeNewList("茶亜");
/*22*/ home = first_home;
/*23*/ home = AddNextHome(home, "トット");
/*24*/ home = AddNextHome(home, "ピッピ");
/*25*/ home = AddNextHome(home, "チッチ");
/*26*/ AddNextHome(home, "ポッポ");
/*27*/
/*28*/
/*29*/ home = first_home;
/*30*/ do{
/*31*/ printf("ここの住所は %d で、\n", home);
/*32*/ printf("私は %s です。\n", home->name);
/*33*/ printf("次の人の住所は %d です。\n", home->next_home);
/*34*/ printf("------------\n");
/*35*/ }while((home = home->next_home) != NULL);
/*36*/
/*37*/ DeleteList(first_home);
/*38*/ }
/*39*/
/*40*/ HOME *MakeNewList(char *name)
/*41*/ {
/*42*/ HOME *first_home;
/*43*/ first_home = (HOME *)malloc(sizeof(HOME));
/*44*/ strcpy(first_home->name, name);
/*45*/ first_home->next_home = NULL;
/*46*/
/*47*/ return first_home;
/*48*/ }
/*49*/
/*50*/ HOME *AddNextHome(HOME *home, char *name)
/*51*/ {
/*52*/ HOME *next_home;
/*53*/
/*54*/ if(home->next_home != NULL) return NULL;
/*55*/
/*56*/ next_home = (HOME *)malloc(sizeof(HOME));
/*57*/ strcpy(next_home->name, name);
/*58*/ next_home->next_home = NULL;
/*59*/ home->next_home = next_home;
/*60*/
/*61*/ return next_home;
/*62*/ }
/*63*/
/*64*/ void DeleteList(HOME *first_home)
/*65*/ {
/*66*/ HOME *home;
/*67*/ HOME *next_home;
/*68*/
/*69*/ home = first_home;
/*70*/ do{
/*71*/ next_home = home->next_home;
/*72*/ free(home);
/*73*/ }while((home = next_home) != NULL);
/*74*/ }
list-7.4.1-05
まず、今回使う構造体 struct home 型を typedef で HOME と定義しておきます。
list-7.4.1-07
実際に struct home 構造体を見てみましょう。
struct home{
char name[256];
HOME *next_home;
};
name はその家に住む人の名前です。next_home には次の家の住所（アドレス）を保存します。最後の家では next_home を NULL とします。
list-7.4.1-14
このプログラムで使う関数を見てみます。関数の中身はあとで見るとして、今はそれぞれの関数がどんな働きをするのか知っておきましょう。
HOME *MakeNewList(char *name);
新しい訪問リストとなる最初の家を作ります。name はそこに住む人の名前で、戻り値は作られた家の住所（アドレス）です。next_home には訪問リストの終了であることを示す NULL が設定されます。内部では malloc を使って新しい家をメモリ上に確保しています。
HOME *AddNextHome(HOME *home, char *name);
home の次に訪問するべき家を新しく作ります。home->next_home には作られた家の住所（アドレス）が設定されます。name は作られる家に住む人の名前です。戻り値は作られた家の住所（アドレス）です。作られた家の next_home は NULL とします。内部では malloc を使って新しい家をメモリ上に確保しています。
void DeleteList(HOME *first_home);
first_home は最初の家の住所（アドレス）で、一連の家をすべて破棄します。内部では free を使って一連の家をメモリ上から解放しています。
list-7.4.1-21
それでは家庭訪問リストを作ってみましょう。まず、
first_home = MakeNewList("茶亜");
home = first_home;
として訪問リストの起点となる家を作り、first_home にその住所（アドレス）を保存しておき、home に 今作られた家、first_home を代入しておきます.。
次に
home = AddNextHome(home, "トット");
として home の次の家をつくり、その今作られた家の住所（アドレス）を home に格納します。この時点で元の home の home->next_home には作られた家の住所が入っていて、新しい home の next_home は NULL です.。あとはこれの繰り返しです.。
list-7.4.1-29
それでは実際に訪問リストをたどってみましょう。イメージは上図のとおりです。home は先生が現在いる家の住所をあらわすものとします。そこで home を 最初の家 first_home にセットしておきます。ループでは do-while を使っています。ループのなかでは home の住所（アドレス）、home に住む人の名前（home->name）、home の次に訪問すべき家の住所（home->next_home）を表示しています。次にループの条件式を見てみましょう。
}while((home = home->next_home) != NULL);
home には次に訪問すべき家の住所を代入します。これで先生は次の家を訪問することができます。ただし、次の家 next_home が NULL の場合は訪問を終了します。
list-7.4.1-37
家庭訪問が終わったら DeleteList で作られた家を破棄します。これをやらないと家はメモリ上に残ったままになってしまうので、忘れずに行ってください。
次に MakeNewList AddNextHome DeleteList などの関数を説明していきますが、とりあえずここまでをきっちり理解してこのサンプルプログラムを実際に動かしてみると良いでしょう。
list-7.4.1-40
MakeNewList 関数を見てみましょう。
HOME *MakeNewList(char *name)
{
HOME *first_home;
first_home = (HOME *)malloc(sizeof(HOME));
strcpy(first_home->name, name);
first_home->next_home = NULL;
return first_home;
}
まず malloc で新しい家（HOME）をメモリ上に作ります。あとは作られた家に住む人の名前を name に設定し、次に訪問すべき家 next_home を NULL に設定して終了です。
list-7.4.1-50
次は AddNextHome 関数です。
HOME *AddNextHome(HOME *home, char *name)
{
HOME *next_home;
if(home->next_home != NULL) return NULL;
next_home = (HOME *)malloc(sizeof(HOME));
strcpy(next_home->name, name);
next_home->next_home = NULL;
home->next_home = next_home;
return next_home;
}
まず、関数が呼び出された時点で home が訪問リストの最後であるかどうかチェックし、もし最後でなければエラーを示す値として NULL を返します。あとはほぼ MekeNewList と同じです。異なるのは、home の次に訪問すべき家の住所（アドレス） home->next_home に今新しく作った家の住所（アドレス） next_home を設定しているところです。ところで、もし home が訪問リストの最後でないのに home->next_home に新しい家を設定してしまったらどうなるでしょうか。当然、それまで home->next_home に設定されていた家の住所（アドレス）情報は消えてしまうので、どこからもアクセスできなくなってしまいます。そうなるとそれ以降の家はどこからもアクセスされることなくメモリ上に取り残されてしまうのです。そういった事態を避けるためにチェックが必要なのです。
list-7.4.1-64
最後に DeleteList を見てみます。
void DeleteList(HOME *first_home)
{
HOME *home;
HOME *next_home;
home = first_home;
do{
next_home = home->next_home;
free(home);
}while((home = next_home) != NULL);
}
この関数では 27-1-5 でやったように次々と家をたどっていって破棄しています。ただし、次のような例ではうまくいきません。
do{
free(home);
}while((home = home->next_home) != NULL);
こうしてしまうと、home->next_home ではすでに解放されて存在しない home にアクセスすることとなってしまいます。ですから、free(home) とする前に next_home に home_next_home を保存しておくわけです。
(untitled)
以上のように、次々と情報をたどっていく仕組みを
リストの途中にデータを追加する
このセクションのソース
また長い例ですが、list-7.4.1 に加えて InsertHome という関数を作ったことと、InsertHome 関数を main 側で呼び出している点の2箇所の変更があるだけで、あとは list-7.4.1 とまったく一緒です。
/*01*/ #include <stdio.h>
/*02*/ #include <stdlib.h>
/*03*/ #include <string.h>
/*04*/
/*05*/ typedef struct home HOME;
/*06*/
/*07*/ struct home{
/*08*/ char name[256];
/*09*/ HOME *next_home;
/*10*/ };
/*11*/
/*12*/ main()
/*13*/ {
/*14*/ HOME *MakeNewList(char *name);
/*15*/ HOME *AddNextHome(HOME *home, char *name);
/*16*/ HOME *InsertHome(HOME *first_home, int index, char *name);
/*17*/ void DeleteList(HOME *first_home);
/*18*/ HOME *first_home = NULL;
/*19*/ HOME *home;
/*20*/
/*21*/ first_home = MakeNewList("茶亜");
/*22*/ home = first_home;
/*23*/ home = AddNextHome(home, "トット");
/*24*/ home = AddNextHome(home, "ピッピ");
/*25*/ home = AddNextHome(home, "チッチ");
/*26*/ AddNextHome(home, "ポッポ");
/*27*/
/*28*/ InsertHome(first_home, 3, "トット2世");
/*29*/
/*30*/ home = first_home;
/*31*/ do{
/*32*/ printf("ここの住所は %d で、\n", home);
/*33*/ printf("私は %s です。\n", home->name);
/*34*/ printf("次の人の住所は %d です。\n", home->next_home);
/*35*/ printf("------------\n");
/*36*/ }while((home = home->next_home) != NULL);
/*37*/
/*38*/ DeleteList(first_home);
/*39*/ }
/*40*/
/*41*/ HOME *MakeNewList(char *name)
/*42*/ {
/*43*/ HOME *first_home;
/*44*/ first_home = (HOME *)malloc(sizeof(HOME));
/*45*/ strcpy(first_home->name, name);
/*46*/ first_home->next_home = NULL;
/*47*/
/*48*/ return first_home;
/*49*/ }
/*50*/
/*51*/ HOME *AddNextHome(HOME *home, char *name)
/*52*/ {
/*53*/ HOME *next_home;
/*54*/
/*55*/ if(home->next_home != NULL) return NULL;
/*56*/
/*57*/ next_home = (HOME *)malloc(sizeof(HOME));
/*58*/ strcpy(next_home->name, name);
/*59*/ next_home->next_home = NULL;
/*60*/ home->next_home = next_home;
/*61*/
/*62*/ return next_home;
/*63*/ }
/*64*/
/*65*/ void DeleteList(HOME *first_home)
/*66*/ {
/*67*/ HOME *home;
/*68*/ HOME *next_home;
/*69*/
/*70*/ home = first_home;
/*71*/ do{
/*72*/ next_home = home->next_home;
/*73*/ free(home);
/*74*/ }while((home = next_home) != NULL);
/*75*/ }
/*76*/
/*77*/ HOME *InsertHome(HOME *first_home, int index, char *name)
/*78*/ {
/*79*/ int i;
/*80*/ HOME *home;
/*81*/ HOME *new_home;
/*82*/
/*83*/ if(index == 0) return NULL;
/*84*/
/*85*/ home = first_home;
/*86*/ for(i = 0; i < index - 1; i++){
/*87*/ if((home = home->next_home) == NULL)
/*88*/ return NULL;
/*89*/ }
/*90*/
/*91*/ new_home = (HOME *)malloc(sizeof(HOME));
/*92*/ strcpy(new_home->name, name);
/*93*/ new_home->next_home = home->next_home;
/*94*/ home->next_home = new_home;
/*95*/
/*96*/ return new_home;
/*97*/ }
list-7.4.2-77
では InsertHome 関数を見ていきましょう。まず関数の仕様ですが、first_home は訪問リストの最初の家で、index 番目に name という名前の人が住む家を追加します。この関数では最初の家を0番目として扱うことにします。さて、この機能を満たすためにはどうしたらよいでしょうか。まず新しい家 new_home を作ります。new_home の new_home->next_home は index 番目の住所（アドレス）を入れておきましょう。そうしたら index-1 番目 next_home に new_home の住所を入れます。こうすれば index-1 番目の next_home 見て new_home へ行くことができ、new_home の new_home->next_home を見て次の家へ行くことができますね。たとえば「トット2世」くんの家を3番目に挿入する場合、.のようなイメージになります。これを実際にどうプログラミングするか見てみましょう。
list-7.4.2-83
ここでは index が0のとき、つまりリストの最初の家を変えたいという場合は扱いません。ですのでエラーとして NULL を返します。index が0の場合の処理は、皆さん自身で考えてみてください。
list-7.4.2-85
まず、index-1 番目の家を home に取得します。このとき、index が最後の家を超える値だった場合にはエラーとして NULL を返します。
list-7.4.2-91
new_home を作ったら、new_home->name を設定し、new_home の new_home->next_home に home->next_home を設定します。最後に home->next_home に new_home を設定してやれば終了です。
(untitled)
(untitled)
以上がリスト構造の概要です。今回のリストは先頭の家からしかたどることができません。このような一方方向のリストを
