【C語言資料結構】棧 - 順序棧

文章目錄

一、棧的表示和實作

1.1 棧的概念
1.2 棧的初始化
1.3 棧的銷毀
1.4 棧的擴容
1.5 元素入棧
1.6 元素出棧
1.7 傳回棧頂元素
1.8 傳回棧的元素個數
1.9 棧的判空與清空
1.10 棧的列印輸出

二、棧的應用

2.1 數制轉換
2.2 括号比對檢驗
2.3 行編輯程式
2.4 表達式求值
2.5 漢諾塔

棧

一、棧的表示和實作

1.1 棧的概念

棧（stack）又名堆棧，它是一種運算受限的線性表。限定僅在表尾進行插入和删除操作的線性表。這一端（表尾）被稱為棧頂，相對地，把另一端稱為棧底。

向一個棧插入新元素又稱作進棧、入棧或壓棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個棧删除元素又稱作出棧或退棧，它是把棧頂元素删除掉，使其相鄰的元素成為新的棧頂元素。棧又稱為後進先出表（LIFO）

主要接口：

#pragma one

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

// 自定義資料類型
typedef int StackDataType;
// 定義棧結構體
typedef struct Stack {
  StackDataType* a; // 指向動态開辟的數組
  int top; // 棧頂
  int capacity;  // 棧的容量
} ST;

// 初始化棧
void StackInit(ST* ps);

// 銷毀棧
void StackDestory(ST* ps);

// 入棧
void StackPush(ST* ps,StackDataType x);

// 出棧
void StackPop(ST* ps);

// 傳回棧頂元素
StackDataType StackTop(ST* ps);

// 棧的大小
int StackSize(ST* ps);

// 判斷空棧
bool StackEmpty(ST* ps);

// 棧的列印
void StackPrint(ST* ps);

傳回頂部

1.2 棧的初始化

建立一個新的空元素棧，棧頂指向下标0，此後指向棧頂資料的下一個；初始容量賦為0。

// 初始化棧
void StackInit(ST* ps) {
  // 斷言
  assert(ps);
  // 初始化棧
  ps->a = NULL; 
  ps->top = 0; // 指向棧頂資料的下一個
  ps->capacity = 0;
}

傳回頂部

1.3 棧的銷毀

将棧的記憶體位址釋放并置空，将棧頂歸零，棧的容量大小置零。

// 銷毀棧
void StackDestory(ST* ps) {
  // 斷言
  assert(ps);
  // 釋放
  free(ps->a);
  // 置空
  ps->a = NULL;
  ps->top = ps->capacity = 0;
}

傳回頂部

1.4 棧的擴容

如果棧頂指向與棧的空間大小相等（同為

，初始配置設定4個大小空間；同不為

，棧滿，擴容）

// 擴容
if (ps->top == ps->capacity) {
    // 定義新的空間大小
    int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    // 重新開辟記憶體
    StackDataType* tmp = realloc(ps->a, sizeof(StackDataType) * newCapacity);
    if (tmp == NULL) {
        printf("開辟空間失敗！");
        exit(-1);
    }
    // 開辟成功
    ps->a = tmp;
    ps->capacity = newCapacity;
}

傳回頂部

1.5 元素入棧

入棧，首先判斷棧滿（空棧），進行擴容（初始配置設定空間）操作。接着，将元素從

top

位置進行插入，并将

top++

。

// 入棧
void StackPush(ST* ps, StackDataType x) {
  // 斷言
  assert(ps);
  // 擴容
  if (ps->top == ps->capacity) {
    // 定義新的空間大小
    int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    // 重新開辟記憶體
    StackDataType* tmp = realloc(ps->a, sizeof(StackDataType) * newCapacity);
    if (tmp == NULL) {
      printf("開辟空間失敗！");
      exit(-1);
    }
    // 開辟成功
    ps->a = tmp;
    ps->capacity = newCapacity;
  }
  // 棧頂添加新的元素
  ps->a[ps->top] = x;
  ps->top++;
}

傳回頂部

1.6 元素出棧

