您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

C 語言實現鏈棧與括號匹配應用詳解

編輯：關於C++

鏈棧數據結構設計

採用帶頭結點的單鏈表實現棧，頭結點不存數據，next 指向棧頂元素。結構定義：

typedef char DataType;
typedef struct node {
    DataType data;
    struct node *next;
} LStackNode, *LinkStack;

核心操作實現

操作	關鍵邏輯	時間複雜度
初始化	分配頭結點，`next = NULL`	O(1)
判空	檢查 `top->next == NULL`	O(1)
進棧	新結點插入頭結點之後，`p->next = top->next; top->next = p;`	O(1)
出棧	刪除首元結點，`top->next = p->next; free(p);`	O(1)
取棧頂	返回首元結點數據，不刪除	O(1)
求長度	遍歷鏈表計數	O(n)
銷毀	逐個釋放結點	O(n)

應用示例：括號匹配驗證

利用棧的後進先出特性，遇左括號進棧，遇右括號檢查棧頂是否為對應左括號：

int Match(DataType e, DataType ch) {
    return (e=='('&&ch==')') || (e=='['&&ch==']') || (e=='{'&&ch=='}');
}

void main_Match() {
    LinkStack S; InitStack(&S);
    char ch[100]; gets(ch);
    char *p = ch;
    while (*p) {
        switch(*p) {
            case '(': case '[': case '{': PushStack(S, *p++); break;
            case ')': case ']': case '}':
                if (StackEmpty(S)) { printf("缺少左括號.\n"); return; }
                GetTop(S, &e);
                if (Match(e, *p)) PopStack(S, &e);
                else { printf("左右括號不配對.\n"); return; }
                p++; break;
            default: p++;
        }
    }
    if (StackEmpty(S)) printf("括號匹配.\n");
    else printf("缺少右括號.\n");
}