数据结构课程设计——大整数程序.ppt

1、1,数据结构课程设计,陈正铭,2,教学目的与要求,数据结构课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。 通过这次课程设计，要求掌握数据结构的逻辑特性和物理表示，数据结构的选择应用、算法的设计及其实现和性能分析等方面中加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。,3,数据结构基本原理简要复习,1数据元素之间的四种基本逻辑结构： 非线性，线性，树，图 2数据物理表示（存储方法）： 顺序存储，链式存储，索

2、引存储，散列存储 3算法的特征： 有穷性，可行性，确定性，正确性 算法设计的要求： 可读性，健壮性，高效性,4,4算法的时间复杂度、空间复杂度及分析： O（1），O（n），O（logn），O（n2） 5典型的几种数据结构： 顺序表，链表， 顺序栈，链栈，循环队列，链队列， 字符串， 多维数组， 二叉链表树，二叉顺序树， 邻接矩阵图，邻接表图， 散列表,5,设计题目,大整数运算（加法、乘法）的实现 （数据结构课程设计案例精编P160） 该参考教材同学们可自行借阅或在网上购买（一般8折），也可联系出版社市场部集体定购（清华大学出版社市场部电话转分机号220），可能有更大

3、折扣。 该参考教材内容丰富，尤其是C+语言 STL方面的内容，对日后从事开发设计工作的同学有较大参考作用。但教材价格较贵，零售价45元，因此没为大家集中定购，大家可按需购买。,6,设计要求,大整数运算（加法、乘法）的实现 基本要求：实现一个大整数（要求允许绝对值232）的运算程序。要求程序读入操作数A和B，选择相应的加法或乘法运算符，然后计算结果并输出到屏幕上。 选做内容：实现整除运算，求出运算时间，图形化窗口操作界面 。 （参考教材的本题目设计指导部分的扫描页） 程序建议使用c语言完成，建议开发工具为Microsoft Visusl C+ 2005 Express（可在微软网站免费下载）。,

4、7,设计报告撰写指导,1、 需求分析 以无歧义的陈述说明所选设计题目的任务，强调的是程序要做什么？明确规定：输入的形式和输出、值的范围；输出的形式；程序所能达到的功能；测试的数据：包括正确的输入和错误的输入及其相应的输出结果； 2、 概要设计 问题解决的思路概述；说明程序中用到的所有抽象数据类型的定义，主程序的流程以及各程序模块之间的层次（调用）关系。,8,3、 详细设计 实现概要设计中定义所有数据类型，对每个操作只需要写出伪代码算法，画出函数的调用关系图。 4、 调试分析报告 调试过程中遇到的问题并且是如何解决的以及对设计实现的回顾讨论和分析算法的时空分析（包括基本操作和主要算法的时空复杂度

5、的分析）和改进设想经验和体会等,9,5、 用户使用说明 向用户说明如何使用你编写的程序，详细列出每一步的操作步骤。 6、 测试结果 列出测试结果，包括输入的数据和相应的输出数据。这里的测试数据应该完整和严格，最好多于需求分析中所列的测试项。 7、 附录（电子版文档必须要，打印版该部分可不打印） 应附上带详细注释的可读性好的源程序。 数据结构课程设计报告示例文档,10,时间安排,11,考核方式与成绩,程序：30 课程设计报告：70 2010年11月10日前以班为单位交齐全部课程考核资料（光盘和课程设计打印稿），逾期者以缺考处理，课程成绩0分。,12,设计指导,一、大整数算法的意义 随着计算机信息

6、安全的要求不断提高，密码学被大量应用到生活中，RSA、DSA、ECC等公钥密码算法和数字签名算法都建立在大整数运算的基础上，比较耗时的大整数乘法除法幂运算等却被上述算法大量使用，它们的运算速度对这些算法的高效实现起着重要的作用，如何快速实现上述几种运算是公钥密码领域普遍关注的热点问题。 不同的计算机系统所能表示的整数范围不同，在C+环境中，一个long类型的整数的范围是-3131-。但是在一些应用中，我们需要处理的数远远大于这个范围。这就需要我们借助已经存在的数据结构来构造可以存储大整数的结构。,13,二、大整数的存储方式 大整数的存储方式主要是两种链式存储和顺序存储。链式存储可以适应不定长度

7、的大数，这种方式的存储空间包括大整数的表示部分和指针部分，其空间利用率不高，而且存储空间是离散的，所以随机访问效率低；顺序存储方式可以分为静态存储方式和动态存储方式。静态存储方式数组的大小是事先已经知道的，适合知道大小的整数运算。而因其数组长度是固定不变，因此在运算时候容易造成溢出，所以不适合不定长度的整数运算。动态存储方式可以根据大整数位数变化调整大小，而且是连续分配，可随机访问，又没有指针等其他存储开销，空间利用高，是最常用的顺序存储方式。,14,三、符号相同的大整数加法运算 采用顺序存储方式的符号相同的大整数加法运算实现过程：因为两个整数符号相同，可以直接对两个整数数组对应位元素相加，并考虑进位问题。两个整数的数位存在以下3种情况（不妨设两个大整数为A和B）：A-length=B-length; A-lengthB-length; A-lengthlength.所以在处理加法时候，对数位较大的整数一分为二，第一部分和另一大整数长度相等，先把相同长度部分先计算，然后再对多出的长度部分直接赋值，可加快运算。如下所示：,