コメント (教科書のプログラムからの変更点など)
<問題> 自己参照型構造体と再帰関数による実装例。プログラムを読み、自分なりのコメント文をつけて解読してみてください。
<実行例> main関数で、問2.11 練習問題 を実行 c v a (→ここまで、1回プリント) v a (→いくつかの操作のあと、最後にもう一度)
<注意> ppp.164 - 166 分割コンパイル 下は、3つのソースファイル
list.h (共有情報)
list.c (リスト操作)
0302.c
(main関数)
gcc -c list.c
gcc -c 0302.c
gcc -o 0302 list.o 0302.o
ソースファイルを1つのファイルにするときは、重複がないように注意
<ヒント>
解答例 ここから、list.hです。 #include <stdio.h> #include <stdlib.h> /* リスト構造体の定義、型宣言。CELLという名前でもいいでしょう。*/ typedef struct list { struct list *next; /* 次のlist構造体へのポインター; 自己参照型 */ char data; /* データは1つ。1文字。もっと、増やしてもいい */ } List; /* 型の名前は、List。typedefは構造体によく出てくるが、型の読み替えにも利用される。工学実験では多用する */ /* 関数のプロトタイプ宣言 */ List *create(void); /* create関数はアドレスを返す。(List *)だから、List型データが格納されている領域のアドレス */ char access(List *L, int i); void insert(List *L, int i, char x); void delete(List *L, int i); void initialize(List *L); int empty(List *L); void printlist(List *L); /* 追加 */ void FreeData(List *L); ------------------------------- ここから、list.cです。 #include "list.h" List *create(void){ List *p; p = (List *)malloc(sizeof(List)); /* mallocの使い方に注意。sizeofで確保して、得られたアドレスをキャストする */ p->next = NULL; p->data = '\0'; /* セルのデータを、ヌル文字で初期化 */ /* insertで、すぐに値が代入されるので、初期化はいらないともいえるが、美しくないともいえる。後者が望ましい。 このプログラムでは先頭がダミーになるので、ヌルを代入し、プリントしないようにする */ return (p); } char access(List *L, int i) { if (L->next != NULL) { if (i > 1) { /* 再帰条件 */ return (access(L->next,i-1)); /* 次のセルからのリストで、i-1番目にアクセス ということだ */ } else { /* 停止条件 */ return (L->next->data); /* 1番目ということは、先頭のセルの値 */ } } else { printf("List L ends before arriving "); /* もうリストがない場合の、エラー処理。仕様による。最後の要素にしてしまうという手もある */ printf("at the position.\n"); return('\0'); } } void insert(List *L, int i, char x) { List *p; if (L != NULL) { if (i > 1) { /* 再帰条件 */ insert(L->next,i-1,x); /* 次のセルからのリストで、i-1番目にinsertということだ */ } else { /* 停止条件 */ /* 以下、新しいセルを確保、つなぎかえているはずだ */ p = create(); /* セルを1つ */ p->data = x; /* 確保したセルのdataメンバーに、xを。->演算子に注目 pはアドレスです*/ p->next = L->next; /* 確保したセルのnextメンバーには、前のセルのnextをつなぐ。これでpからはつながった */ L->next = p; /* 前のセルのnextには、pをつないで、前とも接続 */ } } else { printf("List L ends before arriving "); /* リストが短い。例外処理 */ printf("at the position.\n"); } } void delete(List *L, int i) { List *del; if (L->next != NULL) { if(i > 1) { delete(L->next,i-1); } else { del = L->next; L->next = L->next->next; free(del); } } else { printf("List L ends before arriving "); printf("at the position.\n"); } } /* 使っていないぞ、という指摘。正しい。これはリストを空にしている */ void initialize (List *L) { while (!empty(L)) { delete(L,1); } } /* 空リストかどうかを判定する。真 TRUEなら、1 */ int empty(List *L){ if (L -> next == NULL) { return(1); } return(0); } /* ここから2つは、例題集13.3の関数を、こちらに移動、調整 */ /* どちらもほぼ同じことをしている。どんどん辿って(プリントするか、freeするか)。 上は非再帰。下は再帰で書かれていることに注意 */ /* 非再帰. whileループでNULLでない間。次を辿っていく */ void printlist (List *L) { printf("\n"); while (L != NULL) { if (L -> data != '\0') /* ヌル文字だったら、出力しない。出力されないのは、ヘッダーのセルだけ */ printf("%c \n", L -> data); L = L -> next; } } /* 再帰 */ void FreeData(List *L) { if (L != NULL) { /* 再帰条件。NULLでないなら、残りのリストをFreeDataし、自分をfree */ FreeData(L -> next); free (L); } /* 停止条件は、何もしないで、正常終了 */ } ---------------------- ここから、0302.cです。 #include "list.h" int main(void){ List *L; L = create(); /* ダミーリスト(ヘッダの格納)を作成 */ insert (L,1,'a'); /* 1番目にa */ insert (L,1,'c'); /* (a)の1番目にc */ insert (L,2,'v'); /* (c a)の2番目にv */ printlist(L); /* ダミーリストから、順にプリント。ヌル文字はプリントせず */ delete (L,1); insert(L,2,'a'); delete(L,3); printlist(L); /* while(!empty(L)){ printf("%c",access(L,1)); delete(L,1); } printf("\n"); */ FreeData(L); return(0); }