堆疊(Stacks)

  • 只能在頂端進行插入和刪除的線性串列(後進先出LIFO)
// 線性串列實作堆疊
typedef struct {
    ElemType data[MAXSIZE];
    int top;
} SqStack;

int InitStack(SqStack *S) {
    S->top = -1;
    return 0;
}

int Push(SqStack *S, ElemType e) {
    if (S->top == MAXSIZE - 1)
        return -1;
    S->data[++S->top] = e;
    return 0;
}

int Pop(SqStack *S, ElemType *e) {
    if (S->top == -1)
        return -1;
    *e = S->data[S->top--];
    return 0;
}

// 兩堆疊共用空間(對於空間需求有相反的關係)
typedef struct {
    ElemType data[MAXSIZE];
    int top1;
    int top2;
} SqDoubleStack;

int Push(SqDoubleStack *S, ElemType e, int stackNumber) {
    if (S->top1 + 1 == S->top2)
        return -1;
    if (stackNumber == 1)
        S->data[++S->top1] = e;
    else if (stackNumber == 2)
        S->data[--S->top2] = e;
    return 0;
}

int Pop(SqDoubleStack *S, ElemType *e, int stackNumber) {
    if (stackNumber == 1) {
        if (S->top1 == -1)
            return -1;
        *e = S->data[S->top1--];
    } else if (stackNumber == 2) {
        if (S->top2 == MAXSIZE)
            return -1;
        *e = S->data[S->top2++];
    }
    return 0;
}

// 鏈結串列實作堆疊
typedef struct StackNode {
    ElemType data;
    struct StackNode *next;
} StackNode, *StackNodePtr;

typedef struct LinkStack {
    StackNodePtr top;
    int count;
} LinkStack;

int InitStack(LinkStack *S) {
    S->top = NULL;
    S->count = 0;
    return 0;
}

int Push(LinkStack *S, ElemType e) {
    StackNodePtr s = (StackNodePtr)malloc(sizeof(StackNode));
    s->data = e;
    s->next = S->top;
    S->top = s;
    S->count++;
    return 0;
}

int Pop(LinkStack *S, ElemType *e) {
    StackNodePtr p;
    if (S->top == NULL && S->count == 0)
        return -1;

    p = S->top;
    *e = p->data;
    S->top = p->next;

    free(p);
    S->count--;
    return 0;
}

// 堆疊的應用 - Fibonacci
int Fbi(int i) {
    if (i < 2)
        return i == 0? 0: 1;
    return Fbi(i - 1) + Fbi(i - 2);
}

int main() {
    int i = 0;
    for (i = 0; i < 40; i++)
        printf("%d ", Fbi(i));
    return 0;
}

堆疊的應用(四則運算)

  • 中序式轉後序式
    • 堆疊法
      • 遇運算元直接輸出，堆疊運算子與左括號
      • 堆疊中運算子優先順序若大於等於讀入的運算子優先順序，則輸出堆疊中之運算子，再將讀入的運算子置入堆疊
      • 遇右括號輸出堆疊中的運算子至左括號
    • 手算
      • 將運算子兩旁的運算元依先後順序全部括號起來，然後將所有的右括號取代為左邊最接近的運算子（從最內層括號開始），最後去掉所有的左括號 a+bd+c/d -> ((a+(bd))+(c/d)) -> abd*+cd/+
  • 中序式轉前序式(需要兩個堆疊)
    • 改成由右至左讀入
    • 不直接輸出，需先存入堆疊，最後一起輸出
  • 後序式求值(轉中序式)
    • 遇到運算元先存入堆疊
    • 遇到運算子則由堆疊中取出兩個運算元進行運算，然後將結果存回堆疊
    • 如果運算式讀取完畢，那麼堆疊頂的值就是答案

佇列(Queue)

  • 只允許在一端插入，另一端刪除的線性串列(先進先出FIFO)

環狀佇列(Circular Queue)

