2014 Data Structures and Algorithms


コードを次のように変更してみよう。
  1. 何か操作をするたびに、スタックの中味をすべて表示させるようにしよう。
  2. スタックが満杯になったら自動的にスタックの容量が増えるようにしてみよう。
#include <stdio.h>
#include <stdlib.h>
 
#define STACK_MAX 10
 
/* ※この例では,double型のデータを格納するスタックを作成 */
double stack[STACK_MAX];
/* スタック頂上の位置(最下部からのオフセット) */
int stack_top = 0;
 
/* スタックへpush */
void stack_push(double val) {
    if(stack_top == STACK_MAX) {
        /* スタックが満杯になっている */
        printf("Stack overflow\n");
        exit(EXIT_FAILURE);
    } else {
        /* 渡された値をスタックに積む */
        stack[stack_top] = val;
        stack_top++;
    }
}
 
/* スタックからデータをpop */
double stack_pop(void) {
    if(stack_top == 0) {
        /* スタックには何もない */
        printf("Stack underflow\n");
        exit(EXIT_FAILURE);
        return 0;
    } else {
        /* いちばん上の値を返す */
        stack_top--;
        return stack[stack_top];
    }
}
 
int main(void) {
    int action;
    double val;
    for (;;){
        action = 0;
        printf("実行する操作を入力してください。\n\t1 :push\t2 :pop >");
        scanf("%d", &action);
        switch(action) {
        case 1:
            printf("pushする数値を入力してください:");
            scanf("%lf", &val);
            stack_push(val);
            break;
        case 2:
            val = stack_pop();
            printf("popされた値: %lf\n", val);
            break;
        default:
            return EXIT_SUCCESS;
    }
  }
}



  • list4-2.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
/*カッコの種類*/
#define STAPLE_SMALL  1
#define STAPLE_MEDIUM 2
#define STAPLE_LARGE  3
 
/* 1つのカッコを示す構造体 */
typedef struct _tagstaple {
    int line;       /* カッコのある行 */
    int column;     /* カッコのある列(行頭からの文字数) */
    int type;       /* カッコの種類 */
 
    /* リストによるスタック構造 */
    struct _tagstaple *staple_next;
    struct _tagstaple *staple_prev;
} staple;
 
/* リストによるスタック構造 */
staple *staple_head = NULL;
staple *staple_last = NULL;
 
/*スタックへのpush */
void stack_push(int line,int column,int type) {
    staple *staple_new;
 
    /* 新しい領域を確保 */
    staple_new = (staple*)malloc(sizeof(staple));
    if(staple_new == NULL) {
        printf("スタックオーバフローです。メモリが足りません");
        exit(EXIT_FAILURE);
        return;
    }
 
    /* 渡された値をスタックに積む */
    staple_new->line = line;
    staple_new->column = column;
    staple_new->type = type;
 
    /* リストの最後に追加する */
    staple_new->staple_next = NULL;
    staple_new->staple_prev = staple_last;
    staple_last = staple_new;
    if(staple_head == NULL) {
        staple_head = staple_new;
    }
}
 
/* スタックからpop */
int stack_pop(staple *ret) {
    staple *temp_staple;
 
    if(staple_head == NULL) {
        /* スタックには何もない:カッコの対応がとれていない */
        return 0;   /* エラー */
    }
 
    /* いちばん最後にpushされたカッコの情報を返す */
    ret->line = staple_last->line;
    ret->column = staple_last->column;
    ret->type = staple_last->type;
    ret->staple_next = ret->staple_prev = NULL;
    temp_staple = staple_last;
 
    /* リストから削除する */
    if(staple_last->staple_prev == NULL) {
        staple_head = NULL;
    } else {
        staple_last->staple_prev->staple_next = NULL;
    }
 
    staple_last = staple_last->staple_prev;
 
    free(temp_staple);
 
    return 1;   /* 成功 */
}
 
