1、 课程设计 数 独 解 谜 程 序 2015 年 4 月 20 日 设计题目设计题目 学号学号 专业班级专业班级 学生姓名学生姓名 指导教师指导教师 1 目 录 一、使用资料.错误错误! !未定义书签。未定义书签。 二、设计内容. 11 三、详细设计说明 . 12 四、软件使用说明 . 13 五、附录：部分程序清单（带有较详细的注释）. 19 2 一、一、 使用资料使用资料 C+中栈结构建立与操作 什么是栈结构什么是栈结构 栈结构是从数据的运算来分类的，也就是说栈结构具有特殊的运算规则，即：后进先出。 我们可以把栈理解成一个大仓库，放在仓库门口（栈顶）的货物会优先被取出，然后再取出 里面的货物
2、。 而从数据的逻辑结构来看，栈结构起始就是一种线性结构。 如果从数据的存储结构来进一步划分，栈结构包括两类： 顺序栈结构：顺序栈结构： 即使用一组地址连续的内存单元依次保存栈中的数据。 在程序中， 可以定义一个指定大小的 结构数组来作为栈，序号为 0 的元素就是栈低，再定义一个变量 top 保存栈顶的序号即可。 链式栈结构：链式栈结构： 即使用链表的的形式保存栈中各元素的值。链表首部（head 指针所指向元素）为栈顶，链 表尾部（指向地址为 NULL）为栈底。 在栈结构中只能在一端进行操作，该操作端称为栈顶，另一端称为栈底。也就是说，保存和 取出的数据都只能从栈结构的一端进行。从数据的运算角度
3、来分析，栈结构是按照“后进先 出”的原则处理结点数据的。 3 在栈结构中，只有栈顶元素是可以访问的，栈结构的数据运算也是非常简单。一般栈结构的 基本操作只有两个： 入栈（入栈（PushPush）：）：将数据保存到栈顶的操作。进行入栈操作前，先修改栈顶指针，使其向上移 一个元素位置，然后将数据保存到栈顶指针所指的位置。 出栈（出栈（PopPop）：）：将栈顶数据弹出的操作。通过修改栈顶指针，使其指向栈中的下一个元素。 接下来，我们使用 C+语言建立顺序栈，并完成顺序栈结构的基本运算 准备数据准备数据 准备在栈操作中需要用到的变量及数据结构等。 #define MAXLEN 50 struct D
4、ATA string name; int age; ; struct StackType DATA dataMAXLEN+1; int top; ; 4 定义栈结构的长度 MAXLEN，栈结构的数据元素类型 DATA，以及栈结构的数据结构 StackTyp e。在数据结构 StackType 中，data 为数据元素，top 为栈顶的序号。当 top=0 时，表示栈 为空，当 top=MAXLEN 时表示栈满。 数组元素都是充下标 0 开始的， 这里为了讲述和理解方便， 我们从下标 1 开始记录数据结点， 下标 0 的位置不用。 初始化栈结构初始化栈结构 在使用栈结构之前，首先需要创建一个空的
5、顺序栈，也就是初始化顺序栈。顺序栈的初始化 操作如下： （1）按照符号常量 MAXLEN 指定大小申请一片内存空间，用来保存栈中的数据 （2）设置栈顶指针的值为 0，表示一个空栈。 示例代码如下： StackType *STInit() StackType *p; if(p=new StackType) /申请栈空间 p-top=0; /设置栈顶为 0 return p; /返回栈顶指针 5 return NULL; 首先用 new 申请内存，然后设置栈顶为 0，然后返回申请内存的首地址，申请失败返回 NUL L; 判断空栈判断空栈 判断栈结构是否为空，如果是空栈，则表示该栈结构中没有数据，此
6、时可以进行入栈操作， 但是不可以进行出栈操作。 示例代码如下： int STIsEmpty(StackType *s) int t; t=(s-top=0); /通过栈顶的值进行判断 return t; 输入参数 s 为一个指向操作的栈的指针。 根据栈顶指针 top 判断是否为 0， 判断栈是否为空。 判断满栈判断满栈 判断栈结构是否为满。如果是满栈，则表示该栈结构中没有多余的空间来保存额外数据。此 时不可以进行入栈操作，但是可以进行进栈操作。 示例代码如下： 6 int STIsFull(StackType *s) int t; t=(s-top=MAXLEN); return t; 输入参数 s 为一个指向操作的栈的指针。根据栈顶指针 top 判断是否和 MAXLEN 相等，判断 栈是否已满。 清空栈清空栈 清空栈就是栈中所有的数据被清除。 示例代码如下： void STClear(StackType *s) s-top=0; 将栈顶指针 top 设置为 0，表示执行
