数据结构课程设计示例文档.docx
《数据结构课程设计示例文档.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计示例文档.docx（39页珍藏版）》请在冰点文库上搜索。
数据结构课程设计示例文档
（此文档为word格式，下载后您可任意编辑修改！
）
韶关学院计算机科学学院
数据结构课程设计
题目：
课堂经验值查询系统
专业：
计算机科学与技术
1需求分析
1.1课题背景及意义
随着计算机网络技术的发展和因特网的广泛普及，网络安全事故逐年增加，黑客的攻击已经和病毒并列成为对信息安全影响最严重的两大危害。
其很大程度上是被黑客破解了用户的计算机名及登陆密码及资料的加密较差，而使得黑客来对网民的资料如同自己般的随意更改和破坏。
而安全的密码和账号成为了网民的安全之本，怎么才能提高安全问题成为的人们和社会关注的问题。
而加密大部又是以大素数的计算为基础的，如非对称密码体制RSA的安全性依赖于对大数进行因数分解的耗时性。
大数运算不仅仅运用在密码学中，还运用在一些物理学研究、生物学，化学等科目中。
大数运算，意味着参加的值和计算结果通常是上百位数，上千位数以及更大长度之间的整数运算。
例如大家所熟知圆周率π的值，在一般的数值计算中用到圆周率的不须要多大的精度，但在计算一些星球或是星系上的体积面积时便显的误差很大了，这就要求π值计算的精度达到几百万位甚至更高，才能缩小误差。
人工计算是远远不行了，而且本身误差也无法估计。
只有在计算机中用大数运算求π值了。
又如，考古学家计算石头内的碳元素衰变来考证地球形成的时间，更是将计算的结果精确到了百年以内。
所以说大数的运算是涉及领域多，应用范广，与我们生活息息相关。
《数据结构课程设计》是一门实践性的计算机课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。
通过这次课程设计，要求掌握较大程序的设计方法，相应数据结构的选择应用、算法的设计及其实现和性能分析等方面中加深对课程基本内容的理解。
同时，在设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。
1.2课题要求
A.支持大数精确运算的计算器
B.实现一个大数（要求允许绝对值>10128）的计算器图形化程序软件。
C.要求程序读入大数A和B，选择相应的加、减、乘或除法运算符，然后计算精确结果（不能用科学计数法，不四舍五入）并输出到屏幕上，在普通计算机上运算时间不超过1分钟。
D.选做内容：
实现大数的其他运算（如三角函数），求出运算时间。
1.3软件格式规定
A．输入的形式:
正数的不用输入符号位，数值的第一位可以为零。
位数在0~1000之间
B.程序所能达到的功能:
能进行位数在0~1000（可在源程序里设置位数大小）之间的所有整型数和浮点型数的四则运算。
C.输出的形式:
是整型或浮点型数据
D.测试的数据：
1）、正确的输入：
以下是对两个大数进行加减乘除四则运算所得的正确结果：
正确的运算结果：
2）、windows版本应用程序错误的输入:
数A:
112
数B:
0
1.4设计目标
B.软件组成：
DosBigMath.exe（dos系统应用程序）;WinBigMath.exe（windows系统图形化窗口操作界面应用程序）
C.制作平台及相关调试工具：
Win32；MicrosoftVisuslC++2005Express
D.运行环境：
doswinxpwin7
E.性能特点：
（1）软件由两个可执行文件组成，各具特点:
DosBigMath.exe为dos系统应用程序，体积小，高效快捷，适用范围广，兼容性好。
WinBigMath.exe为windows应用程序，界面友好，使用方便。
（2）输入的大数可为整型，也可以是浮点型。
（3）DosBigMath.exe（dos系统应用程序）的输入和输出形式：
运算符选择→按回车键→输入A的值→按回车键→再输入B的值→按回车键→输出运算结果并显示运算所花时间（ms级）。
（4）WinBigMath.exe（windows应用程序）可支持鼠标点击输入与键盘输入，可支持黏贴的数字。
（5）运行时间较短，精确到毫秒级。
（6）个别其他功能可进行再扩展。
2概要设计
2.1问题解决的思路概述
首先是确定结构化程序设计的流程图，利用已存在的数据结构来构造一个存储大数的结构，接着把四则运算分成四个主要的模块：
实现加法的模块、实现减法的模块、实现乘法的模块、实现除法的模块，然后各个模块里面还要分成若干种情况来考虑并通过函数的嵌套调用来实现其功能。
最后，编写main主函数以实现大整数的正确输入与正确输出，调试程序并将不足的地方加以修改。
总而言之，就是先用自顶向下、逐步细化的设计方法来分析并画出程序设计流程图；然后用自下而上、逐步积累的设计方法来写出程序。
2.2相关函数介绍说明
在dos版本程序和windows版本程序下都定义了一个用于存储大数的结构体类型变量：
typedefstructtagBigNumBigNum;
（1）dos版本程序下定义的相关函数
voidStartCount（）;计时开始
voidEndCount（）;计时结束
doubleTime（）;返回时差
voidInitBigNumToZero（BigNum*pNum）;初始化BigNum为0
intCharLenByBigNum（CONSTBigNum*pNum）;
判断需要多少个字符空间存储BigNum转换的字符串.
voidCharToBigNum（CONSTchar*arr,BigNum*pNum）;
从字符串转换到BigNum.
voidBigNumToChar（char*szBuf,CONSTBigNum*pNum）;
从BigNum转换到字符串.
voidAdjustBits（BigNum*pNum）;
调节数位,删除最高整数位是的和最低小数位是的数位.
voidMoveFloatPoint（BigNum*pNum,intdeta）;
移动小数点,deta=0不移动,deta<0往左移动,deta>0往右移动.
voidMakeInfinite（BigNum*pNum）;使无穷大
char*Result（CONSTchar*val1,CONSTchar*val2,PFNCALCpfnCalc）;
根据算术函数返回结果
intCompare（CONSTBigNum*pn1,CONSTBigNum*pn2）;比较个数大小
intIsZero（CONSTBigNum*pNum）;判断是否为
voidAdd（CONSTBigNum*pn1,CONSTBigNum*pn2,BigNum*pRes）;
加法
voidMul（CONSTBigNum*pn1,CONSTBigNum*pn2,BigNum*pRes）;
乘法
voidSub（CONSTBigNum*pn1,CONSTBigNum*pn2,BigNum*pRes）;
减法
voidDiv（CONSTBigNum*pn1,CONSTBigNum*pn2,BigNum*pRes）;
除法
voidshowmenu（）;显示菜单信息
voidmenu（）;选择运算符的菜单
voidGetNum（CHARARRnuma,CHARARRnumb）;从dos界面获取输入字符串
（2）windows版本程序下定义的相关函数
windows版本程序下定义的相关函数中除了没有“voidshowmenu（）;”、“voidmenu（）;”、“voidGetNum（CHARARRnuma,CHARARRnumb）;”三个dos输入显示函数，其他的函数都和dos版本程序下定义的一样。
2.3主程序的流程基函数调用说明
在这里，主程序的流程以dos版本程序进行说明。
（1）主程序的简要流程图
图1主程序流程图
（2）各程序模块之间的层次（调用）关系
调用“Result（）”函数，以调用“CharToBigNum（）”将输入的字符型大数转换成可用于运算的结构体类型大数，然后调用四则运算的各运算模块进行相应的运算，再调用“BigNumToChar（）”将各运算模块返回的运算结果转换成字符类型用于输出显示，期间还要调用“CharLenByBigNum（）”来判断数据所需的存取空间。
在每一个运算模块都涉及到大数的存取，所以都要调用“InitBigNumToZero（）”对结构体变量初始化。
加法运算程序模块“Add（）”，首先要判断两个大数的符号位，如果是一号相加则调用减法运算程序“Sub（）”；如果是同号相加则直接运行程序。
减法运算程序模块“Sub（）”，首先要判断两个大数的符号位，如果是异号相减则调用加法程序“Add（）”；如果是同号相减则直接运行，然后调用“Compare（）”以实现大数减小数。
乘法运算程序模块“Mul（）”，首先调用“MoveFloatPoint（）”以实现浮点型数以整型数的形式相乘，采用“模拟笔算”的方法，每乘一次都要调用加法程序“Add（）”将结果累加起来，然后在调用“MoveFloatPoint（）”将所得的整型结果转化成正确的浮点型类型相乘结果。
除法运算模块“Div（）”，首先调用“MoveFloatPoint（）”以实现浮点型数以整型数的形式相除，采用“模拟笔算”的方法，以除数的位数长度为基准，多次循环调用“Compare（）”、“MoveFloatPoint（）”、“Mul（）”和“Sub（）”，一直到规定的小数位数为止，最终还要要调用“MoveFloatPoint（）”将所得的整型结果转化成对应的浮点型类型相除结果。
3详细设计
3.1数字存储的实现
大数计算的因数和结果精度一般是少则数十位，多则几万位。
在C语言中定义的类型中精度最多只有二十多位，由于涉及到浮点型大数和负数的运算，因而程序采取定义一个结构体类型存贮的方式来存放大数符号、小数点、整数部分、整数数位、小数部分、小数有效位数。
在计算中会用到从高位开始计算，和从低位开始计算数值的两种情况。
其结构为：
typedefstructtagBigNum{
intintbits;整数数位
intfloatbits;小数有效数位
charinfinite;无穷大
charsign;符号
charintpart[INT_BIT_MAX];整数部分
charfloatpart[FLOAT_BIT_MAX];小数部分
}BigNum;
3.2四则运算算法
在大数四则运算的程序设计中，每一部分都会调用一些其他其它函数来辅助完成运算（例如：
对结构体变量的初始化，比较两个数的大小,将字符型数据转换成结构体类型数据和将结构体类型数据转换成字符型数据等），在这里主要说明四则运算的程序设计，其它函数的程序设计和具体调用关系请查看程序清单。
3.2.1加法运算的实现
加法计算还是比较容易实现的，对于整数部分的计算，以整数部分位数长的作为循环变量，先从低位算起，因为只须要对应的位相加（相加结果小于20），再加上前一位的进位，再判断本位是否有进位，把进位值改为本位除以它的权（也就是10）取整（既有进位时，给进位赋值1，如果没有进位，则给进位赋值0），然后把本位数字改为本位除以它的权（也就是10）取余。
图2加法运算原理图
对于加法运算中小数部分的计算，也是从低位算起，以小数部分位数长作为循环变量，相加的原理跟整数部分一样。
在程序中设计时应注意：
以上加法运算的原理只针对两个符号位相同的大数相加，如果是异号相加则要调用减法运算模块；
结束循环时，不仅仅是最后一位加完就停止，还应加入如果有进位，也要再循环一次。
如最后一位是9，进位是1，则相加时进位，要加上进位这一位值。
具体看代码。
如果是两个负数相加，最终结果还要加负号。
3.2.2减法运算的实现
由于使用结构体类型来分别存储了大数的整数及其位数、小数及其位数、符号（正、负），所以对于减法运算的实现也是比较简单的。
对于整部部分，算法从低位开始减。
首先判断两个数是否相等，如果相等则直接返回结果位0；否则要判断减数和被减数那一个位数长，被减数位数长是正常减；减数位数长，则减数减被减数，最后还要加上负号。
两数位数长度相等时，比较哪一个数大，被数大则正常减；减数数大则减数减被减数。
处理每一项时，如果前一位相减有借位，就先减去上一位的借位，无则不减，再去判断是否能够减开被减数，如果减不开，就要借位后再去减，同时置借位为1，否则置借位为0。
图3减法运算原理图
对于减法运算中小数部分的计算，也是从低位算起，减法原理跟整数部分一样。
在程序设计时应注意：
两个浮点型数的减法运算是从小数部分开始的，当小数部分计算完了才开始计算整数部分；而计算整数部分的时候还要判断小数部分的计算是否有向整数部分借位。
以上减法运算的原理只针对两个符号位相同的大数相减，如果是异号相减则要调用加法运算模块。
3.2.3乘法运算的实现
首先说一下乘法计算的算法，从低位向高位乘，在竖式计算中，我们是将乘数第一位与被乘数的每一位相乘，记录结果，之后，用第二位相乘，记录结果并且左移一位，以此类推，直到计算完最后一位，再将各项结果相加。
得出最后结果。
当然我们可以直接用这种方法，但要用多个结构体变量来保存计算出的分结果，之后结果再相加得到最后结果，但是这样会浪费很多空间；因此，可以再优化一下，就是只用两个结构体变量来表示结果，先把第一位乘数与被乘数的结果保存在第一个结构体变量中，然后将此次分结果与第二个结构体变量中的数相加并将结果保存于第二个结构体变量中；在进行下一次相乘，第二位乘数与被乘数结果存在第一个结构体变量中，再与第二个结构体变量中保留的累加结果相加。
以此类推，直到结束。
这样就可以用两个结构体变量来存储相乘后的结果并节省了一些空间。
图4乘法运算原理图
在程序设计时应注意：
两个浮点型数的乘法运算是先将浮点型数转换成整型数，再从低位开始计算，当计算完后了还要将整型结果转换成浮点型结果。
两个异号大数相乘时，结果要加上负号。
将各分结果相加时，直接调用加法运算函数即可。
3.2.4除法运算的实现
首先次除法运算所要得到的结果，当被除数除不开除数时，被除数补零继续向下除，一直除到规定的小数位数。
从高位向低位减，减时以被除数长度为单位，从高位取出大于被除数的字符串（被除数），然后将原除数乘以一个权值（小于10）得到一个不大于被除数的新的被除数，再用被除数减去新的除数，权值既为结果，余数从剩下的被除数高位再取出几位做补位，如此类推，循环减。
最终，将相应的小数结果返回。
图5除法运算原理图
在程序设计时应注意:
上述除法原理是从两个整型数相除的角度来说明的。
当两个大数中有浮点型数时，要先将小数转换成整数再进行除法运算，运算完毕后，还要将最后的结果转换成相对应得小数结果。
减数（亦即除数）乘上一个权值后不能大于被减数（亦即被除数）。
乘以一个权值时，可直接调用乘法运算函数即可；循环相减时，可直接调用减法运算函数即可。
3.3函数调用关系图
此函数调用关系图以dos版本应用程序来进行说明。
此函数调用关系图主要描述了四则运算的实现及实现各运算所要调用的函数，详情还请看程序清单。
图6函数调用关系图
4调试分析
表1调试过程情况表
序号
时间
出现问题
解决方法
1
做减法时由于没有考虑到a将减法分成三部分，a>b,ab时的操作，a=b时就直接输出0
2
减法输出结果中测试到，当高位的值相减为0时，也是把0给输出
存储数组c，用一个for语句，if（c[i]!
=0）break;到第一个非0开始，将后面的字符串逐个输出cout<3
乘法运算编程算法是逐个转化为数字，进行整型运算，结果存储很麻烦，需要多次进行加法运算，还要进行移位运算，使数字的相加位一致。
可以这样做乘法，先将每一位上有的每一个数字相乘在相加，求模作为那一位的数字再转化为字符，求整除则将结果加到高一位的结果中，如此循环，直到最后一位，并存到c中。
（运算方法在详细设计的乘法中给出。
）
4
乘法结果c的存储大小没考虑到最大的进位，只是考虑了最高的进位不大于9，没有考虑到进位大于10的情况，导致溢出位没有输出，结果错误。
对于乘法的进位，最大的不会超过99，但有会有超过10的情况，所以存放结果的c的大小应该为两个大整数的个数的和加上2，当进位没达到c[0]时，则将这些位置为’\0’，在进行结果输出。
5
对于除法，结果输出的时候也是遇到了与减法运算时，没有清零的情况
参考减法运算的算法，将商的无效的0
6
除法参考别人的算法，发现当输入的大整数a将除法的情况也分为两种：
a>=b,a当a7
一次输入两个大整数只能运算一次，发现很麻烦
用for语句将四个运算符加入里面，用第二次输入来判断运算，只有当运算符不是四个中的一个时才跳出到下一次运算输入。
8
可以重复输入下一次的大整数，但是屏幕上的东西太多了，但是一次清理就会使屏幕清空，不能做下一次的运算。
用一个while
（1）一个永真语句进入一个循环，在循环的开始就设置清屏语句system（"cls"）;然后输入是否选择是否进入计算系统，不进入的话就跳出循环，结束执行。
9
在输入运算选择符时一开始用了scanf（），发现会导致内存written出错
用getch（）输入就没出现内存问题，但是同时使用者也不知道自己输入的是什么选择符，再使用一个pirntf（），将输入的字符显示出来。
10
在输入大整数运算后，进入到多重运算符多次操作的时候，结果会出现乱码。
将输入的两个数再次初始化，复制到另外的两个数组中，并显示出来运算的两个数，发现没有问题了。
11
再进行结果的测试的过程中又再次出现结果为乱码的情况。
询问了别人，原来不但要将进行计算的两个数进行初始化，还要将存储结果的数组c一并清空，将c[i]的每一位都赋值为空。
5用户使用说明
分两部分来分别说明dos版本应用程序的操作和windows版本应用程序的操作：
5.1dos版本应用程序操作说明
（1）运行DosBigMath.exe应用程序后会出现主界面；
（2）选择所要做的运算，按下回车键；
（3）输入第一个操作数，按下回车界；
（4）再输入第二个操作数，按下回车，显示结果。
5.2windows版本应用程序操作说明
（1）运行WinBigMath.exe应用程序后会出现主界面：
图7主界面效果图图8运行效果图
（2）按下数字键（0~9）在输入框A中输入第一个大数，如果发现按错数字键可按“退格”键从后往前一个一个地删除；然后按下“+”“-”“*”“”键，自动切换到B输入框，按下数字键（0~9）输入第二个大数,同样，如果发现按错数字键可按“退格”键从后往前一个一个地删除；最后按下“=”键，输出显示运算结果并显示运算时间；
（3）如果在按下运算符按键后发现第一个输入有错，则可再按一次同样的运算符按键，就自动切换到输入框A，这是按下“退格”键可从后往前一个一个地删除。
6测试结果
6.1dos版本应用程序测试结果：
图9dos版本测试结果图
6.2windows版本应用程序测试结果：
图10windows版本测试结果图
参考文献
[1]陈元春，王中华等.实用数据结构[M].北京：
中国铁道出版社，2003.18-40.
附录：
程序清单
本程序设计由三部分组成（“BigMath..c”，“BigMath.c”）：
毕业论文通用格式分类号：
无锡职业技术学院
毕业设计（论文）
题目（团队课题要注明“团队”二字）
英文并列题目
所在团队
答辩委员会主任主答辩人
二零15年3月
毕业设计（论文）开题报告
毕业设计（论文）任务书
年月日
设计类建议格式一：
封面
开题报告
任务书
摘要、关键词（含中英文）
第一章序言
1.1XXX
1.2XXX
……
第二章XXX工艺设计
2.1XXX
2.2XXX
……
第三章XXX参数确定及计算
3.1XXX
3.2XXX
……
第四章XXX夹具设计
4.1XXX
4.2XXX
……
第N-1章XXX
N-1.1XXX
N-1.2XXX
……
第N章结论
小结与致谢
参考文献
毕业设计附录目录：
1.机械加工工艺流程图
2.机械加工工艺过程卡
3.机械加工工艺工艺卡
4.机械加工工艺工序卡
5.被加工零件图
6.夹具装配图
7.夹具零件图
8.其他系统图
9.其他原理图
10.零件三维造型图
11.夹具三维造型图
12.设计（作品）实物图
13.设计（作品）实物
14.开题报告
15.专业翻译材料
16.企业证明
17.与企业合作开发的技术服务合同
18.四技服务项目验收表
19.毕业设计（论文）指导记录表
20.毕业答辩评审表
表2毕业设计（论文）评阅教师评价表
表3毕业设计（论文）答辩记录表
表4毕业设计（论文）答辩评价表
表4毕业设计（论文）综合评价表
设计类建议格式二：
封面
开题报告
任务书
摘要、关键词（含中英文）
第一章绪论
1.1XXX课题的背景及意义
1.2XXX国内外研究现状
1.3XXX技术特点
1.4XXX课题研究的内容
……
第二章XXX系统的总体设计
2.1XXX系统整体方案设计思路
2.2XXX
……
第三章XXX系统的硬件设计
3.1XXX系统硬件设计思路
3.2XXX
……
第四章XXX系统的电路设计
4.1XXX系统电路设计思路
4.2XXX
……
第五章XXX系统的软件设计
5.1XXX系统软件设计思路
5.2XXX
……
第六章XXX系统的监控中心设计
6.1XXX系统监控中心设计思路
6.2XXX
……
第N-1章XXX
N-1.1XXX
N-1.2XXX
……
第N章总结与展望
小结并致谢
参考文献
毕业设计附录目录：
1.XXX系统的总体设计图
2.XXX系统的硬件设计图
3.XXX系统的电路设计图
4.XXX系统的软件设计方框图
5.软件光盘
6.其他系统图
7.其他原理图
8.设计（作品）实物图
9.设计（作品）实物
10.开题报告
11.专业翻译材料
12.企业证明
13.与企业合作开发的技术服务合同
14.四技服务项目验收表
15.毕业设计（论文）指导记录表
16.毕业答辩评审表
表2毕业设计（论文）评阅教师评价表
表3毕业设计（论文）答辩记录表
表4毕业设计（论文）答辩评价表
表4毕业设计（论文）综合评价表
论文版面格式：
无锡市机电五金行业市场调查
（三号、宋体、加粗、居中、1.5倍行距）
摘要：
（小五号，黑体）无锡位于长三角地区，近年来机电五金行业发展迅猛。
通过对无锡机电五金市场
升级会员 