出棧，需要進行判空操作，否則一直出棧會發生下标越界（C語言中不報錯，通過斷言終止程式）。

top--

實作了棧的上界阻斷，以達到元素出棧的目的。

// 出棧
void StackPop(ST* ps) {
  // 斷言
  assert(ps);
  // 不為空
  assert(!StackEmpty(ps));
  // 棧頂下移一位
  ps->top--;
}

傳回頂部

1.7 傳回棧頂元素

這裡我們考慮

top = 0

，是以

top

每次添加完元素後，指向的是下一個棧元素的位置，是以輸出棧頂元素的時候需要将其減1。

// 傳回棧頂元素
StackDataType StackTop(ST* ps) {
  // 斷言
  assert(ps);
  // 不為空
  assert(!StackEmpty(ps));
  return ps->a[ps->top - 1];
}

傳回頂部

1.8 傳回棧的元素個數

同理，

top

從

開始，元素的個數即為

top

的值大小。

// 棧的大小
int StackSize(ST* ps) {
  // 斷言
  assert(ps);
  return ps->top;
}

傳回頂部

1.9 棧的判空與清空

同理，棧元素的個數為

，即為空棧。

// 判斷空棧
bool StackEmpty(ST* ps) {
  assert(ps);
  return ps->top == 0;
}

// 清空棧
void StackClear(ST* ps) {
  assert(ps);
  // if (ps->top == 0) printf("原本就是空棧！");
  while (ps->top!=0) {
    ps->top--;
  }
  if (ps->top == 0) printf("\n棧已被清空\n");
}

傳回頂部

1.10 棧的列印輸出

因為棧是先進後出表，是以必須将元素從棧頂依次取出，才能擷取下面的元素，是以需要結合出棧、擷取棧頂元素函數實作棧的列印輸出。

// 棧的列印
void StackPrint(ST* ps) {
    assert(ps);
    // 當棧不為空
    while (!StackEmpty(ps)) {
        // 輸出棧頂元素
        printf("%d",StackTop(ps));
        // 棧頂元素出棧
        StackPop(ps);
    }
    printf("\n");
    // 銷毀棧
    StackDestory(ps);
}

void TestStack() {
    // 建立棧
    ST stack;
    // 初始化查娜
    StackInit(&stack);
    // 元素入棧
    StackPush(&stack, 1);
    StackPush(&stack, 2);
    StackPush(&stack, 3);
    StackPush(&stack, 4);
    StackPush(&stack, 5);
    // 列印輸出棧
    StackPrint(&stack);
}

int main() {
    // 測試
    TestStack();
    system("pause");
    return 0;
}

傳回頂部

二、棧的應用

2.1 數制轉換

十進制數和其他

為整除運算，

例如：

N	N div 8	N mod 8
1348	168	4
168	21
21	2	5
2	2

分析：對于任意的一個非負十進制整數，列印輸出與其相等的8進制數。按照上述的計算過程，從低位到高位依次産生，最後逆序輸出。其過程與棧的存取十分相似，滿足先進後出的條件。

// 進制問題
void Conversion(ST* ps, int N) {
  // 初始化棧
  StackInit(ps);
  // 求餘入棧
  while (N > 0) {
    StackPush(ps, N % 8);
    N = N / 8;
  }
  // 輸出出棧
  while (!StackEmpty(ps)) {
    printf("%d", StackTop(ps));
    StackPop(ps);
  }
  printf("\n");
}

傳回頂部

2.2 括号比對檢驗

括号比對的思想：

依次從左至右檢查字元串，若為左括号，則入棧；
若遇右括号則擷取棧頂元素，檢查棧頂元素與目前元素是否比對，

若比對，則棧頂元素出棧。
反之，則不比對，程式結束。

以此類推，直至檢查完所有字元串。如果此時棧空則比對，反之則不比對。

// 自定義資料類型
typedef char StackDataType;
// 定義棧結構體
typedef struct Stack {
    StackDataType* a; // 指向動态開辟的數組
    int top; // 棧頂
    int capacity;  // 棧的容量
} ST;

