2014 Data Structures and Algorithms


  • list3-1.c
#include <stdio.h>
#include <stdlib.h>
 
#define NMAX    10
 
int main(void) {
    int buf, sum, count, n;
    int array[NMAX];
 
    count = 0;
    do {
        printf("整数を入力してください(0を入力すると終了):");
        scanf("%d", &buf);
        if(buf) {
            array[count] = buf;
            count++;
        }
    } while(buf != 0);
 
    /* 合計値を算出 */
    printf("--入力されたのは以下の数です--\n");
    for(sum = n = 0; n < count; n++) {
        printf("%d \t", array[n]);
        sum += array[n];
    }
    printf("\n----\n以上の数の合計値は%dです。\n", sum);
 
    return EXIT_SUCCESS;
}




  • list3-2.c
#include <stdio.h>
#include <stdlib.h>
 
int main(void) {
    int buf, sum, count, n, i;
    int *array;
 
    /* 入力するデータの個数を最初に聞いて,必要なメモリを確保 */
    printf("何個の数値を入力しますか:");
    scanf("%d", &count);
    array = (int*)malloc(sizeof(int) * count);
 
    n = 0;
    do {
        printf("整数を入力してください(0を入力すると終了):");
        scanf("%d", &buf);
        if(buf) {
            array[n] = buf;
            n++;
        }
    } while(buf != 0);
 
    /* 合計値を算出 */
    printf("--入力されたのは以下の数です--\n");
    for(sum = i = 0; i < n; i++) {
        printf("%d\t", array[i]);
        sum += array[i];
    }
    printf("\n----\n以上の数の合計値は %d です。\n", sum);
 
    free(array);
    return EXIT_SUCCESS;
}




コードを次のように変更してみよう。
  1. 合計値を算出するかわりに、最大値を算出してみよう。
  2. 手で値を入力するのではなく、1から1,000までの整数など適当な値を自動的に次々と追加するように変更してみよう。
  3. 配列が満杯になった時に、配列を倍にするのではなく、ひとつずつだけサイズを増やすように変更してみよう。
  4. 上のようにしたとき、実行時間がどう変わるか、確認してみよう。 (差が分かるような実験をすること。配列の最大のサイズを大きくする、全体の作業を何回か繰り返す、など。)
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
 
int main(void) {
    int buf, sum, count, n, size;
    int *array, *temp;
 
    /* 最初の配列サイズは10 */
    size = 10;
    array = (int*)malloc(sizeof(int) * size);
 
    count = 0;
    do {
        printf("整数を入力してください(0を入力すると終了):");
        scanf("%d", &buf);
        if(buf) {
            array[count] = buf;
            count++;
            /* 配列が満杯になったら,倍の大きさに拡張する */
            if(count == size) {
                /* 新しい大きなメモリブロックを確保して,
                   元の内容をコピー。
                   realloc()を使っても同様の作業が行われる */
                temp = (int*)malloc(sizeof(int) * size * 2);
                memcpy(temp, array, sizeof(int) * size);
                free(array);
                array = temp;
                size *= 2;
            }
        }
    } while(buf != 0);
 
    /* 合計値を算出 */
    printf("--入力されたのは以下の数です--\n");
    for(sum = n = 0; n < count; n++) {
        printf("%d\t", array[n]);
        sum += array[n];
    }
    printf("\n----\n以上の数の合計値は%dです。\n", sum);
 
    free(array);
    return EXIT_SUCCESS;
}




コードを次のように変更してみよう。
  1. 入力するデータの型をintからdoubleに変更しよう。
  2. 合計値を算出するかわりに、平均値を算出してみよう。
#include <stdio.h>
#include <stdlib.h>
 
/* リストの要素(ノード)を表す構造体 */
typedef struct tagListNode {
    struct tagListNode *prev;    /* 前の要素へのポインタ */
    struct tagListNode *next;    /* 次の要素へのポインタ */
    int data;   /* この要素がもっているデータ */
} ListNode;
 
int main(void) {
    int buf, sum;
    ListNode *firstnode, *lastnode, *newnode, *thisnode, *removenode;
 
    firstnode = lastnode = NULL;
 
    do {
        printf("整数を入力してください(0を入力すると終了):");
        scanf("%d", &buf);
        if(buf) {    /* 新たな入力があったら */
            /* 新しいノードを作成 */
            newnode = (ListNode*)malloc(sizeof(ListNode));
            newnode->data = buf;
            newnode->next = NULL;
 
            if(lastnode != NULL) {
                /* すでにあるリストの末尾に
                   新しいノードをつなげる */
                lastnode->next = newnode;
                newnode->prev = lastnode;
                lastnode = newnode;
            } else {
                /* これが最初の要素だった場合 */
                firstnode = lastnode = newnode;
                newnode->prev = NULL;
            }
        }
    } while(buf != 0);
 
    /* 合計値を算出 */
    printf("--入力されたのは以下の数です--\n");
    sum = 0;
    for(thisnode = firstnode; thisnode != NULL;
                                thisnode = thisnode->next) {
        printf("%d\t", thisnode->data);
        sum += thisnode->data;
    }
    printf("\n----\n以上の数の合計値は%dです。\n", sum);
 
    /* リストの全ノードを削除 */
    for(thisnode = firstnode; thisnode != NULL;) {
        removenode = thisnode;
        thisnode = thisnode->next;
        free(removenode);
    }
 
    return EXIT_SUCCESS;
}




