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

<注意> pp.164 - 166 分割コンパイル下は、３つのソースファイル
list.h （共有情報)
list.c (リスト操作)
0302.c (main関数)

gcc -c list.c
gcc -c 0302.c
gcc -o 0302 list.o 0302.o

１つのファイルにまとめるときは、ダブった行がないように、注意

解答例

ここから、list.hです。

#include <stdio.h>
#include <stdlib.h>

typedef struct list {
   struct list *next;
   char data;
} List;

List *create(void);

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));
   p->next = NULL;
   p->data = '\0'; /* セルのデータを、ヌル文字で初期化 */
   return (p);
}

char access(List *L, int i) {
   if (L->next != NULL) {
      if (i > 1) { /* 再帰条件 */
         return (access(L->next,i-1));
      } else { /* 停止条件 */
         return (L->next->data);
      }
   } 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);
      } else { /* 停止条件 */
         p = create(); /* セルを１つ */
         p->data = x; /* アドレスの実体にあるセルのdataメンバーに、x */
         p->next = L->next; /* 後ろのポインターをnextに */
         L->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);
   }
}

int empty(List *L){
   if (L -> next == NULL) {
      return(1);
   }
      return(0);
}

/* ここから２つは、例題13.3の関数を、こちらに移動、調整 */
/* どちらもほぼ同じことをしている。どんどん辿って（プリントするか、freeするか)。
   上は非再帰。下は再帰で書かれていることに注意 */

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) {
      FreeData(L -> next);
      free (L);
   }
}

----------------------
ここから、0302.cです。
#include "list.h"

int main(void){
   List *L;
   L = create();
   insert (L,1,'a');
   insert (L,1,'c');
   insert (L,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);
}

STEP 3.2A