// 括号比對問題
void Match(ST* ps, char str[]) {
    // 初始化棧
    StackInit(ps);
    // 初始化變量存儲、計數
    char ch;
    int i;
    for (i = 0; str[i] != '\0'; i++) {
        switch (str[i]) {
        case '{':
        case '[':
        case '(':
            StackPush(ps, str[i]);
            break;
        case '}':
        case ']':
        case ')':
            // 如果棧為空
            if (StackEmpty(ps)) {
                return 0;
            }
            else {
                // 擷取棧頂元素
                char top = StackTop(ps);
                // 比較棧頂元素與目前的括号是否比對 
                if (top + 1 == str[i] || top + 2 == str[i]) {
                    StackPop(ps);
                } else {
                    return 0;
                }
            }
        }
    }
    // 如果最後棧為空，則整體是比對的
    if (StackEmpty(ps)) {
        printf("該字串符合條件！");
    } else {
        printf("該字串不符合條件！");
    }
    StackDestory(ps);
}

解析：

if (top + 1 == str[i] || top + 2 == str[i]) {...}

，通過如下的Ascall碼字元比對表可以看到，

、

之間相差為2，

（

）

之間相差為1。

傳回頂部

2.3 行編輯程式

一個簡單的行編輯程式的功能是：接受使用者從終端輸入的程式或資料，并存入使用者的資料區。

由于使用者在終端上進行輸入時，不能保證不出差錯，是以，若在編輯程式中，“每接受一個字元即存入使用者資料區”的做法顯然不是最恰當的。

較好的做法是，設立一個輸入緩沖區，用以接受使用者輸入的一行字元，然後逐行存入使用者資料區。允許使用者輸入出差錯，并在發現有誤時可以及時更正。

例如，當使用者發現剛剛鍵入的一個字元是錯的時，可補進一個倒退符

“#”

，以表示前一個字元無效；如果發現目前鍵入的行内差錯較多或難以補救，則可以鍵入一個退行符

“@”

，以表示目前行中的字元均無效。

// 棧的列印
void StackPrint(ST* ps) {
  assert(ps);
  // 當棧不為空
  while (!StackEmpty(ps)) {
    // 輸出棧頂元素
    printf("%c", StackTop(ps));
    // 棧頂元素出棧
    StackPop(ps);
  }
  printf("\n");
}

// 行編輯程式
void LineEdit(ST* ps) {
  // 初始化棧
  StackInit(ps);
  char ch = getchar();
  // EOF為全文結束符
  while (ch != EOF) {
    while (ch != EOF && ch != '\n') {
      switch (ch) {
        case '#':
          StackPop(ps);  // 棧頂元素出棧
          break;
        case '@':
          StackClear(ps); // 清空棧
          break;
        default:
          StackPush(ps, ch); // 元素入棧
          break;
      }
      ch = getchar();
    }
    StackPrint(ps);
    // 資料傳輸，清空棧
    StackClear(ps);
    if (ch != EOF) { ch = getchar(); }
  }
  // 銷毀棧
  StackDestory(ps);
}

傳回頂部

2.4 表達式求值

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define N 1000+10           // 字元串長度
#define STACK_INIT_SIZE 100 // 棧初始化大小
#define STACKINCREMENT 10   // 擴容大小
#define OK 1                // 狀态碼
#define OVERFLOW 0
#define ERROR 0

char str[N];            // 輸入的字元串表達式
typedef int Status;    // 自定義狀态碼類型
// 定義算符優先關系字元二維數組
unsigned char prior[7][7] = {
    {'>','>','<','<','<','>','>'},
    {'>','>','<','<','<','>','>'},
    {'>','>','>','>','<','>','>'},
    {'>','>','>','>','<','>','>'},
    {'<','<','<','<','<','=',' '},
    {'<','<','<','<','<',' ','>'},
    {'<','<','<','<','<',' ','='} 
};
// 定義算符數組
char OPSET[7] = { '+','-','*','/','(',')','#' };

typedef  int SElemType; // 自定義棧資料類型
typedef struct {        // 定義棧
    SElemType* base;    // 棧尾
    SElemType* top;     // 棧頂
    int stacksize;      // 棧的大小
}SqStack;

