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

数据结构课程设计陈正铭

教学目的与要求 《数据结构》课程设计的目的就是要达到理论 与实际应用相结合，使同学们能够根据数据对 象的特性，学会数据组织的方法，能把现实世 界中的实际问题在计算机内部表示出来，并培 养基本的、良好的程序设计技能。 通过这次课程设计，要求掌握数据结构的逻 辑特性和物理表示，数据结构的选择应用、算 法的设计及其实现和性能分析等方面中加深对 课程基本内容的理解。同时，在程序设计方法 以及上机操作等基本技能和科学作风方面受到 比较系统和严格的训练。2

数据结构基本原理简要复习1.数据元素之间的四种基本逻辑结构： 非线性，线性，树，图 2.数据物理表示(存储方法): 顺序存储，链式存储，索引存储，散列存储 3.算法的特征： 有穷性，可行性，确定性，正确性 算法设计的要求： 可读性，健壮性，高效性3

4.算法的时间复杂度、空间复杂度及分析： O(1),O(n),O(logn),O(n2) 5.典型的几种数据结构：顺序表，链表， 顺序栈，链栈，循环队列，链队列， 字符串， 多维数组， 二叉链表树，二叉顺序树， 邻接矩阵图，邻接表图， 散列表4

设计题目大整数运算(加法、乘法)的实现(《数据结构课程设计案例精编》P160) 该参考教材同学们可自行借阅或在网上购买(一般8 折),也可联系出版社市场部集体定购(清华大学出版社 市场部电话：010-62788562(转分机号220)),可能有更 大折扣。 该参考教材内容丰富，尤其是C++语言 STL方面的内容，对 日后从事开发设计工作的同学有较大参考作用。但教材价 格较贵，零售价45元，因此没为大家集中定购，大家可按 需购买。5

设计要求大整数运算(加法、乘法)的实现基本要求：实现一个大整数(要求允许绝对值>232)的运算 程序。要求程序读入操作数A和B,选择相应的加法或乘法 运算符，然后计算结果并输出到屏幕上。 选做内容：实现整除运算，求出运算时间，图形化窗口操作 界面 。 (参考教材的本题目设计指导部分的扫描页) 程序建议使用c++语言完成，建议开发工具为Microsoft Visusl C++ 2005 Express(可在微软网站免费下载)。6

设计报告撰写指导1、 需求分析 以无歧义的陈述说明所选设计题目的任务， 强调的是程序要做什么？明确规定：输入的形 式和输出、值的范围；输出的形式；程序所能 达到的功能；测试的数据：包括正确的输入和 错误的输入及其相应的输出结果； 2、 概要设计 问题解决的思路概述；说明程序中用到的 所有抽象数据类型的定义，主程序的流程以及 各程序模块之

间的层次(调用)关系。7

3、 详细设计 实现概要设计中定义所有数据类型，对每 个操作只需要写出伪代码算法，画出函数的调 用关系图。 4、 调试分析报告 调试过程中遇到的问题并且是如何解决的 以及对设计实现的回顾讨论和分析算法的时空 分析(包括基本操作和主要算法的时空复杂度 的分析)和改进设想经验和体会等8

5、 用户使用说明 向用户说明如何使用你编写的程序，详细列出每 一步的操作步骤。 6、 测试结果 列出测试结果，包括输入的数据和相应的输出数 据。这里的测试数据应该完整和严格，最好多于需求 分析中所列的测试项。 7、 附录(电子版文档必须要，打印版该部分可不打印) 应附上带详细注释的可读性好的源程序。

数据结构课程设计报告-示例文档9

时间安排时间 第1周 内容 复习数据结构相关原理，明确题 目要求、确定数据结构与设计方 案 编写程序，准备测试数据 上机演示，回答教师提问，按格 式撰写课程设计报告 地点 课室 实验室或 在实验室或宿舍完成编 宿舍 写程序任务 课程设计报告应严格按 照上述设计报告撰写要 求撰写；最后将报告用 A4纸打印装订； 2010年11月10日前交齐 全部课程资料，逾期者 以缺考处理，课程成绩0 分。10

备注

第2~8周 第9周

实验室

第10周

以班为单位上交课程设计的资料 光盘(内含每个同学的课程设计 的源程序、编译后可直接运行的 目标程序与课程设计报告的电子 文档),课程设计报告打印稿

考核方式与成绩 程序：30% 课程设计报告：70% 2010年11月10日前以班为单位交齐 全部课程考核资料(光盘和课程设计打 印稿),逾期者以缺考处理，课程成绩0 分。11

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

二、大整数的存储方式大整数的存储方式主要是两种——链式存 储和顺序存储。链式存储可以适应不定长度的 大数，这种方式的存储空间包括大整数的表示 部分和指针部分，其空间利用率不高，

而且存 储空间是离散的，所以随机访问效率低；顺序 存储方式可以分为静态存储方式和动态存储方 式。静态存储方式数组的大小是事先已经知道 的，适合知道大小的整数运算。而因其数组长 度是固定不变，因此在运算时候容易造成溢出， 所以不适合不定长度的整数运算。动态存储方 式可以根据大整数位数变化调整大小，而且是 连续分配，可随机访问，又没有指针等其他存 储开销，空间利用高，是最常用的顺序存储方 式。13

三、符号相同的大整数加法运算采用顺序存储方式的符号相同的大整数加法运算实 现过程：因为两个整数符号相同，可以直接对两个整 数数组对应位元素相加，并考虑进位问题。两个整数 的数位存在以下3种情况(不妨设两个大整数为A和 B):A->length=B->length; A->length>B->length; A>length<B->length.所以在处理加法时候，对数位较大 的整数一分为二，第一部分和另一大整数长度相等， 先把相同长度部分先计算，然后再对多出的长度部分 直接赋值，可加快运算。如下所示：