数据结构课程设计报告模板.doc

成绩 计算机与信息工程学院数据结构课程设计报告专 业 名 称 信息与计算科学 学 生 班 级 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日摘 要 线性表有两种不同的存储结构，分别是顺序存储结构和链式存储结构，在实际中应用十分广泛。本设计要求分别利用线性表的两种存储结构，设计算法完成对大数的阶乘、加法、乘法的求解。 数据结构是一门研究非数值计算的程序设计问题中的操作对象以及它们之间的关系的操作的学科，在本次课程设计中，定义存储结构均采用了数据结构中的抽象数据类型，而抽象数据类型是指一个数据模型以及定义在改模型上的一组操作，抽象数据类型的定义仅仅取决于它的一组逻辑特性，而与计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。选择合适存储结构实现大数运算。首先需要先解释的是这里大数计算的因数和结果精度一般是少则数十位，多则几万位。在C语言中定义的类型中精度最多只有二十多位，因而在此我们采取用线性表的顺序和链表存储结构的方式来存放大数,解决一些关于大数的运算应用，原来此问题在现实生活中实用性很强，诸如密码学特别是RSA加密方面、物理研究学、生物学、化学中有特殊应用。目 录课程设计任务书2摘 要3第一部分 课程设计内容与理论基础5第二部分 课程设计算法构造思想6第三部分 课程设计模块划分及其功能7第四部分 课程设计使用说明和运行结果8第五部分 参考文献9第六部分 附 录9第一部分 课程设计内容与理论基础1.课程设计内容在我们常用的32位计算中，CPU中加减乘除的一次运算是32位的值，也就是说2的32次方的一个值，这就是说1加上1的CPU工作量和小于2的32的两位数相加是用的相同的周期。为了避免运算结果大于2的32次，因为大于的话又会造成一次CPU周期运算，但这样当然也可以做。但建议用下面方法，考虑乘法的原因，两个2的16次方相乘就是2的32次方的情况，所以我们定义了本程序算法，结点数巨减，主要是开内存方面，有了极大的减少。本设计要求分别利用线性表的两种存储结构，定义存储结构均采用了数据结构中的抽象数据类型，而抽象数据类型是指一个数据模型以及定义在改模型上的一组操作C语言中定义的类型中精度最多只有二十多位，因而在此我们采取用线性表的顺序和链表存储结构的方式来存放大数,解决一些关于大数的运算应用(大数计算的因数和结果精度一般是少则数十位，多则几万位),设计算法完成对大数的阶乘、加法、乘法的求解。例如：1、阶乘运算的测试数据：60!2、加法运算的测试数据： 9876876787+89678967559999 3、乘法运算的测试数据：9876876787896789675599992.课程设计理论基础本次课程设计使用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数据对象：D=ai|aiElemSet,i=1,2,n,n=0数据关系：R1=|ai-1,aiD,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|aiElemSet,i=1,2,n,n=0数据关系：R1=|ai-1,aiD,i=2,n 约定an端为栈顶，a1为栈底。基本操作： InitStack(&S) 操作结果：构造一个空栈S。 DestoryStack(&S) 初始条件：栈S已存在。 操作结果：栈S被销毁。 Push(&S，e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。 StackTraverse(S,visit() 初始条件：栈S已存在且非空。操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit()。一旦visit()失败，则操作失败。第二部分 课程设计算法构造思想1、阶乘运算的算法思想：一个数的阶乘，利用一个顺序表来存储结果，首先令L.elem0=1，其他全部赋值为零，再用for循环，从1至i完成阶乘运算，其中由于位数越乘越多，故将其按位存储在顺序表中，防止数据范围溢出，在逐位相乘中，利用for循环位数，如若有进位问题，每次运算时，此位保留的数位，t=L.elemj*i+jw; L.elemj=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倒着赋值，同时因为传入和保存的都是字符，所以计算时要将字符转化为数字；从低位向高位乘，在竖式计算中，我们是将乘数第一位与被乘数的每一位相乘，记录结果，之后，用第二位相乘，记录结果并且左移一位，以此类推，直到计算完最后一位，再将各项结果相加，得出最后结果。当然我们可以直接用这种方法，但要用多个数据来保存计算出的分结果， 之后结果再相加得到最后结果，但是这样会浪费很多空间，所以我们可以再优化一下，就是只用一个顺序表来表示结果，先把第一位乘数与被乘数的结果保存在链表中，之后把存储结果的和第二次如此算的结果加在第一次的基础上，二者使用同一个顺序表来表示，以此类推，直到结束，这样就可以用一个顺序表来存储相乘后的结果。另外在运算时乘和加都有进位时要处理，就和大数加法中进位采取方法一样，当前的值加上进位的值再看本位数字是否又有进位就行。第三部分 课程设计模块划分及其功能系统程序的组成框图主函数对各个函数的调用关系图。 大数的运算1、 大数的阶乘运算2、 大数的加法运算3、 大数的加法运算4、 大数的乘法运算5、 返回0、 退出4、调用void multiply()函数3、调用void addition()函数5、该选项作用是返回主菜单0、退出系统，安全退出2、调用void addition1()函数1、调用void factorial()函数void multiply()，利用顺序存储结构完成大数的乘法void addition()，利用顺序存储结构完成大数的加法voidaddition1()，将字符串转换为整形数组，反向传入链表中赋值，并利用链式存储结构完成大数的加法运算，最后用栈来输出结果void factorial()，利用顺序存储结构完成大数阶乘运算Void StrToNum2(SqList *a,char *s)，将字符串转换为整形数组，反向赋值Int StrToNum1(SqList L,char *a)，将字符串转换为整形数组，正向赋值；第四部分 课程设计使用说明和运行结果1. 课程设计使用说明 在选择适当的运行环境中（例如DEV_C+）,可以使用C工程进行编译，主要是在.C窗口中进行上机测试，当打开运行窗口时，根据页面上的提示信息进行试验，采用顺序存储结构完成大数的阶乘运算，采用链式存储结构完成大数的加法运算，选择合适的存储结构完成大数的乘法运算。例如按要求输入以下数据：1、阶乘运算的测试数据：60!2、加法运算的测试数据：9876876787+89678967559999 3、乘法运算的测试数据：987687678789678967559999测验结果可以再运行窗口中显示详细信息(可在下面文件中看到)。2. 课程设计程序运行结果程序的测试结果如下：1、阶乘运算：2、（链式和栈存储结构）加法运算3、（顺序表）加法运算4、乘法运算 第五部分 参考文献1 严蔚敏，数据结构 C语言，清华大学出版社。 2 谭浩强，c语言程序设计，清华大学出版社。第六部分 附 录#include #include #include #define N 100typedef int ElemType;/* 1.顺序表的存储结构 */typedef struct ElemType *elem;int length; SqList;/* 2.链表的存储结构 */typedef struct LNodeElemType data;struct LNode *next; LNode,*LinkList;/* 3.链栈的存储结构 */typedef struct SNode ElemType data; struct SNode *next; SNode, *LinkStack;/* 4.初始化顺序表*/void InitList(SqList *L) L-elem=(ElemType*)malloc(2*N)*sizeof(ElemType); L-length=0; /* 5.初始化链表 */void InitLink(LinkList *L) *L=(LinkList)malloc(sizeof(LNode); (*L)-next=NULL; /*6.初始化链栈(没有头结点) */void InitStack(LinkStack *top) *top=NULL; /*7.销毁顺序表*/void DestroyList(SqList *L) free(L-elem); /*8.清空顺序表 */void ClearList(SqList *L) L-length=0; /*9.顺序表长度 */int ListLength(SqList L) return L.length; /*10.遍历顺序表并输出(数组下标法) */void ListTravarsa(SqList L) int i; printf(nList:t); for(i=0; idata=e;new-next=*top; *top=new; /*12.遍历链栈并输出: 栈顶向栈底方向输出 */void StackTraverse(LinkStack top) LinkStack p; p=top; while (p) printf(%d,p-data);p=p-next; /*13.后接法建立链表 */void CreateList2(LinkList *L, char *a) LinkList p,new; int i; int len=strlen(a); p=*L; for(i=0;ai!=0;i+) new=(LinkList)malloc(sizeof(LNode); new-data=alen-i-1-48; p-next=new; p=p-next; p-next=NULL; /*14.实现阶乘的运算 */void factorial() SqList L; int n,i,j,t,jw,top; InitList(&L); printf(n输入求阶乘的数:); scanf(%d,&n);L.elem0=1; top=0; for(i=1;iN;i+) L.elemi=0; for(i=1; i=n; i+) jw=0; for(j=0; j=top & jw=0) top=j; break; printf(%d!=,n); for(i=top; i=0; i-) printf(%d,L.elemi);/*15.（链表和栈）实现加法的运算 */void addition1() int jw=0;/jw表示进位 char aN,bN;LinkStack top; LinkList L1,L2,sum,p,q,r,new; printf(n(链表和栈方法)输入大数加法的第一个数:); scanf(%s,a); printf(n(链表和栈方法)输入大数加法的第二个数:); scanf(%s,b); InitLink(&L1);InitLink(&L2);InitLink(&sum);InitStack(&top);CreateList2(&L1,a); CreateList2(&L2,b); p=L1-next;q=L2-next; r=sum;while(p&q) new=(LinkList)malloc(sizeof(LNode); new-data=(p-data+q-data+jw)%10; new-next=NULL; jw=(p-data+q-data+jw)/10; p=p-next;q=q-next; r-next=new;r=r-next; while(p) new=(LinkList)malloc(sizeof(LNode); new-data=(p-data+jw)%10; new-next=NULL; jw=(p-data+jw)/10; p=p-next; r-next=new;r=r-next; while(q) new=(LinkList)malloc(sizeof(LNode); new-data=(q-data+jw)%10; new-next=NULL; jw=(q-data+jw)/10; q=q-next; r-next=new;r=r-next; if(jw!=0) new=(LinkList)malloc(sizeof(LNode); new-data=jw;/解决最高位的进位问题 new-next=NULL; r-next=new;r=r-next; printf(%s+%s=,a,b);r=sum-next;while(r)Push(&top,r-data);r=r-next;StackTraverse(top);/*16.（顺序表）实现大数的加法运算 */int StrToNum1(SqList L,char *a) int i; for(i=0;ai!=0;i+) /把字符串转化成整形数组 L.elemi=ai-48; i-;/i回退1，则i对应的最后一个字符就不是0 return i;void addition() int i,j,k,m,jw=0;/jw表示进位 char aN,bN; SqList L1,L2,sum; printf(nn（顺序表）输入大数加法的第一个数:); scanf(%s,a); printf(（顺序表）输入大数加法的第二个数:); scanf(%s,b); InitList(&L1);InitList(&L2); InitList(&sum); i=StrToNum1(L1,a); j=StrToNum1(L2,b);if(ij)/把位数较大的下标记下来 k=i; else k=j; m=k+1; for(k=k+1;i=0 & j=0;k-,i-,j-)/求和 sum.elemk=(L1.elemi+L2.elemj+jw)%10; jw=(L1.elemi+L2.elemj+jw)/10; if(j=0;i-,k-) sum.elemk=(L1.elemi+jw)%10; jw=(L1.elemi+jw)/10; if(i=0;j-,k-) sum.elemk=(L2.elemj+jw)%10; jw=(L2.elemj+jw)/10; sum.elemk=jw;/解决最高位的进位问题 printf(%s+%s=,a,b); for(k=0;k=m;k+) if(sum.elem0=0 & k=0) continue; else printf(%d,sum.elemk); /*17.顺序表赋值*/void StrToNum2(SqList *a,char *s) int i; int len = strlen(s); /对数组初始化 for(i = 0; i N; +i) (*a).elemi=0; for(i = 0; i len; +i) (*a).elemlen-1-i=*(s+i)-0;/给*a赋值 /*18.实现大数的乘法运算*/ void multiply()/将数组a与数组b逐位相乘以后存入数组c SqList a,b,c; char s1N,s2N; int i,j; int k = 2*N-1; InitList(&a);InitList(&b); InitList(&c);printf(nn输入大数乘法的第一个数:); scanf(%s,s1); printf(输入大数乘法的第二个数:); scanf(%s,