3 応用 3.1 連結リスト 前回 先頭に追加する例を扱いました しかし start が指す node を変更することから 関数 の戻り値として作成しました 今回は ポインタ変数 start の値を関数で変更できるように ポイ ンタ変数へのポインタを利用します 先頭を削除するものと 最後を削除する関数を追加します ex25.c /* リストの追加と削除 */ typedef struct node { int value; struct node *next; node; void print_list(node *s); void add_first(node **s, int x); void del_first(node **s); void del_last(node **s); node first, * NULL; add_first(&start, 40); print_list(start); add_first(&start, 30); print_list(start); add_first(&start, 20); print_list(start); add_first(&start, 10); print_list(start); del_first(&start); print_list(start); del_last(&start); print_list(start); del_first(&start); print_list(start); del_last(&start); print_list(start); /* データの表示 */ void print_list(node *s) { printf(" %p n", s); for( ; s!= NULL; s = s->next) { printf("%d(%p) ", s->value, s); printf("null n"); /* データの追加 */ void add_first(node **s, int x) { node *new; new = (node *)malloc(sizeof(node)); new->value = x; new->next = *s; *s = new; 30
/* 先頭データの削除 */ void del_first(node **s) { node *z = *s; *s = z->next; free(z); /* 最後のデータの削除 */ void del_last(node **s) { node *z, *p = *s; for(z = *s ; z->next!= NULL; z = z->next) { p = z; if(z == *s) { *s = NULL; else { p->next = NULL; free(z); 31
今までは 順序良く入力してきましたが 入力されたものを順序良く格納する例を考えてみます こ の場合も 最初に入る可能性があるために 先頭を表すポインタ変数へのポインタを利用します ex26.c /* リストにデータの挿入 */ typedef struct node { int value; struct node *next; node; void print_list(node *s); void insert_list(node **s, int x); node * NULL; int i, x; printf(" 値を入力してください : "); scanf("%d", &x); insert_list(&start, x); print_list(start); /* データの表示 */ void print_list(node *s) { printf(" %p n", s); for( ; s!= NULL; s = s->next) { printf("%d(%p) ", s->value, s); printf("null n"); /* データの挿入 */ void insert_list(node **s, int x) { node *new, *z; new = (node *)malloc(sizeof(node)); new->value = x; if(*s == NULL (*s)->value > x) { /* 先頭に追加する場合 */ new->next = *s; *s = new; else { /* 途中または最後に追加する場合 */ for(z = *s ; z->next!= NULL && z->next->value < x; z = z->next); new->next = z->next; z->next = new; 32
順に入力してどのようなリストが出来ているか考えてみましょう 最初の状態 30 を入力 50 を入力 40 を入力 33
10 を入力 20 を入力 34
では このリストを用いた簡単な例を考えてみましょう flight.txt ANA 羽田 652 710 825 ANA 羽田 654 920 1035 ANA 羽田 656 1245 1400 ANA 羽田 658 1650 1810 ANA 羽田 660 2005 2125 JAL 羽田 232 710 815 JAL 羽田 234 1005 1115 JAL 羽田 236 1250 1400 JAL 羽田 240 1645 1755 JAL 羽田 242 1830 1940 ADO 札幌 113 825 1015 JTA 沖縄 011 830 1040 岡山空港を出発する時刻表です これを出発時刻順に連結リストに格納します ex27.c /* ファイルからリストを作成 */ typedef struct flight { char co[20], dest[20]; int no, dep, arr; struct flight *next; flight; void print_list(flight *s); void input_flight(file *in, flight *x); void insert_list(flight **s, flight *x); flight * NULL; flight *x; FILE *input; /* オープンした結果を保存するポインタ変数 */ /* flight.txt を読み込み専用でオープン */ input = fopen("flight.txt", "r"); if(input == NULL) { printf("error! flight.txt が見つかりません n"); else { while(!feof(input)) { x = (flight *) malloc(sizeof(flight)); input_flight(input, x); /* データの入力 */ insert_list(&start, x); /* データの出力 */ print_list(start); 35
/* データの表示 */ void print_list(flight *s) { for( ; s!= NULL; s = s->next) { printf("%5s %6s %4d %4d %4d n", s->co, s->dest, s->no, s->dep, s->arr); /* データの挿入 */ void insert_list(flight **s, flight *x) { flight *z; if(*s == NULL (*s)->dep > x->dep) { /* 先頭に追加する場合 */ x->next = *s; *s = x; else { /* 途中または最後に追加する場合 */ for(z = *s ; z->next!= NULL && z->next->dep < x->dep; z = z->next); x->next = z->next; z->next = x; /* 入力用関数 */ void input_flight(file *input, flight *x) { fscanf(input, "%5s %15s %d %d %d", x->co, x->dest, &x->no, &x->dep, &x->arr); 次に 超長整数の例を挙げます ここでは 整数を 4 桁ずつに区切ったものを 5 つ 1 セットとして扱 います つまり 20 桁が構造体ひとつ分です 繰り上がりの計算を行い 足りなくなったら 桁を増 やす ( 構造体を増やす ) ということを行っています このとき 連結リストにすることで とても長 い整数を表すことができます 理論上 メモリの許すだけの長い整数が計算できることになります ex28.c /* 超長整数 */ /* 構造体の定義 */ typedef struct long_long_int { int num[5]; struct long_long_int *next; long_long_int; long_long_int *new_long_long_integer(int n); void mul_int(long_long_int *x, int n); void add_int(long_long_int *x, int t); void print_long_long_int(long_long_int *x); long_long_int *x; int i, n; 36
x = new_long_long_integer(1); printf(" 階乗を計算します n いくつまで計算しますか : "); scanf("%d", &n); for(i = 1; i <= n; i++) { mul_int(x, i); printf("%5d! = ", i); print_long_long_int(x); printf(" n"); /* 新しい構造体の作成 */ long_long_int *new_long_long_integer(int n) { int i; long_long_int *x; x = (long_long_int *)malloc(sizeof(long_long_int)); x->next = NULL; x->num[i] = n % 10000; n /= 10000; return(x); /* 超長整数に整数を掛ける関数 */ void mul_int(long_long_int *x, int n) { int i, t = 0; x->num[i] = x->num[i] * n + t; t = x->num[i] / 10000; x->num[i] %= 10000; if(x->next!= NULL) { mul_int(x->next, n); add_int(x->next, t); else if(t!= 0) { x->next = new_long_long_integer(t); /* 超長整数に整数を足す関数 */ void add_int(long_long_int *x, int t) { int i; x->num[i] += t; t = x->num[i] / 10000; x->num[i] %= 10000; 37
/* 超長整数の表示 */ void print_long_long_int(long_long_int *x) { int i; if(x->next == NULL) { for(i = 4; (x->num[i] == 0) && (i > 0); i--); printf("%d", x->num[i]); else { print_long_long_int(x->next); i = 5; for(i--; i >= 0; i--){ printf("%04d", x->num[i]); 練習問題 3.1 指定された値のノードがあればその node 構造体へのポインタを なければ NULL を返す関数 find_node を作成せよ ex29.c /* リストからデータの探索 */ typedef struct node { int value; struct node *next; node; void print_list(node *s); void insert_list(node **s, int x); node *find_node(node *s, int x); node * NULL, *find; int i, x; printf(" 値を入力してください : "); scanf("%d", &x); insert_list(&start, x); print_list(start); printf(" 検索する整数 : "); scanf("%d", &x); find = find_node(start, x); if(find == NULL) { printf(" 見つかりませんでした n"); else { printf(" 見つかりました : %d(%p) n", find->value, find); 38
/* データの表示 */ void print_list(node *s) { printf("start "); for( ; s!= NULL; s = s->next) { printf("%d ", s->value); printf("null n"); /* データの挿入 */ void insert_list(node **s, int x) { node *new, *z; new = (node *)malloc(sizeof(node)); new->value = x; if(*s == NULL (*s)->value > x) { /* 先頭に追加する場合 */ new->next = *s; *s = new; else { /* 途中または最後に追加する場合 */ for(z = *s ; z->next!= NULL && z->next->value < x; z = z->next); new->next = z->next; z->next = new; /* データの探索 */ node *find_node(node *s, int x) { 練習問題 3.2 指定された値のノードがあればその node を削除 なければ何もしない関数 del_node を作成せよ ex30.c /* リストからデータの探索 */ typedef struct node { int value; struct node *next; node; void print_list(node *s); void insert_list(node **s, int x); void del_node(node **s, int x); 39
node * NULL, *find; int i, x; printf(" 値を入力してください : "); scanf("%d", &x); insert_list(&start, x); print_list(start); printf(" 検索する整数 : "); scanf("%d", &x); del_node(&start, x); print_list(start); /* データの表示 */ void print_list(node *s) { printf("start "); for( ; s!= NULL; s = s->next) { printf("%d ", s->value); printf("null n"); /* データの挿入 */ void insert_list(node **s, int x) { node *new, *z; new = (node *)malloc(sizeof(node)); new->value = x; if(*s == NULL (*s)->value > x) { /* 先頭に追加する場合 */ new->next = *s; *s = new; else { /* 途中または最後に追加する場合 */ for(z = *s ; z->next!= NULL && z->next->value < x; z = z->next); new->next = z->next; z->next = new; /* データの削除 */ void del_node(node **s, int x) { 40