// 線性串列實作環狀佇列
typedef struct SqQueue {
    ElemType data[MAXSIZE];
    int front;
    int rear;
} SqQueue;

int InitQueue(SqQueue *Q) {
    Q->front = 0;
    Q->rear = 0;
    return 0;
}

int QueueLength(SqQueue Q) {
    return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}

int EnQueue(SqQueue *Q, ElemType e) {
    if ((Q->rear + 1) % MAXSIZE == Q->front)
        return -1;
    Q->data[Q->rear] = e;
    Q->rear = (Q->rear + 1) % MAXSIZE;
    return 0;
}

int DeQueue(SqQueue *Q, ElemType *e) {
    if (Q->front == Q->rear)
        return -1;
    *e = Q->data[Q->front];
    Q->front = (Q->front + 1) % MAXSIZE;
    return 0;
}

// 鏈結串列實作佇列
typedef struct QNode {
    ElemType data;
    struct QNode *next;
} QNode, *QNodePtr;

typedef struct LinkQueue {
    QNodePtr front, rear;
} LinkQueue;

int InitQueue(LinkQueue *Q) {
    Q->front = NULL;
    Q->rear = NULL;
    return 0;
}

int EnQueue(LinkQueue *Q, ElemType e) {
    QNodePtr s = (QNodePtr)malloc(sizeof(QNode));
    if (!s)
        return -1;
    s->data = e;
    s->next = NULL;

    if (Q->rear == NULL) {
        Q->rear = s;
        Q->front = Q->rear;
    } else {
        Q->rear->next = s;
        Q->rear = s;
    }
    return 0;
}

int DeQueue(LinkQueue *Q, ElemType *e) {
    QNodePtr p;
    if (Q->front == NULL)
        return -1;
    p = Q->front;
    *e = p->data;
    Q->front = p->next;

    if (Q->front == NULL)
        Q->rear = Q->front;
    free(p);
    return 0;
}

堆疊(Stacks)：只能在頂端進行插入和刪除的線性串列(後進先出LIFO)

// 線性串列實作堆疊
typedef struct {
    ElemType data[MAXSIZE];
    int top;
} SqStack;

int InitStack(SqStack *S) {
    S->top = -1;
    return 0;
}

int Push(SqStack *S, ElemType e) {
    if (S->top == MAXSIZE - 1)
        return -1;
    S->data[++S->top] = e;
    return 0;
}

int Pop(SqStack *S, ElemType *e) {
    if (S->top == -1)
        return -1;
    *e = S->data[S->top--];
    return 0;
}

// 兩堆疊共用空間(對於空間需求有相反的關係)
typedef struct {
    ElemType data[MAXSIZE];
    int top1;
    int top2;
} SqDoubleStack;

int Push(SqDoubleStack *S, ElemType e, int stackNumber) {
    if (S->top1 + 1 == S->top2)
        return -1;
    if (stackNumber == 1)
        S->data[++S->top1] = e;
    else if (stackNumber == 2)
        S->data[--S->top2] = e;
    return 0;
}

int Pop(SqDoubleStack *S, ElemType *e, int stackNumber) {
    if (stackNumber == 1) {
        if (S->top1 == -1)
            return -1;
        *e = S->data[S->top1--];
    } else if (stackNumber == 2) {
        if (S->top2 == MAXSIZE)
            return -1;
        *e = S->data[S->top2++];
    }
    return 0;
}

// 鏈結串列實作堆疊
typedef struct StackNode {
    ElemType data;
    struct StackNode *next;
} StackNode, *StackNodePtr;

typedef struct LinkStack {
    StackNodePtr top;
    int count;
} LinkStack;

int InitStack(LinkStack *S) {
    S->top = NULL;
    S->count = 0;
    return 0;
}

int Push(LinkStack *S, ElemType e) {
    StackNodePtr s = (StackNodePtr)malloc(sizeof(StackNode));
    s->data = e;
    s->next = S->top;
    S->top = s;
    S->count++;
    return 0;
}

