數(shù)據(jù)結(jié)構(gòu)與算法-棧

1. 順序存儲(chǔ)

優(yōu)點(diǎn)：

  • 實(shí)現(xiàn)簡(jiǎn)單

缺點(diǎn)：

  • 長(zhǎng)度有限

1.1 結(jié)構(gòu)定義

#define MAXSIZE 20

typedef int Status;
typedef int SElemType;

typedef struct
{
    SElemType data[MAXSIZE];
    int top;
} SqStack;

1.2 函數(shù)實(shí)現(xiàn)

// 1.構(gòu)建一個(gè)空棧S
Status InitStack(SqStack *S) {
    if (!S) return ERROR;
    S->top = -1;
    return OK;
}

// 2.將棧置空
Status ClearStack(SqStack *S) {
    if (!S) return ERROR;
    S->top = -1;
    return OK;
}

// 3.判斷順序棧是否為空;
Status StackEmpty(SqStack S) {
    if (S.top == -1)
        return TRUE;
    else
        return FALSE;
}

// 4.返回棧的長(zhǎng)度
int StackLength(SqStack S) {
    return S.top + 1;
}

// 5.獲取棧頂元素
Status GetTop(SqStack S, SElemType *e) {
    if (S.top == -1)
        return ERROR;
    else
        *e = S.data[S.top];
    return OK;
}

// 6.壓棧
Status Push(SqStack *S, SElemType e) {
    if (!S || S->top == MAXSIZE -1) return ERROR;
    S->data[++S->top] = e;
    return OK;
}

// 7.出棧
Status Pop(SqStack *S,SElemType *e) {
    if (!S || S->top == -1) return ERROR;
    *e = S->data[S->top--];
    return OK;
}

// 8.從棧底到棧頂依次對(duì)棧中的每個(gè)元素打印
Status StackTraverse(SqStack S) {
    int i = S.top;
    while (i >= 0) {
        printf("%d ",S.data[i--]);
    }
    printf("\n");
    return OK;
}
// 輸出
順序棧的表示與實(shí)現(xiàn)!
順序棧中元素為: 
9 8 7 6 5 4 3 2 1 
彈出棧頂元素為: 9
8 7 6 5 4 3 2 1 
是否為空棧: 0
棧頂元素: 8 
棧長(zhǎng)度: 8
是否已經(jīng)清空棧 1, 棧長(zhǎng)度為: 0

2. 鏈?zhǔn)酱鎯?chǔ)

優(yōu)點(diǎn)：

  • 長(zhǎng)度無限(只要內(nèi)存夠)

缺點(diǎn)：

  • 實(shí)現(xiàn)復(fù)雜
  • 節(jié)點(diǎn)的內(nèi)存管理

2.1 結(jié)構(gòu)定義

typedef int Status;
typedef int SElemType;

/* 鏈棧結(jié)構(gòu) */
typedef struct StackNode
{
    SElemType data;
    struct StackNode *next;
} StackNode, *StackNodePtr;

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

2.2 函數(shù)實(shí)現(xiàn)

// 1.構(gòu)造一個(gè)空棧S
Status InitStack(LinkStack *S) {
    if (!S) return ERROR;
    S->top = NULL;
    S->count = 0;
    return OK;
}

// 2.棧S置為空棧
Status ClearStack(LinkStack *S){
    if (!S) return ERROR;
    StackNodePtr p, q;
    p = S->top;
    while (p) {
        q = p;
        p = p->next;
        free(q);
    }
    S->top = NULL;
    S->count = 0;
    return OK;
}

// 3.棧S是否為空棧
Status StackEmpty(LinkStack S) {
    if (!S.top)
        return TRUE;
    else
        return FALSE;
    /*
     if (S.count == 0)
         return TRUE;
     else
         return FALSE;
     */
}

// 4.棧S的長(zhǎng)度
int StackLength(LinkStack S) {
    return S.count;
}

// 5.返回棧頂元素
Status GetTop(LinkStack S, SElemType *e) {
    if (!S.top)
        return ERROR;
    else
        *e = S.top->data;
    return OK;
}

// 6.壓棧
Status Push(LinkStack *S, SElemType e) {
    if (!S) return ERROR;
    StackNodePtr node = (StackNodePtr)malloc(sizeof(StackNode));
    node->data = e;
    node->next = S->top; // 頭插法
    S->top = node; // 更換頭結(jié)點(diǎn)
    S->count++;
    return OK;
}

// 7.出棧
Status Pop(LinkStack *S, SElemType *e) {
    if (!S || !S->top) return ERROR;
    *e = S->top->data;
    StackNodePtr node = S->top;
    S->top = S->top->next; // 更換頭結(jié)點(diǎn)
    free(node);
    S->count--;
    return OK;
}

// 8.遍歷棧
Status StackTraverse(LinkStack S) {
    StackNodePtr node;
    node = S.top;
    while (node) {
        printf("%d ",node->data);
        node = node->next;
    }
    printf("\n");
    return OK;
}