// 初始化棧
Status InitStack(SqStack* s) {
    s->base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType)); // 開辟空間
    if (!s->base) exit(OVERFLOW);
    s->top = s->base;
    s->stacksize = STACK_INIT_SIZE;
    return OK;
}
 
// 入棧 
Status Push(SqStack* s, SElemType c){
    // 擴容
    if ((s->top - s->base) >= s->stacksize){
        s->base = (SElemType*)realloc(s->base, (s->stacksize + STACKINCREMENT) * sizeof(SElemType));
        // 擴容失敗
        if (!s->base) exit(OVERFLOW);
        // 擴容成功
        s->stacksize += STACKINCREMENT;
    }
    // 指派
    *(s->top)++ = c;
    return OK;
}

// 取棧頂元素 
Status GetTop(SqStack* s){
    SElemType e;
    if (s->base == s->top)
        return ERROR;
    e = *(s->top - 1);  // 擷取棧頂元素
    return e;
}

// 出棧 脫括号函數 
Status Pop(SqStack* s){
    int e;
    if (s->base == s->top) return ERROR;
    e = *--(s->top);
    return e;
}

// 判斷是否為運算符 3*(7-2) { '+','-','*','/','(',')','#' }
Status In(char c, char str[]){
    
    int i = 0;
    // 周遊字元串，
    while (c != str[i]){
        i++;
    }
    // 如果是運算符,最終i最大為6
    if (i < 7) return OK; // 1
    return ERROR; // 0
}
// 字元串連接配接函數，把字元串str2連接配接到str1後 
void  Strcat(char* str1, char* str2){
    int i = 0, j = 0;
    while (str1[i] != '\0'){
        i++;
    }
    // str2追加到str1後面
    while (str2[j] != '\0'){
        str1[i++] = str2[j++];
    }
    // 添加結束标志
    str1[i] = '\0';
}
// 把字元串轉為數字 
Status Atoi(char* c){
    int data = 0, d = 0;
    int i = 0;
    while (c[i] != '\0'){
        data = data * 10 + c[i] - '0';
        i++;
    }
    return data;
}
// 判斷優先級函數 
Status precede(int a, char b){
    int i = 0, j = 0;
    while (OPSET[i] != a){
        i++;
    }
    while (OPSET[j] != b){
        j++;
    }
    return prior[i][j];
}
// 運算函數 
Status Operate(int a, int b, int c){
    switch (b){
        case '+':
            return a + c;
        case '-':
            return a - c;
        case '*':
            return a * c;
        case '/':
            return a / c;
    }
}
// 表達式求值 - 算術表達式求值的算符優先算法
int EvaluateExpression(char* MyExpression) {

    // 設 OPTR 和 OPND 分别為 運算符棧 和 運算數棧
    SqStack OPTR;//運算符棧，字元元素 
    SqStack OPND;//運算數棧，實數元素 
    // 初始化棧
    InitStack(&OPTR);
    Push(&OPTR, '#');
    InitStack(&OPND);

    char* c, Dr[2];
    c = MyExpression;  // 輸入的字元表達式：3*(7-2)
    char TempData[20];
    TempData[0] = '\0';
    int data, a, b, theta;
    
    while (*c != '#' || GetTop(&OPTR) != '#'){
        // 不是運算符則進棧 
        if (!In(*c, OPSET)){
            // 擷取字串的一個字元
            Dr[0] = *c; // 3
            Dr[1] = '\0';
            Strcat(TempData, Dr);
            c++;
            // 是運算符時 
            if (In(*c, OPSET)){
                data = Atoi(TempData);
                Push(&OPND, data);
                TempData[0] = '\0';
            }
        } else {
            // 将運算符棧頂元素與輸入表達式中的運算符比較優先級
            switch (precede(GetTop(&OPTR), *c)){
            case '<':
                Push(&OPTR, *c);
                c++;
                break;
            case '=':
                Pop(&OPTR);
                c++;
                break;
            case '>':
                a = Pop(&OPND);
                b = Pop(&OPND);
                theta = Pop(&OPTR);
                Push(&OPND, Operate(b, theta, a));
                break;
            }
        }
    }
    return GetTop(&OPND);
}
int main(){
    while (scanf("%s", str) != EOF){
        printf("%d\n", EvaluateExpression(str));
    }
    return 0;
}