int Pop(LinkStack *S, ElemType *e) {
    StackNodePtr p;
    if (S->top == NULL && S->count == 0)
        return -1;

    p = S->top;
    *e = p->data;
    S->top = p->next;

    free(p);
    S->count--;
    return 0;
}

// 堆疊的應用 - Fibonacci
int Fbi(int i) {
    if (i < 2)
        return i == 0? 0: 1;
    return Fbi(i - 1) + Fbi(i - 2);
}

int main() {
    int i = 0;
    for (i = 0; i < 40; i++)
        printf("%d ", Fbi(i));
    return 0;
}

堆疊的應用(四則運算)：

  • 中序式轉後序式：

    • 堆疊法：
      1. 遇運算元直接輸出，堆疊運算子與左括號
      2. 堆疊中運算子優先順序若大於等於讀入的運算子優先順序，則輸出堆疊中之運算子，再將讀入的運算子置入堆疊
      3. 遇右括號輸出堆疊中的運算子至左括號
    • 手算：將運算子兩旁的運算元依先後順序全部括號起來，然後將所有的右括號取代為左邊最接近的運算子（從最內層括號開始），最後去掉所有的左括號 a+bd+c/d -> ((a+(bd))+(c/d)) -> abd*+cd/+

  • 中序式轉前序式(需要兩個堆疊)：

    • 改成由右至左讀入

    • 不可直接輸出，需先存入堆疊，最後一起輸出

  • 後序式求值(轉中序式)：

    1. 遇到運算元先存入堆疊

    2. 遇到運算子則由堆疊中取出兩個運算元進行對應的運算，然後將結果存回堆疊

    3. 如果運算式讀取完畢，那麼堆疊頂的值就是答案

佇列(Queue)：只允許在一端插入，另一端刪除的線性串列(先進先出FIFO)

環狀佇列(Circular Queue)：

// 線性串列實作環狀佇列
typedef struct SqQueue {
    ElemType data[MAXSIZE];
    int front;
    int rear;
} SqQueue;

int InitQueue(SqQueue *Q) {
    Q->front = 0;
    Q->rear = 0;
    return 0;
}

int QueueLength(SqQueue Q) {
    return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
}

int EnQueue(SqQueue *Q, ElemType e) {
    if ((Q->rear + 1) % MAXSIZE == Q->front)
        return -1;
    Q->data[Q->rear] = e;
    Q->rear = (Q->rear + 1) % MAXSIZE;
    return 0;
}

int DeQueue(SqQueue *Q, ElemType *e) {
    if (Q->front == Q->rear)
        return -1;
    *e = Q->data[Q->front];
    Q->front = (Q->front + 1) % MAXSIZE;
    return 0;
}

// 鏈結串列實作佇列
typedef struct QNode {
    ElemType data;
    struct QNode *next;
} QNode, *QNodePtr;

typedef struct LinkQueue {
    QNodePtr front, rear;
} LinkQueue;

int InitQueue(LinkQueue *Q) {
    Q->front = NULL;
    Q->rear = NULL;
    return 0;
}

int EnQueue(LinkQueue *Q, ElemType e) {
    QNodePtr s = (QNodePtr)malloc(sizeof(QNode));
    if (!s)
        return -1;
    s->data = e;
    s->next = NULL;

    if (Q->rear == NULL) {
        Q->rear = s;
        Q->front = Q->rear;
    } else {
        Q->rear->next = s;
        Q->rear = s;
    }
    return 0;
}

int DeQueue(LinkQueue *Q, ElemType *e) {
    QNodePtr p;
    if (Q->front == NULL)
        return -1;
    p = Q->front;
    *e = p->data;
    Q->front = p->next;

    if (Q->front == NULL)
        Q->rear = Q->front;
    free(p);
    return 0;
}

results matching ""

    No results matching ""