DS Project 6: BST

DS_project6.md

題目

In this project you need to use Binary Search Tree. Input Data is a text file containing a keyword in a line, prefixed by an operator

+ for insertion - for deletion

For example:

+apple
+banana
+lemon
+apple
+apple
-lemon
+apple
-lemon
-apple
+lemon
+lemon

程式讀進資料後建立一個 Binary Search Tree (BST)，每個節點存放 keyword 與它的次數。

+apple 表示新增一個 apple。 如果 apple 已經存在則增加它的個數；不存在則為 apple 新增一個節點並把個數設為 1。

-apple 表示刪減一個 apple。 如果 apple 存在則其個數減 1；假設減完後個數變成零，則刪除該節點。如果要刪減的 keyword 不存在，則輸出"XXX does not exist"的錯誤訊息。

當 keyword 前沒有 operator 則跳過該行。

全部資料處理完畢後進入互動模式： The following commands need to be supported

s keyword : 如果 keyword 存在，則輸出其個數

i : 依照 inorder traversal 列出所有的 keyword 及其個數

n : 依照個數由大到小輸出所有的 keyword

##Example

Invoke

./bst input.txt

maybe yields

"candy does not exist.

interactive mode:

> s banana
banana 1

> i
apple 3
banana 1
candy 2

> n
3 apple
2 candy
1 banana

Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

struct Node_ {
    struct Node_* left;
    struct Node_* right;
    char* data;
    int cnt;
};

typedef struct Node_ Node;

int node_cmp(const void* a, const void* b) {
    Node* na = (Node*) a;
    Node* nb = (Node*) b;

    return ((na->cnt) - (nb->cnt));
}

Node* bst_insert(Node* p, const char* s) {
    if (p == NULL) {
        Node* q = (Node*) malloc (sizeof(Node));
        q->left = NULL;
        q->right = NULL;
        q->cnt = 1;
        q->data = (char*) malloc (sizeof(char) * (strlen(s)+1));
        strcpy(q->data, s);
        return q;
    }
    else {
        int flag = strcmp(s, p->data);
        if (flag < 0)
            p->left = bst_insert(p->left, s);
        else if (flag > 0)
            p->right = bst_insert(p->right, s);
        else
            (p->cnt)++;
        return p;
    }
}

Node* bst_find(Node* p, const char* s) {
    if (p == NULL) return NULL;
    int flag = strcmp(s, p->data);
    if (flag > 0)
        return bst_find(p->right, s);
    else if (flag < 0)
        return bst_find(p->left, s);
    else
        return p;
}

Node* bst_remove(Node* p, const char* s) {
    if (p == NULL) return NULL;

    int flag = strcmp(s, p->data);
    if (flag > 0)
        p->right = bst_remove(p->right, s);
    else if (flag < 0)
        p->left = bst_remove(p->left, s);
    else {
        if (p->cnt > 1) {
            (p->cnt)--;
            return p;
        }
        else if (p->left == NULL) {
            Node* q = p->right;
            free(p->data);
            free(p);
            return q;
        }
        else if (p->left->right == NULL) {
            Node* q = p->left;
            q->right = p->right;
            free(p->data);
            free(p);
            return q;
        }
        else {
            Node* q;
            for (q=p->left; q->right->right != NULL; q=q->right);
            Node* r = q->right;
            q->right = r->left;
            r->left = p->left;
            r->right = p->right;
            free(p->data);
            free(p);
            return r;
        }
    }

    return p;
}

void bst_inorder(Node* p) {
    if (p == NULL) return;

    bst_inorder(p->left);
    printf("%s: %d\n", p->data, p->cnt);
    bst_inorder(p->right);
}

int bst_build_list(Node* p, Node* list) {
    static int idx = 0;

    if (p == NULL) return 0;

    bst_build_list(p->left, list);
    list[idx++] = *p;
    bst_build_list(p->right, list);

    return idx;
}

void free_bst(Node* root) {
    if (root == NULL) return;

    free_bst(root->left);
    free_bst(root->right);

    free(root->data);
    free(root);
}

int main(int argc, char* argv[]) {
    if (argc < 2) {
        return -1;
    }

    FILE* f = fopen(argv[1], "r");
    if (f == NULL) {
        puts("File not exist!");
        return -1;
    }

    Node* root = NULL;

    char input[1024];
    while (fgets(input, 1024, f) != NULL) {
        int len = strlen(input);
        if (input[len-1] == '\n') {
            input[len-1] = '\0';
            len--;
        }

        printf("%s: ", input);
        if (input[0] == '+') {
            const char* s = input+1;
            root = bst_insert(root, s);

            puts("Success");
        }
        else if (input[0] == '-') {
            const char* s = input+1;
            if (bst_find(root, s) == NULL) {
                puts("Not exist");
                continue;
            }
            bst_remove(root, s);
            
            puts("Success");
        }
        else {
            printf("Illegal Data: %s\n", input);
            continue;
        }
    }

    while (true) {
        printf("> ");
        fgets(input, 1024, stdin);

        int len = strlen(input);
        if (input[len-1] == '\n') {
            input[len-1] = '\0';
            len--;
        }

        char* cmd = strtok(input, " ");
        char* arg = strtok(NULL, " ");
        if (strcmp(cmd, "s") == 0 && arg != NULL) {
            Node* f = bst_find(root, arg);
            if (f == NULL) {
                puts("Not exists!");
                continue;
            }
            printf("%d\n", f->cnt);
        }
        else if(strcmp(input, "i") == 0) {
            bst_inorder(root);
        }
        else if (strcmp(input, "n") == 0) {
            Node list[1024];
            int N = bst_build_list(root, list);
            qsort(list, N, sizeof(Node), node_cmp);

            for (int i=N-1; i>=0; i--)
                printf("%d %s\n", list[i].cnt, list[i].data);
        }
        else if (strcmp(input, "q") == 0) {
            break;
        }
        else {
            puts("Illegal Command!");
            continue;
        }
    }

    free_bst(root);

    puts("program exits");

    return 0;
}

bst_build_list 因使用 static var 有瑕疪，只能正確運行一次，待改