STEP 3.1 実行

<問題>
まず、STEP3.1 のプログラムを解読する。(STEP3.1 Aはコメントなし、Bは少しコメント)
次に、STEP3.1Aのプログラムを使用して、insert, delete操作により、リストが変化するオリジナルな実行例を用意しなさい。

STEP3. 1Aを実行すると、リストを表現している配列の内容が出力される。出力される配列表現や表現の変化について、以下の2点をできるだけ説明しよう。

  1. どんなリストを表しているのか、また、操作によって、どのような変化をしたのかを説明せよ。
    (略記とセル表現を説明できるように: 配列の意味の確認)
  2. 配列の変化について、説明せよ。 (コードが解読できていると、何をしているのかを説明できる)
    (リスト基本操作と、対応する配列操作実行の説明)

1.については、授業のパワーポイントでも説明
2. は、コードを読み、実際の実行について説明する


配列nextに注目 2種類の情報を表現しています


こんな例もやってみよう:


(コメント)

 プログラム
後半には、実行例をつけました

#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 linitialize(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[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');
   }
}

/* ヒントなしに読み取るのは、なかなか大変かもしれない */
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);
}

/* 新セル挿入 */
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(); /* 新セルを1つ */
         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 */
int empty (void) {
   if (next[next[0]] == 0) {
       /* next[1]がNULL */
      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){
   initialize();
   printf("initialized\n");
   print_array(0, MAX-1);

   printf("insert 1 a \n") ;
   insert(next[0],1,'a');  /* [a] 3にaのはずだ */
   print_array(0, MAX-1);

   printf("delete 1 \n") ;
   delete(next[0],1);     /* [] 1は0に戻る */
   print_array(0, MAX-1);

   printf("insert 1 c \n") ;
   insert(next[0],1,'b'); /* [b] 4にbのはずだ */
   print_array(0, MAX-1);

   printf("insert 2 v \n") ;
   insert(next[0],2,'c'); /* [b, c] 5にcのはずだ。4のnextは5になるはずだ */
   print_array(0, MAX-1);

   printf("insert 2 d \n") ;
   insert(next[0],2,'d'); /* [b,d,c] 6にdのはずだ。4のnextは6になり、6のnextは5だ */
   print_array(0, MAX-1);

   printf("delete 3 \n") ;
   delete(next[0],3);  /* [b,d] セル5が削除。6のnextはnilだ */
   print_array(0, MAX-1);


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

   printf("insert 2 g \n") ;
   insert(next[0],2,'g'); /* 残念、セルを解放していないので、使い切り */

   /* 最後に、先頭から、1つずつプリントして削除。手繰られているイメージ deleteしなければリストのプリント関数のヒント。再帰で書いてもよい*/
  /*  while(!empty()){
      printf("%3d -- ",next[next[0]]);
      printf("%c\n", access(next[0],1));
      delete(next[0],1);
   }
   printf("\n"); */

   return(0);
}


以下、実行結果の例(配列の意味はmain関数側に。配列が何をどう表現しているのかは授業の資料も)
2つ目の説明のヒントをつけておきます。たとえば、insert 1 aでどんな操作が起きているのかを説明してみよう。

initialized (空リストを表しているはず。next[0], next[1]とnext[9], next[2]に注目)
next[0] =   1: data[0] =
next[1] =   0: data[1] =
next[2] =   3: data[2] =     (フリーリストの先頭は3)
next[3] =   4: data[3] =
next[4] =   5: data[4] =
next[5] =   6: data[5] =
next[6] =   7: data[6] =
next[7] =   8: data[7] =
next[8] =   9: data[8] =
next[9] =   2: data[9] =


insert 1 a (新セルに3。最後の要素なので、next[3]=0。next[2]をみると、フリーリストの先頭は4になった)
next[0] =   1: data[0] =
next[1] =   3: data[1] =
next[2] =   4: data[2] =
next[3] =   0: data[3] = a
next[4] =   5: data[4] =
next[5] =   6: data[5] =
next[6] =   7: data[6] =
next[7] =   8: data[7] =
next[8] =   9: data[8] =
next[9] =   2: data[9] =


delete 1 (3番のセルのデータがNULLに。next[1]=0なので、データリストは、空リスト。3番目のセルは、フリーリストにつながっていない。再利用すべきだ)
next[0] =   1: data[0] =
next[1] =   0: data[1] =
next[2] =   4: data[2] =
next[3] =   0: data[3] =
next[4] =   5: data[4] =
next[5] =   6: data[5] =
next[6] =   7: data[6] =
next[7] =   8: data[7] =
next[8] =   9: data[8] =
next[9] =   2: data[9] =


insert 1 c (新セルは4。next[1]= 4で、data[4]にb。フリーリストの先頭は5になっている)
next[0] =   1: data[0] =
next[1] =   4: data[1] =
next[2] =   5: data[2] =
next[3] =   0: data[3] =
next[4] =   0: data[4] = b
next[5] =   6: data[5] =
next[6] =   7: data[6] =
next[7] =   8: data[7] =
next[8] =   9: data[8] =
next[9] =   2: data[9] =


insert 2 v (新セルは5. [b,c]に。フリーリストの先頭は6に)
next[0] =   1: data[0] =
next[1] =   4: data[1] =
next[2] =   6: data[2] =
next[3] =   0: data[3] =
next[4] =   5: data[4] = b
next[5] =   0: data[5] = c
next[6] =   7: data[6] =
next[7] =   8: data[7] =
next[8] =   9: data[8] =
next[9] =   2: data[9] =


insert 2 d (新セルは6。[b,d,c]になっている。フリーリストの先頭は7に)
next[0] =   1: data[0] =
next[1] =   4: data[1] =
next[2] =   7: data[2] =
next[3] =   0: data[3] =
next[4] =   6: data[4] = b
next[5] =   0: data[5] = c
next[6] =   5: data[6] = d
next[7] =   8: data[7] =
next[8] =   9: data[8] =
next[9] =   2: data[9] =


delete 3 (3番目の要素は、data[5]。[b,d]へ。next[6] = 0になっている。5番のセルも回収されていない)
next[0] =   1: data[0] =
next[1] =   4: data[1] =
next[2] =   7: data[2] =
next[3] =   0: data[3] =
next[4] =   6: data[4] = b
next[5] =   0: data[5] =
next[6] =   0: data[6] = d
next[7] =   8: data[7] =
next[8] =   9: data[8] =
next[9] =   2: data[9] =


insert 2 e
insert 2 f
next[0] =   1: data[0] =
next[1] =   4: data[1] =
next[2] =   9: data[2] =
next[3] =   0: data[3] =
next[4] =   8: data[4] = b
next[5] =   0: data[5] =
next[6] =   0: data[6] = d
next[7] =   6: data[7] = e
next[8] =   7: data[8] = f
next[9] =   2: data[9] =


insert 2 g
List overflows.