C++約瑟夫環(huán)實驗報告

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

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