「栈-链式结构」C语言实现

文章目录
  1. 链式栈示意图
  2. 数据结构定义
  3. 源码

链式栈示意图

数据结构定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*--------------------------- 链式栈结构定义 ---------------------------*/

typedef int ElemType;

// 定义节点的数据类型
typedef struct node {
    ElemType data;
    struct node * pNext;
} Node, *pNode;

// 定义栈的数据类型
typedef struct linkstack {
    pNode pTop;     // 栈顶指针，指向栈顶元素
    pNode pBottom;  // 栈底指针，保持不动，指向头节点(无效数据)
} LinkStack, *pLinkStack;

/*--------------------------- 链式栈结构定义 ---------------------------*/

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
/*
 * 功能: 栈-链式结构
 * 作者: Guyue
 * 微信公众号: https://img.arctee.cn/one/pokeai-wechat.png
 * 网站：https://pokeai.cn
 * Github: https://github.com/Pokoai/DaHua-Data-Structure/tree/main/A1-LatestVersion
 * Date: 2022-09-14
 */

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


/*--------------------------- 链式栈结构定义 ---------------------------*/

typedef int ElemType;

// 定义节点的数据类型
typedef struct node {
    ElemType data;
    struct node * pNext;
} Node, *pNode;

// 定义栈的数据类型
typedef struct linkstack {
    pNode pTop;     // 栈顶指针，指向栈顶元素
    pNode pBottom;  // 栈底指针，保持不动，指向头节点(无效数据)
} LinkStack, *pLinkStack;

// 链栈示意图：https://img.arctee.cn/one/202209162331521.png

/*--------------------------- 链式栈结构定义 ---------------------------*/


// 函数前置声明
void InitStack(pLinkStack S);
bool PushStack(pLinkStack S, ElemType elem);
void TraverseStack(pLinkStack S);
bool IsEmpty(pLinkStack S);
bool PopStack(pLinkStack S, ElemType * pElem);
void ClearStack(pLinkStack S);
void DestoryStack(pLinkStack S);


// 主函数
int main(void)
{
    LinkStack S;

    InitStack(&S);
    PushStack(&S, 1);
    PushStack(&S, 2);
    PushStack(&S, 3);
    PushStack(&S, 4);
    PushStack(&S, 5);
    TraverseStack(&S);

    ElemType e;
    PopStack(&S, &e);
    PopStack(&S, &e);
    PopStack(&S, &e);
    TraverseStack(&S);

    ClearStack(&S);
    DestoryStack(&S);

    return 0;

}

// 初始化
void InitStack(pLinkStack S)
{
    // 首先创建一个头节点
    pNode pHead = (pNode)malloc(sizeof(Node));
    if ( NULL == pHead ) {
        printf("内存分配失败！\n");
        exit(-1);
    }

    pHead->pNext = NULL;

    // 将栈顶、栈底指针均指向头节点
    S->pBottom = pHead;
    S->pTop = pHead;
}

// 压栈
bool PushStack(pLinkStack S, ElemType elem)
{
    // 创建新节点
    pNode pNew = (pNode)malloc(sizeof(Node));
    if ( NULL == pNew ) {
        printf("压栈失败！\n");
        return false;
    }

    pNew->data = elem;
    pNew->pNext = S->pTop;
    S->pTop = pNew;

    return true;
}

// 遍历栈
void TraverseStack(pLinkStack S)
{
    pNode p = S->pTop;

    while ( p != S->pBottom ) {
        printf("%d ", p->data);
        p = p->pNext;
    }
    printf("\n");
}

// 是否为空
bool IsEmpty(pLinkStack S)
{
    return (S->pBottom == S->pTop );
}

// 出栈
bool PopStack(pLinkStack S, ElemType * pElem)
{
    if ( IsEmpty(S) ) {
        printf("栈空，出栈失败！\n");
        return false;
    }

    pNode p = S->pTop;

    *pElem = p->data;
    S->pTop = p->pNext;

    free(p);  // 勿忘释放栈顶
    p = NULL;

    return true;
}

// 清空栈
void ClearStack(pLinkStack S)
{
    pNode p = S->pTop;
    pNode q = p->pNext;

    while ( p != S->pBottom ) {
        free(p);
        p = q;
        q = q->pNext;
    }

    S->pTop = S->pBottom;
}

// 销毁栈（不保留头节点）
void DestoryStack(pLinkStack S)
{
    ClearStack(S);
    
    free(S->pBottom);  // 释放掉头节点
    S->pBottom = S->pTop = NULL;
}