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

数据结构 课 程 设 计题 目 栈的基本操作及其应用 系 (部) 计算机科学与技术系 班 级 16计本（2） 姓 名 学 号 指导教师 2018 年 1 月 8日 至 2018 年 1 月 12日 共 1 周 数据结构 课程设计任务书一、设计题目、内容及要求1、设计题目：栈的应用算法设计与实现。2、设计内容及要求： （1）实现栈的基本操作，如进栈、出栈、判栈空等。（2）实现栈的三种应用算法：如数制转换、表达式求值、括号匹配、文本编辑等应用。（3）实现栈的应用迷宫求解的应用算法。注：（2）（3）选择其一即可。二、要求的设计成果（课程设计说明书、设计实物、图纸等）1、用C语言或者C+语言进行程序设计，实现算法的功能。注重算法效率，代码要有适当的注释。2、撰写课程设计说明书一份，不少于2000字。课程设计说明书应包括封面、任务书、成绩评定表、正文（设计思路、设计步骤等）、参考文献（资料）等内容。三、进程安排1月8日：进行需求分析，确定算法的主要功能和算法思路；进行详细设计，确定各模块的算法思路；1月9日1月10日：进行编码实现；进行测试调试，完善设计；1月11日：撰写设计说明书，准备答辩；1月12日：答辩。四、主要参考资料 1.严蔚敏，吴伟民.数据结构.清华大学出版社，20072.苏仕华.数据结构课程设计.机械工业出版社，20103.滕国文.数据结构课程设计.清华大学出版社，2010指导教师（签名）：教研室主任（签名）：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，令12为了算法简洁，在表达式的左边和右边虚设一个“#”，这一对“#”表示一个表达式求值完成。“（”=“）”当一对括号相遇时表示括号内已运算完成。“）”和“（”、“#”和“(”、“(”和“#”无法相继出现如果出现则表达式出现语法错误。为实现优先算法，可以使用两个工作栈，一个是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）功能实现开始 创建栈并初始化判断是否栈满栈满 则不能压入栈内 NOYES选择入栈元素个数输入元素入栈成功结束 图（2）入栈流程开始初始化栈S 余数N%n入栈 YES除数N!=0 NO栈S为空 NO 栈顶元素出栈 YES 输出结果结束图(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)选择序号2 图(7)用户自己输入 图(8)选择序号3：用户自己输入一串表达式进行求解:选择4输入起点坐标后 ，可得到路径！6总结(1)通过这次课程设计使我懂得了理论与实际相结合的重要性。我们不仅要牢固的掌握理论知识，更要把所学到的理论与实践相结合。从实践中得出理论，才是真正的知识 ，才能提高自己设计的意义的实际动手能力和独立思考的能力。(2)在此次课程设计当中遇到了很多困难，发现自己原本的很多知识也没有掌握好，通过这次自己动手操作让我学会了很多，以前的很多知识也没有掌握好, 通过自己动手操作让我学会了很多，对以前的知识也加深了印象。当然，这也让我对栈及其基本操作和应用有了更为深刻的了解。本节给出程序运行结果并进行分析、得出相关的结论和下一版本的改进建议。本次实验，我们小组运用了顺序栈的方法来实现栈的设计，在实验初我们紧实现了入栈，出栈，获取栈顶等操作，操作过程不具备人机交互的智能性，程序相对简单。在实验过程中经老师指导，我们对程序进行了修改，使功能更加丰富，增加了工作界面，具有多层次的选择提示，基本上能满足多种数据的输入和输出。设计的内容具有以下优点：1：有可视化的可供选择的界面。2：操作简便和简单。3：功能齐全4：用户可自定义数据个数同时设计存在如下不足：1：代码使用c