int main(void) {
    char buffer[4096];
    int i, len, line = 1, carryover = 0;
    staple open;
 
    for(;;) {
        if(fgets(buffer, 4096, stdin) == NULL) {
        /* 終端まで読み込んだ */
            break;
        }
        len = strlen(buffer);
        if(len == 0) {
            continue;
        }
 
        for(i = 0; i < len; i++) {
            switch(buffer[i]) {
            case '(':
                stack_push(line,carryover + i + 1, STAPLE_SMALL);
                break;
            case '{':
                stack_push(line,carryover + i + 1, STAPLE_MEDIUM);
                break;
            case '[':
                stack_push(line,carryover + i + 1, STAPLE_LARGE);
                break;
            case ')':
                if(stack_pop(&open) == 0) {
                    printf("カッコの対応がとれていません\n");
                    printf("%d行%d文字に対応する"
                               "開きカッコがありません\n",
                                        line, carryover + i + 1);
                    return EXIT_FAILURE;
                }
                if(open.type!=STAPLE_SMALL) {
                    printf("カッコの対応がとれていません\n");
                    printf("%d行%d文字に対応するカッコと"
                            "%d行%d文字に対応するカッコの種類が"
                            "違います\n", open.line, open.column,
                                            line, carryover + i + 1);
                    return EXIT_FAILURE;
                }
                break;
            case '}':
                if(stack_pop(&open) == 0) {
                    printf("カッコの対応がとれていません\n");
                    printf("%d行%d文字に対応する開きカッコが"
                            "ありません\n", line, carryover + i + 1);
                    return EXIT_FAILURE;
                }
                if(open.type!=STAPLE_MEDIUM) {
                    printf("カッコの対応がとれていません\n");
                    printf("%d行%d文字に対応するカッコと"
                            "%d行%d文字に対応するカッコの種類が"
                            "違います\n", open.line, open.column,
                                            line, carryover + i + 1);
                    return EXIT_FAILURE;
                }
                break;
            case ']':
                if(stack_pop(&open)==0) {
                    printf("カッコの対応がとれていません\n");
                    printf("%d行%d文字に対応する開きカッコが"
                            "ありません\n", line, carryover + i + 1);
                    return EXIT_FAILURE;
                }
                if(open.type!=STAPLE_LARGE) {
                    printf("カッコの対応がとれていません\n");
                    printf("%d行%d文字に対応するカッコと"
                            "%d行%d文字に対応するカッコの種類が"
                            "違います\n", open.line, open.column,
                                            line, carryover + i + 1);
                    return EXIT_FAILURE;
                }
                break;
            }
        }
 
        if(buffer[len - 1] == '\n') {
            carryover = 0;
            line++;
        } else {
            /* 4096文字読み込んでも,改行に出会わなかった場合 */
            carryover += len;
        }
    }
 
    /* 完全にカッコの対応がとれていれば
       スタックは空になっているはず */
    if(staple_head != NULL) {
        /* 開きカッコが多い */
        printf("カッコの対応がとれていません\n");
        printf("開きカッコの数が多すぎます\n");
        return EXIT_FAILURE;
    }
 
    printf("カッコの対応は正しくとれています\n");
    return EXIT_SUCCESS;
}



コードを次のように変えてみよう。
  1. 加減乗除だけでなく、余りを求める演算(%)やべき乗演算(^)も使えるようにしてみよう。
#include <stdio.h>
#include <stdlib.h>
 
#define STACK_MAX 10
 
/* 配列によるスタック構造 */
double stack[STACK_MAX];
/* スタック頂上の位置(最下部からのオフセット)*/
int stack_top = 0;
 
/* スタックへのpush */
void stack_push(double val) {
    if(stack_top == STACK_MAX) {
        /* スタックが満杯になっている */
        printf("エラー:スタックが満杯です(Stack overflow)\n");
        exit(EXIT_FAILURE);
    } else {
        /* 渡された値をスタックに積む */
        stack[stack_top] = val;
        stack_top++;
    }
}
 
/* スタックからpop */
double stack_pop(void)
{
    if(stack_top == 0) {
        /* スタックには何もない */
        printf("エラー:スタックが空なのにpopが呼ばれました"
                                    "(Stack underflow)\n");
        exit(EXIT_FAILURE);
        return 0;
    } else {
        /* いちばん上の値を返す */
        stack_top--;
        return stack[stack_top];
    }
}
 
