數(shù)據(jù)結構實驗報告.doc

數(shù)據(jù)結構實驗報告實驗一線性表實驗1、約瑟夫問題求解一問題描述設有編號為1，2，n（n0)的個人圍成一個圈，每個人持有一個密碼m。從第1個人開始報數(shù)，報到m時停止報數(shù)，報m的人出圈，再從他的下一個人起重新報數(shù)，報到m時停止報數(shù)，報m的出圈如此下去，直到所有人全部出圈為止。當任意給定n和m后，設計算法求n個人出圈的次序。二基本要求（1）建立模型，確定存儲結構（2）對任意n個人，密碼為m，實現(xiàn)約瑟夫問題（3）出圈次序依次輸出三本實驗用到的理論知識該實驗主要要求用線性表完成一些具體問題的應用，在實驗中需用到順序表的定義，循環(huán)單鏈表的建立以及節(jié)點類型的選擇等問題，將用到模板函數(shù)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）循環(huán)單鏈表存儲時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；五主函數(shù)實現(xiàn)（1）順序表時A、m相同voidmain()intn,m,a100；cout請輸入圈中人的個數(shù)n(n0)和出圈人的序號m(m=0)：nm；while(n100|n=0|m0)cout輸入有誤,請重新輸入!n；cout請輸入圈中人的個數(shù)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請輸入圈中的總人數(shù)n(n0)和初始的報數(shù)上限m(m=0):nm；while(n100|n=0|m0)cout輸入有誤,請重新輸入數(shù)據(jù)!n；cout請輸入圈中的總人數(shù)n(n=100)和初始的報數(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）單鏈表時A、m相同voidmain()intm,n,a100,b100；cout請輸入圈中的總人數(shù)n(n0)和出圈人的編號m(m=0):nm；while(n100|n=0|m0)cout您輸入有誤，請重新輸入數(shù)據(jù)!n；cout請輸入圈中的總人數(shù)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請輸入圈中的總人數(shù)n(n0)和初始出隊數(shù)m(m0):nm；while(n100|n=0|m=0)cout您的輸入有誤，請按要求輸入數(shù)據(jù)!n；cout請輸入圈中的總人數(shù)n(n0)和初始出隊數(shù)m(m0):nm；for(inti=0；in；i+)ai=i+1；bi=2*(i+1)；LinkListdata(a,b,n)；Josephus(&data,m)；六、運行結果（1）順序表實現(xiàn)A、m相同B、m不同（2）單鏈表實現(xiàn)A、m相同B、m不同2、一元代數(shù)多項式求和一、結點類型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ù)實現(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