数据结构课程设计报告模板成绩计算机与信息工程学院专业名称信息与计算科学学生班级 10 级1班学生姓名刘远远学生学号 2010025707设计起止时间: 2012年12月17日至 2012年12月21日课程设计任务书一、课程设计题目: 线性表的应用(大数运算)二、课程设计目的与要求:1、课程设计目的(1)对数据结构中线性结构的理解和掌握;(2)熟练掌握顺序和链式存储结构有关知识和方法;(3)深入掌握各种数据结构的理论知识和实践操作;(4) 养成良好的编程风格，掌握各种数据结构的编程思想和编程方法;(5)将数据结构的理论知识和实践有机结合起来，为后续知识的学习做好准备。

2、课程设计要求(1) 选择合适的存储结构实现大数存储;(2) 设计算法，采用顺序存储结构完成大数的阶乘运算;(3) 设计算法，采用链式存储结构完成大数的加法运算;(4) 设计算法，选择合适的存储结构完成大数的乘法运算;(5) 其中某一算法采用两种存储结构实现。

三、工作计划:第一阶段(12月17日,12月18日):查阅各种数据结构相关资料书籍，整理出课程设计初步模型，并形成课程设计的整体理论框架，理论模型 ;第二阶段(12月19日,12月21日):在DEV-C++5或TURBOC2相关开发语言上，进行编码、上机调试，逐步形成完善的设计程序，使其达到上机完善演示出系统性的课程设计。

四、课程设计提交的文件:(1) 课程设计报告(2) 课程设计可运行程序(刻录成光盘)指导教师: 张绍兵2012 年 12 月 1日2线性表有两种不同的存储结构，分别是顺序存储结构和链式存储结构，在实际中应用十分广泛。

本设计要求分别利用线性表的两种存储结构，设计算法完成对大数的阶乘、加法、乘法的求解。

数据结构是一门研究非数值计算的程序设计问题中的操作对象以及它们之间的关系的操作的学科，在本次课程设计中，定义存储结构均采用了数据结构中的抽象数据类型，而抽象数据类型是指一个数据模型以及定义在改模型上的一组操作，抽象数据类型的定义仅仅取决于它的一组逻辑特性，而与计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。

选择合适存储结构实现大数运算。

首先需要先解释的是这里大数计算的因数和结果精度一般是少则数十位，多则几万位。

在C语言中定义的类型中精度最多只有二十多位，因而在此我们采取用线性表的顺序和链表存储结构的方式来存放大数,解决一些关于大数的运算应用，原来此问题在现实生活中实用性很强，诸如密码学特别是RSA加密方面、物理研究学、生物学、化学中有特殊应用。

3目录课程设计任务书 ........................................2 摘要 ..............................................3 第一部分课程设计内容与理论基础 ........................5 第二部分课程设计算法构造思想 ..........................7 第三部分课程设计模块划分及其功能 ......................8 第四部分课程设计使用说明和运行结果 ....................9 第五部分参考文献 ....................................10 第六部分附录 (10)4第一部分课程设计内容与理论基础1.课程设计内容在我们常用的32位计算中，CPU中加减乘除的一次运算是32位的值，也就是说2的32次方的一个值，这就是说1加上1的CPU工作量和小于2的32的两位数相加是用的相同的周期。

为了避免运算结果大于2的32次，因为大于的话又会造成一次CPU周期运算，但这样当然也可以做。

但建议用下面方法，考虑乘法的原因，两个2的16次方相乘就是2的32次方的情况，所以我们定义了本程序算法，结点数巨减，主要是开内存方面，有了极大的减少。

本设计要求分别利用线性表的两种存储结构，定义存储结构均采用了数据结构中的抽象数据类型，而抽象数据类型是指一个数据模型以及定义在改模型上的一组操作C语言中定义的类型中精度最多只有二十多位，因而在此我们采取用线性表的顺序和链表存储结构的方式来存放大数,解决一些关于大数的运算应用(大数计算的因数和结果精度一般是少则数十位，多则几万位),设计算法完成对大数的阶乘、加法、乘法的求解。