int main(void) {
    char buffer[256];
    double cal1, cal2;
    int i;
 
    do {
        printf("現在のスタック(%d個):", stack_top);
        for(i = 0; i < stack_top; i++) {
            printf("%0.3f ", stack[i]);
        }
        printf("\n>");
        fgets(buffer, 255, stdin);
        switch(buffer[0]) {
        case '+':
            cal1 = stack_pop();
            cal2 = stack_pop();
            stack_push(cal2 + cal1);
            break;
        case '-':
            cal1 = stack_pop();
            cal2 = stack_pop();
            stack_push(cal2 - cal1);
            break;
        case '*':
            cal1 = stack_pop();
            cal2 = stack_pop();
            stack_push(cal2 * cal1);
            break;
        case '/':
            cal1 = stack_pop();
            cal2 = stack_pop();
            stack_push(cal2 / cal1);
            break;
        case '=':
            /* =の場合はこのすぐあとでwhile文からも抜ける */
            break;
        default:
            /* 入力された値は数字のはずなので,スタックに積む */
            stack_push(atoi(buffer));
            break;
        }
    } while(buffer[0] != '=');
 
    printf("計算結果は%f です。\n",stack_pop());
    if(stack_top != 0) {
        printf("エラー:スタックにまだ数が残っています\n");
        return EXIT_FAILURE;
    }
 
    return EXIT_SUCCESS;
}



コードを次のように変更してみよう。
  1. 何か操作をするたびに、キューの中味をすべて表示させるようにしよう。
  2. キューが満杯になったら自動的にキューの容量が増えるようにしてみよう。
#include <stdio.h>
#include <stdlib.h>
 
#define QUEUE_MAX (5 + 1)   /* キューのサイズ+1 */
#define QUEUE_EMPTY -1
 
/* 配列によるキュー構造 */
int queue[QUEUE_MAX];
int queue_first = 0;      /* キューの先頭位置 */
int queue_last = 0;       /* キューの末尾位置 */
 
/* キューにデータを追加する */
void enqueue(int val) {
    /* lastの次がfirstならば */
    if((queue_last + 1) % QUEUE_MAX == queue_first) {
        /* 現在配列の中身は,すべてキューの要素で埋まっている */
        printf("Queue overflow\n");
    } else {
        /* キューに新しい値を入れる */
        queue[queue_last] = val;
        /* queue_lastを1つ後ろにずらす。
           もし,いちばん後ろの場合は,先頭にもってくる */
        queue_last = (queue_last + 1) % QUEUE_MAX;
    }
}
 
/* キューからデータを取り出す */
int dequeue(void) {
    int ret;
 
    if(queue_first == queue_last) {
        /* 現在キューは1つもない */
        return QUEUE_EMPTY;
    } else {
        /* いちばん先頭のキューを返す準備 */
        ret = queue[queue_first];
        /* キューの先頭を次に移動する */
        queue_first = (queue_first + 1) % QUEUE_MAX;
        return ret;
    }
}
 
/* キューの全内容を表示する */
void queue_print(void) {
    int i;
    for(i = queue_first; i != queue_last; i = (i + 1) % QUEUE_MAX) {
        printf("%d ", queue[i]);
    }
}
 
int main(void) {
    int i, j;
    do {
        printf("current queue: ");
        queue_print();
        printf("\n0:終了 1:jobをためる 2:jobを実行\n>");
        scanf("%d", &i);
        switch(i) {
        case 1:
            printf("jobの識別番号(1~1000)を適当に入力してください:");
            scanf("%d", &j);
            if(j >= 1 && j <= 1000) {
                enqueue(j);
            }
            break;
        case 2:
            j = dequeue();
            if(j==QUEUE_EMPTY) {
                printf("Queue underflow\n");
            } else {
                printf("識別番号%dのjobを実行中...\n" ,j);
            }
            break;
        }
    } while(i != 0);
 
    return EXIT_SUCCESS;
}