中国地质大学(武汉)信息工程学院_数据结构实习报告.docxVIP

《数据结构》课程设计学生姓名： 占 昭 班 学 号： 20111003494 指导教师： 吴 亮 中国地质大学（武汉）信息工程学院 2012 年 11 月1.题目: n（n20）的阶乘【问题描述】 大数运算——计算n的阶乘（n=20）。【基本要求】 （1）数据的表示和存储； （1.1） 累积运算的中间结果和最终的计算结果的数据类型要求是整型——这是问题本身的要求； （1.2） 试设计合适的存储结构，要求每个元素或结点最多存储数据的3位数值。 （2）数据的操作及其实现： 基于设计的存储结构实现乘法操作，要求从键盘上输入n值，在屏幕上显示最终计算结果。【测试数据】 （1）n＝20，n！＝2432902008176640000 （2）n＝30，n！＝265252859812191058636308480000000【实现提示】1）设计数据的存储结构： 介于阶乘运算的精确性以及实型数据表示的不精确性，本题不能采用实型表示累积运算的中间结果和最终的计算结果，而只能用整型。然而由于普通整型和长整型所能表述数的范围受其字长的限制，不能表示大数阶乘的累积结果，故必须设计一个合适的数据结构实现对数据的存储，例如可以让每个元素或结点存储数据的若干位数值。 从问题描述不难看出n值为任意值，故为使程序尽量不受限制，应采用动态存储结构【可采用的数据结构】 （1）采用链式存储结构实现（普通单链表，循环单链表，普通双项链表和双向循环链表中任选一种结构）。 （2）采用动态数组实现。设计思路：本题思路较为简单,将大数数存于一个数组里,每个元素存一个3位数,然后设计好数与数之间的乘法,已经将数存入数组的函数即可;输入：（1）n＝20，输出：n！＝2432902008176640000输入：（2）n＝30，输出：n！＝265252859812191058636308480000000////////////////////////////////////////////////////////////////////////////////////////////源码：// test21.cpp : Defines the entry point for the console application.//#include stdafx.h#include iostreamusing namespace std;int trans(int b[],int a);int mult(int *b,int l,int *c,int n);void OutPut(int b[],int k);int add(int b[],int k);int main(int argc, char* argv[]){int c[60];memset(c,0,60);int i(1);int L=trans(c,i);//////将i存入c中int b[60];memset(b,0,60);int sum(1);int k=trans(b,sum);//////把sum存入b中int n;cinn;while(n--){k=mult(b,k,c,L);//sum=i*sumL=add(c,L);//i++}OutPut(b,k);return 0;}int trans(int b[],int a)//////////把a存入b中{int i=0;memset(b,0,60);while(a!=0){b[i++]=a%1000;a=a/1000;}//////////////////////////////////每三位存入数组b中return i;////b的位数（3个3个的）}int mult(int *b,int l,int *c,int n)//l为b的长度{int s[60];memset(s,0,60);for(int j=0;jn;j++)/////////////////////////c{for(int i=0;il;i++)///////////////b{s[i+j]+=b[i]*c[j];////s【k】：b中第i+j位的数之和}}int max=n+l-1;//当前长度for(int i=0;imax;i++){b[i]=s[i];}for (int k=0;kmax;k++)///////////////////////进位操作{if (b[k]999){int s=b[k]/1000;b[k]%=1000;b[k+1]+=s;}}if(b[max]!=0) ++max;return max;}void OutPut(int b[],int k)//输出结果{for(int i=0;ik;i++){if(i==0) coutb[k-i-1];//首位不