《[工学]数据结构与算法》由会员分享，可在线阅读，更多相关《[工学]数据结构与算法（49页珍藏版）》请在金锄头文库上搜索。
1、数据结构与算法实验报告学 号： 20101003342 班级序号： 116101-20 姓 名： 程 子 洋 授课老师： 陈 占 龙 吴 亮中国地质大学（武汉）信息工程学院信息工程系2011年11月实习一【线性表及应用】【实习目的】本次实习的主要目的在于熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉各种链表的操作为侧重点。【实习题目】 n（n20）的阶乘【问题描述】大数运算计算 n的阶乘（ n=20）。【基本要求】（1）数据的表示和存储；（1.1）累积运算的中间结果和最终的计算结果的数据类型要求是整型 这是问题本身的要求；（1.2）试设计合适的存储结构，要求每个元素或结点最多存储数据的
2、 3位数值。（2） 数据的操作及其实现：基于设计的存储结构实现乘法操作，要求从键盘上输入 n值；在屏幕上显示最终计算结果。【测试数据】（1）n20，n！2432902008176640000 （2）n30，n！265252859812191058636308480000000 【实现提示】（1）设计数据的存储结构：介于阶乘运算的精确性以及实型数据表示的不精确性，本题不能采用实型表示累积运算的中间结果和最终的计算结果，而只能用整型。然而由于普通整型和长整型所能表述数的范围受其字长的限制，不能表示大数阶乘的累积结果，故必须设计一个合适的数据结构实现对数据的存储，例如可以让每个元素或结点存储数据的若
3、干位数值。从问题描述不难看出 n值为任意值，故为使程序尽量不受限制，应采用动态存储结构。（2） 数据的操作及其实现：（2.1） 累积运算的特点是当前的计算结果是下次乘法运算的乘数；（2.2） 实现两个数的乘法运算须考虑： （a）乘数的各位数都要与被乘数进行乘法运算； （b） 乘法过程中的进位问题及其实现； （c） 因每个元素或结点最多存储数据的 3位数值，故当元素或结点中的数值大于 999，需向前一个元素或结点进位。（3）要求采用链式存储结构实现（普通单链表，循环单链表，普通双项链表和双向循环链表中任选一种结构）。【算法思想】首先，定义两个整型的数组： int fac1000;/暂且先设定是1
4、000位，我称之为“结果数组” int add1000;/我称之为“进位数组” 现在具体说明两个数组的作用： 1. fac1000 比如说，一个数5的阶乘是120，那么我就用这个数组存储它： fac0=0 fac1=2 fac2=1 现在明白了数组fac的作用了吧。用这样的数组我们可以放阶乘后结果是1000位的数。 2. 在介绍add1000之前，我介绍一下算法的思想，就以6！为例： 从上面我们知道了5！是怎样存储的。 就在5！的基础上来计算6！，演示如下： fac0=fac0*6=0 fac1=fac1*6=12 fac2=fac2*6=6 3. 现在就用到了我们的：“进位数组”add100
5、0. 先得说明一下：add就是在第2步中用算出的结果中，第i位向第i+1位的进位数值。还是接上例： add0=0; add1=1; / 计算过程：就是 (fac1+add0) % 101 add2=0; / 计算过程：就是 (fac2+add1) % 10=0 . . . addi+1 =( faci+1 + add ) % 10 现在就知道了我们的数组add是干什么的了吧，并且明白了add是如何求得的了吧。 4. 知道了add1000的值，现在就在 1. 和 3 . 两步的基础上来计算最终的结果。（第2步仅作为我们理解的步骤，我们下面的计算已经包含了它） fac0 = ( fac0*6 )
6、mod 10 =0 fac1 = ( fac1*6 + add0 ) mod 10 2 fac2 = ( fac2*6 + add1 ) mod 10=7 到这里我们已经计算完了6！。然后就可以将数组fac1000中的数，以字符的形式按位输出到屏幕上了。 5. 还有一点需要说明，就是我们需要一个变量来记录fac1000中实际用到了几位，比如5！用了前3位； 我们在这里定义为 top 为了计算top，我们有用到了add1000,还是以上面的为例： 5！时，top=3,在此基础上我们来看6！时top=? 由于 add2=0 所以 top=3（没有变） 也就是说，如果最高位有进位时，我们的top=t
7、op+1,否则，top值不变。 6. 总结一下，可以发现，我们把阶乘转化为 两个10以内的数的乘法，还有两个10以内的数的家法了。 因此，不管再大的数，基本上都能算出了，只要你的数组够大就行了。【代码部分】/ Big.cpp/定义控制台应用程序的入口点#include stdafx.h#include llist.h#include xcept.h#include using namespace std;int _tmain(int argc, _TCHAR* argv)LinearList L(200000); /声明一个线性表有个元素int i,j,k,n,l;L.Insert(0,1);
8、 /将放入线性表中成为它的第一个元素coutn; /输入一个你将要算阶乘的数字if(n=0|n=1) /0和的阶乘为cout L endl; /输出else /如果输入的数字大于for(i=1;i=n;i+)int j_last=L.Length(); /j_last的值为线性表中的已有的元素个数L.Length()for(j=1;j=j_last;j+)L.Find (j,k); /依次找到线性表中的第j个元素（j=1,2,3j_last)k=i*k; /每一次循环的时候线性表中的第j个元素k与i相乘/n次循环后相当于是k=1*2*3*nL.Update(j,k); /将变化后的k从新放到第
9、j个元素中for(j=1;j=1000) /如果它超过了三位数字if (j j_last) /如果第j个元素不是线性表中的最后一个L.Find(j+1,l);/就将j的后一个元素找到并存入l中else /如果j就是最后一个元素L.Insert(j, 0);/那么就在这个元素后面插入一个相当于是将线性表开辟一个元素l=0; /给l赋初值l+=k/1000; /l是k的进位当l更新的时候加的就是进位L.Update(j+1,l); /把进位值更新k=k%1000; /进位后余下的数字L.Update(j,k);coutL.Reverse()endl;return 0;/ file llist.h/
10、 formula-based linear list#ifndef LinearList_#define LinearList_#include #include #include #include xcept.husing namespace std;templateclass LinearList public: LinearList(int MaxListSize = 10); / constructor LinearList() delete element; / destructor bool IsEmpty() const return length = 0; int Length
11、() const return length; bool Find(int k, T& x) const; / return the kth element of list in x int Search(const T& x) const; / return position of x LinearList& Delete(int k, T& x); / delete kth element and return in x LinearList& Insert(int k, const T& x); / insert x just after kth element LinearList&
12、Update(int k,T& x); LinearList& Reverse( ); void Output(ostream& out) const; private: int length; int MaxSize; T *element; / dynamic 1D array;templateLinearList:LinearList(int MaxListSize)/ Constructor for formula-based linear list. MaxSize = MaxListSize; element = new TMaxSize; length = 0;templatebool LinearList:Find(int k, T& x) const/ Set x to the kth element of the list. / Return false if no kth; true otherwise. if (k length) return false; / no kth x = elementk - 1; return
