STEP 3.2B

コメント (教科書のプログラムからの変更点など)

<問題> 自己参照型構造体と再帰関数による実装例。プログラムを読み、自分なりのコメント文をつけて解読してみてください。

<実行例> 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);
}