栈的课程设计--栈的基本操作及其应用

1、数据结构课程设计题目 系（部）栈的基本操作及其应用计算机科学与技术系班 级16计本（2）姓 名学 号指导教师2018年 1 月8日至 2018年1月12日共1周数据结构课程设计任务书一、设计题目、内容及要求1、设计题目：栈的应用算法设计与实现。2、设计内容及要求：（1）实现栈的基本操作，如进栈、出栈、判栈空等。（2）实现栈的三种应用算法：如数制转换、表达式求值、括号匹配、文本编辑等应 用。（3）实现栈的应用一迷宫求解的应用算法。注：（2） （3）选择其一即可。二、要求的设计成果（课程设计说明书、设计实物、图纸等）1、用c语言或者c+语言进行程序设计，实现算法的功能。注重算法效率，代码要 有适当

2、的注释。2、撰写课程设计说明书一份，不少于2000字。课程设计说明书应包拈封面、任务 书、成绩评定表、正文（设计思路、设计步骤等）、参考文献（资料）等内容。三、进程安排1月8日：进行需求分析，确定算法的主要功能和算法思路；进行详细设计，确定各 模块的算法思路；1月9日1月10日：进行编码实现；进行测试调试，完善设计；1月11日：撰写设计说明书，准备答辩；1月12日：答辩。四、主要参考资料1. 严蔚敏，吴伟民.数据结构.清华大学出版社，20072. 苏仕华.数据结构课程设计.机械工业出版社，20103. 滕国文.数据结构课程设计.清华大学出版社，2010指导教师（签名）:教研室主任（签名）:在计

3、算机系统屮，栈则是一个具有以上属性的动态内存区域。程序可以将数据压入栈屮，也可 以将数据从栈顶弹出。在i386机器屮，栈顶巾称为esp的寄存器进行定位。压栈的操作使得栈顶的 地址减小，弹出的操作使得栈顶的地址增大。首先系统或者数据结构栈屮数据内容的读取与插入(压 入push和弹fli pop)是两回事！插入是增加数据，弹出是删除数据，这些操作只能从栈顶即最低地 址作为约束的接口界而入手操作，但读取栈屮的数据是随便的没有接口约束之说。很多人都误解这 个理念从而对栈产生困惑。而系统栈在计算机体系结构屮又起到一个跨部件交互的媒介区域的作用 即cpu与闪存的交流通道，cpu只从系统给我们向己编写的应用

4、程序所规定的栈入口线性地读取执 行指令，用一个形象的词来形容它就是pipeline (管道线、流水线)。cpu内部交互具体参见eu与 biu的概念介绍。栈作为一种数椐结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按 照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从 栈顶开始弹出数据(最后一个数据被第一个读出来)。栈具有记忆作用，对栈的插入与删除操作屮， 不需要改变栈底指针。桟是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈 顶(top)，另一端为栈底(bottom);栈底固定，而栈顶浮动；找中元素个数为零时称为空找

5、。插入一般 称为进栈(push),删除则称为退栈(pop)。栈也称力后进先出表。桟可以川来在函数调用的时 候存储断点，做递归时要用到栈！一、基本概念栈(stack)在计算机科学中是限定仅在表尾进行插入或删除操作的线形表。栈是一种数据结构，是只能在某一端插入和删除的特殊线性表。它按照先 进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在找顶，需要读数据的 时候从栈顶开始弹出数据(最后一个数据被第一个读出来)。栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的 一端称为栈顶(top)，另一端为栈底(bottom);栈底冏定，而栈顶浮动；栈中元素个数为零 时称为空栈。插

