【問題描述】
約瑟夫(Joseph)問題的一種描述是:編號為1,2,.....,n的n個人按順時針方向圍坐一圈,每人持有一個密碼(正整數)。一開始任選一個正整數作為報數上限值m,從第一個人開始順時針方向自1開始報數,報到m時停止報數。報m的人出列,將他的密碼作為新的m值,從他的順時針方向上的下一個人開始重新從1報數,如此下去,直至所有的人都出列為止。試設計一個程序求出列順序。
【其本要求】
利用單向循環鏈表存儲結構模擬此過程,按照出列的順序印出各人的編號。
【測試數據】
M的初值為20;n=7,7個人密碼依次為:3,1,7,2,4,8,4,首先m的值為6(正確的出列順序應為6,1,4,7,2,3,5)。
#include "iostream" using namespace std; typedef struct LNode { int num; //表示該元素的編號 int password; //表示該元素的密碼 struct LNode *next; }LNode,*LinkList; // 結點類型,指針類型 int Insert(LinkList &L,int password, int num) //引用類型的參數 { LinkList p; if(L==NULL) //第一個結點 { p=(LinkList)malloc(sizeof(LNode)); if(!p) { cout<<"分配空間失??!"<<endl; return -1; } p->num=num; p->password=password; L=p; } else { p=(LinkList)malloc(sizeof(LNode)); if(!p) { cout<<"分配空間失敗!"<<endl; return -1; } p->num=num; p->password=password; L->next=p; p->next=NULL; L=p; } return 0; } void Joseph(LinkList &L,int k,int m) //引用類型的參數 { int i; LinkList p,q; p=q=L; while(q->next!=L) q=q->next; while(k>0) { for(i=1;i<m;i++) { q=q->next; p=p->next; } q->next=p->next; cout<<p->num<<" "; m=p->password; //更新m的值 free(p); k--; //人數減1 p=q->next; } cout<<endl; } int main(void) { int m,n,i,t; LinkList head,p=NULL; cout<<"請輸入人數:"; //輸入人數n cin>>n; cout<<"請輸入初始密碼:"; //輸入初始密碼m cin>>m; cout<<"請輸入大家手中的密碼:"<<endl; for(i=1;i<=n;i++) { cin>>t; if(Insert(p,t,i)==-1) return 0; if(i==1) head=p; } p->next=head; //構成約瑟夫環 cout<<"出列的順序如下:"<<endl; Joseph(head,n,m); system("pause"); return 0; }
運行結果如下圖:
結構體定義中
typedef struct LNode { int num; int password; struct LNode *next; }LNode,*LinkList; // 結點類型,指針類型
typedef 聲明,簡稱 typedef,為現有類型創建一個新的名字。
typedef struct Node
{
int data;
struct Node* next;
}LNode, *LinkList;
LNode就相當于struct Node ,起了一個別名。
*LinkList也相當于struct Node
也就是:
LNode 等價 struct Node
LinkList 等價 LNode* 等價 struct Node*
LNode a;等價 struct Node a;
LinkList p;等價 LNode* p;等價 struct Node* p;
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