例如:1、阶乘运算的测试数据:60!2、加法运算的测试数据: 9876876787+896789675599993、乘法运算的测试数据:9876876787×89678967559999 2.课程设计理论基础本次课程设计使用C语言进行设计，在DEV_C++中编译运行的，主要使用了以下理论知识:1、顺序表的顺序存储结构:typedef struct {ElemType *elem;int length; } SqList;2、顺序表的链式存储结构:typedef struct LNode{ElemType data;struct LNode *next; } LNode,*LinkList;3、链栈的存储结构:typedef struct SNode{ElemType data;struct SNode *next;} SNode, *LinkStack;4、顺序表的各种抽象数据类型的定义如下ADT list_Sq{5数据对象:D={ai|ai?ElemSet,i=1,2,…,n,n>=0}数据关系:R1={<ai-1,ai>|ai-1,ai?D,i=2,…,n}基本操作:Status InitList_Sq(SqList &L)操作结果:构造一个空的线性顺序表L。

Status ClearList(&L)初始条件:线性表L已存在。

操作结果:将L重置为空表。

Status DestroyList(&L)初始条件:线性表L已存在。

操作结果:销毁线性表L。

Status ListLength(L)初始条件:线性表L已存在。

操作结果:返回L中数据元素个数。

Status ListTraverse(L,visit())初始条件:栈L已存在且非空。

操作结果:从栈底到栈顶依次对L的每个数据元素调用函数visit()。

一旦visit()失败，则操作失败。

}5、栈的抽象数据类型定义:ADT Stack{数据对象:D={ai|ai?ElemSet,i=1,2,…,n,n>=0}数据关系:R1={<ai-1,ai>|ai-1,ai?D,i=2,…,n}约定an端为栈顶，a1为栈底。

基本操作:InitStack(&S)操作结果:构造一个空栈S。

DestoryStack(&S)初始条件:栈S已存在。

操作结果:栈S被销毁。

Push(&S，e)初始条件:栈S已存在。

操作结果:插入元素e为新的栈顶元素。

StackTraverse(S,visit())初始条件:栈S已存在且非空。

操作结果:从栈底到栈顶依次对S的每个数据元素调用函数visit()。

一旦visit()失败，则操作失败。

}6第二部分课程设计算法构造思想1、阶乘运算的算法思想:一个数的阶乘，利用一个顺序表来存储结果，首先令L.elem[0]=1，其他全部赋值为零，再用for循环，从1至i完成阶乘运算，其中由于位数越乘越多，故将其按位存储在顺序表中，防止数据范围溢出，在逐位相乘中，利用for循环位数，如若有进位问题，每次运算时，此位保留的数位，t=L.elem[j]*i+jw;L.elem[j]=t%10;jw=t/10;如果满足j>=top && jw==0;程序跳出，进行下一步i运算，此处top位保留上一位的位数，如此运算下去，输出顺序表。

2、加法运算的算法思想:本运算分别采用了两种存储结构，链式和栈存储结构。

加法是两个数位数对齐，从低位向高位加的运算，如果在哪位有进位，则后一位，进行加法还要另加上前面的进位，由此将输入的字符大数，存入链表中，且改为整形存入，此时是的链表是倒序的，定义一个变量表示每次的进位jw=0，建立一个链表，让他存储结果，如此两链表的数相加，每次还要加上上次留下的进位，此为保留的数位:new->data =(p->data +q->data +jw)%10; new->next =NULL;jw =(p->data+q->data+jw)/10;当两个数是一场一短时，自然当相等的长度加完后在执行下面的判断，保留住剩下的数同时每次加上jw，最后就是当最后一位有进位时将最后一个链表值赋jw，由于现在此链表存储的结果是反序的，故将其压入栈中，让后再输出栈元素，就是想加的结果。

3、加法运算的算法思想:主要采用顺序存储结构，先从低位算起，只须要对应的位相加，再加上前一位的进位，使用变量jw存储，每次运算时加上jw运算，再去判断是否本位是否有进位，有则将jw的值赋成本位进位数;没有进位，则给进位赋值0。

其中，若两个加数中那一个数的位数长，以位数长的作为循环变量;结束循环时，不仅仅是最后一位加完就停止，还应加入如果有进位，也要再循环一次。

如最后一位是9，进位是1，则相加时进位，要加上进位这一位值。

4、乘法运算的算法思想:传入的乘数和被乘数是以字符串形式放入的，为了要让指针指向最后一位，自己写了个函数StrNum2倒着赋值，同时因为传入和保存的都是字符，所以计算时要将字符转化为数字;从低位向高位乘，在竖式计算中，我们是将乘数第一位与被乘数的每一位相乘，记录结果，之后，用第二位相乘，记录结果并且左移一位，以此类推，直到计算完最后一位，再将各项结果相加，得出最后结果。

当然我们可以直接用这种方法，但要用多个数据来保存计算出的分结果，之后结果再相加得到最后结果，但是这样会浪费很多空间，所以我们可以再优化一下，就是只用一个顺序表来表示结果，先把第一位乘数与被乘数的结果保存在链表中，之后把存储结果的和第二次如此算的结果加在第一次的基础上，二者使用同一个顺序表来表示，以此类推，直到结束，这样就可以用一个顺序表来存储相乘后的结果。

另外在运算时乘和加都有进位时要处理，就和大数加法中进位采取方法一样，当前的值加上进位的值再看本位数字是否又有进位就行。

7第三部分课程设计模块划分及其功能系统程序的组成框图主函数对各个函数的调用关系图。

大数的运算1、大数的阶乘运算2、大数的加法运算3、大数的加法运算4、大数的乘法运算5、返回0、退出4、调用 1、调用 2、调用 3、调用 0、退出系5、该选void void void void 统，安全项作用 multiply()factorial() addition1() addition() 退出是返回函数函数函数函数主菜单void void void voidaddition1()，将字符串转 factorial()，利addition()，利multiply()，利换为整形数组，反向传入链表用顺序存储结用顺序存储用顺序存储结中赋值，并利用链式存储结构构完成大数阶结构完成大构完成大数的完成大数的加法运算，最后用乘运算数的加法乘法栈来输出结果Int StrToNum1(SqList L,char *a)，将字Void StrToNum2(SqList *a,char *s)，将字符串转换为整形数组，反向赋值符串转换为整形数组，正向赋值;8第四部分课程设计使用说明和运行结果1. 课程设计使用说明在选择适当的运行环境中(例如DEV_C++),可以使用C工程进行编译，主要是在.C窗口中进行上机测试，当打开运行窗口时，根据页面上的提示信息进行试验，采用顺序存储结构完成大数的阶乘运算，采用链式存储结构完成大数的加法运算，选择合适的存储结构完成大数的乘法运算。