大整数计算器
卖房子的人-美的历程
数据结构课程设计报告撰写要求
(一)纸张与页面要求
1.采用国际标准A4型打印纸或复印纸,纵向打印。
2.封页和页面按照下面模板书写(正文为:小四宋体1.5倍行距)。
3.图表及图表标题按照模板中的表示书写。
(二)
课设报告书的内容应包括以下各个部分:(按照以下顺序装订)
1.封页(见课设模版)
2、学术诚信声明,所有学生必须本人签字,否则教师拒绝给予成绩。
2.任务书(学生教师均要签字,信息填写完整)
3.目录
4.正文一般应包括以下内容:
(1)题目介绍和功能要求(或描述)
课程设计任务的详细描述(注意不能直接抄任务书),将内容做更详细的具体的分析与描述;
(2) 系统功能模块结构图
绘制系统功能结构框图及主要模块的功能说明;
(3) 使用的数据结构的描述: 数据结构设计及用法说明;
(4)
涉及到的函数的描述
(5) 主要算法描述( 程序流程图)
(6) 给出程序测试运行的结果
设计多组数据加以描述(包括输入数据和输出结果)
(7) 课程设计的总结及体会
(8) 参考文献
格式要求:[1]作者,等. 书名.出版地:出版社,出版年
5.附录:程序清单
(应带有必要的注释)
沈阳航空航天大学
课 程 设
计 报 告
课程设计名称:数据结构课程设计
课程设计题目:
大整数计算器
院(系):计算机学院
专 业:
班 级:
学 号:
姓 名:
指导教师
说明:结论(优秀、良好、中等、及格、不及格)作为相关教环节考核必要依据;格式不符合
要求;数据不实,不予通过。报告和电子数据必须作为实验现象重复的关键依据。
沈阳航空航天大学课程设计报告
学术诚信声明
本人声明:所呈交的报告(含电子版及数
据文件)是我个人在导师指
导下独立进行设计工作及取得的研究结果。尽我所知,除了文中特别
加以标注或致谢中所罗列的内容以外,报告中不包含其他人己经发表
或撰写过的研究结果,也不包含其它
教育机构使用过的材料。与我一
同工作的同学对本研究所做的任何贡献均己在报告中做了明确的说
明并表示了谢意。报告资料及实验数据若有不实之处,本人愿意接受
本教学环节“不及
格”和“重修或重做”的评分结论并承担相关一切
后果。
本人签名: 日期: 年 月 日
I
沈阳航空航天大学课程设计报告
沈阳航空航天大学
课程设计任务书
课程设计名
学学生姓班24010201
题目名
日起起止日日
1652015
2015
1
1
课设内容和要求
内容
由于整形数据存储位数有限因此引入串的概念将整型数据用字
符串进行存储利
用字符串的一个字符存储大整数的一位数值然后根据四则运算规则对相应位依
进
行运算,同时保存进位,从而实现大整数精确的运算
要求
.以大整数形式从键盘输入操作数
.演算在求值的运算操作中,输入操作数和主要的操作的变化过程
.利用所学知识,设计相应的数据结构
参考资料
[1]严蔚敏,吴伟数据结(语言[M北清华大学出版,2006
[2]吕国算法设计与分[M北清华大学出版,2006
[3]徐宝李.
程序设计语[M]北:机械工业出版,200
教研室审核意见:同意
教研室主任签字:
指导教师(签名) 年 月 日
29 12
2014
日 学生(签名)年 月
31
12
2014
II
沈阳航空航天大学课程设计报告
目 录
1 课程设计内
容
..................................................
..................................................
........ 1
1.1题目介绍 ..................
..................................................
.......................................... 1
1.2功能要求 ...........................
..................................................
................................. 2
2 系统功能模
块 ................................
..................................................
.......................... 3
2.1主模块 .
..................................................
..................................................
............. 3
2.1.1 系统功能结构图
.............................................
3
2.2主要模块功能说明 .......................
..................................................
...................... 3
3 详细设
计 ..................................
..................................................
................................ 5
3.1数据结构描述 ....................................
..................................................
............... 5
3.2 算法流程 ..
..................................................
..................................................
.... 7
4 程序测试及总结 ....................
..................................................
...................................
11
4.1测试、运行 ................................
..................................................
....................... 11
参考文献
..................................................
..................................................
....................
13
附
录(关键部分程序清单) ......................................
............................................
16
III
沈阳航空航天大学课程设计报告
1 课程设计内容
1.1 题目介绍
由于整形数据存储位数有限,因此将整型数据用字
符串进行存储。在大整数计算
器分为四个大模块,分别为大整数加法运算、大整数减法运算、大整数乘法
运算、
大整数除法运算函数模块。由一个主模块所调用。
加法运算功能,从个位开始逐位相
加,超过或达到10则进位,同时将该位计算
结果存到另一个字符串中,直至加完大整数的所有位为止。
减法运算功能,首先调用库函数strcmp判断这两个大整数是否相等,如果相等
则结果为0
,否则用Compare函数判断被减数和减数的大小关系,进而确定结果
为正数还是负数,然后对齐位
依次进行减法,不够减则向前借位,直至求出每一
位减法之后的结果。
乘法运算功能,首先
让乘数的每一位都和被乘数进行乘法运算,两个乘数之积与
进位相加作为当前位乘积,求得当前位的同时
获取进位值,进而实现大整数的乘
法运算。
除法运算功能,类似做减法,基本思想是反复做
减法,从被除数里最多能减去多
少次除数,所求得的次数就是商,剩余不够减的部分则是余数,这样便可
计算出
大整数除法的商和余数。
主函数,主函数是程序的入口,采用模块化设计。通过一定
的入口可以进行加法
运算功能、减法运算功能、乘法运算功能、除法运算功能。
1
沈阳航空航天大学课程设计报告
1.2
功能要求
1.大整数加法:采用数学中列竖式的方法,从个位开始逐位相加,超过或达到<
br>10则进位,同时将该位计算结果存到另一个字符串中,直至加完大整数的所有
位为止。
2.大整数减法:首先调用库函数判断这两个大整数是否相等,如果相等则结果为
0,否则用Compare函数判断被减数和减数的大小关系,进而确定结果为正数还
是负数,然后对齐
位依次进行减法,不够减则向前借位,直至求出每一位减法之
后的结果。
3.
大整数乘法:首先让乘数的每一位都和被乘数进行乘法运算,两个乘数之积与
进位相加作为当前位乘积,
求得当前位的同时获取进位值,进而实现大整数的乘
法运算。
4.大整数除法
:反复做减法,从被除数里最多能减去多少次除数,所求得的次数
就是商,剩余不够减的部分则是余数。
5.其实就是利用算法中的高精度算法进行加减乘除的实现。来实现大整数计算器。
2
沈阳航空航天大学课程设计报告
2 系统功能模块
2.1
主模块
2.1.1
系统功能结构图
设计程序实现两个大整数四则运算,输出这两个大整数的和、差、积、商及
余数,
实现大整数(200位以内的整数)的加、减、乘、除运算。根据需要可以进行如
下操作
:加法、减法、乘法、除法。其功能模块图如图2-1所示。
图2.1 主模块设计图
2.2
数据结构描述
大整数计算器分为四个大
模块,分别为大整数加法运算、大整数减法运算、大整
数乘法运算、大整数除法运算函数模块。
加法运算功能,加法运算功能是将两个字符从个位开始进行逐位相加,然后
3
沈阳航空航天大学课程设计报告
把每一位的相加结果存放到字符串中,并且输出运算结果。其流程图如图3-2所
示。 输入两个相加的字符,然后从个位开始逐位相加,判断两个数相加的结果是否大
于或等于十,如果是
,那么向前一位进一,并将所得结果存放到另一个字符串中,
如果不是,则直接将所得结果存放到另一个
字符串中。当所有结果都存入该字符
串中时,判断是否所有位都进行了加法运算,若是,输出结果,若不
是,重复上
述过程,继续进行运算,直至所有位都进行了加法运算时输出结果。
减法运算功能,减法运算功能是将输入的两个相减的大整数,对齐位依次进行
减法运算,并输出结果。
首先,在输入两个大整数后开始判断他们是否相等,若相等,输出结果为零,结
束运算。若不相
等,开始进行运算结果的正负判断,当被减数大于减数时,结果
为正,否则结果为负。然后,对两个大整
数对齐位依次进行减法,若够减且每一
位都已减完,那么输出运算结果;若不够减,则向前借位依次进行
减法运算,直
到每一位都已减完,输出结果。其功能流程图如图3-3所示。
乘法运算功能
,首先让乘数的每一位都和被乘数进行乘法运算,两个乘数之积与
进位相加作为当前位乘
积,求得当前位的同时获取进位值,进而实现大整数的乘
法运算。
除法运算功能,类似做减
法,基本思想是反复做减法,从被除数里最多能减去多
少次除数,所求得的次数就是商,剩余不够减的部
分则是余数,这样便可计算出
大整数除法的商和余数。
主函数,主函数是程序的入口,采用
模块化设计。通过一定的入口可以进行加法
运算功能、减法运算功能、乘法运算功能、除法运算功能。
4
沈阳航空航天大学课程设计报告
错误!未指定书签。
3 算法描述
3.1
数据结构描述
⑴ 加法运算功能
加法运算功能是将两个字符从个位开始进行逐
位相加,然后把每一位的相加结果
存放到字符串中,并且输出运算结果。
输入两个相加的字
符,然后从个位开始逐位相加,判断两个数相加的结果是否大
于或等于十,如果是,那么向前一位进一,
并将所得结果存放到另一个字符串中,
如果不是,则直接将所得结果存放到另一个字符串中。当所有结果
都存入该字符
串中时,判断是否所有位都进行了加法运算,若是,输出结果,若不是,重复上
述
过程,继续进行运算,直至所有位都进行了加法运算时输出结果。详细代码及
程序见附录中的代码的——
void IntAddition(char *augend, char
*addend,
char *sum)整数加法 模块。流程图见图3.1加法模块
⑵
减法运算功能
减法运算功能是将输入的两个相减的大整数,对齐位依次进行减法运算,并输出
结果。 首先,在输入两个大整数后开始判断他们是否相等,若相等,输出结果为零,结
束运算。若不相等,
开始进行运算结果的正负判断,当被减数大于减数时,结果
为正,否则结果为负。然后,对两个大整数对
齐位依次进行减法,若够减且每一
位都已减完,那么输出运算结果;若不够减,则向前借位依次进行减法
运算,直
到每一位都已减完,输出结果。详细代码及程序见附录中的代码的void
IntSubtration(char *minuend, char *subtrahend,
char *difference)整数
减法 模块。流程图见图3.2减法模块
5
沈阳航空航天大学课程设计报告
错误!未指定书签。
⑶ 乘法运算功能
乘法运算功能是将输入的两个大整数进行乘法运算,并输出结果。
首先,输入两个大整数
,一个为乘数一个为被乘数,让乘数和被乘数的每一位相
乘,并将相乘后所得的结果存放到另一个字符串
中,以此循环下去。
然后,判断两个大整数的每一位是否乘完,若是,则将所得的i个字符串相加,
并输出相加后的结果,其值为两数相乘的乘积,若不是,继续进行以上操作,直
至得到两个大整
数相乘的结果。详细代码及程序见附录中void
IntMultiplication(char
*multiplicand, char *multiplier, char
*product)整数乘模块。流程图见图3..3乘法模块
⑷ 除法运算功能
除法运算功能是将输入的两个大整数进行除法运算,并输出结果。 <
br>输入两个数,其中一个是除数,一个是被除数。用被除数减去除数,若被除数小
于除数,则输出被
除数减除数的个数作为商,剩余不够减的数则为余数,并输出
商和余数。若被除数大于除数,继续循环被
除数减除数的过程,直至被除数小于
除数,输出所得结果。详细代码及程序见附录中void
IntDivision(char
*dividend, char *divisor,
char *quotient, char
*remainder)整数除模块。
流程图见图3.4除法模块
6
沈阳航空航天大学课程设计报告
错误!未指定书签。
3.2
算法流程
1.
加法运算功能
图3.1 加法模块设计图
7
沈阳航空航天大学课程设计报告
错误!未指定书签。
2.减法功能
图3.2减法模块设计图
8
沈阳航空航天大学课程设计报告
错误!未指定书签。
3.乘法功能
乘
法运算功能,首先让乘数的每一位都和被乘数进行乘法运算,两个乘数之积与
进位相加作为当前位乘积,
求得当前位的同时获取进位值,进而实现大整数的乘
法运算。
图3.3乘法模块设计图
9
沈阳航空航天大学课程设计报告
错误!未指定书签。
4.除法功能
除法运算功能,类
似做减法,基本思想是反复做减法,从被除数里最多能减去多
少次除数,所求得的次数就是商,剩余不够
减的部分则是余数,这样便可计算出
大整数除法的商和余数。
图3.4除法模块设计图
10
沈阳航空航天大学课程设计报告
错误!未指定书签。
4
程序测试及总结
4.1
测试、运行 1、一般而言,编写
一个能运行在操作系统上的程序,
都需要一个主函数。主函数意味着建立一个独立进程,且该进程成为了
程序的入
口,对其它各函数进行调用,当然其它被调用函数也可以再去调用更多函数。主
函数既
是程序的入口,又是程序的出口。先输入两个数,选择所需的运算。其功
能实现图如图4-1所示。
主界面图4.1
2、加法运算功能,采用数学中列竖式的方法,从个位(即字符串的最后一个字
符)开始逐位相加,
超过或达到10则进位,同时将该位计算结果存到另一个字
符串中,直至加完大整数的所有位为止。其功
能实现图如图4-2所示。
3、减法运算功能,首先调用库函数strcmp判断这两个大整数是否相等,如
11
沈阳航空航天大学课程设计报告
错误!未指定书签。
果相等则结果为0,否则用Compare函数判断被减数
和减数的大小关系,进而确
定结果为正数还是负数,然后对齐位依次进行减法,不够减则向前借位,直至
求
出每一位减法之后的结果。其功能实现图如图4-3所示。
图4.2加法运行
图4.3减法运算
3、乘法运算功能,首先让乘数的每一位都和被乘数进行乘法运
算,两个乘数之
积与进位相加作为当前位乘积,求得当前位的同时获取进位值,进而实现大整数
的乘法运算。功实现图如图4-4所示
4、除法运算功能,类似做减法,基本思想是反复做减法,从
被除数里最多能减
去多少次除数,所求得的次数就是商,剩余不够减的部分则是余数,这样便可
12
沈阳航空航天大学课程设计报告
错误!未指定书签。
计算出大整数除法的商和余数。其功能实现图如图4-5所示。
图4.4乘法运算实现
图4.5除法运算
13
沈阳航空航天大学课程设计报告
错误!未指定书签。
5、按5退出计算本次计算,按任意键继续运算,按Ctr
l+z退出计算器,其功能
实现图如图4-6所示。
图4.5结束界面
图4.6 0与0运算
14
沈阳航空航天大学课程设计报告
错误!未指定书签。
参考文献
1、谭浩强.C程序设计.北京:清华大学出版社.1999.12
2、滕国文.数据结构课程设计.北京:清华大学出版社.2010.09
苏仕华 等编著. 数据结构课程设计. 北京:机械工业出版社.2005.05
、3
张乃笑.数据结构与算法.电子工业出版社.2004.10
、4
徐孝凯.数据结构课程实验.清华大学出版.2002.7
5、
严蔚敏.数据结构(C语言版). 清华大学出版社.2006
、6
15
沈阳航空航天大学课程设计报告
错误!未指定书签。
附 录(关键部分程序清单)
#include
#include
#include
#define MAX 200
int Compare(const char *a, const char *b);
void IntAddition(char *augend, char *addend,
char *sum);
void IntSubtration(char *minuend,
char *subtrahend, char *difference);
void
IntMultiplication(char *multiplicand, char
*multiplier, char *product);
void
IntDivision(char *dividend, char *divisor, char
*quotient, char *remainder);
int Radix(char
*toStr, char *fromStr);
void
FloatAddition(char *augend, char *addend, char
*sum);
void FloatSubtration(char *minuend,
char *subtrahend, char *difference);
void
FloatMultiplication(char *multiplicand, char
*multiplier, char *product);
void
FloatDivision(char *dividend, char *divisor, char
*quotient, int precision);
void Insert(char
s[], int left, int right);
int IsCycle(char
a[][MAX], int label);
int main(void)
{
int t;int p;
char a[MAX] = {0};
char b[MAX] = {0};
char c[3*MAX] = {0};
char d[MAX] = {0};
異獴尨输入任意值开始计算
Ctrl+z结束计算);
while(scanf(%d,&p)!=EOF)
{
異獴尨请输入两个数a,b:);
scanf(%s %s,&a,&b);
printf(====================选择运算方式=========
===========);
printf(
printf(
printf(
printf(
printf(
tttn1.加法运算n);
tttn2.减法运算n);
tttn3.乘法运算n);
tttn4.除法运算n);
ttttn5.退出n);
printf(==========
========================================n);
puts(a);
puts(b);
16
沈阳航空航天大学课程设计报告
错误!未指定书签。
t=1;
while(t!=5)
{
scanf(%d,&t);
if(t==1)
{
FloatAddition(a, b, c);
異獴尨两者之和:);
puts(c);
}
else
if(t==2)
{
FloatSubtration(a,
b, c);
異獴尨两者之差:);
puts(c);
}
else if (t==3)
{
FloatMultiplication(a, b, c);
異獴尨两者之积:);
puts(c);
}
else
if(t==4)
{
FloatDivision(a, b,
c, MAX);
異獴尨两者之商:);
puts(c);
}
}
system(pause);
}
}
void
FloatAddition(char *augend, char *addend, char
*sum)加法
{
char cAug[MAX] = {0};
char cAdd[MAX] = {0};
char cSum[MAX] = {0};
17
沈阳航空航天大学课程设计报告
错误!未指定书签。
int lenAug, lenAdd,
lenSum;分别存储三个数的小数点后的数字个数
int i, topAug,
topAdd;
去掉小数点,把浮点数转化成整数后存储到新的字符串
lenAug = Radix(cAug, augend);
lenAdd =
Radix(cAdd, addend);
topAug = strlen(cAug);
topAdd = strlen(cAdd);
在小数部分较短的字符串后补零,使得两个数的小数部分长度相等
if (lenAug >
lenAdd)
{
lenSum = lenAug;
for
(i=lenAug-lenAdd; i>0; i--)
cAdd[topAdd++]
= '0';
}
else
{
lenSum =
lenAdd;
for (i=lenAdd-lenAug; i>0; i--)
cAug[topAug++] = '0';
}
cAdd[topAdd++] = '0';
cAug[topAug++] = '0';
执行整数加法运算
IntAddition(cAdd, cAug,
cSum);
i = strlen(cSum) - 1;
while (lenSum > 0 && cSum[i] == '0')去掉小数部分多余的零
{
i--;
lenSum--;
}
cSum[i+2] = '0';
while
(lenSum > 0)在适当位置插入'.'
{
cSum[i+1] =
cSum[i];
i--;
lenSum--;
}
cSum[i+1] = '.';
18
沈阳航空航天大学课程设计报告
错误!未指定书签。
strcpy(sum, cSum);
}
void FloatSubtration(char *minuend, char
*subtrahend, char *difference)减法
{
if
(strcmp(minuend, subtrahend) == 0)
{
strcpy(difference,
return;
}
char cM[MAX] = {0};
char cS[MAX] = {0};
char cD[MAX] = {0};
int lenM, lenS,
lenD;
int i, topM, topS;
lenM = Radix(cM, minuend);
lenS = Radix(cS,
subtrahend);
topM = strlen(cM);
topS =
strlen(cS);
if (lenM > lenS)
{
lenD = lenM;
for (i=lenM-
lenS; i>0; i--)
cS[topS++] = '0';
}
else
{
lenD = lenS;
for (i=lenS-lenM; i>0; i--)
cM[topM++] =
'0';
}
cM[topM++] = '0';
cS[topS++] = '0';
IntSubtration(cM, cS, cD);
i =
strlen(cD) - 1;
while (lenD > 0 && cD[i] ==
'0')
19
沈阳航空航天大学课程设计报告
错误!未指定书签。
{
i--;
lenD--;
}
cD[i+2] = '0';
while (lenD > 0)
{
cD[i+1] = cD[i];
i--;
lenD--;
}
cD[i+1] =
'.';
if (i == -1)
{
cD[0] =
'0';
cD[1] = '.';
cD[2] = '0';
}
strcpy(difference, cD);
}
void FloatMultiplication(char *multiplicand,
char *multiplier, char *product)乘法
{
char cD[MAX] = {0};
char cR[MAX] = {0};
char cP[2*MAX] = {0};
int lenD, lenR,
lenP;
lenD = Radix(cD,
multiplicand);
lenR = Radix(cR, multiplier);
lenP = lenD + lenR;
IntMultiplication(cD, cR, cP);
int i =
strlen(cP) - 1;
while (lenP > 0 && cP[i] ==
'0')
{
i--;
lenP--;
}
cP[i+2] = '0';
20
沈阳航空航天大学课程设计报告
错误!未指定书签。
while (lenP > 0 &&
i >= 0)
{
cP[i+1] = cP[i];
i--;
lenP--;
}
cP[i+1] = '.';
if (i == -1)
{
for
(i=strlen(cP); i>0; --i)
cP[i+1+lenP] =
cP[i];
for (i=0; i
cP[1] = '.';
cP[0] =
'0';
}
strcpy(product, cP);
}
void FloatDivision(char *dividend, char
*divisor, char *quotient, int precision)除法
{
if (Compare(dividend, divisor) == 0)
{
strcpy(quotient, .);
return
}
if (strcmp(divisor,
{
strcpy(quotient,
return
}
char cD[MAX] = {0};
char cR[MAX] = {0};
char cQ[MAX] = {0};
char cY[MAX] = {0};
char tcY[MAX][MAX] = {0};
int lenD,
lenR, lenQ;
int i, j, t, s, left;
21
沈阳航空航天大学课程设计报告
错误!未指定书签。
lenD = Radix(cD,
dividend);
lenR = Radix(cR, divisor);
if (lenD > lenR)
lenQ = lenD -
lenR;
else
{
lenQ = 0;
i
= strlen(cD);
for (j=0; j
cD[i] = '0';
}
IntDivision(cD, cR, cQ, cY);
t = j = strlen(cQ);
for (i=0;
i
if (t > 0)
cQ[t] = cQ[t-1];
else
{
t =
1;
cQ[t] = '0';
}
}
cQ[t] = '.';
if (t == 0)
{
for (i=j++; i>=0; --i)
cQ[i+1] = cQ[i];
cQ[0] = '0';
}
++j;
i = t = 0;
while (i < precision &&
strcmp(cY,
{
strcpy(tcY[t++], cY);
left = IsCycle(tcY, t-1);
22
沈阳航空航天大学课程设计报告
错误!未指定书签。
if (left != t-1)
如果找到相等的余数,就结束循环
{
Insert(cQ, j-(t-1-left), j);在字符数组s中适当位置插入符号'('
if (cQ[j-1] == '(' && cQ[j]
== '0')去除多余的循环节,即特殊处理可以除尽的情况
cQ[--j] = '0';
else否则用“()”把循环节括起来
{
cQ[j+1] = ')';
cQ[j+2] = '0';
}
break;
}
否则继续计算小数部分
strcat(cY,
s = 0;
if (Compare(cY,
cR) < 0)
cQ[j++] = '0';
else
{
while (Compare(cY, cR) >= 0)
{
++s;
IntSubtration(cY, cR, cY);
}
cQ[j++] = s + '0';
}
++i;
}
if (i == precision)
cQ[j] = '0';
strcpy(quotient,
cQ);
}
void Insert(char s[], int
left, int right)
{
int i;
for
(i=right; i>left; i--) 把数组元素后移,为插入符号'('腾出位置
{
s[i] = s[i-1];
}
23
沈阳航空航天大学课程设计报告
错误!未指定书签。
s[left] = '(';插入符号'('
}
int IsCycle(char a[][MAX],
int label)
{
int i;
for (i=0;
i
<
br>许多多问题,同时在设计到经验掌握对一些前面学过的知识理解得不够深刻过程
中发现了自己的不
足之处不够牢固,在使用高精度算法时,加减还好些,乘除就
比较困难了。有写步骤要看参考书才能明白
这次课设,我的题目并不是很难,但
我也绞尽脑汁,书都快泛滥了,我也刻的认识到自己的不足,好多东
西都是一知
半解,知识掌握的不全面,不扎实为今后的学习敲响警钟总之,这次课设为我们
提供
了与众不同的学习方法,在书本中面对现实,我们将来在社会上立足提供了
良好的前提
25