C++約瑟夫環(huán)實(shí)驗(yàn)報(bào)告

數(shù)據(jù)結(jié)構(gòu)集中上機(jī)試驗(yàn)報(bào)告學(xué)院：計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)學(xué)號(hào)：111111111111班級(jí)：（6）姓名：莫莫莫200joseph環(huán)上機(jī)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱：joseph環(huán)題目要求的約瑟夫環(huán)操作：編號(hào)是1，2，……,n的n個(gè)人按照順時(shí)針方向圍坐一圈，每個(gè)人只有一個(gè)密碼（正整數(shù)）。一開始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m,從第一個(gè)仍開始順時(shí)針方向自1開始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針方向的下一個(gè)人開始重新從1報(bào)數(shù)，如此下去，直到所有人全部出列為止。設(shè)計(jì)一個(gè)程序來求出出列順序。實(shí)驗(yàn)要求：1~）利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬此過程，按照出列的順序輸出各個(gè)人的編號(hào)。2~）建立輸入處理輸入數(shù)據(jù)，輸入每個(gè)人的密碼，建立單循環(huán)鏈表。3~）測試數(shù)據(jù)：m的初值為6，n=7,7個(gè)人的密碼依次為3，1，7，2，4，8，4，首先m=6,則正確的輸出是什么？實(shí)驗(yàn)過程：1.基本算法以及分析：本程序主要是以建立單循環(huán)鏈表的形式，建立起一個(gè)約瑟夫環(huán)，然后根據(jù)之前創(chuàng)立的結(jié)點(diǎn)，輸入結(jié)點(diǎn)里的一些數(shù)據(jù)，如下structJoseph{ longnumber; Joseph*next; floatscore;};程序有主函數(shù)開始，首先，提示輸入每個(gè)環(huán)上所帶的密碼。然后，開始調(diào)用Joseph*Create()函數(shù)，利用單循環(huán)鏈表建立起約瑟夫環(huán)， pEnd->next=head;就是將最后一個(gè)結(jié)點(diǎn)的后繼指向頭結(jié)點(diǎn)，函數(shù)結(jié)尾return(head);將約瑟夫環(huán)的頭指針返回，并將它賦值head，依次錄入各節(jié)點(diǎn)的密碼值，然后主函數(shù)繼續(xù)調(diào)用 Delete函數(shù)，實(shí)現(xiàn)如下功能：編號(hào)是1，2，……,n的n個(gè)人按照順時(shí)針方向圍坐一圈，每個(gè)人只有一個(gè)密碼（正整數(shù)）。一開始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m,從第一個(gè)仍開始順時(shí)針方向自1開始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針方向的下一個(gè)人開始重新從1報(bào)數(shù)，如此下去，直到所有人全部出列為止。2.程序源代碼：約瑟夫環(huán)#include<iostream>usingnamespacestd;structJoseph{ longnumber; Joseph*next; floatscore;};Joseph*head;Joseph*Create(){ intk=1; Joseph*ps;//當(dāng)前要插入的結(jié)點(diǎn) Joseph*pEnd;//鏈尾指針 ps=newJoseph;//為當(dāng)前要插入的結(jié)點(diǎn)分配空間 cin>>ps->score; ps->number=k++; head=NULL;//初始化鏈表，開始時(shí)鏈表為空 pEnd=ps; while(ps->score!=0)//以輸入的學(xué)生號(hào)為0作為結(jié)束條件 { if(head==NULL)//當(dāng)前插入的結(jié)點(diǎn)為鏈表的第一個(gè)結(jié)點(diǎn) head=ps; else pEnd->next=ps; pEnd=ps; ps=newJoseph; cin>>ps->score; ps->number=k++; } pEnd->next=head; deleteps;//釋放結(jié)點(diǎn)成員number為0的結(jié)點(diǎn)所占的內(nèi)存 return(head);}voidDelete(Joseph*q,intm){ Joseph*p;Joseph*pGuard; pGuard=q; p=newJoseph; p->next=pGuard; while(pGuard->next!=pGuard)//循環(huán)判斷，若只剩下最后一個(gè)節(jié)點(diǎn)，則循環(huán)結(jié)束 { for(inti=1;i<m;i++)//開始順序報(bào)數(shù) { p=pGuard; pGuard=pGuard->next; } p->next=pGuard->next; cout<<pGuard->number<<"havebeendeleted\n"<<endl;//輸出循環(huán)刪除的結(jié)點(diǎn)m=pGuard->score;//將節(jié)點(diǎn)密碼作為新的m值 delete(pGuard); pGuard=p->next; }cout<<pGuard->number<<"havebeendeleted\n"<<endl;//輸出最后刪除的結(jié)點(diǎn) }voidmain(){ cout<<"請(qǐng)依次輸入每個(gè)人的密碼："; head=Create(); Delete(head,6); }3.運(yùn)行結(jié)果初始密碼6，輸入七個(gè)人的密碼，以0作為結(jié)束條件輸入密碼：3172484輸出結(jié)果：6147235

4此程序目前的缺點(diǎn)在于，結(jié)點(diǎn)密碼數(shù)據(jù)類型定義的存儲(chǔ)類型是int型，不能超過-2147483648～21