19、链式栈

Stack.h

 1 #ifndef STACK_H
 2 #define STACK_H
 3 
 4 #include<stdio.h>
 5 #include<stdlib.h>
 6 #include<string.h>
 7 
 8 #define OK 1
 9 #define ERROR 0
10 #define TRUE 1
11 #define FALSE 0
12 
13 typedef int SElemType;
14 typedef int Status;
15 //初始化结构
16 typedef struct StackNode{
17     SElemType data;
18     struct StackNode* next;
19 }StackNode,*LinkStackPtr;
20 
21 typedef struct LinkStack {
22     StackNode* top;
23     int count;
24 }LinkStack;
25 
26 
27 //初始化操作，建立一个空栈
28 LinkStack* InitStack();
29 //将栈清空
30 void ClearStack(LinkStack *s);
31 //销毁
32 void DestoryStack(LinkStack *s);
33 //若栈为空,返回TRUE，否则返回false
34 Status IsEmpty(LinkStack s);
35 //若栈存在且非空，用e返回S的栈顶元素
36 void GetTop(LinkStack s, SElemType *e);
37 //插入元素e为新的栈顶元素
38 Status Push(LinkStack *s, SElemType e);
39 //若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK，否则返回ERROR
40 Status Pop(LinkStack *s, SElemType *e);
41 //返回栈S的元素个数
42 Status StackLength(LinkStack *s);
43 
44 //打印
45 void PrintfStack(LinkStack *s);
46 
47 #endif

Stack.c

 1 #include"Stack.h"
 2 
 3 //初始化操作，建立一个空栈
 4 LinkStack* InitStack() {
 5     LinkStack *s = (LinkStack*)malloc(sizeof(LinkStack));
 6     s->count = 0;
 7     s->top = (StackNode*)malloc(sizeof(StackNode));
 8     s->top->data = NULL;
 9     s->top->next = NULL;
10     return s;
11 }
12 //将栈清空
13 void ClearStack(LinkStack *s) {
14 
15 
16 }
17 //销毁
18 void DestoryStack(LinkStack *s) {
19     if (s == NULL) {
20         return;
21     }
22     LinkStackPtr p;
23     p = s->top;//将栈顶结点赋值给p
24     while (p != NULL) {
25         LinkStackPtr pNext = p->next;
26         free(p);//释放结点p
27         p = pNext;
28     }
29     s->count = 0;
30     free(s);
31 }
32 //若栈为空,返回TRUE，否则返回false
33 Status IsEmpty(LinkStack s) {
34     if (s.top->next == NULL) {
35         return TRUE;
36     }
37     return FALSE;
38 }
39 //若栈存在且非空，用e返回S的栈顶元素
40 void GetTop(LinkStack s, SElemType *e) {
41 
42 
43 }
44 //插入元素e为新的栈顶元素
45 Status Push(LinkStack *s, SElemType e) {
46     LinkStackPtr a = (LinkStackPtr)malloc(sizeof(StackNode));
47     a->data = e;
48     a->next = s->top;//把当前的栈顶元素赋给新结点的直接后继
49     s->top = a;//将新结点a赋值给栈顶指针
50     s->count++;
51     return OK;
52 }
53 //若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK，否则返回ERROR
54 Status Pop(LinkStack *s, SElemType *e) {
55     StackNode* p;
56     if (IsEmpty(*s)) {
57         return ERROR;
58     }
59     *e = s->top->data;
60     p = s->top;//将栈顶结点赋值给p
61     printf("删除前s->top：%d
", s->top->data);
62     s->top = p->next;//使得栈顶指针下移一位，指向后一结点
63     free(p);//释放结点p
64     printf("删除后结点释放后s->top：%d
",s->top->data);
65     s->count--;
66     return OK;
67 }
68 //返回栈S的元素个数
69 Status StackLength(LinkStack *s) {
70     
71     int j = s->count;
72     return j;
73 }
74 
75 //打印
76 void PrintfStack(LinkStack *s) {
77     if (s == NULL) {
78         return;
79     }
80     LinkStackPtr pCurrent = s->top;
81     for (int i = 0; i < StackLength(s);i++) {
82         printf("%d ",pCurrent->data);
83         pCurrent = pCurrent->next;
84     }
85     printf("
");
86 }

main.c

 1 #define _CRT_SECURE_NO_WARNINGS
 2 
 3 #include<stdio.h>
 4 #include<stdlib.h>
 5 #include<string.h>
 6 #include"Stack.h"
 7 
 8 
 9 
10 int main()
11 {
12     int m[] = { 13,24,45,46,68,78,98 };
13     int n = 7;
14     //初始化
15     LinkStack* b = InitStack();
16     SElemType e;
17     printf("栈的长度为：%d 
", StackLength(b));
18     //入栈
19     for (int i = 0; i < n; i++) {
20         Push(b, m[i]);
21     }
22     //打印
23     printf("栈的长度为：%d 
", StackLength(b));
24     PrintfStack(b);
25 
26     //出栈
27     Pop(b, &e);
28 
29     //打印
30     printf("栈的长度为：%d 
", StackLength(b));
31     PrintfStack(b);
32 
33     //释放
34     DestoryStack(b);
35 
36 
37 
38     printf("
");
39     system("pause");
40     return 0;
41 }

VS2015运行结果：