数据结构课程设计报告.docx
- 文档编号:11364994
- 上传时间:2023-05-31
- 格式:DOCX
- 页数:19
- 大小:104.14KB
数据结构课程设计报告.docx
《数据结构课程设计报告.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计报告.docx(19页珍藏版)》请在冰点文库上搜索。
数据结构课程设计报告
计算机科学与信息工程学院
数据结构课程设计
设计题目:
简单计算器
专业计算机软件
班级计软2班
小组成员蔡松佐陈吉院王希刘军符锦柏
曾祖滨刘一霖
指导教师张显全
2010年12月25日
数据结构分工情况
组长:
蔡松佐
组员:
曾祖滨、陈吉院、符锦柏、刘军、刘一霖、王希
王希:
负责设计程序的整体框架(定义数据结构,编写主函数)
评分:
90分
符锦柏:
负责编写栈的代码
评分:
95分
蔡松佐:
负责编写计算算术表达式的代码
评分:
95分
陈吉院:
负责编写比较符号优先级的代码
评分:
90分
曾祖滨:
负责将所有代码整合成一个完整的程序
评分:
88分
刘军:
负责写实验报告
评分:
90分
刘一霖:
负责测试程序,看其是否具有良好的健壮性
评分:
88分
简单计算器
一基本功能描述
简单的计算器的功能是对基本的加、减、乘、除、四则运算,可对输入的操作数,包括整数,小数等进行运算。
二设计思路
本程序主要是采用栈的理论知识,主要用到两个结构体栈,一个用来转化表达式,一个用来计算表达式。
区别就在于一个存储字符,一个存储浮点。
首先,用一个字符数组来存储用户输入的中缀表达式。
然后用栈来把这个表达式转化为后缀表达式,转化时要进行符号优先级比较,这里将‘*’‘/’的优先级定为2,‘+’‘-’定为1,括号和‘=’定为0。
具体思想如下:
例如用户输入了1+2*3=,将其存放入一个字符数组中。
先在栈的底部存放一个‘=’号符,用作符号优先级比较。
首先将1存放到另外一个字符数组s1中,再将‘+’号入栈。
入栈的同时与底部的‘=’比较优先级,‘+’的优先级高于‘=’,所以不出栈,之后将2存放入s2中,然后再将‘*’入栈,入栈的同时与‘+’比较符号优先级,‘*’比‘+’高,所以不出栈。
再将3存入s2中。
之后将栈中不是‘=’的运算符都弹出栈,并依次存入s2中。
所以s2中的表达式为123*+。
之后进行计算,计算时用到浮点栈。
首先将s2中的字符依次入栈,遇到运算符时进行计算。
所以将123入栈后,再将‘*’入栈的同时,将前面两个数字进行运算,算出结果为6并存入栈中,之后再将‘+’入栈,再与1进行运算,结果即为7,然后输出结果。
三概要设计
1,子函数功能
structStack{……}
用来转化表达式的机构体栈。
StructFStack{……}
用来计算表达式的结构体栈
voidInitStack(Stack&s)
初始化结构体栈
voidInitFStack(FStack&s)
初始化结构体栈
charGetTop(Stacks)
获取栈顶数据
voidIncrementStackSize(Stack&s)
为栈扩充ncrementsize个存储空间
voidIncrementFStackSize(FStack&s)
为栈扩充ncrementsize个存储空间
voidPush(Stack&s,chare)
第一个栈入栈操作
voidPushF(FStack&s,floate)
第二个栈入栈操作
boolEmpty(Stacks)
判断第一个栈是否为空。
boolEmptyF(FStacks)
判断第二个栈是否空
charPop(Stack&s)
表达式出栈
floatPopF(FStack&s)
计算的数据出栈
intPrecede(charop)
确定优先级的函数
voidChange(char*s1,char*s2)
改变两个字符串的储存位置
floatCompute(char*s2)
实现数据的运算
2函数的调用
3测试数据及测试结果
(1)测试1+2+3=6
(2)测试2*4=8
(3)测试3/2=1.5
(4)测试(1+2)*3=9
四程序代码
#include
#include
#include
#include
#include
#include
structStack{//转换表达式
char*elem;
inttop;
intstacksize;
intincrementsize;
};
structFStack{//计算
float*elem;
inttop;
intstacksize;
intincrementsize;
};
voidInitStack(Stack&s)
{
s.elem=newchar[100];
s.top=-1;
s.stacksize=100;
s.incrementsize=10;
}
voidInitFStack(FStack&s)
{
s.elem=newfloat[100];
s.top=-1;
s.stacksize=100;
s.incrementsize=10;
}
charGetTop(Stacks)
{
returns.elem[s.top];
}
voidIncrementStackSize(Stack&s)
{
char*a=newchar[s.stacksize+s.incrementsize];
for(inti=0;i<=s.top;i++)
a[i]=s.elem[i];
delete[]s.elem;
s.elem=a;
s.stacksize+=s.incrementsize;
}
voidIncrementFStackSize(FStack&s)
{
float*a=newfloat[s.stacksize+s.incrementsize];
for(inti=0;i<=s.top;i++)
a[i]=s.elem[i];
delete[]s.elem;
s.elem=a;
s.stacksize+=s.incrementsize;
}
voidPush(Stack&s,chare)
{
if(s.top==(s.stacksize-1))
IncrementStackSize(s);
s.top++;
s.elem[s.top]=e;
}
voidPushF(FStack&s,floate)
{
if(s.top==(s.stacksize-1))
IncrementFStackSize(s);
s.top++;
s.elem[s.top]=e;
}
boolEmpty(Stacks)
{
returns.top==-1;
}
boolEmptyF(FStacks)
{
returns.top==-1;
}
charPop(Stack&s)//表达式出栈
{
returns.elem[s.top--];
}
floatPopF(FStack&s)//计算的数据出栈
{
returns.elem[s.top--];
}
intPrecede(charop)//确定优先级的函数
{
switch(op)
{
case'+':
case'-':
return1;//定义加减运算的优先级为1
case'*':
case'/':
return2;//定义乘除运算的优先级为2
case'(':
case'[':
case'{':
case'=':
default:
return0;//定义在栈中的左括号和栈底字符的优先级为0
}
}
voidChange(char*s1,char*s2)
{
StackR;//定义用于暂存运算符的栈
InitStack(R);
Push(R,'=');//给栈底放入‘='字符,它具有最低优先级0
inti,j;
i=0;//用于指示扫描s1串中字符的位置,初值为0
j=0;//用于指示s2串中待存字符的位置,初值为0
charch=s1[i];
while(ch!
='=')
{
if(ch=='')
{
ch=s1[++i];//对于空格字符不做任何处理
}
//-------------------------------------------------------------
elseif(ch=='(')
{//对于左括号,直接进栈
Push(R,ch);
ch=s1[++i];
}
elseif(ch==')')
{//对于右括号,使括号内的仍停留在栈中的运算符依次出栈并写入到s2中
while(GetTop(R)!
='(')
{
s2[j++]=Pop(R);
}
Pop(R);//删除栈顶的左括号
ch=s1[++i];
}
//-------------------------------------------------
elseif(ch=='[')
{//对于左括号,直接进栈
Push(R,ch);
ch=s1[++i];
}
elseif(ch==']')
{//对于右括号,使括号内的仍停留在栈中的运算符依次
//出栈并写入到s2中
while(GetTop(R)!
='[')
{
s2[j++]=Pop(R);
}
Pop(R);//删除栈顶的左括号
ch=s1[++i];
}
//---------------------------------------------
elseif(ch=='{')
{//对于左括号,直接进栈
Push(R,ch);
ch=s1[++i];
}
elseif(ch=='}')
{//对于右括号,使括号内的仍停留在栈中的运算符依次
//出栈并写入到s2中
while(GetTop(R)!
='{')
{
s2[j++]=Pop(R);
}
Pop(R);//删除栈顶的左括号
ch=s1[++i];
}
//---------------------------------------------------
elseif(ch=='+'||ch=='-'||ch=='*'||ch=='/')
{//对于四则运算符,使暂存在栈中的不低于ch优先级
//的运算符依次出栈并写入到s2中
charw=GetTop(R);
while(Precede(w)>Precede(ch))
{//优先级()函数返回运算符形参的优先级
s2[j++]=w;
Pop(R);
w=GetTop(R);
}
Push(R,ch);
ch=s1[++i];
}
else
{//此处为数字或小数点字符的处理
while(isdigit(ch)||ch=='.')
{
s2[j++]=ch;
ch=s1[++i];
}
s2[j++]='';//被转换后的每个数值后放一个空格
}
}
//---------------------------------------------------------
ch=Pop(R);
while(ch!
='=')
{
s2[j++]=ch;
ch=Pop(R);
}
s2[j++]='=';//加入字符串结束符
s2[j++]='\0';
}
floatCompute(char*s2)
{
FStackS;//用S栈存储操作数和中间计算结果
InitFStack(S);
istrstreamins(s2);//把s2定义为输入字符串流对象ins
charch;//用于输入字符
floatx;//用于输入浮点数
ins>>ch;
while(ch!
='=')
{
switch(ch)
{
case'+':
x=PopF(S)+PopF(S);
break;
case'-':
x=PopF(S);
x=PopF(S)-x;
break;
case'*':
x=PopF(S)*PopF(S);
break;
case'/':
x=PopF(S);
x=PopF(S)/x;
break;
default:
ins.putback(ch);
ins>>x;
}
PushF(S,x);
ins>>ch;
}
if(!
EmptyF(S))
{
x=PopF(S);
if(EmptyF(S))//如果栈中只有一个值那一定是结果
{
returnx;
}
}
}
voidmain()//主程序
{
FStacks;
chara[10];
floatb,c;
charstr1[50],str2[50];//暂时存储表达式
charj='y';
cout<<"***************************欢迎使用本计算器***************************"< haha: while(j=='Y'||j=='y') { inti=0,m=0,n=0,k=0,l=0,q=0,p=0; cout<<"请输入一个以'='字符结束的中缀算术表达式: "< cin.getline(str1,sizeof(str1)); while(str1[i]! ='\0') i++; if(str1[i-1]! ='=') { cout<<"表达式错误..请重新输入.."< gotohaha; } i=0; while(str1[i]! ='\0') { if(str1[i]=='0'&&str1[i-1]=='/') { cout<<"表达式错误..请重新输入.."< gotohaha; } i++; } i=0; while(str1[i]! ='\0') { if(str1[i]=='(') m++; if(str1[i]==')') n++; if(str1[i]=='[') k++; if(str1[i]==']') l++; if(str1[i]=='{') q++; if(str1[i]=='}') p++; i++; } if(m! =n||k! =l||q! =p) { cout<<"表达式错误..请重新输入.."< gotohaha; } Change(str1,str2);//处理结果 cout<<"\n求值结果为: "< cout<<"是否继续: (Y/N)"< cin>>j; cin.getline(str1,2); } cout< } 五课程设计总结 1收获 通过这次课程设计,更进一步了解了栈的原理和应用,同时也锻炼了数据结构在实际中的熟练运用。 2心得体会 在这次数据结构设计中遇到了很多实际性的问题,在实际设计中才发现,书本上理论性的东西与在实际运用中的还是有一定的出入的,所以有些问题要不断地更正以前的错误思维。 通过这次设计,我懂得了学习的重要性,了解到理论知识与实践相结合的重要意义,学会了坚持、耐心和努力,这将为自己今后的学习和工作做出了最好的榜样。 我觉得作为一名计科专业的学生,这次课程设计是很有意义的。 更重要的是如何把自己平时所学的东西应用到实际中。 虽然自己对于这门课懂的并不多,很多基础的东西都还没有很好的掌握,觉得很难,也没有很有效的办法通过自身去理解,但是靠着学习,渐渐对这门课逐渐产生了些许的兴趣,自己开始主动学习并逐步从基础慢慢开始弄懂它。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 报告