数据结构算法C语言实现（七）--- 3.1栈的线性实现及应用举例
一.简述
栈，LIFO。是操作受限的线性表，和线性表一样有两种存储表示方法。下面以顺序存储为例，实现。
二.ADT
暂无。
三.头文件
1 //3_1.h
2 /**
3 author:zhaoyu
4 email:zhaoyu1995.com@gmail.com
5 date:2016-6-7
6 note:realize my textbook <<数据结构（C语言版）>>
7 */
8 //Page 46
9
10 #ifndef _3_1_H_
11 #define _3_1_H_
12 #include <cstdio>
13 #include <cstdlib>
14 #include "head.h"
15 /**
16 My Code
17 */
18 #define SElemType char
19 //----栈的顺序存储表示----
20 #define STACK_INIT_SIZE 100//存储空间的初始分配值
21 #define STACKINCREMENT 10//存储空间分配增量
22 typedef struct{
23 SElemType *base;//在栈构造之前和销毁之后，base 值为 NULL
24 SElemType *top;//栈顶指针
25 int stacksize;//当前已分配的存储空间，以元素为单位
26 }SqStack;
27 //----基本操作的函数原型说明及部分实现----
28 Status InitStack(SqStack &S)
29 {
30 //构造一个空栈 S
31 S.base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
32 if (!S.base)
33 {
34 exit(OVERFLOW);
35 }
36 S.top = S.base;
37 S.stacksize = STACK_INIT_SIZE;
38 return OK;
39 }//InitStack
40 Status DestroyStack(SqStack &S)
41 {
42 //销毁栈 S，S 不再存在
43 }
44 Status ClearStack(SqStack &S)
45 {
46 //将 S 置为空栈
47 S.top = S.base;
48 return OK;
49 }
50 Status StackEmpty(SqStack S)
51 {
52 //若 S 为空栈， 则返回 TRUE， 否则返回 FALSE
53 if (S.base == S.top)
54 {
55 return TRUE;
56 }
57 else
58 {
59 return FALSE;
60 }
61 }
62 int StackLength(SqStack S)
63 {
64 //返回 S 的元素的个数，即栈的长度
65 }
66 Status GetTop(SqStack S, SElemType &e)
67 {
68 //若栈不空，则用 e 返回 S 的栈顶元素，并返回 OK；
69 //否则返回ERROR
70 if (S.top == S.base)
71 {
72 return ERROR;
73 }
74 e = *(S.top - 1);
75 return OK;
76 }//GetTop
77 Status Push(SqStack &S, SElemType e)
78 {
79 //插入元素 e 为新的栈顶元素
80 if (S.top - S.base >= S.stacksize)
81 {//栈满，追加存储空间
82 S.base = (SElemType *)realloc(S.base,
83 (S.stacksize+STACKINCREMENT)*sizeof(SElemType));
84 if (!S.base)
85 {
86 exit(OVERFLOW);
87 }
88 S.top = S.base + S.stacksize;
89 S.stacksize += STACKINCREMENT;
90 }
91 *S.top++ = e;
92 return OK;
93 }//Push
94 Status Pop(SqStack &S, SElemType &e)
95 {
96 //若栈不空，则删除 S 的栈顶元素，用 e 返回其
97 //值，并返回OK；否则返回ERROR
98 if (S.top == S.base)
99 {
100 return ERROR;
101 }
102 e = *--S.top;
103 return OK;
104 }//Pop
105 Status StackTraverse(SqStack S, Status (* visit)())
106 {
107 //从栈底到栈顶一次对栈中每个元素调用函数visit()
108 //一旦visit() 失败，则操作失败
109 }
110
111 //----栈的应用举例-----
112 //注意代码之间的数据类型冲突，所以编译时要根据要编译的部分
113 //注释掉阈值冲突的部分
114 /**
115 algorithm 3.1
116 */
117 /*
118 void conversion()
119 {
120 //对于输入的任意一个非负十进制整数，
121 //打印输出与其等值的 n 进制数
122 //note:书上是8进制，这里稍作拓展
123 SqStack S;
124 InitStack(S);
125 int N, n, e;
126 scanf("%d%d", &N, &n);
127 while (N)
128 {
129 Push(S, N%n);
130 N = N/n;
131 }
132 while (!StackEmpty(S))
133 {//while (!StackEmpty)竟然不报错
134 //StackEmppty是一个非NULL的指针！！！
135 Pop(S, e);
136 printf("%d", e);
137 }
138 }//conversion
139 */
140
141
142 //note:以下两个函数不能与conversion()同时编译
143 //因为具体处理的数据类型不同
144 /**
145 algorithm 3.4
146 */
147
148 void PrintStack_LineEdit(SqStack S)
149 {
150 char ch;
151 SqStack TempStack;
152 InitStack(TempStack);
153 while (!StackEmpty(S))
154 {
155 Pop(S, ch);
156 Push(TempStack, ch);
157 }
158 while (!StackEmpty(TempStack))
159 {
160 Pop(TempStack, ch);
161 putchar(ch);
162 }
163 printf("\n");
164 }
165 void LineEdit()
166 {
167 //利用字符栈 S 从终端接收一行并传送至调用过程的数据区
168 //编译时要将 SElemType 设置成 char（而不是 int）
169 SqStack S;
170 InitStack(S);
171 char c,ch;
172 ch = getchar();
173 while (EOF != ch)//EOF 为全文结束符
174 {
175 while (EOF != ch && '\n' != ch)
176 {
177 switch (ch)
178 {
179 case '#':
180 {
181 Pop(S, c);
182 break;//仅当栈非空时退栈
183 }
184 case '@':
185 {
186 ClearStack(S);//重置 S 为空栈
187 break;
188 }
189 default:
190 {
191 Push(S, ch);//有效字符进栈
192 break;
193 }
194 }
195 ch = getchar();//从终端接收下一个字符
196 }
197 //将从栈底到栈顶的栈内字符传送至调用过程的数据区
198 PrintStack_LineEdit(S);
199 ClearStack(S);//重置 S 为空栈
200 if (EOF != ch)
201 {
202 ch = getchar();
203 }
204 }
205 DestroyStack(S);
206 }//LineEdit
207 #endif
View Code
四.CPP文件
1 #include "3_1.h"
2 int main(int argc, char const *argv[])
3 {
4 /* for (int i = 0; i < 5; i++)
5 {
6 conversion();
7 }*/
8 LineEdit();
9 return 0;
10 }
View Code
五.测试
进制转换
行编辑程序
