Microsoft Word - no205.docx

Transcription

1 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

2 /* 先頭データの削除 */ 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

3 今までは 順序良く入力してきましたが 入力されたものを順序良く格納する例を考えてみます こ の場合も 最初に入る可能性があるために 先頭を表すポインタ変数へのポインタを利用します 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

4 順に入力してどのようなリストが出来ているか考えてみましょう 最初の状態 30 を入力 50 を入力 40 を入力 33

5 10 を入力 20 を入力 34

6 では このリストを用いた簡単な例を考えてみましょう flight.txt ANA 羽田 ANA 羽田 ANA 羽田 ANA 羽田 ANA 羽田 JAL 羽田 JAL 羽田 JAL 羽田 JAL 羽田 JAL 羽田 ADO 札幌 JTA 沖縄 岡山空港を出発する時刻表です これを出発時刻順に連結リストに格納します 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

7 /* データの表示 */ 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

8 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

9 /* 超長整数の表示 */ 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

10 /* データの表示 */ 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

11 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