コードを次のように変更してみよう。
  1. 検索するたびにリストの中身をすべて表示するようにしよう。(ヒント:list3-4.cをよく読む。)
  2. 検索して見つかっても削除しないようにしてみよう。
  3. 検索して見つかったら、ひとつ前のノードと入れ替えるようにしてみよう。(値を入れ替えるだけはダメ。)
#include <stdio.h>
#include <stdlib.h>
 
/* リストの要素(ノード)を表す構造体 */
typedef struct tagListNode {
    struct tagListNode *prev;   /* 前の要素へのポインタ */
    struct tagListNode *next;   /* 次の要素へのポインタ */
    int data;   /* この要素がもっているデータ */
} ListNode;
 
int main(void) {
    int buf;
    ListNode *firstnode, *lastnode, *newnode, *thisnode, *removenode;
 
    firstnode = lastnode = NULL;
 
    do {
        printf("整数を入力してください(0を入力すると終了):");
        scanf("%d", &buf);
        if(buf) {    /* 新たな入力があったら */
            /* 新しいノードを作成 */
            newnode = (ListNode*)malloc(sizeof(ListNode));
            newnode->data = buf;
            newnode->next = NULL;
 
            if(lastnode != NULL) {
                /* すでにあるリストの末尾に
                   新しいノードをつなげる */
                lastnode->next = newnode;
                newnode->prev = lastnode;
                lastnode = newnode;
            } else {
                /* これが最初の要素だった場合 */
                firstnode = lastnode = newnode;
                newnode->prev = NULL;
            }
        }
    } while(buf != 0);
 
    /* 検索値を入力 */
    do {
        printf("検索する値を入力してください(0を入力すると終了):");
        scanf("%d", &buf);
 
        if(buf != 0) {
            /* 最初に入力した値のなかから検索し,
               見つかったら削除 */
            for(thisnode = firstnode; thisnode != NULL;
                                        thisnode = thisnode->next) {
                if(thisnode->data==buf) {
                    printf("入力された値のなかに%dが見つかり"
                           "ました。ノードを削除します。\n", buf);
 
                    if(thisnode->prev != NULL) {
                        thisnode->prev->next = thisnode->next;
                    } else {
                        firstnode = thisnode->next;
                    }
 
                    if(thisnode->next != NULL) {
                        thisnode->next->prev = thisnode->prev;
                    }
 
                    free(thisnode);
                    break;
                }
            }
            if(thisnode == NULL) {
                printf("%dは入力されていないか,すで削除されています。\n", buf);
            }
        }
    } while(buf != 0);
 
    /* 残ったノードをすべて削除 */
    for(thisnode = firstnode; thisnode != NULL;) {
        removenode = thisnode;
        thisnode = thisnode->next;
        free(removenode);
    }
 
    return EXIT_SUCCESS;
}




コードについて次のことを確認してみよう。
  1. list3-5.cに比べて、どのような場合に効率が良くなるか、どのような場合に効率が変わらないか、考えてみよう。
  2. それらの場合に相当する検索を自動的に行うようなコードを書き、実際に実行時間がどうなるか、測ってみよう。
#include <stdio.h>
#include <stdlib.h>
 
/* リストの要素(ノード)を表す構造体 */
typedef struct tagListNode {
    struct tagListNode *next;   /* 次の要素へのポインタ */
    int data;   /* この要素がもっているデータ */
} ListNode;
 
int main(void) {
    int buf;
    ListNode *firstnode, *lastnode, *newnode, *thisnode, *tmpnode;
 
    firstnode = lastnode = NULL;
 
    do {
        printf("整数を入力してください(0を入力すると終了):");
        scanf("%d", &buf);
        if(buf) {    /* 新たな入力があったら */
            /* 新しいノードを作成 */
            newnode = (ListNode*)malloc(sizeof(ListNode));
            newnode->data = buf;
            newnode->next = NULL;
 
            if(lastnode != NULL) {
                /* すでにあるリストの末尾に
                   新しいノードをつなげる */
                lastnode->next = newnode;
                lastnode = newnode;
            } else {
                /* これが最初の要素だった場合 */
                firstnode = lastnode = newnode;
            }
        }
    } while(buf != 0);
 
    do {
        printf("現在の並び:\n");
        for(thisnode = firstnode; thisnode != NULL;
                                        thisnode = thisnode->next) {
            printf("%d\t",thisnode->data);
        }
 
        /* 検索値を入力 */
        printf("\n検索する値を入力してください"
               "(0を入力すると終了):");
        scanf("%d", &buf);
 
        if(buf!=0) {
            /* 最初に入力した値のなかから検索 */
            for(thisnode = firstnode; thisnode != NULL;
                        tmpnode = thisnode, thisnode = thisnode->next) {
                if(thisnode->data == buf) {
                    printf("入力された値のなかに%dが"
                                       "見つかりました。\n", buf);
 
                    if(thisnode!=firstnode) {
                        /* 検索で見つかったノードを
                           先頭にもってくる */
                        tmpnode->next = thisnode->next;
 
                        if(lastnode == thisnode) {
                            lastnode = tmpnode;
                        }
 
                        thisnode->next = firstnode;
                        firstnode = thisnode;
                    }
                    break;
                }
            }
            if(thisnode == NULL) {
                printf("%dは入力されていませんでした。\n", buf);
            }
        }
    } while(buf != 0);
 
    thisnode = firstnode;
    while(thisnode != NULL) {
        tmpnode = thisnode->next;
        free(thisnode);
        thisnode = tmpnode;
    }
 
    return EXIT_SUCCESS;
}