哈工大数据结构线性结构及其应用.doc

哈尔滨工业大学计算机科学与技术学院 实验报告 课程名称：数据结构 课程类型：必修 实验项目名称：线性结构及其应用 实验题目： 线性结构及其应用 设计成绩 报告成绩 指导老师 一、实验目的 二、实验要求及实验环境 三、设计思想（本程序中的用到的所有数据类型的定义，主程序的流程图及各程序模块之间的调用关系） 1．逻辑设计 2．物理设计 四、测试结果 五、系统不足与经验体会 六、附录：源代码（带注释） 一、实验目的 输入中缀表达式保存并显示，之后转换为后缀表达式，并且求出表达式的结果。 二、实验要求及实验环境 实验要求 (1)从键盘输入任意一个语法正确的（中缀）表达式，显示并保存该表达式。 (2)利用栈结构，把上述（中缀）表达式转换成后缀表达式，并显示栈的状态变化过程和所得到的后缀表达式。 (3)利用栈结构，对上述后缀表达式进行求值，并显示栈的状态变化过程和最终结果。 实验环境 Dev-C++软件中运行 Win7系统 三、设计思想 本实验中定义了int 型，char型，struct 型，char *型，struct型 逻辑设计：应用栈后进先出的规律，在转换为后缀表达式时，将操作运算符压入栈中，碰见更高级运算符时栈中元素出栈，继续比较；否则压栈。这样可以完成表达式的转换。 在利用得到的后缀表达式计算结果时，将操作数压栈，遇见符号直接计算，这是后缀表达式的特点。 物理设计：建立一个结构体数组的栈，数组中存放运算符。数组的添加和减少都在数组末尾元素进行。可以视为一个栈。 四、测试结果 样例1. 输入1+2*（3-4/2） 输出为1+2*（3-4/2） -此为保存并输出的中缀表达式 12342/-*+ -此为输出后缀表达式 3 -此为表达式的值 样例2. 输入1+2*3/4-5 输出为1+2*3/4-5 123*4/+5- -3 五、系统不足与经验体会 不足 此程序只能进行整形一位数上的计算，无法实现实数范围内的计算。 程序用的是结构体数组来表示栈的存储结构，数组定义时，定义一段很大的空间，导致空间利用率不高。 经验体会 建立算法框架时如中缀表达式变后缀表达式，后缀表达式的求值时，需要用到很多的函数来搭建。这个可以先放下，先将该算法编好，完成之后再将所需要的函数填补起来。这样可以简化步骤。 算法分模块解决，不把所有算法堆到一个函数里面。这样可以使程序简洁明了，各个函数的分工明确。易于调试差错。 六、附录：源代码（带注释） #includestdio.h #includestdlib.h #define MAX 100 //定义栈中最多有100个元素 /*创建结构体，结构体中含有两个量，一个数组栈，一个指向栈顶元素*/ typedef struct{ int data[MAX]; //定义数组栈 int top; //栈顶标号 }seqstack,*pseqstack; /*创建一个顺序栈，入口无参数，返回一个指向顺序栈的指针*/ pseqstack init_seqstack() { pseqstack s; s=(pseqstack)malloc(sizeof(seqstack)); //申请栈的内存空间 if(s) s-top=-1; //创建新栈时栈顶指针指向-1 return s; } /*判断栈是否为空，返回1表示空，0表示非空*/ int empty_seqstack(pseqstack s) { if(s-top==-1) //判断条件为top指针是否指向-1 return 1; else return 0; } /*入栈：栈顶插入x*/ int push_seqstack(pseqstack s,int x) { if(s-top==MAX-1) return 0; //栈已满，返回0 else { s-top++; //栈顶指针+1，指向将要压栈的x s-data[s-top]=x; return 1; } } /*出栈：入口参数为s,*x。删除栈顶元素，并且保存在*x中*/ int pop_seqstack(ps