数据结构课程设计报告.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心得体会
在这次数据结构设计中遇到了很多实际性的问题，在实际设计中才发现，书本上理论性的东西与在实际运用中的还是有一定的出入的，所以有些问题要不断地更正以前的错误思维。
通过这次设计，我懂得了学习的重要性，了解到理论知识与实践相结合的重要意义，学会了坚持、耐心和努力，这将为自己今后的学习和工作做出了最好的榜样。
我觉得作为一名计科专业的学生，这次课程设计是很有意义的。
更重要的是如何把自己平时所学的东西应用到实际中。
虽然自己对于这门课懂的并不多，很多基础的东西都还没有很好的掌握，觉得很难，也没有很有效的办法通过自身去理解，但是靠着学习，渐渐对这门课逐渐产生了些许的兴趣，自己开始主动学习并逐步从基础慢慢开始弄懂它。
升级会员 