《数据结构（C语言版）》栈的实现与应用
清华大学计算机系列教材 累计发行超400万册
严蔚敏 吴伟明 编著
数据结构（C语言版）
以下是本人对该紫皮书第三章栈中顺序栈的代码实现，并且完成了数制转换、括号匹配的检验、行编辑程序等功能，代码（含详细注释）在450行左右
（貌似专栏把我缩进吃了，懒得加了，另外建议用visual studio编译）
//顺序栈的表示和实现
//用顺序栈实现数制转换、括号匹配检查、行编辑程序
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define STACK_INIT_SIZE 100//存储空间初始分配量
#define STACKINCREMENT 10//存储空间分配增量
typedef int SElemType;
typedef int Status;
typedef struct
{
SElemType* base;
SElemType* top;
int stacksize;//当前已分配的存储空间，以元素为单位
}Sqstack;
/*
通常top指示真正的栈顶元素之上的下标地址，初始值指向栈底
base始终指向栈底的位置，若base的值为NULL则表明栈结构不存在
栈空：top==base
栈满：top-base==stacksize
*/
Status InitStack(Sqstack& S);//初始化一个空栈
Status DestoryStack(Sqstack& S);//销毁栈
Status ClearStack(Sqstack& S);//把S置为空栈
Status StackEmpty(Sqstack S);//判断栈是否为空
int StackLength(Sqstack S);//求栈的长度
Status GetTop(Sqstack& S, SElemType& e);//返回栈顶元素，若为空则返回ERROR
Status Push(Sqstack& S, SElemType e);//顺序栈的入栈
Status Pop(Sqstack& S, SElemType& e);//顺序栈的出栈
Status StackTraverse(Sqstack S, Status(*visit)(SElemType*));//从栈底到栈顶一次对栈中每个元素调用函数visit()，一旦visit()失败则操作失败
Status ShowStack(SElemType* p);//打印顺序栈中的元素(从栈底到栈顶）
Status ShowStack2(SElemType* p);//该打印函数是为行编辑函数服务的，因为要打印字符
void conversion();//对于输入的任意一个非负十进制整数，打印输出与其值等值得八进制数
Status CheckParenMatching(char* str);//括号匹配检验
void LineEdit();//利用字符栈S，从终端接受一行并传送至调用过程的数据区
void Menu1()
{
printf("******************************\n");
printf("********0.退出本次使用********\n");
printf("********1.栈的基本功能********\n");
printf("********2.不同数制转换********\n");
printf("********3.括号匹配检验********\n");
printf("********4.行编辑程序**********\n");
printf("******************************\n");
}
void Menu2()
{
printf("**************************\n");
printf("********0.返回上步********\n");
printf("********1.入 栈********\n");
printf("********2.出 栈********\n");
printf("********3.求 栈 长********\n");
printf("********4.求 栈 顶********\n");
printf("********5.打 印 栈********\n");
printf("********6.置 空 栈********\n");
printf("********7.销 毁 栈********\n");
printf("********8.判断空栈********\n");
printf("**************************\n");
}
int main()
{
int option1 = -1;
int option2 = -1;
int value = 0;
char str[100] = { 0 };
Sqstack Mystack;
InitStack(Mystack);
Menu1();
while (scanf("%d", &option1) != EOF)
{
while (getchar() != '\n');
switch(option1)
{
case 1:
Menu2();
while (scanf("%d", &option2) != EOF)
{
while (getchar() != '\n');
switch (option2)
{
case 1:
printf("请输入你要入栈的元素：");
while (scanf("%d", &value) != 1)
{
printf("你输入了非法字符，请重新输入:");
while (getchar() != '\n');
}
if (Push(Mystack, value))
{
printf("入栈成功！\n");
}
break;
case 2:
if (Pop(Mystack, value))
{
printf("出栈成功！\t您出栈的元素为%d\n", value);
}
else
{
printf("该顺序栈已空！不能出栈！\n");
}
break;
case 3:
printf("该顺序栈的栈长为：%d\n", StackLength(Mystack));
break;
case 4:
if (GetTop(Mystack, value))
{
printf("该顺序栈栈顶元素为：%d\n", value);
}
else
{
printf("该顺序栈为空栈！\n");
}
break;
case 5:
if (StackEmpty(Mystack))
{
printf("该顺序栈为空栈！\n");
}
else
{
printf("从栈底到栈顶依次为：");
if (StackTraverse(Mystack, ShowStack))
{
printf("\n");
}
}
break;
case 6:
if (ClearStack(Mystack))
{
printf("栈已置空！\n");
}
break;
case 7:
if (DestoryStack(Mystack))
{
printf("栈已销毁！\n");
}
break;
case 8:
if (StackEmpty(Mystack))
{
printf("该顺序栈为空栈！\n");
}
else
{
printf("该顺序栈非空！\n");
}
case 0:
break;
default:
printf("你输入了非法字符，请重新输入\n");
break;
}
if (option2 == 0)
{
break;
}
Menu2();
}
break;
case 2:
conversion();
break;
case 3:
printf("您可以用此功能检查形如5-{3-[5*(9/3)-4]}的算术表达式括号是否匹配\n");
printf("请输入表达式：");
fgets(str, 100, stdin);
if (CheckParenMatching(str))
{
printf("括号成功匹配!\n");
}
else
{
printf("括号不匹配!\n");
}
break;
case 4:
printf("您可以用此功能在不小心输入错误时用#代替退格符Backspace，用@代替退行符\n");
printf("例如你输入了如下两段字符：\n");
printf("whli##ilr#e(s#*s)\n");
printf(" outcha@putchar(*s=#++);\n");
printf("则实际有效的是下列两行\n");
printf("while(*s)\n");
printf("putchar(*s++);\n");
printf("当你按住Ctrl+z可停止输入\n");
printf("请输入一串字符：\n");
LineEdit();
break;
case 0:
printf("感谢使用！\n");
exit(0);
default:
printf("你输入了非法字符，请重新输入\n");
}
Menu1();
}
return 0;
}
Status InitStack(Sqstack& S)//初始化一个空栈
{
S.base = (SElemType*)malloc(STACK_INIT_SIZE * sizeof(SElemType));
if (!S.base)
{
exit(OVERFLOW);
}
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}
Status DestoryStack(Sqstack& S)//销毁栈
{
if (S.base)
{
free(S.base);
S.stacksize = 0;
S.top = NULL;
S.base = NULL;
}
return OK;
}
Status ClearStack(Sqstack& S)//把S置为空栈
{
if (S.base)
{
S.top = S.base;
return OK;
}
}
Status StackEmpty(Sqstack S)//判断栈是否为空
{
if (S.top == S.base)
{
return TRUE;
}
else
{
return FALSE;
}
}
int StackLength(Sqstack S)//求栈的长度
{
return S.top - S.base;
}
Status GetTop(Sqstack& S, SElemType& e)//返回栈顶元素，若为空则返回ERROR
{
if (S.top == S.base)
{
return ERROR;
}
e = *(S.top - 1);
return OK;
}
Status Push(Sqstack& S, SElemType e)//顺序栈的入栈
{
if (S.top - S.base >= S.stacksize)
{
/*
这里和课本有一点点不同，我是先realloc一个指针为New_ptr的空间，再把这个指针分配给S.base
原因是visual studio太高级了，它觉得realloc不安全，可能会引出一个内存泄露的问题
当realloc分配失败的时候，会返回NULL。如果直接赋值给S.base的话，S.base的内存是没有被释放的
如果直接将realloc的返回值赋给S.base，那么当申请内存失败时，就会造成S.base原来指向的内存丢失，造成泄露。
*/
SElemType* New_ptr = (SElemType*)realloc(S.base, ((S.stacksize) + STACKINCREMENT) * sizeof(SElemType));
if (!New_ptr)
{
exit(OVERFLOW);
}
S.base = New_ptr;
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++ = e;
return OK;
}
Status Pop(Sqstack& S, SElemType& e)//顺序栈的出栈
{
if (S.top == S.base)
{
return ERROR;
}
e = *--S.top;
return OK;
}
Status StackTraverse(Sqstack S, Status(*visit)(SElemType*))//从栈底到栈顶一次对栈中每个元素调用函数visit()，一旦visit()失败则操作失败
{
while (S.top != S.base)
{
if (!visit(S.base++))
{
return ERROR;
}
}
return OK;
}
Status ShowStack(SElemType* p)//打印顺序栈中的元素(从栈底到栈顶）
{
printf("%d ", *p);
return OK;
}
Status ShowStack2(SElemType* p)//该打印函数是为行编辑函数服务的，因为要打印字符
{
printf("%c", *p);
return OK;
}
void conversion()//对于输入的任意一个非负十进制整数，打印输出与其值等值得八进制数
{
Sqstack S;
int N = 0;
SElemType e = 0;
InitStack(S);
printf("请输入你想转换的数：");
while (scanf("%d", &N) != 1)
{
printf("你输入了非法字符，请重新输入:");
while (getchar() != '\n');
}
while (N)
{
Push(S, N % 8);
N = N / 8;
}
printf("转换成八进制后的数为：");
while (!StackEmpty(S))
{
Pop(S, e);
printf("%d", e);
}
printf("\n");
}
Status CheckParenMatching(char* str)//括号匹配检验
/*
算法具体描述如下
依次读取代码字符串中的字符
若是非括号字符，则忽略并继续读取下一个字符；
若是左括号字符，则压栈；
否则为右括号，与栈顶元素进行匹配：
若栈空，则是多余的右括号，报错返回；
否则
若匹配成功，则栈顶元素弹栈，继续读取下一个字符；
否则匹配错误，报错返回；
代码字符串遍历结束时：
若栈空，则匹配成功，正确返回；
否则有左括号还没匹配，报错返回。
*/
{
Sqstack S;
InitStack(S);
int Length = strlen(str);
SElemType e = 0;
for (int i = 0; i < Length; i++)
{
switch (str[i])
{
case '{':
case '[':
case '(':
Push(S, str[i]);
break;
case '}':
if (StackEmpty(S))
{
return ERROR;
}
Pop(S, e);
if (e != '{')
{
return ERROR;
}
break;
case ']':
if (StackEmpty(S))
{
return ERROR;
}
Pop(S, e);
if (e != '[')
{
return ERROR;
}
break;
case ')':
if (StackEmpty(S))
{
return ERROR;
}
Pop(S, e);
if (e != '(')
{
return ERROR;
}
break;
default:
break;
}
}
if (!StackEmpty(S))
{
return ERROR;
}
return OK;
}
void LineEdit()//利用字符栈S，从终端接受一行并传送至调用过程的数据区
{
Sqstack S;
InitStack(S);
SElemType c = 0;
char ch = getchar();
while (ch != EOF)
{
while (ch != EOF && ch != '\n')
{
switch (ch)
{
case '#':
Pop(S, c);
break;
case '@':
ClearStack(S);
break;
default:
Push(S, ch);
}
ch = getchar();
}
printf("你最终输入的字符为：");
if (StackTraverse(S, ShowStack2))
{
printf("\n");
}
printf("已将你所编辑的字符传入到数据区\n");
ClearStack(S);
if (ch != EOF)
{
ch = getchar();
}
}
DestoryStack(S);
}
