数据结构实验报告二

《数据结构实验报告二》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、XXX计算机学院数据结构课程实验报告实验二姓名：学号：专业：完成日期：XXXX计算机学院4一、实验目的1.理解顺序存储和链接存储的基本思想。2.掌握顺序表和链表基本操作的实现。3.理解顺序表和链表的优缺点。二、实验内容1.利用顺序表实现大整数求和。（必做）2.利用单链表实现一元多项式求和。（必做）3.约瑟夫环问题：设有编号为1，2，……，n的n(n>0)个人围成一个圈，每个人持有一个密码m，从第1个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈

2、，……。如此下去，直到所有人全部出圈为止。当任意给定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.data[i]=(A.data[i]

3、+B.data[i]+flag)%10;3.3.2计算该进位的进位：flag=(A.data[i]+B.data[i]+flag)/10;3.4.计算大整数A或B余下的部分，与进位flag相加；3.5.计算结果的位数。4.用逆遍历arcPrintList()输出C。第二道题：1.工作指针pre、p、qre、q初始化；2.while（p存在且q存在）执行下列三种情形之一42.1如果p->exp小于q->exp,则指针p后移；2.2如果p->exp大于q->exp,则2.2.1将结点q插入到结点p之前

4、；2.2.2指针q指向原指结点的下一个结点；2.3如果p->exp等于q->exp，则2.3.1p->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(DataTypea[],intn)函数是

5、建立长度为n的顺序表。2.Change(SeqListA,charB[],intn)函数中A.data[b]=a*10+B[i]-‘0’是将字符串数组的内容转换成整数，并输入顺序表A中。3.friendSeqListAdd(SeqListA,SeqListB)友元函数是将顺序表A与顺序表B的值相加。在Add函数中，C.length=(n>m?n:m)+flag是判断A与B的哪个表长度更长和表C的长度；if运算到最后存在进位flag==1，则C.data[C.

6、length-1]=1。3.1for(;i

7、和，不是很难。对于我来说，难在大整数的输入后，高位是排在前面的，在用顺序表求和时，是要把低位移前，这有点难度。最后我用字符型输入，再转化成整数，这字符数组转化成整型的过程，我忘了，经过网上查了和看了书本，才发现这过程很简单。从这方面，我知道我的C++基础没打好，这么简单的都忘了。所以，我应该多回去翻翻看看C++的书，温习以前的知识，这样编程起来，才不会那么吃力。在第二题中，我发现，我还是看不懂。纠结了好久，还是没能编写出正确的cpp文件出来。4