STEP 3.1 （ノーヒントバージョン）
<問題> 配列による実装例。教科書とプログラムを読み、自分なりのコメント文をつけて解読してみてください。
（プログラムは、教科書p.31の2.12から17までの解答例をまとめたもの。若干の変更あり）
main 関数は以下。授業中の例題を実行。[c], [c,v], などと変化する。
print_array関数の表示から、リスト構造を表現している２つの配列の変化を説明しよう。（この実行例は問2.11）
int main(void){
printf("(initialized)\n");
initialize();
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);
}
<実行例>
initialze関数、insert関数、delete関数のプログラムを読んで、これらの実行例が、何をどのように表しているのか、説明しなさい。
(initialized)
next[0] = 1: data[0] =
next[1] = 0: data[1] =
next[2] = 3: data[2] =
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)
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] =
(insert 1 c)
next[0] = 1: data[0] =
next[1] = 4: data[1] =
next[2] = 5: data[2] =
next[3] = 0: data[3] = a
next[4] = 3: data[4] = c
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)
next[0] = 1: data[0] =
next[1] = 4: data[1] =
next[2] = 6: data[2] =
next[3] = 0: data[3] = a
next[4] = 5: data[4] = c
next[5] = 3: data[5] = v
next[6] = 7: data[6] =
next[7] = 8: data[7] =
next[8] = 9: data[8] =
next[9] = 2: data[9] =
(delete 1)
next[0] = 1: data[0] =
next[1] = 5: data[1] =
next[2] = 6: data[2] =
next[3] = 0: data[3] = a
next[4] = 5: data[4] =
next[5] = 3: data[5] = v
next[6] = 7: data[6] =
next[7] = 8: data[7] =
next[8] = 9: data[8] =
next[9] = 2: data[9] =
(insert 2 a)
next[0] = 1: data[0] =
next[1] = 5: data[1] =
next[2] = 7: data[2] =
next[3] = 0: data[3] = a
next[4] = 5: data[4] =
next[5] = 6: data[5] = v
next[6] = 3: data[6] = a
next[7] = 8: data[7] =
next[8] = 9: data[8] =
next[9] = 2: data[9] =
(delete 3)
next[0] = 1: data[0] =
next[1] = 5: data[1] =
next[2] = 7: data[2] =
next[3] = 0: data[3] =
next[4] = 5: data[4] =
next[5] = 6: data[5] = v
next[6] = 0: data[6] = a
next[7] = 8: data[7] =
next[8] = 9: data[8] =
next[9] = 2: data[9] =
（最後の状態は、リスト [v,a] を表現している。どこからどのように読めば、[v,a]なのか。
次にinsert(next[0],3,'c')などとすれば、配列はどのように変わるのか)
（全く、コメントありません。本来、ここから読むべき）
解答例
#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[MAX-1]=2;
}
char access (int p, int i) {
if (next[p] != 0) {
if (i > 1) {
return (access(next[p],i-1));
} else {
return (data[next[p]]);
}
} else {
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]];
delete (next[MAX-1],1);
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();
data[q] = 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");
}
}
int empty (void) {
if (next[next[0]] == 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();
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);
}