数据结构课程设计报告表达式翻译.doc

数据结构课程设计报告 : 表达式翻译 系（院）: 专 业: 班 级: 姓 名: 学 号: 指导教师: 学年学期: ~ 学年 第 学期 年 月 日 设计任务书 课题 名称 设计 目的 通过一周的课程设计，实现问题的方法，达到巩固理论知识、锻炼实践能力、构建合理知识结构的目的。 实验 环境 Windows2000以上操作系统 Visual C++6.0以上编译环境 任务 要求 搜集问题方面的资料； 编写代码，实现； 撰写课程设计报告； 参加答辩； 工作进度计划 序号 起止日期 工 作 内 容 1 2 3 4 指导教师： 年 月 日 注意： 任务书格式参照“任务书范例”执行。 范例中的红色文字应根据你所选择的具体课题，修改为对应的内容。 范例中的其它内容不变。1 需求分析 1 1.1 任务要求 1 1.2 课程设计思想 1 1.3 运行环境 1 2 概要设计 1 2.1 总体功能结构 1 2.2 数据结构设计 2 2.3 程序原理 2 3 详细设计和实现 3 3.1 模块功能 3 3.2 算法原理 4 3.3 流程图 12 4 调试与操作说明 12 总 结 15 致 谢 16 参 考 文 献 17 指导教师评语 18 1 需求分析 1.1 任务要求 本次的课程设计实践周，我做的课题是表达式翻译。此次课程设计的任务是收集一些有关中缀表达式翻译成后缀表达式知识的资料，还有括号匹配方面的资料。编写完整程序，将中缀表达式翻译成后缀表达式。认真主动完成课程设计的要求。有问题及时主动通过各种方式与教师联系沟通。学生要发挥自主学习的能力，充分利用时间，安排好课程设计的时间计划，。课程设计周课程设计的调试上机小时数据结构是一门涉及多门课程的课程，难度较大，需要较好的C语言的程序设计和调试能力，如果学生能够按照要求，从时间和精力上保证完全的投入，相信能够有很大的收获，几分投入几分收获 设计一个顺序栈类SeqStack，作为程序的头文件SeqStack.h。再设计四个函数：栈内优先级函数isp(),栈外优先级函数icp(),表达式检查函数ExpIsCorrect()和表达式转换函数postfix()。 2.2 数据结构设计 利用一个顺序栈可以实现将中缀表达式转换为后缀表达式，也能实现对括号是否匹配进行检测。用一个字符型数组存放从键盘输入的中缀表达式，经运行后由屏幕输出转化后的后缀表达式。 2.3 程序原理 栈（stack）是最常用和最重要的数据结构。局部变量是放在栈中的，表达式的优先级处理也是基于栈来实现的，函数调用时的参数传递和函数值的返回都是由栈来实现的。栈是限制在表的一端进行插入和删除的线性表（即一维数组）。允许插入删除的一端为栈顶，另一固定端为栈底。当表中没有元素时称为空栈。如图2-1所示，栈中有三个元素，进栈的顺序是a、b、c，当需要出栈时其顺序为c、b、a。所以栈又称为后进先出的线性表（Last In First Out）,简称LIFO表。 在日常生活中，有很多后进先出的例子。在程序设计中，常常需要使得与保存数据时相反顺序来使用这些数据，这时就需要用一个栈来实现。 对于栈，常做的基本运算有： （1）栈初始化：Init_Stack(s) 初始条件：栈s不存在 操作结果：构造了一个空栈。 （2）判断栈空：Empty_Stack(s) 初始条件:栈s已存在 操作结果：若栈s为空栈返回为1，否则返回为0. （3）入栈：Push_Stack(s,x) 初始条件：栈s已存在 操作结果：在栈s的顶部插入一个新元素x，x成为新的栈顶元素。栈发生变化。 （4）出栈：Pop_Stack(s) 初始条件：栈s存在且非空 操作结果：栈s的顶部元素从栈中删除，栈中少了一个元素。栈发生变化。 （5）读栈顶元素：Top_Stack(s) 初始条件：栈s存在且非空 操作结果：栈顶元素作为结果返回，栈不变化。 栈可以用顺序表实现，称为顺序栈；也可以用链表实现，称为链栈。顺序栈和链栈的逻辑功能一样。顺序栈必须先开一定大小的内存空间，执行起来简单并且速度快，但可能溢出；链栈的内存空间随用随开，不会溢出；但执行复