數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告.doc

數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)一線性表實(shí)驗(yàn)1、約瑟夫問(wèn)題求解一問(wèn)題描述設(shè)有編號(hào)為1，2，n（n0)的個(gè)人圍成一個(gè)圈，每個(gè)人持有一個(gè)密碼m。從第1個(gè)人開(kāi)始報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)，報(bào)m的人出圈，再?gòu)乃南乱粋€(gè)人起重新報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)，報(bào)m的出圈如此下去，直到所有人全部出圈為止。當(dāng)任意給定n和m后，設(shè)計(jì)算法求n個(gè)人出圈的次序。二基本要求（1）建立模型，確定存儲(chǔ)結(jié)構(gòu)（2）對(duì)任意n個(gè)人，密碼為m，實(shí)現(xiàn)約瑟夫問(wèn)題（3）出圈次序依次輸出三本實(shí)驗(yàn)用到的理論知識(shí)該實(shí)驗(yàn)主要要求用線性表完成一些具體問(wèn)題的應(yīng)用，在實(shí)驗(yàn)中需用到順序表的定義，循環(huán)單鏈表的建立以及節(jié)點(diǎn)類型的選擇等問(wèn)題，將用到模板函數(shù)LinkList，其中各頭文件的定義如下：順序表結(jié)點(diǎn)類型：templatestructNodeTdata；/存放個(gè)人的編號(hào)Node*next；/存放個(gè)人的密碼；單鏈表結(jié)點(diǎn)類型單鏈表Node.h：templatestructNodeTdata；/存放個(gè)人的編號(hào)Tcode；/存放個(gè)人密碼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個(gè)元素的單鏈表；四主要算法（1）順序表存儲(chǔ)時(shí)A、m相同voidJosephus(inta,intn,intm)ints=0；/length表示表長(zhǎng)cout=2；length-)/表示每次減一s=(s+m-1)%length；coutassetw(7)；/s為第s個(gè)人for(inti=s+1；ilength；i+)ai-1=ai；/刪除couta0endl；/最后只剩下一個(gè)人B、m不同voidJosephus(Nodedata,intn,intm)ints=0,k；/k用于保存出圈人的密碼cout個(gè)人的編號(hào)和密碼分別為：=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）循環(huán)單鏈表存儲(chǔ)時(shí)A、m相同voidJosephus(LinkList*d,intm)Node*p=d-first,*pre,*last=d-first；intcount；cout出隊(duì)序號(hào)為: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圈中出隊(duì)人的編號(hào)和密碼分別為: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；五主函數(shù)實(shí)現(xiàn)（1）順序表時(shí)A、m相同voidmain()intn,m,a100；cout請(qǐng)輸入圈中人的個(gè)數(shù)n(n0)和出圈人的序號(hào)m(m=0)：nm；while(n100|n=0|m0)cout輸入有誤,請(qǐng)重新輸入!n；cout請(qǐng)輸入圈中人的個(gè)數(shù)n(n=0)：nm；cout出圈人的順序?yàn)?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請(qǐng)輸入圈中的總?cè)藬?shù)n(n0)和初始的報(bào)數(shù)上限m(m=0):nm；while(n100|n=0|m0)cout輸入有誤,請(qǐng)重新輸入數(shù)據(jù)!n；cout請(qǐng)輸入圈中的總?cè)藬?shù)n(n=100)和初始的報(bào)數(shù)上限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）單鏈表時(shí)A、m相同voidmain()intm,n,a100,b100；cout請(qǐng)輸入圈中的總?cè)藬?shù)n(n0)和出圈人的編號(hào)m(m=0):nm；while(n100|n=0|m0)cout您輸入有誤，請(qǐng)重新輸入數(shù)據(jù)!n；cout請(qǐng)輸入圈中的總?cè)藬?shù)n(n0)和出圈人的編號(hào)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請(qǐng)輸入圈中的總?cè)藬?shù)n(n0)和初始出隊(duì)數(shù)m(m0):nm；while(n100|n=0|m=0)cout您的輸入有誤，請(qǐng)按要求輸入數(shù)據(jù)!n；cout請(qǐng)輸入圈中的總?cè)藬?shù)n(n0)和初始出隊(duì)數(shù)m(m0):nm；for(inti=0；in；i+)ai=i+1；bi=2*(i+1)；LinkListdata(a,b,n)；Josephus(&data,m)；六、運(yùn)行結(jié)果（1）順序表實(shí)現(xiàn)A、m相同B、m不同（2）單鏈表實(shí)現(xiàn)A、m相同B、m不同2、一元代數(shù)多項(xiàng)式求和一、結(jié)點(diǎn)類型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；三、主函數(shù)實(shí)現(xiàn)#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