6、入一般称为进栈(push),删除则称为退栈(pop)。栈也称为后进先 出表(lifo表)，栈可以用来在函数调用的时候存储断点，做递归时要用到栈！木课程设计涉及的主要内容是对栈进行基木操作和实现栈的一些实际应用，在课程 设计中，系统开发平台为windows 7。程序设计语言使用visual c+。程序的运行平台为 windows 2000/xp/7/10。/*2问题分析本次课程设计主要介绍栈的概念和桟的基本操作和栈的两种存储结构及其应用。其 中栈的基本操作主要包括置空栈，判断栈空，进栈，出栈，取栈顶元素。栈的两种存储结构是顺序存储结构和链式存储结构。栈是一种简单的数据结构。但在程序设计屮却有 着

7、广泛的应用，很多程序都要用栈来做存储结构。如：判断字符串的屮心对称，数制转 换，函数的递归调用，文字编辑器的设计，算术表达式求值，树或图的遍历，拓扑排序， 关键路径。在此次课程设计中做出了栈的其中两种应用，即数制转换和判断括号是否匹 配以及迷宫求解。了解桟的两种存储结构：栈的顺序存储结构(简称数字栈)数字栈是利用一批地址连续顺序存储结构单元依次存放自栈底到栈顶的数据元素。 栈的链式存储结构(简称为链栈)它是运算受限制的单链表，其插入和删除操作只能在表头位置上进行 (1)数制转换：十进制和其他d进制数的转换是计算机实现计算的基木问题，其中一个简单算法 基于下列原理：n= (ndivd) *d+n

8、 mod d (div力整除运算，mod为求余运算)(2):括号匹配括号匹配在很多字符串处理的场景屮时常被用到，诸如各大ide括号不匹配的错 误提示，编译器编译时检查应该成对出现的括号是否符合要求等，在这里我们就直接 使用一种比较常规，但效率不差的方法去解决括号匹配的问题就行了为了方便描述，对于需要做匹配的两个符号，比如(和)，前者可称为左侧符号，后者 可称为右侧符号。在做符号匹配时，如果以左侧符号为标准，左侧符号需要右侧符号来 完成匹配，但是由于诸如括号这类的符号可以做嵌套，所以左侧符号之后既能有左侧符 号，也能冇右侧符号，处理起来很麻烦。以右侧符号为标准就没冇这个问题了，每一个 右侧符号都

9、需要一个左侧符号来闪配，并且要求该右侧符号之前最近的一个符号必须是 和匹配的左侧符号，这样处理起来就方便多了。利用栈可以很容易地解决这个问题，在 遍历字符申时，若当前位置是右侧符号，那它需要一个该位置之前最近的一个符号为左 侧符号，否则不匹配。定义一个栈，用以记录遍历到当前位置时，所遇到的左侧符号， 处理方式是这样的，每当遇到一个右侧符号吋，检査栈是否为空，若此吋栈不为空，则 对栈进行pop操作表明顶部元素己被闪配，否则为不匹配情况，直接返回false。当整个 字符串遍历结束，我们就可以通过判断该栈是否为空来判断整个字符串中的符号是否匹 配。具体代码如下：(3)：表达式求值表达式求值是程序设计

10、语言编译屮的一个棊本问题。它的实现就是对“栈”的典型应用。 本文针对表达式求值使用的是最简单直观的算法“算符优先法”。我们都知道算术四则运算的运算规则是：先乘除，后加减。从左到右计算先算括号内，再算括号外表达式组成任何一个表达式都有操作数、运算符和界定符组成。操作数即可以是常量，也可以是被说明为变量或常量的标识符。运算符可以分为算术运算，关系运算和逻辑运算符。界定符冇左右括号和结束符等。本文为了方便演示只使用算术运算。加减乘除优先性都低于“（”但是高于“）”，由运算从左到右可知，当0 1= （） 2，令o 1 02为了算法简洁，在表达式的左边和右边虚设一个“#”，这一对“#”表示一个表达式求值

11、 完成。当一对括号相遇时表示括号内己运算完成。“）”和“（”、“#”和“（”、“（”和“#”无法相继出现如果出现则表达式出现语法错误。 为实现优先算法，可以使用两个工作栈，一个是optr，用于寄存运算符，一个是opnd, 用于寄存运算数和运算结果。算法蘿本思路。首先罝操作数栈为空栈，表达式起始符为“#”为栈底元素。依次读入表达式中的每个字符，若是操作数则进opnd栈，若是运算符则和optr栈的 栈顶运算符比较优先权作相应操作，直至整个表达式求值完毕（optr栈顶元素和当前 读入的字符均为（4）:迷宫求解为了描述迷宫的布局，将定义迷宫的数组m设为全局变量以减少形参传 递。另外还需要一个结构体来描

12、述迷宫足迹的坐标，定义如下：struct maze_location int x; /行坐标 inty; /列坐标;int cur_num为记录通道的编号变量，悔当有一个可走的通道时，cur_num就加1，最终找到一条路径的时候，该路径的呈现方式是1,2,3,4依次按编号连成的一条线。刚开始还需设定入口和出门的坐标，并且入口坐标对应的块应该（确切的说是必须）为通 道块，因此先将该坐标对应的位置上赋值为1，即cur_mini当前的初始编号。为迷宫设 定通道块和墙（通道块对应的值是-1,墙为0）程序的大体流程如下：按（由东北）的方向寻找路径若下一步是通道块，则编号加1,并且赋值给下一步足迹块;若此

13、时的这一步的坐标为出口坐标直接打印出路径；（一条路径己经找到！）否则递归调用该算法，但是此时的参数有变化，参数为当 前这一步的坐标与当前编号（每次递归的参数都是下一步）编号减1;将该块的值恢复为-1;3总体设计说明总体设计思路，画出模块结构阁和总体流程阁。桟的应用系统栈的基本操作1迷宫求解输出结果（1）功能实现册桟满则不能压 入栈内(2)入栈流程输出操作数 伐浅顶纪果4详细设计对各个模块进行详细设计。对程序设计中的关键技术进行说明，是重点部分，可以 给出关键代码。每个模块均画出程序流程图。详细设计的任务主要包括对总体设计的深化和界面设计。在对总体设计的深化中，通过设计具体的存储结构以及算法所需

14、的辅助数据结构， 对数据结构和基本操作的规格说明做进一步的深化，按照算法书写规范，用类c语言写 出函数形式的算法框架，也可以给出算法流程阁。该过程应注意尽量避免陷入语言细节, 不必过早描述辅助数据结构和局部变量。界面设计主要是给出用户与程序交互的实现以及运算结果的呈现方式。详细设计的结果是对数据结构和棊本操作的进一步求精，写出数据存储结构的类型 定义，写出函数形式的算法框架。4.1模块介绍木程序共分为三个模块数制转换2.括号匹配3.迷宫求解switch语句分步求解4.1.1设计思路具体内容：首先创建一个栈（初始化）。确定栈是否为空。确定栈是否为满。取桟顶元素。出栈（删 除）元素运算。入栈（插入

15、）元素运算。建一个顺序栈，正如顺序表一样。由于栈在栈顶进 行操作，所以要保存栈顶位置。可以设置一个栈顶指针top指向栈顶。还有一些注意点，进栈时，首先要判断栈是否为满。如果桟为满，则返回null。 否则桟顶指针加1,然后将x插入当前栈顶。出栈时（删除），所以首先要判断栈是否 为空，可以直接调用判断栈空的函数，如果为空，则返冋0,否则删除栈顶元素。取栈顶 元素吋，首先判断栈是否为空，若为空，则返回0,否则取栈顶元素。5运行测试给出运行测试的结果，可以附上运行情况抓图。将各个功能模块均运行测试一遍。 包括调试过程中遇到的问题的解决、算法的时空分析和改进等。.首先，用户在打开软件吋，可以进入以下欢迎

16、界面，欢迎界面采用英文。主要介绍程 序的相关内容，以及软件发行后的维修和更新问题，并介绍相关操作系统。用户在阅读 之后，可以选择esc键退出软件，或者按照enter键进入程序。欢迎界面如下：进入欢迎界面，可听到一首悦人的音乐。 mcisendstringc'open ./res./音乐.mp3 alias love”，0,0,0）; mcisendstringc'play love repeat，0,0,0）;ss c:windowssystem32cmd.exewelcom to the interfacehello? user? welcome to use the sof

17、tware i developed，i am the software dev loper zhou dengviang.this software is nainlv applied to the knov/ledgeof the comp |uter stack? software development is used for 13 hours-the development enuironnen :is the windows 7 operating systen!using the development software as the uisual studio 2015.1 ho

18、pe you can use it-if there is any problem in the process of punning the software， you can con act ne.we will maintain and update the software after it is developed.thank you| for your support and i hope this software can nake you satisfied-esc:退出enter:开始enter键进入程序后，出现程序序号选择界面:c:windowssystem32cmd.ex

19、ewelcom to the interfacehello? user! ueleone to use the software i developed，i an the software dev loper zbou denguang - this software is mainli/ applied to the knowledgeof the comp |uter stack? software development is used for 13 hours-the deuelopment enuironmen :is the windows 7 operating systentu

20、sing the development software as the uisual studio 2015.1 hope you can use it.if there is any problem in the process of running the software# you can con ftact ne.we will maintain and update the software after it is deueloped-the backg kound of the software is <a girl of deep loue>- the softwa

21、re is still being perf ctedj. and i hope that the people i love can support me .thank you for your suppo h'tand i hope this software can make you satisfied.esc:退出enter:开始界面中共冇四个选项，0.退出1.进制转换2.括号匹配3.表达式求值4迷宫求解 用户可以根据自己的需求进行选择相应选择序号1:图(5)用户可以自己输入数值图(6)选择序号2用户白己输入图选择序号3:用户&己输入一串表达式进行求解:选择4回sb c

22、:windowssystem32cmd.exe欢迎进入迷宫程序1 f主:起点不能在迷宫墙上? k青输入起点坐标x:输入起点坐标后，可得到路径!c:windowssvstem32cmdj1h宫如下： t?|请输入起点坐标x:1v：:1|<1.1 <1.2><2,2><3,2<3,1><4.1<5,1><5,2<5,3><6,3<6.4<6.5><5,5<4.5<4.7><3<3,8<4,8<5,8<6.8<7,8><8,8 d6总结(r)通过这次课程设计使我懂得y理论与实际相结合的重要性。我们不仅要牢固的掌 握理论知识