山东理工大学计算机学院
课 程 设 计
（数据结构）
计科0503班 班 级
王新政 姓 名
0512105988 学 号
肖爱梅 张艳华 指导教师
二○○七 年 七 月十三日
课程设计任务书及成绩评定
课题名称 长整数四则运算
Ⅰ、题目的目的和要求：
设计中要求综合运用所学知识，上机解决一些与实际应用结合紧密
的、规模较大的问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握数据结构和算法设计技术，掌握分析、解决实际问题的能力。
通过这次设计，要求在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。
Ⅱ、设计进度及完成情况
Ⅲ、主要参考文献及资料
[1] 严蔚敏，吴伟民主编. 《数据结构》（C 语言版）. 清华大学出版社. 2002 [2] 殷人昆等著. 《数据结构》（C++版）. 清华大学出版社. 2001 [3] 金远平著. 《数据结构》（C++描述）. 清华大学出版社. 2005 [4] Frank M.Carrano 等著. 《数据结构与Ｃ++高级教程》. 清华大学出版社. 2004
[5] 严蔚敏, 吴伟民主编. 《数据结构习题集》（C 语言版）. 清华大学出版社. 2002
学科部主任___________（签字）
Ⅳ、成绩评定：
设计成绩： （教师填写）
指导老师： （签字）
二○○七 年 七 月十三日
目 录
第一章 概述………………………………………………………….1 第二章 系统分析…………………………………………………….2 第三章 概要设计…………………………………………………….3 第四章 详细设计与源程序………………………………………….4 第五章 调试过程中的问题及系统测试情况…………………….12 第六章 结束语………………………………………………………13 参考文献…………………………………………………………….14
第一章 概述
课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。《数据结构》是一门重要的专业基础课，是计算机理论和应用的核心基础课程。
数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。
本课程设计是利用栈的相关操作实现对任意长的整数进行加、减、乘、除四则运算。 程序运行可以实现任意长整数的四则运算。例如：
进行加法运算时：
输入-23456789；-76543211；输出-100000000。 输入-99999999；[1**********]00输出[1**********]1。
图1-1长整数四则运算加法
进行乘法运算时：
输入-123456；123456；输出-[1**********]。 输入789456；123456；输出[1**********]。
图1-2长整数四则运算乘法
第二章 系统分析
2.1设计思想
开始建立两个空的栈。一个用来存放长整数运算的运算符。另一个用来存放长整数数字字符。通过调整栈内元素的进出顺序来实现长整数的加、减、乘、除四则运算
2.2主要功能
系统通过建立两个空栈Stack(so)和Stack(sd)用来存放运算符和数据。建立一个函数
Getnumbersize()来获取数字字符的长度。用一个函数Transfer()来将数字字符转换成整数数据。然后利用if 和else 语句实现对从键盘采集来的字符利用栈的后进先出的性质进行判断和进出栈操作。从而实现任意长整数的四则运算。
第三章 概要设计
图3-3整数四则运算流程图
第四章 详细设计与源程序
1详细设计：
系统建立两个空栈Stack(so)和Stack(sd)用前一个存放运算符“+”、“-”、“*”、“/”且程序规定“（”为1，“+”为2，“-”为3，“*”为4，“/”为5，“”为。后一个存放将要进行运算的操作数。当系统运行开始时输出“提示：若有负数输入请用括号括起来”和“Please input formula(format:(1+2)*1.2/4=):”。
用户输入一连串的字符，开始进行键盘采集。当采集完毕时，系统开始判断运算的优先级，若为“（”则将“(”的代码1直接入到栈Stack(so)中，然后将后面的数字字符转换成整数数据入到栈Stack(sd)中。当入栈完毕再次判断数字字符后面的运算符，若是“+”、“-”则直接将2，3入栈到Stack(so)中。如果是“*”或“/”则进行 优先级判断，看“*”（“/”）后面是不是有“（”如果有则将4（5）入到栈 Stack(so)中。如果没有则将前面的整数数据出栈与“*”（“/”）后的数字字符转换成的整数数据进行运算将结果存入定义的变量 t3中然后将t3入到栈Stack(sd)中。等到读入的数据出现“=”时确定入栈完毕。然后按照栈的“后进先出”规则进行出栈逐步进行运算得最后结果。
2源程序如下：
#include #include #include #include #include #define M 40 /*定义堆栈*/ typedef struct{ double data[M]; int top; }Stack;
/*初始化堆栈*/ InitStack(Stack *s) {
s->top=0; }
/*判断栈是否为空*/ int StEmpty(Stack *s)
{if(s->top==0) {
return 1; } else
{
return 0; } }
/*入栈操作*/
StPush(Stack *s,double x) {
if(s->top==M) {
printf("The stack is overflow!");
//此处应该用malloc 函数分配一定的空间给栈 } else {
s->top=s->top+1; s->data[s->top]=x; } }
/*出栈操作*/
double StPop(Stack *s) {
double t;
if(!StEmpty(s)) {
t=s->data[s->top]; s->top=s->top-1; } else {
printf("StPop:The stack is empty!"); t=NULL; }
return t; }
/*获取栈顶元素*/
double StGetTop(Stack *s) {
double t;
if(!StEmpty(s)) {
t=s->data[s->top]; } else
{
printf("StGeTop:The stack is empty!");
t=NULL;
}
return t;
}
/*将数字字符转换成整形*/
int ChrTransferint(char c)
{
int n;
switch(c)
{
case '0': n=0;break;
case '1': n=1;break;
case '2': n=2;break;
case '3': n=3;break;
case '4': n=4;break;
case '5': n=5;break;
case '6': n=6;break;
case '7': n=7;break;
case '8': n=8;break;
case '9': n=9;break;
}
return n;
}
/*获取两个操作符之间数字字符的个数, 返回的是最后一个数字字符的位置*/
int GetNumsize(char str[],int n1)
{
int n2=n1;
while(isdigit(str[n2])||(str[n2])==46)/*isdigit()判断是否数字字符*/
{
n2=n2+1; //为何要加1？？？
}
return n2; //数据长度加1
}
/*判断上个函数中获得的数字字符串中是否包含小数点，并返回它的位置，不包含，返回-1*/
int IsIncludepoint(char str[],int n1,int n2) //n1初始值是0
{
int n3=-1; //不包含小数点
int i;
for(i=n1;i
{
if(str[i]=='.')
{
n3=i;
break;
}
}
return n3;
}
/*将数字字符转换成数值*/
double Transfer(char str[],int n1,int n2,int n3)
{
double data=0;
int i,ct;
if(n3
{
for(i=n2;i>=n1;i--)
{
ct=ChrTransferint(str[i]);
data=data+ct*pow(10,n2-i);/*pow(x,y)计算x 的y 次方的值*/
}
}
//含有小数点
else
{
for(i=n3-1;i>=n1;i--)
{
ct=ChrTransferint(str[i]);
data=data+ct*pow(10,n3-1-i);/*pow(x,y)计算x 的y 次方的值*/
}
for(i=n3+1;i
{
ct=ChrTransferint(str[i]);
data=data+ct*pow(0.1,i-n3);/*pow(x,y)计算x 的y 次方的值*/
}
} //含有小数点的数字字符转换成数字完成
return data;
}
/*主程序*/
main()
{
char str[M],c;
char a;
int n,p1,p2,p3; /*n为字符串长度，p1,p2,p3分别为数字字符起始位置，结束位置，和小数点位置*/
double data; /*存放转换后的数值*/
int i=0;
Stack *so=(Stack *)malloc(sizeof(Stack)); /*存储操作符 '(':1,'+':2,'-':3, '*':4,'/':5 字符'), ＝' 不压栈*/
Stack *sd=(Stack *)malloc(sizeof(Stack)); /*存储操作数*/
InitStack(so);
InitStack(sd); //该栈存放数据
printf("提示：若有负数输入请用括号括起来\n");
printf("Please input formula(format:(1+2)*1.2/4=):\n");
n=0;
while((a=getchar())!='\n') //用a 开始记录输入的数据包括加减运算符。
{
str[n]=a;
n++;
}
while(i
{
c=str[i];
if(c=='(')
{ /*c若是'('直接入栈so ，i++*/ StPush(so,1);
i++;
}
else if(isdigit(c))
{
p1=i; /*c若是数字字符，一并将后面的连续数字字符转换为数值并压栈到sd, 并把i 设为后面的*/
p2=GetNumsize(str,p1);
p3=IsIncludepoint(str,p1,p2-1); /*仅仅是用来找到第一个非数字字符的位置*/
data=Transfer(str,p1,p2-1,p3);
StPush(sd,data);
i=p2;
}
else if(c=='+')
{
StPush(so,2); /*c若是'+'直接入栈so,i++*/
i++;
}
else if(c=='-')
{
StPush(so,3); /*c若是'-' 直接入栈so,i++*/
i++;
else if(c=='*')
{
if(str[i+1]=='(') /*c若是'*'它后面的字符是否为'('，若是直接将'*'压栈so ，*/ {
StPush(so,4);
i++;
}
else
{
double t1,t2,t3; /*若不是，为数字字符, 将后面的连续数字字符一并转换成数值t2,sd 出栈给t1, 将t3=t2*t1压栈到sd*/
t1=StPop(sd); /*操作符'*'不压栈so*/
p1=i+1; //原先p1已经等于第一个数字字符的长度，p1+1则是下一个连续数字字符的开始。
p2=GetNumsize(str,p1);
p3=IsIncludepoint(str,p1,p2-1);
t2=Transfer(str,p1,p2-1,p3);
t3=t1*t2;
StPush(sd,t3);
i=p2;
}
}
else if(c=='/')
{
if(str[i+1]=='(')
{
StPush(so,5);
i++;
}
else
{
double t1,t2,t3;
t1=StPop(sd); /*c是'/'同'*'*/
p1=i+1;
p2=GetNumsize(str,p1);
p3=IsIncludepoint(str,p1,p2-1);
t2=Transfer(str,p1,p2-1,p3);
t3=t1/t2;
StPush(sd,t3);
i=p2;
}
}
else if(c==')')
double t1,t2,t3;
int p;
while((p=StPop(so))!=1&&!StEmpty(so)) /*c若是')', 出栈so, 判断是'+'或'-', 出栈sd 两个操作数，进行加减运算*/
{ /*直到StPop=='('*/
t1=StPop(sd);
t2=StPop(sd);
if(p==2)
{
t3=t2+t1;
StPush(sd,t3);
}
else if(p==3)
{
t3=t2-t1;
StPush(sd,t3);
}
}
if(StGetTop(so)==4) /*然后判断so 栈顶是否为'*'或者'/'*/ {
StPop(so);
t1=StPop(sd); /*为'*'出栈so, 出栈 sd 获得2个操作数，进行乘法操作*/
t2=StPop(sd);
t3=t2*t1;
StPush(sd,t3);
}
else if(StGetTop(so)==5)
{
StPop(so);
t1=StPop(sd); /*为'/'出栈so, 出栈 sd 获得2个操作数，进行除法操作*/
t2=StPop(sd);
t3=t2/t1;
StPush(sd,t3);
}
i++;
}
else if(c=='=')
{
double t1,t2,t3; /*c若是'='，这是so 内只有加减号，出栈so 到p ，sd 到t1,t2*/ int p;
while(!StEmpty(so))
{
t1=StPop(sd);
t2=StPop(sd);
p=StPop(so);
if(p==2)
{
t3=t2+t1; /*p=='+',加法运算，并将结果t3压栈sd*/ StPush(sd,t3);
}
else if(p==3)
{
t3=t2-t1;
StPush(sd,t3); /*p=='-',减法运算，并将结果t3压栈sd*/
}
}
i++;
}
}
if(!StEmpty(so)||StEmpty(sd))
{
printf("Input error,Back!\n"); /*若so 不为空，或者sd 为空，且sd 中只有一个元素, 则输入的式子不对*/
}
else
{
double end;
int i; /*否则，sd 中的那个数据就是最后计算结果，打印输出*/
end=StGetTop(sd);
printf("The value of this formula:\n");
for(i=0;i
{
printf("%c",str[i]);
}
printf("%f\n",end);
}
}
第五章 调试过程中的问题及系统测试情况
1编译时出现的问题：
①出现的错误一般是由粗心造成的，例如：因多重大括号而导致的大括号丢失或过多。偶尔掉落“；”等导致系统调试时出现错误。经系统提示都可找到错误出处并修改成功。
②当输入数据进行测试时。出现过比较重大的错误。如果输入的数为负数非常容易出现数据溢出现象，得不到正确结果，例如：-12+4按照原先的结果应该是-8。结果当运行时结果却是-16。如果输入12-4结果和预期的一样。但是如果第一个数是负数不论后面是什么样的数据和运算符总是得不到预期的结果。经过反复的数据测试最后经过思考决定在输入负数时用括号括起来这样就解决了上面所述问题。当再次输入（-12）+4时能够得到-8。输入35+（-20）也可以得到应得数据15。即使是象-99999999这样很大的整数进行相应的四则运算也可以实现准确无误。本以为问题已经全部解决。但当输入数据48-（-18）时 却又出现了问题。本应该是66，结果却是-30。即使将-18用括号括起来也无济于事。尝试另外一表达式123-（-123）结果却是0。限于现在所学和掌握知识状况暂时无法解释此问题。
图5-1数据溢出实例
2系统测试情况：
系统经过多组数据的测试基本可以实现课程设计要求。例如：
如果输入100010001-100010001=
系统输出0。
如果输入（-99999999）+[1**********]00=
系统输出[1**********]1。
如果输入（-12）*123456=
系统输出-1481472。
图5-2长整数乘法运算
第六章 结束语
经过长整数四则运算的分析、设计，提高了我的分析问题、解决问题的能力。另外通过大量的查阅资料，我拓宽了自己的知识的深度和广度，把自己所学的知识融会贯通到了实际当中去，锻炼了自己的动手能力。同时在程序设计中我也发现了自己的不足，比如：基本功不扎实、想问题的思路有待拓宽、解决实际问题的能力有待提高等缺点。我会以此次课程设计为契机在老师和同学的帮助下改正不足、提高能力。通过这次的课程设计对我以后的学习、工作将有很大帮助！
在两周的课程设计工作中，我不仅得到了肖老师和张老师的指导还得到了同学们的帮助，在课程设计完成之际我向你们道谢。谢谢老师和同学们给我的帮助。
参考文献
[1] 严蔚敏，吴伟民主编. 《数据结构》（C 语言版）. 清华大学出版社. 2002
[2] 殷人昆等著. 《数据结构》（C++版）. 清华大学出版社. 2001
[3] 金远平著. 《数据结构》（C++描述）. 清华大学出版社. 2005
[4] 许卓群等著. 《数据结构与算法》. 高等教育出版社. 2004
[5] Frank M.Carrano 等著. 《数据结构与Ｃ++高级教程》. 清华大学出版社. 2004
[6] 严蔚敏, 吴伟民主编. 《数据结构习题集》（C 语言版）. 清华大学出版社. 2002
[7] 吕军等著.
visualC++与面向对象程序设计教程》. 高等教育出版社.2006
《