数据结构上机实验报告文档格式.docx
《数据结构上机实验报告文档格式.docx》由会员分享,可在线阅读,更多相关《数据结构上机实验报告文档格式.docx(27页珍藏版)》请在冰点文库上搜索。
判断字符是否是运算符,运算符即返回1。
Precede(c1,c2)
初始条件:
c1,c2为运算符。
操作结果:
判断运算符优先权,返回优先权高的。
Operate(a,op,b)
a,b为整数,op为运算符。
a与b进行运算,op为运算符,返回其值。
EvaluateExpression()
输入表达式合法。
返回表达式的最终结果。
}
1.栈定义及栈函数:
用结构体定义栈,并实现对栈的以下操作:
构造栈、取栈顶元素、入栈、出栈
2.运算符优先级比较,返回优先级高的:
算符间的优先关系如下:
+
-
*
/
(
)
#
>
<
=
表1
3.主要操作函数。
算法概要流程图:
各函数具体定义见附1程序清单。
3.实验总结
这次实验的目的主要是在表达式求值中应用栈这种线性数据结构。
DOS框实现实验操作虽然更加本质,但是却不利于与用户,尤其是非编程人员的交互,因此我设计了简单的人机交互对话框,显得更加人性化。
实验结果还有许多可以改进之处,例如使程序可以接受矩阵并作一些运算,对话框界面也有必要做进一步的功能添加。
4.附1:
程序清单
(实验结果与实验程序已分享到网址
#include<
iostream>
usingnamespacestd;
#defineOK1
#defineERROR0
#defineOVERFLOW-1
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT10
typedefintStatus;
typedefstruct
{
double*base;
double*top;
intstacksize;
}SqStack1;
char*base;
char*top;
}SqStack2;
StatusInitStack1(SqStack1&
S.base=(double*)malloc(STACK_INIT_SIZE*sizeof(double));
if(!
S.base)exit(OVERFLOW);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
returnOK;
}//InitStack1
StatusInitStack2(SqStack2&
S.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char));
}//InitStack2
StatusGetTop1(SqStack1S,double&
e)
//若栈不空,则用e返回S的栈顶元素,并返回OK;
否则返回ERROR
if(S.top==S.base)returnERROR;
e=*(S.top-1);
//返回栈顶元素
}//GetTop1
charGetTop2(SqStack2S)
if(S.top==S.base)
{
//cout<
"
aaa"
;
returnERROR;
chare=*(S.top-1);
e<
ww"
endl;
returne;
}//GetTop2
StatusPush1(SqStack1&
S,doublee)
//插入元素e为新的栈顶元素
xinshuis"
if(S.top-S.base>
=S.stacksize)//栈满,追加存储空间
{
S.base=(double*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(float));
S.base)returnERROR;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}//if
*S.top++=e;
}//Push1
StatusPush2(SqStack2&
S,chare)
S.base=(char*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char));
}//Push2
StatusPop1(SqStack1&
S,double&
//若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;
if(S.top==S.base){//cout<
aaaa"
}
e=*--S.top;
thisis"
}//Pop1
StatusPop2(SqStack2&
S,char&
}//Pop2
StatusIn(charch)//判断字符是否是运算符,运算符即返回1
return(ch=='
+'
||ch=='
-'
*'
/'
('
)'
#'
);
charPrecede(charch1,charch2)
inti=0,j=0;
staticchararray[49]={
'
'
'
'
='
!
};
switch(ch1)
//i为下面array的横标
case'
:
i=0;
break;
i=1;
i=2;
i=3;
i=4;
i=5;
i=6;
switch(ch2)
//j为下面array的纵标
j=0;
j=1;
j=2;
j=3;
j=4;
j=5;
j=6;
return(array[7*i+j]);
//返回运算符
doubleOperate(doublea,chartheta,doubleb)
switch(theta)
return(a+b);
return(a-b);
return(a*b);
return(a/b);
default:
cout<
输入错误!
returnERROR;
StatusEvaluateExpression()
//算术表达式求值的算符优先算法。
设OPTR和OPND分别为运算符栈和运算数栈,
//OP为运算符集合
SqStack1OPND;
SqStack2OPTR;
charc,x,theta,y,d;
doublea=0,b=0,k=0,z=0;
InitStack1(OPND);
InitStack2(OPTR);
Push2(OPTR,'
请输入您要求解的表达式并以“#”结尾:
y=GetTop2(OPTR);
c=getchar();
//printf("
字符是%c\n"
c);
while(c!
||GetTop2(OPTR)!
if(!
In(c))
{
doubled1=0,d2=1,e=0;
d1=0;
while(c>
0'
&
c<
9'
{
c-='
d1=d1*10+c;
e=d1;
c=getchar();
}//while
if(c=='
.'
c=getchar();
while(c>
{
d2/=10;
c-='
e+=d2*c;
c=getchar();
}//while
}//if
Push1(OPND,e);
}
else
d=Precede(y,c);
switch(d){
case'
//栈顶元素优先权低
Push2(OPTR,c);
break;
//脱括号并接收下一字符
Pop2(OPTR,x);
//退栈并将运算结果入栈
Pop2(OPTR,theta);
Pop1(OPND,b);
Pop1(OPND,a);
Push1(OPND,Operate(a,theta,b));
cout<
请输入正确的表达式:
}//switch
}//while
GetTop1(OPND,k);
表达式结果为:
"
k<
}//EvaluateExpression
intmain()
EvaluateExpression();
//system("
pause"
return0;
5.附2:
运行结果
分别对实验简介中的三个式子进行结果检验
(一)DOS框:
(二)界面优化(MFC):
上机实验二
对用户指定的.htm文件,将文件中的所有TAG及TAG中所包含的内容全部去掉。
对简单的个人网页《qingtianzhe的个人主页》与下载的西安交通大学数学与统计学院首页(http:
//202.117.3.94/sxtjxy/index.jsp).htm文件做测试,其中《qingtianzhe的个人主页》内容如下:
doctypehtml>
html>
head>
style>
a{text-decoration:
none;
color:
#FFF;
font-size:
16px;
font-family:
微软雅黑"
position:
relative;
float:
left;
display:
block;
.nav{background-color:
#000;
overflow:
hidden;
height:
50px;
a:
hover{border-bottom:
5pxsolid#09F;
18px;
迷你简菱心"
.navbox{width:
610px;
margin:
auto;
.navboxa{margin:
15px20px;
padding-bottom:
12px;
/style>
metacharset="
utf-8"
title>
qingtianzhe的个人主页...<
/title>
/head>
body>
marquee>
center>
h1>
qingtianzhe的个人主页...<
/h1>
/center>
/marquee>
divclass="
nav"
<
navbox"
ahref="
base.html"
基<
my>
本信息<
/a>
zuopin.html"
作品<
xingqu.html"
兴趣爱好<
zuji.html"
足迹<
xuexiaoshenghuo.html"
学习生活<
DW制作/index.html"
我的非诚勿扰<
/div>
br>
imgsrc="
images/1.jpg"
width="
520"
height="
320"
/body>
/html>
为实现上述程序功能,我们利用栈的数据结构,首先新建一个字符型栈,依次读入目标.htm文件的字符,当遇到左标签符“<
”时进栈,后面字符继续进栈,当遇到右标签符“>
”时,后面的内容写入新文件new.htm中,循环这个过程,当原文件结束时,得到去除tag符的新文件new.htm。
头文件、栈定义及栈函数、实现读取与写入非tag内容操作的主函数
构造栈、入栈
2.实现读取与写入非tag内容操作的主函数:
这一步借助C++的文件流实现,定义两个文件流,人流与出流,入流读取.htm文件,做完入栈操作到了非tag内容时将字符写入new.htm文件中。
上次实验是对栈的初次计算机程序实现,需要的栈操作也更多,而这次可以说是对栈操作的一次熟练。
需要注意的就是实验之前需要将需要读取的文件放在程序目录下以便读取,结果文件是同样目录下的new.htm,可以用记事本打开查看。
还有一点美中不足的就是,.htm文件通常在开头会包括很多设置性语句,如语句a{text-decoration:
}用来设置字体,当前实现的程序没有考虑这种问题。
与实验一相同,程序的界面化、可交互也是没有完全实现的问题,问题在于edit控件无法显示.htm文件中的中文字符,会显示乱码,而这样做的好处在于可以不用管待读取文件的目录问题,可以在对话框中选择路径。
//输入输出需要
fstream>
//结构体部分
}SqStack;
StatusInitStack(SqStack&
}//InitStack
StatusPush(SqStack&
}//Push
SqStacklabel;
InitStack(label);
charc;
ifstreamin;
in.open("
index.htm"
//待读取文件
if(!
in)
cout<
cannotopenoldfile."
return1;
ofstreamout;
out.open("
new.htm"
//去除tag文件
out)
cannotopennewfile."
in.get(c);
while(in){
while(c=='
){
Push(label,c);
in.get(c);
while(c!
Push(label,c);
in.get(c);
}
if(in){
out.put(c);
in.get(c);
in.close();
out.close();
分别对实验简介中的两个.htm文件做测试:
(一)qingtianzhe的个人主页
qingtianzhe的个人主页...
qingtianzhe的个人主页...
基本信息
作品
兴趣爱好
足迹
学习生活
我的非诚勿扰
如下图:
(二)学院主页:
由于文件较长,只给出部分截图:
去除tag前
去除tag后:
上