Stack(推疊)

/*
 * An Implementation of a char stack
 */
#define MAXLEN 100
typedef char Data;
typedef struct _stack {
    int top;
    Data data[MAXLEN];
} Stack;

void stackInit(Stack* s) {
    s->top = 0;
}

Data stackPop(Stack *s) {
    return s->data[--s->top];
}

Data stackPush(Stack *s, Data x) {
    s->data[s->top++] = x;
    return x;
}

main() {
    int i;
    Stack s;
    stackInit(&s);
    printf("push %c\n", stackPush(&s, 'a'));
    printf("push %c\n", stackPush(&s, 'b'));
    printf("pop %c\n", stackPop(&s));
    printf("pop %c\n", stackPop(&s));
}

Queue(佇列)

/* 本範例使用循環陣列(cyclic array)來實作Queue*/
#include <stdio.h>
#define MAXLEN 100
typedef struct {
    int count;
    int head;
    int tail;
    int data[MAXLEN];
} QUEUE;
void queueInit(QUEUE *q) {
    // head處有資料,tail處無資料
    q->head = q->tail = q->count = 0;
}
void queueAdd(QUEUE *q, int val) {
    if (q->count >= MAXLEN) {
        printf("Queue is full\n");
        exit(0);;
    }
    // 放到tail上
    q->data[q->tail++] = val;
    // 如果tail超過陣列大小,要設為0
    q->tail %= MAXLEN;
    q->count++;
}
int queueRemove(QUEUE *q) {
    int tmp;
    if (q->count <= 0) {
        printf("Queue is empty\n");
        exit(0);
    }
    q->count--;
    // 拿出head資料
    tmp = q->data[q->head++];
    // 如果head超過陣列大小,要設為0
    q->head %= MAXLEN;
    return tmp;
}
int queueIsFull(QUEUE *q) {
    return q->count >= MAXLEN;
}
int queueIsEmpty(QUEUE *q) {
    return q->count <= 0;
}
void main() {
    QUEUE q;
    queueInit(&q);
    queueAdd(&q, 100);
    queueAdd(&q, 200);
    printf("%d\n", queueRemove(&q));
    printf("%d\n", queueRemove(&q));
}

Binary Tree(二元樹)

#include <stdio.h>
typedef struct tree {
    int size;
    struct node *root;
} TREE;
typedef struct node {
    int data;
    struct node * left;
    struct node * right;
    struct node * parent;
} NODE;
NODE * allocNode(int val) {
    NODE *tmp;
    if ((tmp = (NODE*)malloc(sizeof(NODE))) == NULL) {
        printf("No memory\n");
        exit(0);
    }
    tmp->left = tmp->right = tmp->parent = NULL;
    tmp->data = val;
    return tmp;
}
void treeInit(TREE * t) {
    t->size = 0;
    t->root = NULL;
}
void inorderTreeWalk(NODE * root) {
    if (root != NULL) {
        inorderTreeWalk(root->left);
        printf("%d\n", root->data);
        inorderTreeWalk(root->right);
    }
}
NODE * treeSearch(NODE * root, int val) {
    if (root == NULL || val == root->data) {
        return root;
    }
    if (val < root->data) {
        return treeSearch(root->left, val);
    }
    return treeSearch(root->right, val);
}
NODE * iterativeTreeSearch(NODE * root, int val) {
    while (root != NULL && val != root->data) {
        if (val < root->data) {
            root = root->left;
        } else {
            root = root->right;
        }
    }
    return root;
}
NODE * treeMinimum(NODE * root) {
    while (root->left != NULL) {
        root = root->left;
    }
    return root;
}
NODE * treeMaximun(NODE * root) {
    while (root->right != NULL) {
        root = root->right;
    }
    return root;
}
NODE * treeSuccessor(NODE * root) {
    NODE * y;
    // 有右子樹,找右邊最小的
    if (root->right != NULL) {
        return treeMinimum(root->right);
    }
    // 沒有右子樹,只好往上找,y設定為root的父親
    y = root->parent;
    // 若在父親的左邊,則父親就是下一個
    while (y != NULL && root == y->right) {
        root = y;
        y = root->parent;
    }
    return y;
}
void treeInsert(TREE * t, NODE * z) {
    NODE *x, *y; // y是x的父親
    y = NULL;
    x = t->root;
    // 找leave node y好讓z放在y下面
    while (x != NULL) {
        y = x;
        if (x->data < z->val) {
            x = x->right;
        } else {
            x = x->left;
        }
    }
    z->parent = y;
    t->size++;
    if (y == NULL) { // 第一次新增節點
        t->root = z;
    } else {
        if (z->val < y->data) {
            y->left = z;
        } else {
            y->right = z;
        }
    }
}
/* 刪除z節點,傳回實際刪除的節點 */
NODE * treeDelete(TREE * t, NODE * z) {
    NODE * y, * x;
    // 如果z只有0或1個子樹,則可把z的子樹往上提,
    // 不然只好找z的下一個y,在z有兩個子樹的情況下y保證沒有左子樹,再把z的內容換成y的
    // 因此變數y定義為實際上要刪除的節點,變數x是y的子節點
    if (z->left == NULL || z->right == NULL) {
        y = z;
    } else {
        y = treeSuccessor(z);
    }
    // 找出y下面的子樹(如一開頭的註解,最多1個)
    if (y->left != NULL) {
        x = y->left;
    } else {
        x = y->right;
    }
    if (x != NULL) { // y有子樹x,把x提上來
        x->parent = y->parent;
    }
    if (y->parent == NULL) { // 砍到根節點了
        t->root = x;
    } else {
        // 把y的父節點的子節點設成x
        if (y == y->parent->left) {
            y->parnet->left = x;
        } else {
            y->parent->right = x;
        }
    }
    // 如果是用successor取代的方式,記得把y的資訊複製到z
    if (y != z) {
        z->data = y->data;
    }
    free(y);
    t->size--;
}