int main(int argc, const char * argv[]) {
    printf("鏈棧定義與實(shí)現(xiàn)\n");
    int j;
    LinkStack S;
    int e;
    if (InitStack(&S) == OK)
        for (j=1; j <= 10; j++) Push(&S,j);
    printf("棧中元素依次為:\n");
    StackTraverse(S);
    Pop(&S, &e);
    printf("彈出的棧頂元素: %d\n",e);
    StackTraverse(S);
    printf("?？辗? %d (1:空 0:否)\n",StackEmpty(S));
    GetTop(S,&e);
    printf("棧頂元素: %d 棧的長(zhǎng)度為%d\n",e,StackLength(S));
    ClearStack(&S);
    printf("清空棧后，棧空否: %d (1:空 0:否)\n",StackEmpty(S));
    return 0;
}
// 輸出
鏈棧定義與實(shí)現(xiàn)
棧中元素依次為:
10 9 8 7 6 5 4 3 2 1 
彈出的棧頂元素: 10
9 8 7 6 5 4 3 2 1 
?？辗? 0 (1:空 0:否)
棧頂元素: 9 棧的長(zhǎng)度為9
清空棧后，棧空否: 1 (1:空 0:否)

3. 遞歸

遞歸方法就是直接或者間接的調(diào)用自己，它可以將一些發(fā)雜問題簡(jiǎn)化。

遞歸在下列方法中經(jīng)常會(huì)用到：

  • 定義是遞歸的。

    如斐波拉契數(shù)列、階乘等。

  • 數(shù)據(jù)結(jié)構(gòu)是遞歸的。

    數(shù)據(jù)結(jié)構(gòu)本身具有遞歸性，如鏈表、樹等。

  • 問題的解法是遞歸的。

    有一類問題，雖然問題本身沒有明顯的遞歸結(jié)構(gòu)，但采用遞歸求解比迭代求解更簡(jiǎn)單。如漢諾塔問題、八皇后問題、迷宮問題。

在求解4!時(shí)，我們會(huì)先求解3!，然后再進(jìn)一步分解進(jìn)行求解，這種求解叫做分治法。

使用分治法需要滿足3個(gè)條件：

  • 能將一個(gè)問題轉(zhuǎn)換成一個(gè)小問題，新問題和原問題的解法相同或類同。

    不同的只是被處理的對(duì)象，并且這些處理更小且變化是有規(guī)律的。

  • 可以通過上述轉(zhuǎn)換而使得問題簡(jiǎn)化。

  • 必須有一個(gè)明確的遞歸出口，或成為遞歸邊界。

4. 漢諾塔問題

在經(jīng)典漢諾塔問題中，有 3 根柱子及 N 個(gè)不同大小的穿孔圓盤，盤子可以滑入任意一根柱子。一開始，所有盤子自上而下按升序依次套在第一根柱子上(即每一個(gè)盤子只能放在更大的盤子上面)。

移動(dòng)圓盤時(shí)受到以下限制:

  • 每次只能移動(dòng)一個(gè)盤子；
  • 盤子只能從柱子頂端滑出移到下一根柱子；
  • 盤子只能疊在比它大的盤子上。

4.1 解決思路

我們使用遞歸來解決：

  • n=1時(shí)，直接把盤子從A移動(dòng)到C就行了。(遞歸邊界)
  • n>1時(shí)：
    • 先把n-1個(gè)盤子從A移動(dòng)到B；(子問題，遞歸)
    • 將最大的盤子從A移動(dòng)到C；
    • 再將B上n-1個(gè)盤子移動(dòng)到C。(子問題，遞歸)

4.2 用棧解決

static void move(LinkStack *A, LinkStack *B, LinkStack *C, int n) {
    if (n == 1) {
        int elem;
        Pop(A, &elem);
        Push(C, elem);
    } else {
          // 把棧A中n-1個(gè)盤子放到棧B
        move(A, C, B, n - 1);
        // A棧出棧放入C棧
        int elem;
        Pop(A, &elem);
        Push(C, elem);
          // 把棧B中n-1個(gè)盤子放到棧C
        move(B, A, C, n - 1);
    }
}

void hanoi(LinkStack *A, LinkStack *B, LinkStack *C) {
    move(A, B, C, StackLength(*A));
}

int main(int argc, const char * argv[]) {
    int n = 5;
    LinkStack A, B, C;
    InitStack(&A);
    InitStack(&B);
    InitStack(&C);
    for (int i = n; i > 0; i--) {
        Push(&A, i);
    }
    printf("原始棧A：");
    StackTraverse(A);
    printf("原始棧C：");
    StackTraverse(C);
    
    hanoi(&A, &B, &C);
    
    printf("移動(dòng)后棧A：");
    StackTraverse(A);
    printf("移動(dòng)后棧C：");
    StackTraverse(C);
    
    return 0;
}
// 輸出
原始棧A：1 2 3 4 5 
原始棧C：
移動(dòng)后棧A：
移動(dòng)后棧C：1 2 3 4 5

4.3 移動(dòng)過程

void hanoi2(char *A, char *B, char *C, int n) {
    if (n == 1) {
        printf("move %s to %s\n", A, C);
    } else {
        hanoi2(A, C, B, n - 1);
        printf("move %s to %s\n", A, C);
        hanoi2(B, A, C, n - 1);
    }
}
int main(int argc, const char * argv[]) {
    hanoi2("a", "b", "c", 3);
    return 0;
}
// 輸出
move a to c
move a to b
move c to b
move a to c
move b to a
move b to c
move a to c
漢諾塔問題
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容