发布时间 : 星期三 文章栈的课程设计完整版更新完毕开始阅读
唐山学院课程设计
结构是顺序存储结构和链式存储结构。栈是一种简单的数据结构。但在程序设计中却有着广泛的应用，很多程序都要用栈来做存储结构。如：判断字符串的中心对称，数制转换，函数的递归调用，文字编辑器的设计，算术表达式求值，树或图的遍历，拓扑排序，关键路径。在此次课程设计中做出了栈的其中两种应用，即数制转换和判断括号是否匹配以及迷宫求解。
了解栈的两种存储结构： 栈的顺序存储结构(简称数字栈)
数字栈是利用一批地址连续顺序存储结构单元依次存放自栈底到栈顶的数据元素。 栈的链式存储结构(简称为链栈)
它是运算受限制的单链表，其插入和删除操作只能在表头位置上进行 (1)数制转换:
十进制和其他d进制数的转换是计算机实现计算的基本问题，其中一个简单算法基于下列原理：
N=（N div d）*d+N mod d（div 为整除运算，mod为求余运算）
(2):括号匹配
括号匹配在很多字符串处理的场景中时常被用到，诸如各大IDE括号不匹配的错误提示，编译器编译时检查应该成对出现的括号是否符合要求等，在这里我们就直接使用一种比较常规，但效率不差的方法去解决括号匹配的问题就行了
为了方便描述，对于需要做匹配的两个符号，比如?(?和?)?，前者可称为左侧符号，后者可称为右侧符号。在做符号匹配时，如果以左侧符号为标准，左侧符号需要右侧符号来完成匹配，但是由于诸如括号这类的符号可以做嵌套，所以左侧符号之后既能有左侧符号，也能有右侧符号，处理起来很麻烦。以右侧符号为标准就没有这个问题了，每一个右侧符号都需要一个左侧符号来匹配，并且要求该右侧符号之前最近的一个符号必须是相匹配的左侧符号，这样处理起来就方便多了。 利用栈可以很容易地解决这个问题，在遍历字符串时，若当前位置是右侧符号，那它需要一个该位置之前最近的一个符号为左侧符号，否则不匹配。定义一个栈，用以记录遍历到当前位置时，所遇到的左侧符号，处理方式是这样的，每当遇到一个右侧符号时，检查栈是否为空，若此时栈不为空，则对栈进行pop操作表明顶部元素已被匹配，否则为不匹配情况，直接返回false。当整个字符串遍历结束，我们就可以通过判断该栈是否为空来判断整个字符串中的符号是否匹配。具体代码如下： (3)：表达式求值
2
唐山学院课程设计
表达式求值是程序设计语言编译中的一个基本问题。它的实现就是对“栈”的典型应用。本文针对表达式求值使用的是最简单直观的算法“算符优先法”。 我们都知道算术四则运算的运算规则是： 先乘除，后加减。 从左到右计算
先算括号内，再算括号外 表达式组成
任何一个表达式都有操作数、运算符和界定符组成。
操作数即可以是常量，也可以是被说明为变量或常量的标识符。 运算符可以分为算术运算，关系运算和逻辑运算符。 界定符有左右括号和结束符等。 本文为了方便演示只使用算术运算。 加减乘除优先性都低于“（”但是高于“）”，由运算从左到右可知，当θ1=θ2 ，令θ1>θ2
为了算法简洁，在表达式的左边和右边虚设一个“#”，这一对“#”表示一个表达式求值完成。 “（”=“）”当一对括号相遇时表示括号内已运算完成。 “）”和“（”、“#”和“(”、“(”和“#”无法相继出现如果出现则表达式出现语法错误。 为实现优先算法，可以使用两个工作栈，一个是OPTR，用于寄存运算符，一个是OPND，用于寄存运算数和运算结果。 算法基本思路。
首先置操作数栈为空栈，表达式起始符为“#”为栈底元素。
依次读入表达式中的每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权作相应操作，直至整个表达式求值完毕（OPTR栈顶元素和当前读入的字符均为“#”）
(4):迷宫求解为了描述迷宫的布局，将定义迷宫的数组m[][]设为全局变量以减少形参传递。另外还需要一个结构体来描述迷宫足迹的坐标,定义如下: struct Maze_Location { int x; //行坐标 int y; //列坐标};
int cur_num为记录通道的编号变量，每当有一个可走的通道时，cur_num就加1，最终找到一条路径的时候，该路径的呈现方式是1,2,3,4............依次按编号连成的一条线。刚开始还需设定入口和出门的坐标，并且入口坐标对应的块应该（确切的说是必须）为通道块，因此先将该坐标对应的位置上赋值为1，即cur_num当前的初始编号。为迷宫设定通道块和墙（通道块对应的值是-1，墙为0）程序的大体流程如下： 按（由东---北）的方向寻找路径 {
若下一步是通道块，则 {
编号加1，并且赋值给下一步足迹块;
3
唐山学院课程设计
若此时的这一步的坐标为出口坐标 {直接打印出路径；（一条路径已经找到！）} 否则
{递归调用该算法，但是此时的参数有变化，参数为当前这一步的坐标与当前编号(每次递归的参数都是下一步)} 编号减1；
将该块的值恢复为-1; } }
3总体设计
说明总体设计思路，画出模块结构图和总体流程图。
栈的应用系统 创建栈
栈的基本操作] 数制转换 括号匹配 迷宫求解 输出结果 图（1）功能实现
4
唐山学院课程设计
开始 创建栈并初始化
NO
5
判断是否栈满 则不能压栈满 入栈内 YES 选择入栈元素个数 输入元素 入栈成功 结束 2）入栈流程 图（