1表达式求值
1.表达式求值
[问题描述]
一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。
[基本要求]
（1）从键盘读入一个合法的算术表达式，输出正确的结果。
（2）显示输入序列和栈的变化过程。
[选作内容]
（1）扩充运算符集合。
（2）引入变量操作数。
（3）操作数类型扩充到实数。
2.停车场管理
[问题描述]
设停车场是一个可停放n辆车的狭长通道，且只有一个大门可供汽车进出。在停车场内，汽车按到达的先后次序，由北向南依次排列（假设大门在最南端）。若车场内已停满n辆车，则后来的汽车需在门外的便道上等候，当有车开走时，便道上的第一辆车即可开入。当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门后，其它车辆再按原次序返回车场。每辆车离开停车场时，应按其停留时间的长短交费（在便道上停留的时间不收费）。
[基本要求]
（1）要求以顺序栈模拟停车场，以链队列模拟便道。
（2）从终端读入汽车到达或离去的数据，每组数据包括三项：①是“到达”还是“离去”；②汽车牌照号码；③“到达”或“离去”的时刻。与每组输入信息相应的输出信息为：如果是到达的车辆，则输出其在停车场中或便道上的位置；如果是离去的车辆，则输出其在停车场中停留的时间和应交的费用
3\课程设计模板--交通咨询
《数据结构》课程设计报告
源程序下载
题目：全国交通咨询日期：2003.12.6
年级：2001班级：3班
姓名：陈勇学号：200131832
一．实习目的
通过实习，了解并初步掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及
操作方法，为进一步的应用开发打好基础。
二．问题描述
设计、实现一个全国大城市间的交通咨询程序，为旅客提供三种最优决策方案：（1）时间最短（2）费用最小（3）中转次数最少。
三．需求分析
该程序所做的工作的是模拟全国交通咨询，为旅客提供三种最优决策的交通咨询。此程序规定：
（1）在程序中输入城市名称时，需输入10个字母以内的字母串；输入列车或飞机编号时需输入一个整型数据；输入列车或飞机的费用时需输入一个实型数
据；输入列车或飞机开始时间和到达时间时均需输入两个整型数据（以hh：
mm的形式）；在选择功能时，应输入与所选功能对应的一个整型数据。
（2）程序的输出信息主要是：最快需要多少时间才能到达，或最少需要多少旅费才能到达，或最少需要多少次中转到达，并详细说明依次于何时乘坐哪一趟
列车或哪一次班机到何地。
（3）程序的功能包括：提供对城市信息的编辑，提供列车时刻表和飞机航班表的编辑，提供三种最优决策：最快到达、最省钱到达、最少中转次数到达。
四．概要设计
系统用到的抽象数据类型定义：
1．ADT Graph{
数据对象V：一个集合，该集合中的所有元素具有相同的特性
数据关系R：R={VR}
VR={
基本操作：
（1）initgraph(&G)；
（2）CreateGraph(&G)；
（3）EnterVertex(&G)；
（4）DeleteVertex(&G)；
（5）EnterplaneArc(&G)；
（6）DeleteplanArc(&G)；
（7）EntertrainArc(&G)；
（8）DeletetrainArc(&G)；
}ADT Graph
2．ADT LinkQueue{
数据元素：可以是任意类型的数据，但必须属于同一个数据对象
关系：队列中数据元素之间是线性关系。
基本操作：
（1）InitQueue(&Q)；
（2）IsEmpty(&Q)；
（3）EnterQueue(&Q,x)；
（4）DeleteQueue(&Q,&y)；
}ADT LinkQueue
3．ADT TimeTree{
数据对象D：一个集合，该集合中的所有元素具有相同的特性
数据关系R：若D为空，则为空树。若D中仅含有一个数据元素，则R为空集，
否则R={H}，H为如下二元关系：
（1）在D中存在唯一的称为根的数据元素root，它在关系
H中没有前驱
（2）除root以外，D中每个结点在关系H下有且仅有一个
前驱。
基本操作：
（1）CreateTimeTree(p,i,j,&Q,infolist arcs)；
（2）CopyTimeTree(p,q)；
（3）VisitTimeTree(p)；
}ADT TimeTree
系统中子程序及功能要求：
1．Administer(ALGraph *G)：提供管理员管理城市交通系统的界面，通过该子程
序可调用其他管理交通系统的子程序。
2．initgraph(ALGraph *G)：初始化交通系统的子程序
3．createcityfile( )：创建城市文件的子程序
4．createplanefile( )：创建航班文件的子程序
5．createtrainfile( )：创建列车时刻表文件的子程序
6．LocateVertex(ALGraph *G,char *v)：提供城市名在城市交通系统中相应的编
号
7．CreateGraph(ALGraph *G)：创建城市交通系统
8．cityedit(ALGraph *G)：提供城市编辑功能
9．EnterVertex(ALGraph *G)：提供在城市交通系统中加入城市的功能
10．DeleteVertex(ALGraph *G)：提供在城市交通系统中删除城市的功
能
11．flightedit(ALGraph *G)：提供航班编辑功能
12．EnterplaneArc(ALGraph *G)：提供在城市交通系统中加入航班的功
能
13．DeleteplaneArc(ALGraph *G)：提供在城市交通系统中删除航班的
功能
14：trainedit(ALGraph *G):提供列车车次的编辑功能
15．EntertrainArc(ALGraph *G)：提供在城市交通系统中加入列车车次
的功能
16．DeletetrainArc(ALGraph *G)：提供在城市交通系统中删除列车车
次的功能
17．UserDemand(ALGraph G)：提供用户咨询的界面
18．DemandDispose(int n,ALGraph G)：通过该子程序调用其他咨询子程序
19．InitQueue(LinkQueue *Q)：初始化队列
20．EnterQueue(LinkQueue *Q,int x)：入队操作
21．DeleteQueue(LinkQueue *Q,int *x)：出队操作
22．IsEmpty(LinkQueue *Q)：队列判空操作
23．TransferDispose(int k,infolist(*arcs)[MAX_VERTEX_NUM],
(*arcs)[MAX_VERTEX_NUM] ,ALGraph G,ALGraph G,int v0,int v1)
：提供最少中转次数决策的功能
24．MinExpenditure(infolist arcs,float *expenditure,
float *route)：提供两个城市之间最少费用的功能
25．ExpenditureDispose(int k, infolist (*arcs)[MAX_VERTEX_NUM] ,ALGraph G, int v0,int v1,float *D,int *final)
：提供最少费用决策的功能
26．MinTime(infolist arcs,float *time,float *route)
：提供两个城市之间最短时间的功能
27．TimeTreeDispose(Node *head,infolist
(*arcs)[MAX_VERTEX_NUM])
：提供两个之间相隔一个以上城市的城市间的最短时间的功能
28．CreateTimeTree(TimeTree p,int i,int j,
LinkQueue *Q,infolist(*arcs)[MAX_VERTEX_NUM])：创建时间树
29．CopyTimeTree(TimeTree p,TimeTree q)：复制时间树
30．VisitTimeTree(TimeTree p)：访问时间树
31．DestoryTimeTree(TimeTree p)：销毁时间树
32．TimeDispose(int k,infolist (*arcs)[MAX_VERTEX_NUM],
ALGraphG,int v0,int v1,float *D,int *final)
：提供最少时间决策的功能
33：PrintGraph(ALGraph *G)：显示整个城市交通系统
?各程序模块之间的调用关系（子程序编号见上）：
主函数可调用子程序1，17，33
子程序1可调用子程序2，8，11，14
子程序2可调用子程序3，4，5，7
子程序7，12，13，15，16可调用子程序6
子程序8可调用子程序9，10
子程序11可调用子程序12，13
子程序14可调用子程序15，16
子程序17可调用子程序18
子程序18可调用子程序23，25，32
子程序23可调用子程序19，29，21，22
子程序25可调用子程序24
子程序32可调用子程序26，27
子程序27可调用子程序28，30，31
子程序28可调用子程序29
五．详细设计
?创建交通图算法的伪码描述如下：
int LocateV ertex(ALGaph *G,char *v)/*找出城市名在图中对应结
点位置*/
{
for(k=0;k<图G中的结点个数G->vexnum;k++)
if(第k个结点中的城市名与传过来的城市名相同)
{
j=k;/*记录位置*/
break;
}
}
返回k 的数值；
}
int CreatGraph(ALGraph *G)
{
if(打开城市文件，文件指针返回值为空）
{
输出错误文件信息；
程序返回值为0；
}
while(文件不为空）
{
将文件指针所指的字符串读到城市名数组city[i]中；
i++;
}
关闭文件；
j=0;
while(j<城市个数）
{
将city[i] 中的内容复制到图的结构体的结点数组中;
图的结构体其他项负初值;
j++;
}
G->vexnum=i;
打开航班信息文件"plane.txt";
将文件中的内容以块为单位读到缓冲区数组a中；
关闭文件；]
a的计数变量k=0;
弧的计数变量arc_num=0;
while(k<信息个数)
{
调用函数LocateV ertex(G,a[k].vt)得到起始结点的位置i；
调用函数LocateV ertex(G,a[k].vt)得到起始结点的位置j；
q=G->vertices[i].planfirstarc;
m=0;
while(q!=NULL)
{
if( 弧q中的邻接顶点与j相等）
{
将数组a[i] 中的内容都复制到弧q中；
m=1;
break;
}
q=q->nextarc;
if(m=0);
{
开辟一个弧结点；
将数组a[i]中的内容都复制到新的弧结点中；
将弧结点连接到适当的位置中去；
arc_num++;
}
k++;
}
G->planarcnum=arc_num;
打开列车信息文件"plane.txt";
将文件中的内容以块为单位读到缓冲区数组a中；
关闭文件；]
a的计数变量k=0;
弧的计数变量arc_num=0;
while(k<信息个数)
{
调用函数LocateV ertex(G,a[k].vt)得到起始结点的位置i；
调用函数LocateV ertex(G,a[k].vt)得到起始结点的位置j；
q=G->vertices[i].trainfirstarc;
m=0;
while(q!=NULL)
{
if( 弧q中的邻接顶点与j相等）
{
将数组a[i] 中的内容都复制到弧q中；
m=1;
break;
}
q=q->nextarc;
if(m=0);
{
开辟一个弧结点；
将数组a[i]中的内容都复制到新的弧结点中；
将弧结点连接到适当的位置中去；
arc_num++;
}
k++;
}
G->trainarcnum=arc_num;
返回；
}
创建航班算法的伪码描述如下：
creatplanefile()
{while(flag) /*flag为标志位,初值为1*/
{ 提示“输入航班信息”；
输入航班code;
输入航班的出发城市vt;
输入航班的到达城市vh;
输入机票价格money;
输入航班的出发时间bt;
输入航班的到达时间at;
a.[count].co=code; /* a 为程序头部定义的结构体*/
strcpy(a.[count].vt,vt);
strcpy(a.[count].vh,vh);
a.[count].bt=bt;
a.[count].at=at;
a.[count].mo=money;
计数值count+1;
提示“是否要继续输入航班信息：”；
scanf(“%d”,&flag);
}
if(航班文件不能以读写形式打开)
提示“无法打开文件”；
将计数值count写入航班车文件；
for(i=0;i if(无法将a[i]写入航班文件) 提示“文件无法写入”； 关闭航班文件； } 删除城市结点算法的伪码描述如下： DeleteV ertex(ALGraph *G) /* G是程序头部定义的结构体*/ { 提示“输入删除城市名”； gets(城市名：v); 提示“是否确定要删除（Y/N）“； c=getchar(); if(c==’Y’||c==’y’) {n=0; /*0是记数标志，控制循环次数*/ while(n<图G表头接点总个数&&图G的存储城市名与v不同) /*G表头结点总个数比实际大1*/ 记数值n+1; if(n = =图G表头结点总个数) 提示“无法找到此城市“； else { i=LocateV ertex(G,v); /*利用G函数找到此城市名所处在G中位置*/ 删除从此结点出发的所有航班弧； 删除从此结点出发的所有列车弧； for(j=i;j<图G表头结点总个数-1；j++) 将G第j个结点的信息依前移1位； 将G第j个结点的信息制空； /*以下是删除所有指向此结点的航班弧*/ for(k=0;k<图G表头记点总个数-1；k++) {p指向图G中k结点的第一条飞机弧； while（p！=NULL） { if（该弧指向的顶点位置（p->adjvex ）>i） {将该弧指向顶点位置-1； q=p； p指向下一条飞机弧； } else if（该弧指向的顶点位置（p->adjvex ）= = i） {if（p指向图G中k结点的第一条飞机弧） { m=p； 将图G中k结点的第二条飞机弧改为第一弧； p指向下一条飞机弧； 释放（m）； } else { 将p的下一条弧赋给q的下一条弧； m=p； p指向下一条飞机弧； 释放（q）； } } else {q=p； p指向下一条飞机弧； } } } /*以下是删除所有指向此结点的列车弧*/ for(k=0;k<图G表头记点总个数-1；k++) {p指向图G中k结点的第一条列车弧； while（p！=NULL） { if（该弧指向的顶点位置（p->adjvex ）>i） {将该弧指向顶点位置-1； q=p； p指向下一条列车弧； } else if（该弧指向的顶点位置（p->adjvex ）==i） {if（p指向图G中k结点的第一条列车弧） { m=p； 将图G中k结点的第二条列车弧改为第一弧； p指向下一条列车弧； 释放（m）； } else { 将p的下一条弧赋给q的下一条弧； m=p； p指向下一条列车弧； 释放（q）； } } else {q=p； p指向下一条列车弧； } } } } 图G表头结点总个数-1； } else return； } ?求城市v0，v1之间的最少费用算法的伪码描述如下： ExpenditureDispose( ) {for(v=0；v<城市个数；v++) {城市v还未求得最少费用； *(D+v)=城市v0到v的最少费用； 将城市v的路径设置为空； if(*(D+v) 将城市v0和v加入到城市v的路径中； } 城市v0到城市v0的最少费用为0； 城市v0设为已求得最少费用； for(i=1；i<城市个数；v++) {m=INFINITY; for(w=0；w<城市个数；w++) if(城市w未求得最少费用) if(*(D+w) {v=w; m=*(D+w); } if(v等于v1) {根据城市v的路径输出从城市v0到城市v1所需经过的城市及路线； 输出最少费用*(D+v1)； 返回； } else {将城市v设为已求得最少费用； for(w=0； if(城市w未求得最少费用并且从城市v到w有路径) {求出从城市v到城市w的最少费用及路线； if(*(D+w)>m+城市v到w的最少费用) {*(D+w)=m+城市v到w的最少费用； 将城市w的路径改成城市v的路径并在最后加入城市w； } } } 输出没有列车或飞机从城市v0到v1； } ?最少中转次数算法的伪码描述如下： 求城市v0到城市v1的最少中转次数 TransferDispose( ) {for(v=0；v {城市v设为未访问； 城市v的路径设为空； } 将城市v0设为已访问； 将城市v0入队； while(队列不空) {队首城市v出队； w为与城市v相连的第一个城市； while(w存在) {if(城市w未访问) {将城市w设为已访问； 将城市w的路径改为城市v的路径并在最后加入城市w； if(w等于v1) {根据城市w的路径输出从城市v0到城市v1所需经过的城市及路线； 返回； } 将城市w入队； } w等于城市v相连的下一个城市； } } 输出没有列车或飞机从城市v0到v1； } 求城市v0，v1之间的最少时间算法的伪码描述如下： TimeDispose( ) {for(v=0；v<城市个数；v++) {城市v还未求得最少时间； *(D+v)=城市v0到v的最少时间； 将城市v的路径设置为空； if(*(D+v) 将城市v0和v加入到城市v的路径中； } 城市v0到城市v0的最少时间为0； 城市v0设为已求得最少时间； for(i=1；i<城市个数；v++) {m=INFINITY; for(w=0；w<城市个数；w++) if(城市w未求得最少时间) if(*(D+w) {v=w; m=*(D+w); } if(v等于v1) {根据城市v的路径输出从城市v0到城市v1所需经过的城市及路线； 输出最少时间v1； 返回； } else {将城市v设为已求得最少时间； for(w=0； if(城市w未求得最少时间并且从城市v到w有路径) {保存城市w原来的路径； 将城市w的路径设为城市v的路径并在最后加入城市w； 利用时间树求出从城市v0城市w的最少时间及路径； if(*(D+w)>从城市v0到城市w的最少时间) *(D+w)=从城市v0到城市w的最少时间； else 将城市w的路径还原； } } } } 输出没有列车或飞机从城市v0到v1； } 六．测试分析 按照附录中的测试数据，得出如下测试、分析结果： 1.操作员管理功能. 1>. 当我们从键盘输入有关图的顶点及弧的信息后,用显示图的函数验证,DOS中显示的 图的信息与从键盘输入的信息相同,表明交通系统可以从键盘正确输入信息. 2>. 我们事先建立了有关图的3 个文本文件(包括city.txt,plan.txt,train.txt),在交通系统程 序中,选择从文本文件输入图的信息后,用显示操作验证,表明文本文件的内容可以正确调入图的结构体中,说明交通系统可以从文本文件中读取信息. 3>. 当从键盘或文本文件初始化交通图后,测试增加或删除城市结点,增加或删除航班或 列车弧,以上各功能都正确. 2. 交通咨询功能. 1>. 火车情况. 1.1>.最少费用. a.两地间无中转且有多辆火车. 北京----→郑州 输出结果为: 旅行路线是: 乘坐NO.27列车车次在13：15 从Beijing 到zhengzhou. 最少旅行费用是78元. 而若选择NO.41 则花费为80 元. 结果正确. b.两地之间无中转达且只有一辆火车. 西安----→武汉 输出结果为: 旅行路线是: 乘坐NO.218列车车次在1：34从xi’an到wuhan. 最少旅行费用是178.00 元. 结果正确. c. 两地之间有中转. 昆明----→北京 输出结果为: 旅行路线是: 乘坐NO.323列车车次在16.：31从kunming到Guangzhou. 乘坐NO.59列车车次在3：39从Guangzhou 到shanghai. 乘坐NO.41列车车次在0：35从shanghai 到zhengzhou. 乘坐NO.27列车车次在13：42 从zhengzhou 到Beijing. 最少旅行费用是462 元. 而若选择昆明---→武汉---→兰州---→北京则花费为506 元. 若选择昆明---→武汉---→西安---→郑州---→北京则花费为472 元. 结果正确. 1.2>最短时间. a. 两地间无中转且有多辆火车. 北京----→郑州 输出结果为: 旅行路线是: 乘坐NO.41列车车次在13：15从Beijing 到zhengzhou. 最少旅行时间是7：57. 结果正确. b.两地之间无中转达且只有一辆火车. 乌鲁木齐----→兰州 输出结果为: 旅行路线是: 乘坐No.371列车车次在0：35从wulumuqi 到lanzhou. 最少旅行时间是10：48. 结果正确. c.两地之间有中转. 广州----→兰州 输出结果为: 旅行路线是: 乘坐NO.59列车车次在3：39从guangzhou到shanghai. 乘坐NO.41列车车次在0：35从shanghai到zhengzhou. 乘坐NO.41列车车次在9.40从zhengzhou到Beijing. 乘坐NO.134列车车次在19.24从Beijing到lanzhou. 最少旅行时间是54：49. 结果正确. 1.3>.最短周转次数. a. 两地可直达且有中转. 昆明---→广州 输出结果为: 旅行路线是: 乘坐NO.323列车车次在16：31从kunming到guangzhou. 最少旅行中转次数是0次. 而若选择昆明---→武汉---→长沙---→兰州则结果为3. 结果正确. b.两地间有多条中转路径. 昆明---→上海 输出结果为: 旅行路线是: 乘坐NO.323列车车次在16：31从kunming 到guangzhou. 乘坐NO.59列车车次在3：39从guangzhou 到shanghai. 最少旅行总转次数是1次. 而若选择昆明---→武汉---→西安---→郑州---→上海则结果为4. 结果正确. 2.飞机情况. 2.1>.两地无直达. 兰州---→武汉 输出结果为: 不存在飞机航班从lanzhou到wuhan. 2.2>.两地无直达. 拉萨---→昆明 a.最少费用: 输出结果为: 乘坐NO.173飞机航班在10：20 从lasa 到kunming. 最少旅行费用是830 元. 结果正确. b.最短时间: 输出结果为: 乘坐NO.173 飞机航班在10：20 从lasa 到kunming. 最少旅行时间是1：25. 结果正确. c.最短中转次数. 输出结果为: 乘坐NO.173 飞机航班在10：20 从lasa 到kunming. 最少旅行中转次数是0次. 结果正确. 2.3>两地可中转. 广州----→北京 a.最少费用: 输出结果为: 乘坐NO.2323飞机航班在10：15 从Guangzhou 到xi’an. 乘坐NO.210 飞机航班在12：35 从xi’an 到beijing. 最少旅行费用是2250 元. 结果正确. b.最短时间: 输出结果为: 乘坐NO.2323 飞机航班在10：15 从Guangzhou 到xi’an. 乘坐NO.210 飞机航班在12：35 从xi’an 到beijing. 最少旅行时间是4：00. 结果正确. c.最短中转次数. 输出结果为: 乘坐NO.2323 飞机航班在10：15 从Guangzhou 到xi’an. 乘坐NO.210 飞机航班在12：35从xi’an 到beijing. 最少旅行中转次数是1次. 结果正确. 3.打印 打印结果正确; 4.退出 能正确退出 七．使用说明 1．运行程序，首先出现主界面。主界面包括四个选项：选项一：管理员管理界面，选择该项可进行城市交通系统的管理，具体使用说明见说明2；选项二：用户咨 询界面，选择该项可进行最少费用、最少时间、最少中转次数的决策咨询，具体 使用见说明7；选项三：显示城市交通系统程序，选择该项可显示城市交通系统 的所有信息，包括城市、航班和列车车次；选项四：退出程序，选择该项将退出 程序。 2．管理员管理界面包括5个选项：选项一：初始化城市交通系统界面，可进行城市交通系统的初始化，具体使用见说明3；选项二：城市编辑界面，可进行城市的 增加和删除，具体使用见说明4；选项三：航班编辑界面，可进行航班的增加和 删除，具体使用见说明5；选项四：列车车次编辑界面，可进行列车车次的增加 和删除，具体使用见说明6；选项五：返回上一级菜单，可返回主界面。 3．初始化城市交通系统界面包括两个选项：选项一：通过键盘初始化城市交通系统，选择该项后程序将给出输入说明，按输入说明用户需逐 步输入城市、航班、列车车次的信息来对城市交通系统初始化。在输入航班和 列车信息时需注意两点：a.所输入的航班和列车的发车时间均在同一天。b.若 发车时间小于到达时间，则说明列车在同一天到达，若发车时间大于到达时间， 则说明列车在次日达到。飞机航班也是如此；选项二：通过文档初始化城市交 通系统，选择该项可用文档进行初始化，但文档必须存在于程序的同一目录下， 且必须包含CITY，PLANE，TRAIN三个文本文档，否则程序将提示出错。 4．城市编辑界面包括两个选项：选项一：增加城市，可在城市交通系统中加入新的城市，若用户输入的是已有的城市名，程序将提示出错；选项二：删除城市，可 在城市交通系统中删除城市，用户必须输入一个已有的城市名，否则程序提示出 错。 5．航班编辑界面包括两个选项：选项一：增加航班，可在两个城市之间新增航班，选择该项后用户需输入新增航班的编号，起始城市，到达 城市及费用、时间等信息；选项二，删除航班，可删除两个城市间的 一条航班，选择该项后用户需输入要删除航班的编号，起始城市，到 达城市的信息，若航班不存在或编号、城市输入有误，程序将提示错 误。 6．列车车次编辑界面包括两个选项：选项一：增加列车车次，可在两个 城市之间新增列车车次，选择该项后用户需输入新增列车的编号，起 始城市，到达城市及费用、时间等信息；选项二，删除列车车次，可 删除两个城市间的一条列车车次，选择该项后用户需输入要删除车次 的编号，起始城市，到达城市的信息，若列车车次不存在或编号、城 市输入有误，程序将提示错误。 7．用户咨询界面包括四个选项：选项一：最少费用咨询；选项二：最少时间咨询； 选项三：最少中转次数咨询；选项三：返回上级菜单，可返回主界面。选择选项 一、二、三都要求用户输入咨询信息，包括起始城市，到达城市和交通工具。输 入完毕后城市提示用户是否确认，若不确认则要求用户重新输入咨询信息，若确 认则给出用户所需的最优决策信息。 八．附录：测试数据 航班时刻表 竭诚为您提供优质文档/双击可除数据结构表达式求值实验报告 篇一：数据结构实验二——算术表达式求值实验报告 《数据结构与数据库》 实验报告 实验题目算术表达式求值 学院：化学与材料科学学院 专业班级：09级材料科学与工程系pb0920603 姓学 邮名：李维谷号：pb09206285箱： liwg@https://www.wendangku.net/doc/233596696.html,指导教师：贾伯琪 实验时间：20XX年10月10日 一、需要分析 问题描述： 表达式计算是实现程序设计语言的基本问题之一，它的实现是栈的应用的一个典型例子。设计一个程序，演示通过将数学表达式字符串转化为后缀表达式，并通过后缀表达式结合栈的应用实现对算术表达式进行四则混合运算。 问题分析： 在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。 设置运算符栈（字符型）和运算数栈（浮点型）辅助分析算符优先关系。在读入表达式的字符序列的同时完成运算符和运算数的识别处理，然后进行运算数的数值转换在进行四则运算。 在运算之后输出正确运算结果，输入表达式后演示在求值中运算数栈内的栈顶数据变化过程，最后得到运算结果。 算法规定： 输入形式：一个(:数据结构表达式求值实验报告)算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为使实验更完善，允许操作数为实数，操作符为（、）、.（表示小数点）、+、-、*、/、^（表示乘方），用#表示结束。 输出形式：演示表达式运算的中间结果和整个表达式的最终结果，以浮点型输出。 程序功能：对实数内的加减乘除乘方运算能正确的运算出结果，并能正确对错误输入和无定义的运算报错，能连续测试多组数据。 测试数据：正确输入：12*（3.6/3+4^2-1）# 湖南人文科技学院计算机科学技术系 课程设计说明书 课程名称:数据结构 课程代码:408024 题目: 表达式求值 年级/专业/班:08级计算机科学与技术二班 学生姓名: 黄胜李业芝黄自强 黄沅涛姚洋 学号:08408210 08408211 08408212 08408213 08408215 指导教师: 袁辉勇 开题时间: 2009 年12 月21 日 完成时间: 2010 年 1 月 1 日 目录 摘要 (1) 一、引言 (3) 二、设计目的与任务 (3) 1、课程设计目的 (3) 2、课程设计的任务 (4) 三、设计方案 (4) 1、需求分析 (4) 2、概要设计 (4) 3、详细设计 (6) 4、程序清单 (13) 四、调试分析与体会 (17) 五、运行结果 (18) 六、结论 (20) 七、致谢 (21) 八、参考文献 (21) 摘要 在高级语言环境中算术表达上的结果是通过语言环境预设的算法的思想计算出来的，然而高级语言初学者并不了解表达式的计算过程和方法。本文采用算符优先分析和堆栈的方法给出了算术表达式的计算过程。 所以本次课程设计的程序是在Windows系统上为用户解决包括加、减、乘、除以及括号在内的四则混合运算。用户可通过键盘输入四则运算，经过程序运行之后，可以判断出用户所输入的表达式是否正确。如果正确，就给出表达式的值；如果不正确，就提示输入有误。 关键词：四则混合运算；高级语言；栈 Abstract The arithmetic expression result is the algorithm thought which supposes in advance through the language environment calculatesin the higher order language environment,however the higher order language beginner does not understand the expression the computationprocess and the method. This article used the operator first to analyze and the storehouse method has given the arithmetic expression computa-tion process. Therefore, the procedure in this curriculum design is the solution for users on Windows systems, including add, subtract, multiply, divide and brackets, including four hybrid operation. Users can enter via the keyboard 4 operation, after a program is running, you can determine the user entered expression is correct. If correct, it gives the value of the expression; if not correct, it prompted an error. 江西理工大学软件学院计算机类课程实验报告 课程名称：数据结构 班级：11软件会计4班 姓名：黄健 学号：11222122 江西理工大学软件学院 一、目录（中缀表达式求值） 1、目录--------------------------------------------------------------2 2、实验目的--------------------------------------------------------3 3、实验要求--------------------------------------------------------3 4、实验仪器设备与材料-----------------------------------------3 5、实验原理--------------------------------------------------------4 6、实验步骤--------------------------------------------------------5 7、实验原始记录--------------------------------------------------6 8、实验数据分析计算结果--------------------------------------10 9、实验心得体会--------------------------------------------------11 10、思考题----------------------------------------------------------12 《数据结构与数据库》 实验报告 实验题目 算术表达式求值 学院：化学与材料科学学院 专业班级：09级材料科学与工程系PB0920603 姓名：李维谷 学号：PB09206285 邮箱：liwg@https://www.wendangku.net/doc/233596696.html, 指导教师：贾伯琪 实验时间：2010年10月10日 一、需要分析 问题描述： 表达式计算是实现程序设计语言的基本问题之一，它的实现是栈的应用的一个典型例子。设计一个程序，演示通过将数学表达式字符串转化为后缀表达式，并通过后缀表达式结合栈的应用实现对算术表达式进行四则混合运算。 问题分析： 在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。 设置运算符栈（字符型）和运算数栈（浮点型）辅助分析算符优先关系。在读入表达式的字符序列的同时完成运算符和运算数的识别处理，然后进行运算数的数值转换在进行四则运算。 在运算之后输出正确运算结果，输入表达式后演示在求值中运算数栈内的栈顶数据变化过程，最后得到运算结果。 算法规定： 输入形式：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为使实验更完善，允许操作数为实数，操作符为（、）、.（表示小数点）、+、-、*、/、^（表示乘方），用#表示结束。 输出形式：演示表达式运算的中间结果和整个表达式的最终结果，以浮点型输出。 程序功能：对实数内的加减乘除乘方运算能正确的运算出结果，并能正确对错误输入和无定义的运算报错，能连续测试多组数据。 测试数据：正确输入：12*（3.6/3+4^2-1）# 输出结果：194.4 实验表达式求值问题 1.问题描述 表达式是数据运算的基本形式。人们的书写习惯是中缀式，如：11+22*（7-4）/3.中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进行计算。表达式还有后缀表达式（如：11 22 7 4 - * 3 / +）和前缀表达式（+ 11 / * 22 - 7 4 3）。后缀表达式 和前缀表达式中没有括号，给计算带来方便。如后缀表达式计算时按运算符出现的先后进行计算。本设计的主要任务是进行表达式形式的转换及不同形式的表达式计算。 2.数据结构设计 （1）顺序栈类定义：首先应在类中定义成员函数，以此来完成顺序栈的相关操作，如下： class SqStack { private: T *base; //栈底指针 int top; //栈顶 int stacksize; //栈容量public: SqStack(int m); //构建函数 ~SqStack(){delete [] base;top=0;stacksize=0;} //析构函数 void Push(T x); //入栈 T Pop(); //出栈 T GetTop(); //获取栈顶元素 int StackEmpty(); //测栈空 void ClearStack(); //清空栈 void StackTop(); //返回栈顶指针 void StackTranverse(); //显示栈中元素 }; （2）顺序栈类实现：对顺序栈进行初始化，初始化的首要操作就是创建一个空顺序栈。 Step1：申请一组连续的存空间为顺序栈使用： base=new T[m]; i f(base==NULL) { cout<<"栈创建失败，退出!"< 软件技术基础实验报告 实验名称：表达式计算器 系别：通信工程 年级： 班级： 学生学号： 学生姓名： 《数据结构》课程设计报告 题目简易计算表达式的演示 【题目要求】 要求：实现基本表达式计算的功能 输入：数学表达式，表达式由整数和“+”、“-”、“×”、“/”、“（”、“）”组成输出：表达式的值 基本操作：键入表达式，开始计算，计算过程和结果记录在文档中 难点：括号的处理、乘除的优先级高于加减 1．前言 在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。 算法输入：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为简化，规定操作数只能为正整数，操作符为+、-*、/、=，用#表示结束。 算法输出：表达式运算结果。 算法要点：设置运算符栈和运算数栈辅助分析算符优先关系。在读入表达式的字符序列的同时，完成运算符和运算数的识别处理，以及相应运算。 2．概要设计 2.1 数据结构设计 任何一个表达式都是由操作符，运算符和界限符组成的。我们分别用顺序栈来寄存表达式的操作数和运算符。栈是限定于紧仅在表尾进行插入或删除操作的线性表。顺序栈的存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top 指示栈顶元素在顺序栈中的位置，base 为栈底指针，在顺序栈中，它始终指向栈底，即top=base 可作为栈空的标记，每当插入新的栈顶元素时，指针top 增1，删除栈顶元素时，指针top 减1。 2.2 算法设计 为了实现算符优先算法。可以使用两个工作栈。一个称为OPTR ，用以寄存运算符，另一个称做OPND ，用以寄存操作数或运算结果。 1.首先置操作数栈为空栈，表达式起始符”#”为运算符栈的栈底元素； 2.依次读入表达式，若是操作符即进OPND 栈，若是运算符则和OPTR 栈的栈顶运算符比较优先权后作相应的操作，直至整个表达式求值完毕（即OPTR 栈的栈顶元素和当前读入的字符均为”#”）。 2.3 ADT 描述 ADT Stack{ 数据对象：D={ i a |i a ∈ElemSet,i=1,2,…，n, n ≧0} 数据对象：R1={< 1 ,-i i a a >| 1-i a ,D a i ∈,i=2,…，n} HUNAN UNIVERSITY 课程实习报告 题目：四则运算表达式求值 学生姓名： 学生学号： 专业班级： 指导老师： 完成日期： 一、需求分析 四则运算表达式求值，将四则运算表达式用中缀表达式表示，然后转换为后缀表达式，并计算结果。 本程序要求利用二叉树后序遍历来实现表达式的转换，同时可以使用实验2的结果来求解后缀表达式的值。 在字符界面上输入一个中缀表达式，回车表示结束。如果该中缀表达式正确，那么在字符界面上输出其后缀表达式，其中后缀表达式中两相邻操作数之间利用空格隔开；如果不正确，在字符界面上输出表达式错误提示。 测试数据 输入： 21+23*（12-6） 输出： 21 23 12 6 -*+ 二、详细设计 输入和输出的格式 输入 本程序可以将输入的四则运算表达式（中缀表达式）转换为后缀表达式 输出 后缀表达式为：//输出结果的位置 表达式的值为：//输出结果的位置 三、调试分析 本次实验的难点主要是在建立二叉树的问题上。关于如何把中缀表达式存入二叉树中，我参考了网上的一些方法，成功实现了目标，但是却遇到了一个问题，那就是不能处理小数，甚至两位或两位以上的整数。因为如果采用字符数组来存储操作数，运算符合一位整数还可以处理，但对于两位数就就会出问题，最后我改进采用字符串数组来存储操作数，成功解决了问题。 另外在处理输入的非法表达式问题中，我也费了很大功夫，但总体问题不大。 四、测试结果 五、用户使用说明（可选） 1、运行程序时 提示输入四则运算表达式 本程序可以将中缀表达式转化为后缀表达式，并计算结果 请输入四则运算表达式： 输出 后缀表达式为： 表达式的值为： 程序源代码（c++） #include #include 表达式求值课程设计报告 表达式求值 《数据结构》 课程设计报告 题目: 栈的应用:表达式求值 (系): 信息科学与工程学院院 专业班级: 软件工程1102班学生姓名: 学号: 指导教师: 20 13 年 6 月 8 日至20 13 年 6 月 21 日 表达式求值 目录 目录 (2) 1 概述 (1) 1.1 课程设计目的 (1) 1.2 课程设计内容 (1) 2 系统需求分析 ...................................................... 1 2.1 系统目标 (1) 2.2 主体功能 (1) 2.3 开发环境 (1) 3 系统概要设计 .................................................... 2 3.1 系统的功能模块划分 (2) 3.2 系统流程图 (2) 4系统详细设计 ..................................................... 3 5 测试 ............................................................ 6 5.1 测试方案 (6) 5.2 测试结果 (6) 6 小结 ............................................................ 8 参考文献 .......................................................... 9 附录1 源程序清单 (10) 2 数据结构课程设计报告(2012) 表达式求值 1 概述 1.1 课程设计目的 1(要求学生达到熟练掌握C语言的基本知识和技能。 2(了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力。 3(提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。 4(培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一步提 高程序设计水平。 《数据结构（C++版）》课设计报告2012—2013学年第一学期 课程名称数据结构 设计题目表达式求值 专业班级 姓名 学号 指导教师 课程设计题目：表达式求值 一、问题描述 对一个合法的中缀表达式求值。简单起见，假设表达式只包含+，-，*，/等4个双目运算符，且运算符本身不具有二义性，操作数均为一位整数。 二、基本要求 1.正确解释表达式； 2.符合四则运算规则； 3.输出最后的计算结果。 三、概要设计 对中缀表达式求值，通常使用“算符优先算法”。根据四则运算规则，在运算的每一步中，任意两个相继出现的运算符t和c之间的优先关系至多是下面三种关系之一： （1） t的优先级低于c； （2） t的优先级等于c； （3） t的优先级高于c。 为实现算符优先算法，可以使用两个工作栈：一个栈OPTR存放运算符；另一个栈OPND存放操作数，中缀表达式用一个字符串数组存储。 四、详细设计 利用类模板 #include 实验课程名称 专业班级 学生姓名 学号 指导教师 20 至 20 学年第学期第至周 算术表达式求值演示 一、概述 数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。 在这次的课程设计中我选择的题目是算术表达式求值演示。表达式计算是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子。设计一个程序，演示用算符优先法对算术表达式求值的过程。深入了解栈和队列的特性，以便在解决实际问题中灵活运用它们，同时加深对这种结构的理解和认识。 二、系统分析 1．以字符列的形式从终端输入语确的、不含变量的整数表达式。利用已知的算符优先关系，实现对算术四则混合运算表达式的求值，并仿照教科书的例子在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。 2．一般来说，计算机解决一个具体问题时，需要经过几个步骤：首先要从具体问题抽象出一个适当的数学模型，然后设计一个解决此数学模型的算法，最后编出程序，进行测试，调试直至得到想要的答案。对于算术表达式这个程序，主要利用栈，把运算的先后步骤进行分析并实现简单的运算！为实现算符优先算法，可以使用两个栈，一个用以寄存运算符，另一个用以寄存操作数和运算结果。 3．演示程序是以用户于计算机的对话方式执行，这需要一个模块来完成使用者与计算机语言的转化。 4．程序执行时的命令： 本程序为了使用具体，采用菜单式的方式来完成程序的演示，几乎不用输入什么特殊 的命令，只需按提示输入表达式即可。（要注意输入时格式，否者可能会引起一些错误）5. 测试数据。 三、概要设计 一个算术表达式中除了括号、界限符外，还包括运算数据和运算符。由于运算符有优先级别之差，所以一个表达式的运算不可能总是从左至右的循序执行。每次操作的数据或运算符都是最近输入的，这与栈的特性相吻合，故本课程设计借助栈来实现按运算符的优先级完成表达式的求值计算。 算法设计 程序包含三个模块 (1) 主程序模块，其中主函数为 void main{ 输入表达式； 根据要求进行转换并求值； 输出结果； } (2) 表达式求值模块——实现具体求值。 (3) 表达式转换模块——实现转换。 各个函数之间的调用关系 实验报告 课程名称： 程序设计与数据结构 指导老师： ljq 成绩： 实验名称：基于二叉树结构的表达式求值算法 实验类型： 上机 同组学生姓名： 一、实验目的和要求（必填） 三、代码缺陷及修正记录 五、讨论、心得 二、实验内容和代码（必填） 四、实验结果与分析（必填） 一、实验目的和要求 1. 掌握编程工具的使用 2. 掌握二叉树数据结构在计算机上的实现 3. 掌握通过计算机编程解决问题的基本方法 二、实验内容和代码 1．实验内容： ● 编程实现基于二叉树结构的表达式求值算法 ● 表达式包含加减乘除四则运算以及至少一层括弧运算 ● 首先将输入的原表达式转换成二叉树结构，然后采用二叉树的后序递归遍历 方法求得表达式的值 ● 将所有实验内容合并到一个工程，增加交互操作和循环处理（持续） 2．代码 1.头文件expnbitree .h 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include 嘉应学院计算机学院 实验报告 课程名称：数据结构课程设计 开课学期：2017-2018学年第2学期 班级： 指导老师： 实验题目：学生通讯录管理系统 学号： 姓名： 上机时间： (一) 需求分析 1、输入的形式和输入值的范围： 根据题目要求与提示，先选择你要使用的表达式形式（中缀用1，后缀用0），在输入一个中缀表达式，输入数的范围为int型，此时，程序将计算出表达式的结果。 2、输出的形式： 当按照程序要求选择了1或0之后，再输入表达式；如果选择的是1，则程序将自动运算出表达式结果；如果之前选择的是0，则程序将现将中缀表达式转化为后缀表达式并计算出结果。 3、程序所能达到的功能： 本程序能计算出含+、-、*、/、（、）等运算符的简单运算。 4、测试数据： 输入一个表达式，如果你之前选择的是“中缀表达式”，那么输入5*(4-2)#,那么输出结果是10；如果之前选择的是“后缀表达式”，那么输入5*（4-2）#，那么他将先转换成后缀表达式5 4 2 - * #，再输出结果10。 如果输入表达式没有结束标示符#，如5*（4-2），那将不会输出任何结果，或出现错误结果。 (二) 概要设计 为了实现上述操作，应以栈为存储结构。 1．基本操作： （1）. int GetTop(SqStack *s) 初始条件：栈存在； 操作结果：若栈为空，则返回s的栈顶元素；否则返回ERROR。 （2）. void Push(SqStack *s,int e) 初始条件：栈存在； 操作结果：插入e为新的栈顶元素。 （3）. int Pop(SqStack *s) 初始条件：栈存在； 操作结果：若栈不空，则删除之，并返回其值；否则返回REEOR。 （4）.void InitStack(SqStack *s) 初始条件：栈存在； 操作结果：置栈为空。 （5）. int Empty(SqStack *s) 初始条件：栈存在； 操作结果：判定s是否为空栈。 （6）. int Operate(int a,char theta, int b) 初始条件：操作数a和b存在，且theta是+、-、*、/四则运算； 操作结果：返回a与b间theta运算的结果。 （7）. int In(char s,char* TestOp) 初始条件：s为待判断字符，TestOp为已知的算符集合； 操作结果：s为算符集合中的元素则返回1，否则返回0. （8）. int ReturnOpOrd(char op,char* TestOp) 初始条件：op为待确定运算符，TestOp为已知的算符集合； 操作结果：确定运算符类型。 （9）. char precede(char a, char b) 淮海工学院计算机工程学院 课程设计报告 设计名称：数据结构课程设计 选题名称：表达式求值 姓名：学号： 专业班级： 系（院）：计算机工程学院 设计时间： 设计地点：软件工程实验室、教室 指导教师评语： 成绩： 签名： 年月日 1．课程设计目的 1、训练学生灵活使用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。 2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 4.训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。 2．课程设计任务和要求： 任务 根据教材《数据结构-C语言描述》（耿国华主编）和参考书《数据结构题集（C语言版）》（严蔚敏、吴伟民主编）选择课程设计题目，要求通过设计，在数据结构的逻辑特性和物理表示、数据结构的选择使用、算法的设计及其实现等方面加深对课程基本内容的理解和综合运用。 设计题目从任务书所列选题表中选取，每班每题不得超过2人。 学生自选课题 学生原则上可以结合个人爱好自选课题，要求课题有一定的深度和难度，有一定的算法复杂性，能够巩固数据结构课程所学的知识。学生自选课题需在18周前报课程设计指导教师批准方可生效。 要求： 1、在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。前期准备工作完备和否直接影响到后序上机调试工作的效率。在程序设计阶段应尽量利用已有的标准函数，加大代码的重用率。 2、.设计的题目要求达到一定工作量（300行以上代码），并具有一定的深度和难度。 3、程序设计语言推荐使用C/C++，程序书写规范，源程序需加必要的注释; 4、每位同学需提交可独立运行的程序； 5 、每位同学需独立提交设计报告书（每人一份），要求编排格式统一、规范、内容充实，不少于10页（代码不算）； 6、课程设计实践作为培养学生动手能力的一种手段，单独考核。 3．课程设计说明书 高级语言程序设计 《算术表达式求值》 课程设计报告 算术表达式求值 系统可以实现实现对算术四则混合运算表达式求值，并打印求值过程中运算符栈、操作数栈的变化过程。 第二章系统分析 开始运行时界面如下： 你可以输入一个表达式，按E对其进行求值。 第四章系统实现 #include if(ch=='+'||ch=='-') return 2; if(ch=='*'||ch=='/') return 3; if(ch=='(') return -1; return 0; } double result(double num1,char op,double num2)//计算 { if(op=='+') return num1+num2; if(op=='-') return num1-num2; if(op=='*') return num1*num2; if(op=='/') return num1/num2; return 0; } int compute(char str[]) { double num=0; int i=0,j=1,k=1; numTop=opTop=0; while(str[i]!='\0'||opTop>0) { if(str[i]>='0'&&str[i]<='9') num=num*10+str[i]-'0'; else if( k==1&&str[i]=='-'&&(i==0||op(str[i-1])) ) k=-1; else { if(i>0&&!op(str[i-1])&&str[i]!='('&&str[i-1]!=')') 程序设计实训报告— 表达式求值问题 完成者：何炜 班级：计科1501 学号： 完成日期：2016年7月14日星期四 目录 一、题目的内容及要求................................. 错误!未定义书签。 二、需求分析 ................................................ 错误!未定义书签。 三、概要设计 ................................................ 错误!未定义书签。 四、详细设计 ................................................ 错误!未定义书签。 五、源代码 .................................................... 错误!未定义书签。 六、运行结果及分析..................................... 错误!未定义书签。 七、收获及体会............................................. 错误!未定义书签。 一、题目的内容及要求 求解形如（a+b)*((c+d)*e+f*h*g)的简单算术表达式的求值问题。这种表达式只包括加、减、乘、除4种运算符。 为了实现表达式求值，可以首先读入原表达式（包括括号）并创建对应二叉树，其次对二叉树进行前序遍历、中序遍历、后续遍历（非递归），并输出逆波兰表达式，最后求解原表达式的值，同时对非法表达式格式能予以判断。 用二叉树的结构来存储表达式，后续遍历二叉树即可得到逆波兰表达式 二、需求分析 本程序能解决形如（a+b)*((c+d)*e+f*h*g)并以’#’作为结束标志的简单算术表达式的求值问题。 不仅能够求解出多位浮点数，而且能够对简单的非法表达式进行判断以避免程序异常退出。 三、概要设计 1.用户输入中缀表达式 2.程序将中缀表达式用二叉树的链式存储结构存储下来 3.前序、中序遍历这颗二叉树，输出对应的前缀、中缀表达式 4.后续遍历（非递归）这颗二叉树，并把遍历结果存储在顺序栈内， 并输出后缀表达式 5.对后缀表达式进行求值 清华大学数据结构课程实验报告（20 -20 学年第学期） 报告题目：算术表达式求值 任课老师： 专业： 学号： 姓名： 二0一年月日 摘要：现代科学技术高速发展，各种高科技产品频频问世，而各种技术的基础都离不开基本的表达式求值，它虽然简单，但却是任何复杂系统的基本执行操作。栈是一种重要的线性结构，从数据结构的角度看，它是一种特殊的线性表，具有先入先出的特点。而算符优先法的设计恰巧符合先入先出的思想。故我们基于栈这种数据结构，利用算符优先法，来实现简单算术表达式的求值。 关键字：算符优先法；算术表达式；数据结构；栈 一、课题概述 1、问题描述 一个算术表达式是由运算数、运算符、界限符组成。假设操作数是正整数，运算符只含有加“+”、减“-”、乘“*”、除“/”四种二元运算符，界限符有左括号“（”、右括号“）”和表达式起始、结束符“#”。利用算符优先法对算术表达式求值。 2、设计目的 （1）通过该算法的设计思想，熟悉栈的特点和应用方法； （2）通过对算符优先法对算术表达式求值的算法执行过程的演示，理解在执行相应栈的操作时的变化过程。 （3）通过程序设计，进一步熟悉栈的基本运算函数； （4）通过自己动手实现算法，加强从伪码算法到C语言程序的实现能力。3、基本要求： （1）使用栈的顺序存储表示方式； （2）使用算符优先法； （3）用C语言实现； （4）从键盘输入一个符合要求的算术表达式，输出正确的结果。 4、编程实现平台 Microsoft Visual C++ 6.0 二、设计思路及采取方案 1、设计思路： 为了实现算符优先法，可以使用两个工作栈。一个称做OPTR，用以寄存运 课程设计报告 课程名称数据结构 课题名称中缀算术表达式求值 专业通信工程 班级通信0902 学号 姓名 指导教师 2011 年07 月01 日 湖南工程学院 课程设计任务书 课程名称数据结构 课题中缀算术表达式求值 专业班级通信工程0902 学生姓名 学号 指导老师 审批 任务书下达日期2011 年06 月27日 任务完成日期2011 年07 月01日 设计要求： 1. 课程设计报告规范 （1）需求分析 a.程序的功能。 b.输入输出的要求。 （2）概要设计 a.程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系； 每个模块的功能。 b.课题涉及的数据结构和数据库结构；即要存储什么数据，这些数据是 什么样的结构，它们之间有什么关系等。 （3）详细设计 a.采用C语言定义相关的数据类型。 b．写出各模块的类C码算法。 c.画出各函数的调用关系图、主要函数的流程图。 （4）调试分析以及设计体会 a.测试数据：准备典型的测试数据和测试方案，包括正确的输入及输 出结果和含有错误的输入及输出结果。 b.程序调试中遇到的问题以及解决问题的方法。 c.课程设计过程经验教训、心得体会。 （5）使用说明 用户使用手册：说明如何使用你编写的程序，详细列出每一步的操作步 骤。 （6）书写格式 a.设计报告要求用A4纸打印成册： b.一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行 距为22。 （7）附录 源程序清单（带注释） 2. 考核方式 指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新精神和设计报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出每位同学的课程设计成绩。具体考核标准包含以下几个部分：（1）平时出勤（占10%） （2）系统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占10%） （3）程序能否完整、准确地运行，个人能否独立、熟练地调试程序（占40%）（4）设计报告（占30%） 注意：不得抄袭他人的报告（或给他人抄袭），一旦发现，成绩为零分。 （5）独立完成情况（占10%）。 3 . 课程验收 （1）运行所设计的系统。 （2）回答有关问题。 （3）提交课程设计报告。 （4）提交软盘（源程序、设计报告文档）。 （5）依内容的创新程度，完善程序情况及对程序讲解情况打分。 2 进度安排 第19 周：星期一8：00——12：00 上课 星期一14：30——18：30 上机 星期二14：30——18：30 上机 星期四8：00——12：00 上机 附： 课程设计报告装订顺序：封面、任务书、目录、正文、评分表、附件（A4大小的图纸及程序清单）。 正文的格式:一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。 正文的内容:一、课题的主要功能；二、课题的功能模块的划分（要求画出模块图）；三、主要功能的实现 实验报告 年级班号学号姓名 实验名称：栈的实现及其应用：算术表达式的计算实验日期2016年12月2日 计算机科学与技术系 2016年制 一、实验环境 32位操作系统下的Window平台Microsoft Visual C++ 二、实验目的 掌握栈的实现及使用 三、实验内容 1.实现栈的存储结构 2.实现栈的基本操作的有关算法 3.利用栈解决*算术表达式求值问题 四、数据结构与算法思想描述 顺序读取中缀表达式： 1、当遇到数字时，将数字入数字栈 2、当遇到操作符时，与操作符栈栈顶比较： If(当前操作符优先级大于操作符栈栈顶的优先级) If(非”)”操作符) 将当前操作符进操作符栈; Else While(操作符栈栈顶不等于”(“) 取操作符栈栈顶及数字栈的两个数进行运算，并将结果压入数字栈; Else If(非(“操作符) While(操作符栈栈顶不等于”(“) 取操作符栈栈顶及数字栈的两个数进行运算，并将结果压入数字栈; Continue;(直到当前操作符比栈顶操作符优先级大) Else 将当前操作符进操作符栈; 3、While(操作符栈非空) 操作符栈栈顶及数字栈的两个数进行运算，并将结果压入数字栈; 4、在数字栈取最后结果并输出。 五、程序清单 //10*8^2+16.3+5*(5.2*5+3.01)/4-(-10)+0.1000060+4.00416-40 = 666.666666 //100+(-100)-(-10^2) = 100 //(((2016-2017+(((2015-2014)))))) = 0 //-1+(((((((((1^0))))))))+100%10^2 = 0 #include数据结构表达式求值实验报告
表达式求值算法实现
中缀表达式求值
数据结构实验二——算术表达式求值实验报告
数据结构课程设计_表达式求值问题
数据结构算术表达式求值实验报告
四则运算表达式求值实验报告
后缀表达式求值的算法及代码
表达式求值课程设计报告
表达式求值
《数据结构课程设计》表达式求值实验报告
基于二叉树结构的表达式求值算法
数据结构课程设计-表达式求值问题
表达式求值实验报告
数据结构课程设计算术表达式求值计算器.doc
程序设计实训报告—表达式求值问题
算术表达式求值-数据结构实验报告
数据结构课程设计报告-中缀算术表达式求值
长沙理工大学数据结构栈的实现及应用算术表达式求值实验报告