唐山学院数据结构课程设计题目栈的基本操作及其应用系 (部) 计算机科学与技术系班级 16计本（2）姓名周登旺学号 4164001232指导教师郭琳虹2018 年 1 月8日至2018 年1 月12日共1 周数据结构课程设计任务书课程设计成绩评定表1.引言在计算机系统中，栈则是一个具有以上属性的动态内存区域。
程序可以将数据压入栈中，也可以将数据从栈顶弹出。
在i386机器中，栈顶由称为esp的寄存器进行定位。
压栈的操作使得栈顶的地址减小，弹出的操作使得栈顶的地址增大。
首先系统或者数据结构栈中数据内容的读取与插入（压入push和弹出pop）是两回事！插入是增加数据，弹出是删除数据，这些操作只能从栈顶即最低地址作为约束的接口界面入手操作，但读取栈中的数据是随便的没有接口约束之说。
很多人都误解这个理念从而对栈产生困惑。
而系统栈在计算机体系结构中又起到一个跨部件交互的媒介区域的作用即cpu与内存的交流通道，cpu只从系统给我们自己编写的应用程序所规定的栈入口线性地读取执行指令，用一个形象的词来形容它就是pipeline（管道线、流水线）。
cpu内部交互具体参见EU与BIU的概念介绍。
栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。
它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。
栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。
栈是允许在同一端进行插入和删除操作的特殊线性表。
允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。
插入一般称为进栈（PUSH），删除则称为退栈（POP）。
栈也称为后进先出表。
栈可以用来在函数调用的时候存储断点，做递归时要用到栈！一、基本概念栈（stack）在计算机科学中是限定仅在表尾进行插入或删除操作的线形表。
栈是一种数据结构，是只能在某一端插入和删除的特殊线性表。
它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。
栈是允许在同一端进行插入和删除操作的特殊线性表。
允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。
插入一般称为进栈（PUSH），删除则称为退栈（POP）。
栈也称为后进先出表（LIFO表）,栈可以用来在函数调用的时候存储断点，做递归时要用到栈！本课程设计涉及的主要内容是对栈进行基本操作和实现栈的一些实际应用，在课程设计中，系统开发平台为Windows 7。
程序设计语言使用Visual c++。
程序的运行平台为Windows 2000/XP/7/10。
/*2问题分析本次课程设计主要介绍栈的概念和栈的基本操作和栈的两种存储结构及其应用。
其中栈的基本操作主要包括置空栈，判断栈空，进栈，出栈，取栈顶元素。
栈的两种存储结构是顺序存储结构和链式存储结构。
栈是一种简单的数据结构。
但在程序设计中却有着广泛的应用，很多程序都要用栈来做存储结构。
如：判断字符串的中心对称，数制转换，函数的递归调用，文字编辑器的设计，算术表达式求值，树或图的遍历，拓扑排序，关键路径。
在此次课程设计中做出了栈的其中两种应用，即数制转换和判断括号是否匹配以及迷宫求解。
了解栈的两种存储结构：栈的顺序存储结构(简称数字栈)数字栈是利用一批地址连续顺序存储结构单元依次存放自栈底到栈顶的数据元素。
栈的链式存储结构(简称为链栈)它是运算受限制的单链表，其插入和删除操作只能在表头位置上进行(1)数制转换:十进制和其他d进制数的转换是计算机实现计算的基本问题，其中一个简单算法基于下列原理：N=（N div d）*d+N mod d（div 为整除运算，mod为求余运算）(2):括号匹配括号匹配在很多字符串处理的场景中时常被用到，诸如各大IDE括号不匹配的错误提示，编译器编译时检查应该成对出现的括号是否符合要求等，在这里我们就直接使用一种比较常规，但效率不差的方法去解决括号匹配的问题就行了为了方便描述，对于需要做匹配的两个符号，比如‟(…和‟)‟，前者可称为左侧符号，后者可称为右侧符号。
在做符号匹配时，如果以左侧符号为标准，左侧符号需要右侧符号来完成匹配，但是由于诸如括号这类的符号可以做嵌套，所以左侧符号之后既能有左侧符号，也能有右侧符号，处理起来很麻烦。
以右侧符号为标准就没有这个问题了，每一个右侧符号都需要一个左侧符号来匹配，并且要求该右侧符号之前最近的一个符号必须是相匹配的左侧符号，这样处理起来就方便多了。
利用栈可以很容易地解决这个问题，在遍历字符串时，若当前位置是右侧符号，那它需要一个该位置之前最近的一个符号为左侧符号，否则不匹配。
定义一个栈，用以记录遍历到当前位置时，所遇到的左侧符号，处理方式是这样的，每当遇到一个右侧符号时，检查栈是否为空，若此时栈不为空，则对栈进行pop操作表明顶部元素已被匹配，否则为不匹配情况，直接返回false。
当整个字符串遍历结束，我们就可以通过判断该栈是否为空来判断整个字符串中的符号是否匹配。
具体代码如下：(3)：表达式求值表达式求值是程序设计语言编译中的一个基本问题。
它的实现就是对“栈”的典型应用。
本文针对表达式求值使用的是最简单直观的算法“算符优先法”。
我们都知道算术四则运算的运算规则是：先乘除，后加减。
从左到右计算先算括号内，再算括号外表达式组成任何一个表达式都有操作数、运算符和界定符组成。
操作数即可以是常量，也可以是被说明为变量或常量的标识符。
运算符可以分为算术运算，关系运算和逻辑运算符。
界定符有左右括号和结束符等。
本文为了方便演示只使用算术运算。
加减乘除优先性都低于“（”但是高于“）”，由运算从左到右可知，当θ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，并且赋值给下一步足迹块;若此时的这一步的坐标为出口坐标{直接打印出路径；（一条路径已经找到！）}否则{递归调用该算法，但是此时的参数有变化，参数为当前这一步的坐标与当前编号(每次递归的参数都是下一步)}编号减1；将该块的值恢复为-1;}}3总体设计说明总体设计思路，画出模块结构图和总体流程图。
图（1）功能实现图（2）入栈流程图(3)数制转换图(4)表达式求值4详细设计对各个模块进行详细设计。
对程序设计中的关键技术进行说明，是重点部分，可以给出关键代码。
每个模块均画出程序流程图。
详细设计的任务主要包括对总体设计的深化和界面设计。
在对总体设计的深化中，通过设计具体的存储结构以及算法所需的辅助数据结构，对数据结构和基本操作的规格说明做进一步的深化，按照算法书写规范，用类C语言写出函数形式的算法框架，也可以给出算法流程图。
该过程应注意尽量避免陷入语言细节，不必过早描述辅助数据结构和局部变量。
界面设计主要是给出用户与程序交互的实现以及运算结果的呈现方式。
详细设计的结果是对数据结构和基本操作的进一步求精，写出数据存储结构的类型定义，写出函数形式的算法框架。
…………4.1 模块介绍本程序共分为三个模块: 1. 数制转换 2.括号匹配 3.迷宫求解Switch语句分步求解4.1.1设计思路具体内容:首先创建一个栈(初始化)。
确定栈是否为空。
确定栈是否为满。
取栈顶元素。
出栈（删除）元素运算。
入栈(插入)元素运算。
建一个顺序栈，正如顺序表一样。
由于栈在栈顶进行操作，所以要保存栈顶位置。
可以设置一个栈顶指针Top指向栈顶。
还有一些注意点，进栈时，首先要判断栈是否为满。
如果栈为满，则返回NULL。
否则栈顶指针加1，然后将X插入当前栈顶。
出栈时（删除），所以首先要判断栈是否为空，可以直接调用判断栈空的函数，如果为空，则返回0，否则删除栈顶元素。
取栈顶元素时，首先判断栈是否为空，若为空，则返回0，否则取栈顶元素。
5运行测试给出运行测试的结果，可以附上运行情况抓图。
将各个功能模块均运行测试一遍。
包括调试过程中遇到的问题的解决、算法的时空分析和改进等。
……首先，用户在打开软件时，可以进入以下欢迎界面,欢迎界面采用英文。
主要介绍程序的相关内容，以及软件发行后的维修和更新问题，并介绍相关操作系统。
用户在阅读之后，可以选择ESC键退出软件，或者按照Enter键进入程序。
欢迎界面如下:进入欢迎界面，可听到一首悦人的音乐。
mciSendString(“open ./res./音乐.mp3 alias LOVE”,0,0,0);mciSendString(“play LOVE repeat”,0,0,0);:Enter键进入程序后，出现程序序号选择界面;界面中共有四个选项，0.退出1.进制转换 2.括号匹配 3.表达式求值4迷宫求解用户可以根据自己的需求进行选择相应选择序号1：图(5) 用户可以自已输入数值图(6)图(7) 用户自己输入图(8)用户自己输入一串表达式进行求解:选择4输入起点坐标后，可得到路径！6总结(1)通过这次课程设计使我懂得了理论与实际相结合的重要性。
我们不仅要牢固的掌握理论知识，更要把所学到的理论与实践相结合。