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

《哈工大数据结构线性结构及其应用.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、哈尔滨工业大学计算机科学与技术学院实验报告课程名称：数据结构课程类型：必修实验项目名称：线性结构及其应用实验题目：线性结构及其应用设计成绩报告成绩指导老师一、实验目的二、实验要求及实验环境三、设计思想（本程序中的用到的所有数据类型的定义，主程序的流程图及各程序模块之间的调用关系）1．逻辑设计2．物理设计四、测试结果五、系统不足与经验体会六、附录：源代码（带注释）一、实验目的输入中缀表达式保存并显示，之后转换为后缀表达式，并且求出表达式的结果。二、实验要求及实验环境实验要求(1)从键盘输入任意一个

2、语法正确的（中缀）表达式，显示并保存该表达式。(2)利用栈结构，把上述（中缀）表达式转换成后缀表达式，并显示栈的状态变化过程和所得到的后缀表达式。(3)利用栈结构，对上述后缀表达式进行求值，并显示栈的状态变化过程和最终结果。实验环境Dev-C++软件中运行Win7系统三、设计思想本实验中定义了int型，char型，struct型，char*型，struct型结束输出表达式的值输出change函数中得到的表达式，再调用voidresult(char*b)函数计算表达式的值voiddestroy_s

3、eqstack(pseqstack*s)函数结束循环时，在存入字符的char数组后添加’’表示结束，并调用voiddestroy_seqstack(pseqstack*s)函数销毁栈循环中，先调用isnum函数判断是否为数字，是就存入字符串数组中，否则压入栈中。（其中根据运算符的优先级来判断出栈入栈，若有符号出栈，则存入之前存储数字的字符串中，调用intpriority(charop)函数来比较优先级Priority函数调用Isnum函数While循环直至字符串被读完并且栈中数字也被读完pu

4、sh_seqstackk调用调用intpush_seqstack(pseqstacks,intx)函数，将’’压入栈，便于简化Change函数流程调用pseqstack函数init_seqstack()流程图定义变量，定义栈s，并调用pseqstackinit_seqstack()函数初始s化s调用voidchange(char*in,char*post)函数定义字符串数组，并输入字符串，保存在该数组中且显示出来Intmain开始逻辑设计：应用栈后进先出的规律，在转换为后缀表达式时，将操作运

5、算符压入栈中，碰见更高级运算符时栈中元素出栈，继续比较；否则压栈。这样可以完成表达式的转换。在利用得到的后缀表达式计算结果时，将操作数压栈，遇见符号直接计算，这是后缀表达式的特点。物理设计：建立一个结构体数组的栈，数组中存放运算符。数组的添加和减少都在数组末尾元素进行。可以视为一个栈。四、测试结果样例1.输入1+2*（3-4/2）输出为1+2*（3-4/2）->此为保存并输出的中缀表达式12342/-*+->此为输出后缀表达式3->此为表达式的值样例2.输入1+2*3/4-5输出为1+2*3/4

6、-5123*4/+5--3五、系统不足与经验体会不足1.此程序只能进行整形一位数上的计算，无法实现实数范围内的计算。2.程序用的是结构体数组来表示栈的存储结构，数组定义时，定义一段很大的空间，导致空间利用率不高。经验体会1.建立算法框架时如中缀表达式变后缀表达式，后缀表达式的求值时，需要用到很多的函数来搭建。这个可以先放下，先将该算法编好，完成之后再将所需要的函数填补起来。这样可以简化步骤。2.算法分模块解决，不把所有算法堆到一个函数里面。这样可以使程序简洁明了，各个函数的分工明确。易于调试差错

7、。六、附录：源代码（带注释）#include#include#defineMAX100//定义栈中最多有100个元素/*创建结构体，结构体中含有两个量，一个数组栈，一个指向栈顶元素*/typedefstruct{intdata[MAX];//定义数组栈inttop;//栈顶标号}seqstack,*pseqstack;/*创建一个顺序栈，入口无参数，返回一个指向顺序栈的指针*/pseqstackinit_seqstack(){pseqstacks;s=(ps

8、eqstack)malloc(sizeof(seqstack));//申请栈的内存空间if(s)s->top=-1;//创建新栈时栈顶指针指向-1returns;}/*判断栈是否为空，返回1表示空，0表示非空*/intempty_seqstack(pseqstacks){if(s->top==-1)//判断条件为top指针是否指向-1return1;elsereturn0;}/*入栈：栈顶插入x*/intpush_seqstack(pseqstacks,intx){if(s->top==MAX-