nextは、次のセルへのポインタ
dataは、データ（この例では1文字）
initializeすると　2つの配列は

添え字　　　　0 1 2 3 4 5 6 7 8 9
next 　　　　　1 0 3 4 5 6 7 8 9 2
data 　　　　　　　　　　　　　　　　　　　　　(dataはすべて \0)

next[0]は、ヘッダを格納しているだけ。next[0] = 1(ずっと、変わらない）
next[1]からリストを辿る
- next[1]の初期値は0
- つまり、一番最初、配列全体は空リストを表現している。
- data[0], data[1]は、ダミーのため、ずっと使用されない。
next[9]は、フリーリストのヘッダーを格納している。next[9] = 2（ずっと変わらない）
- フリーリストはnext[2]から辿る。先頭から順に使われて、deleteされていく。
- 最初にnewcellで用意されるのは3
- そのあと、ヘッダーは4を指すはず。

解答例

#include <stdio.h>
#define MAX 10

void print_array(int from, int to);
char access(int p, int i);
int newcell(void);
void insert(int p, int i, char x);
void delete(int p, int i);
void initialize(void);
int empty(void);
int next[MAX]; /* 次のセルのポインタ */
char data[MAX]; /* データ */


void initialize (void) {
   int i;
   for (i = 0 ; i < MAX; i++) {
      next[i]=i+1; /* 次の要素を指すように初期化 :/
      data[i]='\0'; /* データはヌル文字で初期化 */
   }
   next[1]=0; /* next[1]がリストのヘッダ ヘッダーnext[1]にはNULL(nil) */
   next[MAX-1]=2; /* next[9]は、フリーリストのヘッダの格納　フリーリストヘッダは、next[2] */
}

/* 現在のポインタから、i回ポインターを辿って要素を取り出す */
char access (int p, int i) {
   if (next[p] != 0) { /* 再帰 */
      if (i > 1) { /* 再帰条件 */
         return (access(next[p],i-1)); /* 次のポインターから、i-1回 */
      } else { /* 停止条件 */
         return (data[next[p]]);
      }
   } else { /* i回辿れない。NULLポインターになった */
      printf("List L ends before arriving ");
      printf("at the position.\n");
      return('\0');
   }
}

/* セルを1つ用意。何をする、と書いてあるのか */
/* ヒントなしに読み取るのは、なかなか大変かもしれない */
int newcell (void) {
   int new; /* 確保できたセル */
   if (next[next[MAX-1]] != MAX-1) { /* まだセルがあるという条件のはず *//* 末尾のセルを指していない */
      new = next[next[MAX-1]]; /* next[2]がポイントしているセル */
      delete (next[MAX-1],1);  /* ここがキモ。フリーリストの先頭セルをdelete */
      return(new);
   }
   printf("List overflows.\n");
   return(MAX);
}

/* pの前に新セル挿入 */
void insert (int p, int i, char x) {
   int q;
   if (p != 0) {
      if (i > 1) { /* 再帰条件 */
         insert(next[p],i-1,x);
      } else { /* 停止条件 */
         q = newcell(); /* 新セルを１つ */
         data[q] = x; /* そのセルのデータ部にx */
         next[q] = next[p]; /* 自分は後ろを指すように */
         next[p] = q; /* 前は自分を指すように */
      }
   } else {
      printf("List L ends before arriving ");
      printf("at the position.\n");
   }
}


void delete (int p, int i) {
   if (next[p] != 0) {
      if(i > 1) {
         delete (next[p],i-1);
      } else {
         data[next[p]]='\0';
         next[p]=next[next[p]];
      }
   } else {
      printf("List L ends before arriving ");
      printf("at the position.\n");
   }
}

/* 全体が現在空リストを表しているのかを判定する関数 YESなら1 */
/* 下の実行例ではコメントアウトして、使っていない。教科書 p.31 問2.17の答え */
int empty (void) {
   if (next[next[0]] == 0) {
       /* next[0]がポイントしているセルのポインターがNULL */
       /* main関数の最初のinititializeでは、next[0]は1. next[1]は0 */
      return(1);
   }
      return(0);
}

/* 定番の配列プリント用 リストとしてはプリントしていない。配列をそのままプリント */
void print_array(int from, int to) {
   int i;

   for (i = from ; i <= to; i ++)
     printf("next[%d] = %3d: data[%d] = %c \n",i,next[i],i, data[i] );

   printf("\n\n");
}


int main(void){
   printf("(initialized)\n");
   initialize(); /* next[MAX]. data[MAX]の初期化 */
                /* next[0] が1。next[1]がリストのヘッダー。next[1] = 0なので、最初は空リスト 
                　next[MAX-1]が2, next[2]がフリーリストのヘッダー */
   print_array(0, MAX-1); /* その状態をプリントして、確認 */

   printf("(insert 1 a)\n");
   insert(next[0],1,'a');
   print_array(0, MAX-1); /* 状態をプリントして確認 */

   access(next[0], 1); /* このaccess関数は、1番目の要素をreturn。ここでは戻り値 を表示するなどしていない */

   printf("(insert 1 c)\n");
   insert(next[0],1,'c');
   print_array(0, MAX-1); 

   printf("(insert 2 v)\n") ;
   insert(next[0],2,'v');
   print_array(0, MAX-1);

   printf("(delete 1)\n") ;
   delete(next[0],1);
   print_array(0, MAX-1);

   printf("(insert 2 a)\n") ;
   insert(next[0],2,'a');
   print_array(0, MAX-1); 

   printf("(delete 3)\n") ;
   delete(next[0],3);
   print_array(0, MAX-1);

/* empty関数使用の例 先頭から、１つずつプリントして削除する。手繰られているイメ ージ
   while(!empty()) {
      printf("%c",access(next[0],1));
      delete(next[0],1);
   }
   printf("\n");
*/

    return(0);
}

STEP 3.1 （ヒントやコメント付）

STEP 3.1　（ヒントやコメント付）　