《大数据结构 课程设计》表达式求值 实验报告材料Word文档下载推荐.docx
- 文档编号:8646579
- 上传时间:2023-05-12
- 格式:DOCX
- 页数:16
- 大小:87.90KB
《大数据结构 课程设计》表达式求值 实验报告材料Word文档下载推荐.docx
《《大数据结构 课程设计》表达式求值 实验报告材料Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《《大数据结构 课程设计》表达式求值 实验报告材料Word文档下载推荐.docx(16页珍藏版)》请在冰点文库上搜索。
各个函数之间的调用关系
栈的抽象数据类型定义
ADTSqStack{
数据对象:
D={ai|ai∈ElemSet,i=1,2,3……,n,n≥0}
数据关系:
R1={<
ai-1,ai>
|ai-1,ai∈D,i=1,2,3,……,n}
约定其中ai端为栈底,an端为栈顶。
操作集合:
(1)voidInitStack1(SqStack1&
S1);
//声明栈建立函数
(2)voidInitStack2(SqStack2&
S2);
(3)voidevaluate(SqStack1&
S1,SqStack2&
//确定如何入栈函数
(4)voidPush1(SqStack1&
S1,chare);
//声明入栈函数
(5)voidPush2(SqStack2&
S2,floate);
//声明入压栈函数
(6)charGetTop1(SqStack1&
//声明取栈顶元素函数
(7)floatGetTop2(SqStack2&
(8)charPop1(SqStack1&
//声明出栈函数
(9)floatPop2(SqStack2&
(10)charCompare(charm,charn);
//声明比较函数
(11)floatOperate(floata,charrheta,floatb);
//声明运算函数
(12)voidDispStack1(SqStack1&
//从栈底到栈顶依次输出各元素
(13)voidDispStack2(SqStack2&
}ADTSqStack
结构分析:
栈中的数据节点是通过数组来存储的。
因为在C语言中数组是用下标从零开始的,因此我们在调用他们的数据是要特别注意。
指针变量的值要么为空(NULL),不指向任何结点;
要么其值为非空,即它的值是一个结点的存储地址。
注意,当P为空值时,则它不指向任何结点,此时不能通过P来访问结点,否则会引起程序错误。
如果输入的数字不符合题目要求,则会产生错误结果。
算法的时空分析:
时间和空间性能分析:
时间上,对于含n个字符的表达式,无论是对其进行合法性检测还是对其进行入栈出栈操作n次,因此其时间复杂度为O(n)。
空间上,由于是用数组来存储输入的表达式,用栈来存储运算中的数据和运算符,而栈的本质也用到的数组,数组在定义时必须确定其大小。
在不知表达式长度的情况下确定数组的长度确非易事,此时极易造成空间的浪费,因此空间性能不是很好。
四、详细设计
源程序
#include<
iostream>
usingnamespacestd;
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT10
typedefstruct//运算符栈
{
char*base;
char*top;
intstacksize;
}SqStack1;
typedefstruct//运算数栈
float*base;
float*top;
}SqStack2;
voidInitStack1(SqStack1&
voidInitStack2(SqStack2&
voidevaluate(SqStack1&
voidPush1(SqStack1&
voidPush2(SqStack2&
charGetTop1(SqStack1&
floatGetTop2(SqStack2&
charPop1(SqStack1&
floatPop2(SqStack2&
charCompare(charm,charn);
floatOperate(floata,charrheta,floatb);
voidDispStack1(SqStack1&
voidDispStack2(SqStack2&
/*主函数*/
voidmain()
SqStack1S1;
//定义运算符栈
SqStack2S2;
//定义运算数栈
//freopen("
data1.in"
"
r"
stdin);
data1.out"
w"
stdout);
InitStack1(S1);
//调用栈建立函数
InitStack2(S2);
//调用栈建立函数
evaluate(S1,S2);
//调用确定如何入栈函数
cout<
<
"
按任意键结束!
endl;
/*运算符栈函数*/
S1)//构造一个空栈S1
S1.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char));
if(!
S1.base)cout<
存储分配失败!
;
//存储分配失败
S1.top=S1.base;
S1.stacksize=STACK_INIT_SIZE;
S1,chare)//入栈
if(S1.top-S1.base>
=S1.stacksize)//如果栈满,追加存储空间
{
S1.base=(char*)realloc(S1.base,(S1.stacksize+STACKINCREMENT)*sizeof(char));
if(!
S1.base)cout<
else
{
S1.top=S1.base+S1.stacksize;
S1.stacksize=S1.stacksize+STACKINCREMENT;
}
}
*S1.top=e;
S1.top=S1.top+1;
//将元素压入栈中,指针上移
S1)//取栈顶元素
chare;
if(S1.top==S1.base)cout<
\n\t\t\t运算符栈已空!
\n"
elsee=*(S1.top-1);
returne;
S1)//从栈底到栈顶依次输出各元素
chare,*p;
"
else
p=S1.base;
while(p<
S1.top)
e=*p;
p++;
cout<
e;
S1)//出栈
e=*(--S1.top);
/*运算数栈函数*/
S2)//构造一个空栈S2
S2.base=(float*)malloc(STACK_INIT_SIZE*sizeof(float));
S2.base)cout<
S2.top=S2.base;
S2.stacksize=STACK_INIT_SIZE;
S2,floate)//入栈
if(S2.top-S2.base>
=S2.stacksize)//栈满,追加存储空间
S2.base=(float*)realloc(S2.base,(S2.stacksize+STACKINCREMENT)*sizeof(float));
S2.top=S2.base+S2.stacksize;
S2.stacksize=S2.stacksize+STACKINCREMENT;
*S2.top=e;
S2.top=S2.top+1;
//将元素e入栈,指针上移
S2)//从栈底到栈顶依次输出各元素
floate,*p;
if(S2.top==S2.base)cout<
p=S2.base;
S2.top)
S2)//取栈顶元素
floate;
if(S2.top==S2.base)cout<
\n\t\t运算数栈已空!
elsee=*(S2.top-1);
S2)//出栈
e=*(--S2.top);
/*确定如何入栈函数*/
S2)
charc;
floatt,e;
intn=0,i=1,j=0,k=0,l=0;
charch[STACK_INIT_SIZE];
ints=1;
intflag=0,flag2=0;
floatp1,p2;
charch1;
Push1(S1,'
#'
);
//将'
入栈,作为低级运算符
●请输入不含变量的表达式(以#结束!
):
\n"
cin>
>
ch;
c=ch[0];
cout<
\n●对表达式求值的操作过程如下:
<
\n________________________________________________________________________________\n"
步骤\t运算符栈S1\t运算数栈S2\t输入字符\t\t主要操作"
while(c!
='
||GetTop1(S1)!
)
{
i++<
\t"
DispStack1(S1);
cout<
\t\t"
DispStack2(S2);
if(flag==1)
k--;
flag=0;
if(flag2)
k+=flag2;
flag2=0;
for(l=0;
l<
k;
l++)
'
'
for(j=k;
ch[j]!
\0'
j++)
ch[j];
if(ch[k]!
&
flag!
=1){k++;
flag=0;
as:
(c=='
+'
||c=='
-'
*'
/'
('
)'
))
{//输入的字符如果不是运算符号,则继续输入直到输入的是运算符为止,将非运算符转换成浮点数
if(!
.'
)&
n>
=0)
{
e=float(c-48);
n++;
if(n==1)t=e;
elseif(n>
1)t=t*10+e;
c=ch[s++];
}
if(n==-1)
t=t+e/10;
if(c=='
n=-1;
if((c>
0'
c<
9'
)||c=='
flag2++;
gotoas;
if(c<
||c>
Push2(S2,t);
}
\t\tPush2(S2,"
t<
)"
else//输入的是运算符
n=0;
//非运算型数据计数器清零
switch(Compare(GetTop1(S1),c))//比较运算符的优先级
case'
:
//栈顶元素优先级低,则入栈且继续输入
Push1(S1,c);
cout<
\t\tPush1(S1,"
break;
//栈顶元素优先级相等,脱括号并接收下一字符
Pop1(S1);
\t\tPop1(S1)"
//栈顶元素优先级高,则退栈并将运算结果入栈
p1=Pop2(S2);
p2=Pop2(S2);
ch1=Pop1(S1);
Push2(S2,Operate(p2,ch1,p1));
\t\tOperate("
p2<
'
ch1<
p1<
flag=1;
i<
\t'
GetTop2(S2)<
for(j=0;
j<
j++)cout<
#"
RETURN(GETTOP(S2))"
if(S2.top-1==S2.base)//显示表达式最终结果
\n●表达式的结果为:
elsecout<
\n表达式出错!
charCompare(charm,charn)//运算符的优先级比较
if(n=='
||n=='
)//输入符号为"
+"
、"
-"
if(m=='
||m=='
)return'
//栈顶元素为"
("
此时栈顶符号优先级低,返回"
elsereturn'
//否则,栈顶符号优先级高,返回"
elseif(n=='
)//输入的符号为"
*"
/"
此时栈顶符号优先级高,返回"
//否则,栈顶符号优先级低,返回"
)return'
//输入的符号为"
则直接返回"
此时优先级同,返回"
="
else//输入符号为其他
floatOperate(floata,chartheta,floatb)//运算函数
floattmp=0;
if(theta=='
)tmp=a+b;
//从运算符栈取出的符号为"
,则运算数栈的两元素相加,并返回
elseif(theta=='
)tmp=a-b;
,则运算数栈的两元素相减,并返回
)tmp=a*b;
,则运算数栈的两元素相乘,并返回
)//从运算符栈取出的符号为"
,则运算数栈的两元素相除,并返回
if(b==0)cout<
除数不能为0!
elsetmp=a/b;
returntmp;
五、运行与测试
第六章总结与心得
数据结构的研究不仅涉及到计算机硬件的研究,而且和计算机软件的研究有着更密切的关系,无论是编译程序还是操作系统,都涉及到数据元素在存储器中的分配问题。
在研究信息检索时也必须考虑如何组织数据,以便使查找和存取数据元素更为方便。
在课程设计中,应该力求算法简明易懂,而易于转换为上机程序;
如果程序反复多次使用,则应该尽可能选用快速的算法;
如果待解决的问题数据量极大,机器的存储空间较小,则在编写算法时应该考虑如何节省空间。
以后在编写程序时就应该注意到所编写程序的时间复杂度,以及是否运用了良好的算法,而不能只是像以前编写程序时单纯使用C语言的知识,要充分考虑程序的性能,争取编写出更优良的程序来。
让我对数据结构有了更进一步的认识和了解,也让我知道,要想学好它要重在实践,理论与实际应用相结合,提高了自己组织数据及编写大型程序的能力,培养了基本的、良好的程序设计技能力。
通过实际操作,我也发现我的好多不足之处:
(1)用栈的结构来解决表达式的求值,首先要解决的问题是如何将人们习惯书写的表达式转换成计算机容易处理的表达式。
开始有些茫然,后来通过结合课本和同学的帮助完成了该课题。
(2)对一些看似简单的东西掌握不够熟练,比如由于函数的调用参数问题不熟而造成了调试的困难。
对于语法的掌握也欠缺成熟,需要进一步掌握。
(3)栈的结构理解不够清晰,造成了设计程序时理不清头绪,需要对数据结构有更深层次的理解。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 大数据结构 课程设计 大数据结构 课程设计表达式求值 实验报告材料 数据结构 课程设计 表达式 求值 实验 报告 材料