C语言实现链栈的步骤

时间:2022-09-19 12:58:06

链栈图解

C语言实现链栈的步骤

链栈的常规操作

?
1
2
3
4
5
6
7
8
9
10
/********************* 链栈的常规操作 ****************************/
 
LinkStack    InitLinkStack();           // 初始化链栈
int          StackEmpty();              // 判断链栈空
int          StackLength();             // 求链栈长(链栈元素个数)
int          Push();                    // 入栈 压栈
ElemType     Pop();                     // 出栈 弹栈
void         DestroyStack();            // 销毁链栈
 
/***************************************************************/

定义链栈结构体

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include "stdio.h"
#include "malloc.h"
 
 
#define TRUE  1
#define FALSE 0
 
typedef int ElemType;       // 链栈存储元素的数据类型
 
 
/*
 *  定义链栈结构体
*/
typedef struct Node{
    ElemType data;          // 栈结点数据域
    struct Node *next;      // 栈结点指针域
}*LinkStack, Node;

初始化链栈

?
1
2
3
4
5
6
// 初始化链栈(带头结点的链栈)
LinkStack InitLinkStack(){
    LinkStack s = (LinkStack)malloc(sizeof(struct Node));
    s -> next = NULL;
    return s;
}

链栈判空

?
1
2
3
4
5
6
7
8
9
10
/*
 *  判断链栈是否空
 *  s 链栈
*/
int StackEmpty(LinkStack s){
    if(s == NULL){
        return FALSE;
    }
    return s -> next == NULL;
}

因为是链式存储结构,无需链栈判满。

计算链栈的长度

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
 *  求链栈长度(栈中元素个数)
 *  s 链栈
*/
int StackLength(LinkStack s){
    LinkStack p;
    int len = 0;
    if(StackEmpty(s)){
        return FALSE;
    }
    p = s -> next;   // 带头结点的链栈要先移动一下
    while(p != NULL){
        len ++;
        p = p -> next;
    }
    return len;
}

链栈入栈(Push)

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
 *  入栈 压栈
 *  s 链栈
 *  data 入栈数据
*/
int Push(LinkStack s, ElemType data){
    // 分配入栈结点
    Node *new_node = (Node *)malloc(sizeof(struct Node));
    if (new_node == NULL) return FALSE;     // 结点分配失败
    
    // 跟单链表一样使用头插法
    new_node -> data = data;
    new_node -> next = s -> next;
    s -> next = new_node;
    return TRUE;
}

链栈出栈(Pop)

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/*
 *  出栈 弹栈
 *  s 链栈
*/
ElemType Pop(LinkStack s){
    LinkStack top;
    ElemType data;
    // 判栈空
    if(StackEmpty(s)){
        return FALSE;
    }
    top = s -> next; // 访问栈顶结点
    data = top -> data;  // 取出栈顶元素
    s -> next = top -> next;
    free(top);          // 释放栈顶空间
    return data;
}

链栈各操作测试

?
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
// 程序主入口
int main(int argc, char const *argv[])
{
    LinkStack s = InitLinkStack();
    printf("StackEmpty():%d\n", StackEmpty(s));
    printf("StackLength():%d\n\n", StackLength(s));
 
    // 入栈元素
    ElemType datas[] = {1, 3, 5, 7, 9};
 
    // 动态计算入栈元素个数
    int len = sizeof(datas) / sizeof(datas[0]);
 
    // for循环依次入栈
    printf("Push():");
    for(int i = 0; i < len; i++){
        printf("%d\t", datas[i]);
        Push(s, datas[i]);
    }
    printf("\nStackEmpty():%d\n", StackEmpty(s));
    printf("StackLength():%d\n\n", StackLength(s));
 
    // 出栈 弹栈
    printf("Pop(): ");
    while(!StackEmpty(s)){
        printf("%d\t", Pop(s));
    }
    printf("\nStackEmpty():%d\n", StackEmpty(s));
    printf("StackLength():%d\n\n", StackLength(s));
    return 0;
}

结果如下:

?
1
2
3
4
5
6
7
8
9
10
StackEmpty():1
StackLength():0
 
Push():1        3       5       7       9
StackEmpty():0
StackLength():5
 
Pop(): 9        7       5       3       1
StackEmpty():1
StackLength():0

源代码

源代码已上传到 GitHub Data-Structure-of-C,欢迎大家来访。

以上就是C语言实现链栈的步骤的详细内容,更多关于C语言实现链栈的资料请关注服务器之家其它相关文章!

原文链接:https://juejin.cn/post/6963884540276260877