<問題>
まず、STEP3.1 のプログラムを解読する。(STEP3.1 Aはコメントなし、Bは少しコメント)
次に、STEP3.1Aのプログラムを使用して、insert, delete操作により、リストが変化するオリジナルな実行例を用意しなさい。
STEP3. 1Aを実行すると、リストを表現している配列の内容が出力される。出力される配列表現や表現の変化について、以下の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.