数据结构实验报告.doc

数据结构实验报告实验一线性表实验1、约瑟夫问题求解一问题描述设有编号为1，2，n（n0)的个人围成一个圈，每个人持有一个密码m。从第1个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。二基本要求（1）建立模型，确定存储结构（2）对任意n个人，密码为m，实现约瑟夫问题（3）出圈次序依次输出三本实验用到的理论知识该实验主要要求用线性表完成一些具体问题的应用，在实验中需用到顺序表的定义，循环单链表的建立以及节点类型的选择等问题，将用到模板函数LinkList，其中各头文件的定义如下：顺序表结点类型：templatestructNodeTdata；/存放个人的编号Node*next；/存放个人的密码；单链表结点类型单链表Node.h：templatestructNodeTdata；/存放个人的编号Tcode；/存放个人密码Node*next；单链表模板：#include单链表Node.htemplateclassLinkListpublic:Node*first；LinkList(Ta,Tb,intn)first=newNode；first-data=a0；first-code=b0；Node*r=first,*s；for(inti=1；in；i+)s=newNode；s-data=ai；s-code=bi；r-next=s；r=s；r-next=first；/建立有n个元素的单链表；四主要算法（1）顺序表存储时A、m相同voidJosephus(inta,intn,intm)ints=0；/length表示表长cout=2；length-)/表示每次减一s=(s+m-1)%length；coutassetw(7)；/s为第s个人for(inti=s+1；ilength；i+)ai-1=ai；/删除couta0endl；/最后只剩下一个人B、m不同voidJosephus(Nodedata,intn,intm)ints=0,k；/k用于保存出圈人的密码cout个人的编号和密码分别为：=2；length-)if(length=n)s=(s+m-1)%length；elses=(s+k-1)%length；k=datas.next-data；coutdatas.data,kt；for(inti=s+1；ilength；i+)datai-1=datai；coutdata0.data,dataendl；（2）循环单链表存储时A、m相同voidJosephus(LinkList*d,intm)Node*p=d-first,*pre,*last=d-first；intcount；cout出队序号为:next!=d-first)last=last-next；while(p-next!=p)count=m；if(count=1)coutdatanext；deletepre；last-next=p；elsewhile(-count)pre=p；p=p-next；coutdatanext=p-next；deletep；p=pre-next；coutdataendl；deletep；B、m不同voidJosephus(LinkList*d,intm)Node*p,*pre,*last=d-first；intcode=m；p=d-first；cout圈中出队人的编号和密码分别为:next!=d-first)last=last-next；while(p-next!=p)if(code=1)coutdata,codenext=p-next；code=p-code；deletep；p=last-next；elsewhile(-code)pre=p；p=p-next；coutdata,codecode；pre-next=p-next；deletep；p=pre-next；coutdata,codeendl；deletep；五主函数实现（1）顺序表时A、m相同voidmain()intn,m,a100；cout请输入圈中人的个数n(n0)和出圈人的序号m(m=0)：nm；while(n100|n=0|m0)cout输入有误,请重新输入!n；cout请输入圈中人的个数n(n=0)：nm；cout出圈人的顺序为:n；for(inti=0；in；i+)ai=i+1；cout第i+1人；coutendl；Josephus(a,n,m)；B、m不同voidmain()intn,m；Nodedata100,code100；cout请输入圈中的总人数n(n0)和初始的报数上限m(m=0):nm；while(n100|n=0|m0)cout输入有误,请重新输入数据!n；cout请输入圈中的总人数n(n=100)和初始的报数上限m(m=n):nm；for(inti=0；in；i+)codei.data=2*(i+1)；codei.next=NULL；for(i=0；in；i+)datai.data=i+1；datai.next=&codei；Josephus(data,n,m)；（2）单链表时A、m相同voidmain()intm,n,a100,b100；cout请输入圈中的总人数n(n0)和出圈人的编号m(m=0):nm；while(n100|n=0|m0)cout您输入有误，请重新输入数据!n；cout请输入圈中的总人数n(n0)和出圈人的编号m(m=0):nm；for(inti=0；in；i+)ai=i+1；bi=m；LinkListdata(a,b,n)；Josephus(&data,m)；B、m不同voidmain()inta100,b100,m,n；cout请输入圈中的总人数n(n0)和初始出队数m(m0):nm；while(n100|n=0|m=0)cout您的输入有误，请按要求输入数据!n；cout请输入圈中的总人数n(n0)和初始出队数m(m0):nm；for(inti=0；in；i+)ai=i+1；bi=2*(i+1)；LinkListdata(a,b,n)；Josephus(&data,m)；六、运行结果（1）顺序表实现A、m相同B、m不同（2）单链表实现A、m相同B、m不同2、一元代数多项式求和一、结点类型PNode.htemplatestructPNodeTcoef；Texp；PNode*next；二、链表定义LinkList.h#includePNode.htemplateclassLinkListpublic:PNode*first；LinkList(Ta,Tb,intn)；templateLinkList:LinkList(Ta,Tb,intn)first=newPNode；PNode*r=first,*s；for(inti=0；in；i+)s=newPNode；s-coef=ai；s-exp=bi；r-next=s；r=s；r-next=NULL；三、主函数实现#include#includeLinkList.hLinkList*Add(LinkList*A,LinkList*B)PNode*pre,*qre,*p,*q,*v；pre=A-first；p=pre-next；qre=B-first；q=qre-next；while(p&q)if(p-expexp)pre=p；p=p-next；elseif(p-expq-exp)v=q-next；pre-next=q；q-next=p；q=v；elsep-coef=p-coef+q-coef；if(p-coef=0)pre-next=p-next；deletep；p=pre-next；elsepre=p；p=p-next；qre-next=q-next；deleteq；q=qre-next；if(q)pre-next=q；deleteB-first；returnA；voidSort(LinkList*A)/将链表按升序排序PNode*p,*q,*r,*s；if(A-first-next&A-first-next-next)s=A-first-next；q=s-next；while(q)r=A-first；p=r-next；while(pexpexp)r=p；p=p