数据结构_链栈(C语言)_链栈的c语言表示

数据结构总目录

（一）链栈图文解析

链栈是指采用链式结构实现的栈，和单链表的存储结构相同，用数据域和指针域分别代表存储的数据与指针，与单链表不同的是链栈不需要头结点，且只对栈顶元素依次进行入栈和出栈操作，遵循先入后出的原则。

• 入栈
  
• 出栈
  

（二）顺序栈代码解析

1. 基本操作

1.1 存储结构

typedef char DataType;
typedef struct LNode
{
    DataType data;
    struct LNode *next;
}LinkStack;
1
2
3
4
5
6

1.2 初始化

// 初始化
void InitStack(LinkStack **LS)
{
    // 链栈不需要头结点，故初始即为空
    (*LS) = NULL;
    printf("链栈已初始化!\n");
}
1
2
3
4
5
6
7

1.3 入栈

// 入栈
void Push(LinkStack **LS)
{
    DataType x;
    fflush(stdin);
    printf("请输入入栈数据:");
    scanf("%c", &x);

    // 创建一个新的结点
    LinkStack *s;
    s = (LinkStack *)malloc(sizeof(LinkStack));
    s->data = x;

    // 采用头插法,修改头指针的指向
    s->next = (*LS);
    (*LS) = s;
    
    printf("已入栈:%c\n", x);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

1.4 出栈

// 出栈
void Pop(LinkStack **LS)
{
    LinkStack *p = (*LS);
    if (p != NULL)
    {
        // 删除第一个结点，并修改头指针指向
        (*LS) = (*LS)->next;
        printf("出栈结点:%c\n", p->data);
        free(p);
    }
    else
    {
        printf("栈空!\n");
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

1.5 取栈顶元素

// 获取栈顶元素
void GetTop(LinkStack *LS)
{
    if (LS != NULL)
    {
        printf("栈顶元素为:%c\n", LS->data);
    }
    else
    {
        printf("栈为空!\n");
    }  
}
1
2
3
4
5
6
7
8
9
10
11
12

2. 源代码及测试

2.1 源代码：

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

typedef char DataType;
typedef struct LNode
{
    DataType data;
    struct LNode *next;
}LinkStack;

// 初始化
void InitList(LinkStack **LS)
{
    // 链栈不需要头结点，故初始即为空
    (*LS) = NULL;
    printf("链栈已初始化!\n");
}

// 入栈
void Push(LinkStack **LS)
{
    DataType x;
    fflush(stdin);
    printf("请输入入栈数据:");
    scanf("%c", &x);

    // 创建一个新的结点
    LinkStack *s;
    s = (LinkStack *)malloc(sizeof(LinkStack));
    s->data = x;

    // 采用头插法,修改头指针的指向
    s->next = (*LS);
    (*LS) = s;
    
    printf("已入栈:%c\n", x);
}

// 出栈
void Pop(LinkStack **LS)
{
    LinkStack *p = (*LS);
    if (p != NULL)
    {
        // 删除第一个结点，并修改头指针指向
        (*LS) = (*LS)->next;
        printf("出栈结点:%c\n", p->data);
        free(p);
    }
    else
    {
        printf("栈空!\n");
    }
}

// 获取栈顶元素
void GetTop(LinkStack *LS)
{
    if (LS != NULL)
    {
        printf("栈顶元素为:%c\n", LS->data);
    }
    else
    {
        printf("栈为空!\n");
    }  
}

// 遍历栈序列
void Display(LinkStack *LS)
{
    while (LS)
    {
        printf("%c->", LS->data);
        LS = LS->next;
    }
    printf("NULL]\n");  
}

int main()
{
    printf("****************************\n");
    printf("0:退出\t1:入栈\t2:出栈\n");
    printf("3:取栈顶元素\t4:遍历栈序列\n");
    printf("****************************\n");

    int k;
    LinkStack *LS;
    InitStack(&LS);
    while (1)
    {
        printf("请输入操作序号:");
        scanf("%d", &k);
        if (!k)
        {
            break;
        }
        switch (k)
        {
            case 1: Push(&LS);   break;
            case 2: Pop(&LS);    break;
            case 3: GetTop(LS); break;
            case 4: Display(LS);break;
            default: break;
        } 
        printf("\n");
    }
    system("pause");
    return 0;
}
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

2.2 测试结果：