傳回頂部

2.5 漢諾塔

漢諾塔（Tower of Hanoi），又稱河内塔。源自印度古老傳說的一個遊戲，大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞着64片黃金圓盤。大梵天指令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次隻能移動一個圓盤。

若有1個圓盤時，需要移動1次；
若有2個圓盤時，需要移動3次；
若有3個圓盤時，需要移動7次……

不難看出，漢諾塔步數的數學規律為（n為柱子上的圓盤個數）。

是以若有64個圓盤那将會移動2^64-1次（即：18,446,744,073,709,551,615‬次），若每次移動需要1s時間，則需要将近5849億年的時間才能夠做到。

假設：現有三個柱子A、B、C，其中有n個圓盤在A柱上，最終要實作把這n個圓盤從A柱借助B柱移動到C柱上。實作實作思路：先将n-1個圓盤從A柱移動到B柱上，然後将A柱上最後一個圓盤n移動到C柱上，最後再把B柱上的n-2個圓盤移動到A柱上，再将B柱上的最後一個圓盤n-1移動到C柱上，如此往複。如下圖所示：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

void move(char A, char C, int n) {
  printf("把第%d個圓盤從%c--->%c\n", n, A, C);
}

void HanoiTower(char from, char tmp, char to, int n) {
  if (n == 1){
    move(from, to, n);
  } else {
    // 将n-1個圓盤從A柱借助于C柱移動到B柱上
    HanoiTower(from, to, tmp, n - 1);
    // 将A柱子最後一個圓盤移動到C柱上
    move(from, to, n);
    // 将n-1個圓盤從B柱借助于A柱移動到C柱上
    HanoiTower(tmp, from, to, n - 1);
  }
}

int main() {
  int n = 0;
  printf("輸入A柱子上的圓盤個數：");
  scanf("%d", &n);
  // 将n個圓盤從A柱借助于B柱移動到C柱上
  HanoiTower('A', 'B', 'C', n);
  return 0;
}

【C語言資料結構】棧 - 順序棧

文章目錄

棧

一、棧的表示和實作

1.1 棧的概念

1.2 棧的初始化

1.3 棧的銷毀

1.4 棧的擴容

1.5 元素入棧

1.6 元素出棧

1.7 傳回棧頂元素

1.8 傳回棧的元素個數

1.9 棧的判空與清空

1.10 棧的列印輸出

二、棧的應用

2.1 數制轉換

2.2 括号比對檢驗

2.3 行編輯程式

2.4 表達式求值

2.5 漢諾塔

繼續閱讀

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

CRC32和CRC8校驗代碼，C語言版

241 Different Ways to Add Parentheses（C代碼版）

[轉]ISUP信令的IAM消息詳細内容

C語言：初學者必定看懂的注釋！！！猴子吃桃問題。猴子第一天摘下若幹個桃子，每天都吃了前一天剩下的一半零一個，到第10天早上想再吃的時候，就剩下一個桃子. 求第一天共摘多少個桃子。

[轉]九大排序算法——C語言實作及詳解

筆試面試題目：滑動視窗(二)

while 循環、do- while 循環和 for 循環之間的那點事C語言自學之三種循環比較

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

結構體：typedef與struct的差別

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器

hdu7108哈希

【C語言 資料結構】棧 - 順序棧

文章目錄

棧

一、棧的表示和實作

1.1 棧的概念

1.2 棧的初始化

1.3 棧的銷毀

1.4 棧的擴容

1.5 元素入棧

1.6 元素出棧

1.7 傳回棧頂元素

1.8 傳回棧的元素個數

1.9 棧的判空與清空

1.10 棧的列印輸出

二、棧的應用

2.1 數制轉換

2.2 括号比對檢驗

2.3 行編輯程式

2.4 表達式求值

2.5 漢諾塔

繼續閱讀

【C語言資料結構】棧 - 順序棧