俗话说得好，线性表（尤其是链表）是一切数据结构和算法的基础，很多复杂甚至是高级的数据结构和算法，细节处，除去数学和计算机程序基础的知识，大量的都在应用线性表。
一、栈
其实本质还是线性表：限定仅在表尾进行插入或删除操作。 俗称：后进先出 (LIFO=last in first out结构)，也可说是先进后出（FILO）。
同样的，栈也分为顺序和链式两大类。其实和线性表大同小异，只不过限制在表尾进行操作的线性表的特殊表现形式。
1、顺序栈：利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针 top 指示栈顶元素在顺序栈中的位置，附设指针 base 指示栈底的位置。 同样，应该采用可以动态增长存储容量的结构。且注意，如果栈已经空了，再继续出栈操作，则发生元素下溢，如果栈满了，再继续入栈操作，则发生元素上溢。栈底指针 base 初始为空，说明栈不存在，栈顶指针 top 初始指向 base，则说明栈空，元素入栈，则 top++，元素出栈，则 top--，故，栈顶指针指示的位置其实是栈顶元素的下一位（不是栈顶元素的位置）。
复制代码
1 #ifndef _____ADT__
2 #define _____ADT__
3 #include
4 #include
5 #include
6 #define STACK_SIZE 50
7 #define STACK_INCREMENT 10
8
9 typedef struct{
10 int stackSize;//栈容量
11 char *base;//栈底指针
12 char *top;//栈顶指针
13 } SqStack;
14
15 //初始化
16 //本质还是使用动态数组
17 void initStack(SqStack *s)
18 {
19 s->base = (char *)malloc(STACK_SIZE * sizeof(char));
20 //分配成功
21 if (s->base != NULL) {
22 //空栈
23 s->top = s->base;
24 s->stackSize = STACK_SIZE;
25 }
26 else
27 {
28 puts("分配失败！");
29 }
30 }
31
32 //判空
33 bool isEmpty(SqStack s)
34 {
35 return s.top == s.base true : false;
36 }
37
38 //判满
39 bool isFull(SqStack s)
40 {
41 return (s.top - s.base) >= STACK_SIZE true : false;
42 }
43
44 //求当前长度
45 int getLength(SqStack s)
46 {
47 int i = 0;
48 char *q = s.top;
49
50 while (q != s.base) {
51 q--;
52 i++;
53 }
54
55 return i;
56 }
57
58 //求栈顶元素
59 char getTop(SqStack s, char topElement)
60 {
61 if (isEmpty(s)) {
62 puts("栈空！");
63 }
64
65 topElement = *(s.top - 1);
66 return topElement;
67 }
68
69 //入栈
70 void push(SqStack *s, char topElement)
71 {
72 char *q = NULL;
73
74 if (isFull(*s)) {
75 q = (char *)realloc(s->base, STACK_INCREMENT * sizeof(char));
76
77 if (NULL == q) {
78 exit(0);
79 }
80
81 s->base = q;
82 s->stackSize = s->stackSize + STACK_INCREMENT;
83 }
84 //进栈
85 *s->top++ = topElement;
86 }
87
88 //出栈
89 void pop(SqStack *s, char *topElement)
90 {
91 if (isEmpty(*s)) {
92 exit(0);
93 }
94
95 s->top--;
96 *topElement = *s->top;
97 }
98
99 //遍历
100 void traversal(SqStack s)
101 {
102 for (int i = 0; i < getLength(s); i++) {
103 printf("栈中元素遍历：%c \n", s.base[i]);
104 }
105 }
106
107 //清空
108 void cleanStack(SqStack *s)
109 {
110 if (!isEmpty(*s)) {
111 s->top = s->base;
112 puts("栈已经清空！");
113 }
114 }
115
116 //销毁
117 void destroyStack(SqStack *s)
118 {
119 if (s->base != NULL) {
120 free(s->base);
121 s->base = NULL;
122 s->top = NULL;
123 s->stackSize = 0;
124 puts("栈成功销毁！");
125 }
126 }
127
128 #endif /* defined(_____ADT__) */
复制代码
函数: void exit(int status); 所在头文件：stdlib.h
功 能: 关闭所有文件，终止正在执行的进程。
exit(1)表示异常退出.这个1是返回给操作
系统的。
exit(x)（x不为0）都表示异常退出
exit(0)表示正常退出
exit()的参数会被传递给一些操作系统，包括UNIX,
Linux,和MS DOS，以供其他程序使用。
exit()和return