数据结构实验报告二.doc

XXX计算机学院数据结构课程实验报告实验二姓 名 ： 学 号 ： 专 业 ： 完成日期 ： XXXX计算机学院一、实验目的1. 理解顺序存储和链接存储的基本思想。2. 掌握顺序表和链表基本操作的实现。3. 理解顺序表和链表的优缺点。二、实验内容1. 利用顺序表实现大整数求和。（必做）2. 利用单链表实现一元多项式求和。（必做）3. 约瑟夫环问题：设有编号为1，2，n的n ( n 0 ) 个人围成一个圈，每个人持有一个密码m，从第1个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，。如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。（选做）三、算法描述第一道题：1.输入两个大整数给字符型数组，初始化顺序表A和B。 2.字符型数组中的大整数由低位依次转化整数并放入为顺序表A 和B中。 3将大整数相加。 3.1.初始化进位标志flag=0和顺序表C； 3.2.求大整数A和B的长度：n=A.length; m=B.length; 3.3.从个位开始逐位开始第i位的加法，直到A或B计算完毕： 3.3.1 计算第i位的值：C.datai=(A.datai+B.datai+flag)%10; 3.3.2 计算该进位的进位：flag=(A.datai+B.datai+flag)/10; 3.4.计算大整数A或B余下的部分，与进位flag相加； 3.5.计算结果的位数。 4.用逆遍历arcPrintList()输出C。第二道题：1.工作指针pre、p、qre、q初始化； 2.while（p存在且q存在）执行下列三种情形之一 2.1 如果p-exp小于q-exp,则指针p后移； 2.2 如果p-exp大于q-exp,则 2.2.1 将结点q插入到结点p之前； 2.2.2指针q指向原指结点的下一个结点； 2.3 如果p-exp等于q-exp，则 2.3.1 p-coef =p-coef+q-coef; 2.3.2 如果p-coef=0,则执行下列操作，否则，指针p后移； 2.3.3 删除结点q; 2.3.4 使指针q指向它原指结点的下一个结点； 3.如果q不为空，将结点q链接在第一个单链表的后面；四、程序清单说明第一题:在cpp文件中，strlen()函数用来求字符型数组的长度。 在main.h头文件中，1. SeqList(DataType a,int n)函数是建立长度为n的顺序表。2. Change(SeqList A,char B,int n)函数中A.datab=a*10+Bi-0是将字符串数组的内容转换成整数，并输入顺序表A中。3. friend SeqList Add(SeqList A,SeqList B) 友元函数是将顺序表A与顺序表B的值相加。在Add函数中，C.length=(nm?n:m)+flag是判断A与B的哪个表长度更长和表C的长度；if运算到最后存在进位flag=1，则 C.dataC.length-1=1。3.1 for(;in;i+)是计算大整数A与B相加后，余下的部分。3.2 for(;im;i+)是计算大整数B与A相加后，余下的部分。 4. arcPrintList()函数是用逆向，由高位到低位输出表C。第二题：五、实验结果第一题：输入第一个大整数:123 输入第二个大整数:987; 输出计算的结果为:1110; 第二题:六、实验总结 这次实验对我来说,很难.让我纠结了好久。最后还是没能把第二道题必做的一元多项式求和做出来。链表很难。逻辑性对我来说有点复杂。做第一题用顺序表求和，不是很难。对于我来说，难在大整数的输入后，高位是排在前面的，在用顺序表求和时，是要把低位移前，这有点难度。最后我用字符型输入，再转化成整数，这字符数组转化成整型的过程，我忘了，经过网上查了和看了书本，才发现这过程很简单。从这方面，我知道我的C+基础没打好，这么简单的