河北工業(yè)大學(xué)-數(shù)據(jù)結(jié)構(gòu)實驗報告-約瑟夫環(huán)問題實驗報告

PAGEPAGE4實驗一：約瑟夫環(huán)問題一．實驗?zāi)康模阂笤O(shè)計一個程序模擬約瑟夫環(huán)問題過程，求出出列編號序列。二．實驗內(nèi)容：約瑟夫環(huán)問題：設(shè)編號為1，2，3，……，n的n(n>0)個人按順時針方向圍坐一圈，每個人持有一個正整數(shù)密碼。開始時任選一個正整數(shù)做為報數(shù)上限m，從第一個人開始順時針方向自1起順序報數(shù)，報到m是停止報數(shù)，報m的人出列，將他的密碼作為新的m值，從他的下一個人開始重新從1報數(shù)。如此下去，直到所有人全部出列為止。令n最大值取30。要求設(shè)計一個程序模擬此過程，求出出列編號序列。三．實驗過程：用一個不帶頭結(jié)點的循環(huán)鏈表來處理Josephu問題：先構(gòu)成一個有n個結(jié)點的單循環(huán)鏈表，然后由k結(jié)點起從1開始計數(shù)，計到m時，對應(yīng)結(jié)點從鏈表中刪除，把被刪除結(jié)點的密碼作為新的m值，然后再從被刪除結(jié)點的下一個結(jié)點又從1開始計數(shù)，直到最后一個結(jié)點從鏈表中刪除算法結(jié)束。#include<stdio.h>#include<stdlib.h>#defineMAX_NODE_NUM30#defineTRUE1#defineFALSE0typedefstructNodeType{intnumber;intpassword;structNodeType*next;}NodeType;/*創(chuàng)建單向循環(huán)鏈表*/staticvoidCreaList(NodeType**,constint);/*運行"約瑟夫環(huán)"問題*/staticvoidStatGame(NodeType**,int);/*打印循環(huán)鏈表*/staticvoidPrntList(constNodeType*);/*得到一個結(jié)點*/staticNodeType*GetNode(constint,constint);/*測試鏈表是否為空,空為TRUE，非空為FALSE*/staticunsignedEmptyList(constNodeType*);intmain(void){intn,m;NodeType*pHead=NULL;while(1){printf("輸入總的人數(shù)n(<=%d):",MAX_NODE_NUM);scanf("%d",&n);printf("初始循環(huán)的密碼為:");scanf("%d",&m);if(n>MAX_NODE_NUM){printf("數(shù)字太大，請重新輸入!\n");continue;}elsebreak;}CreaList(&pHead,n);printf("\n打印出原始每個結(jié)點的序列號和密碼\n");PrntList(pHead);printf("\n最終每個結(jié)點退出的序列號和密碼\n");StatGame(&pHead,m);return0;}staticvoidCreaList(NodeType**ppHead,constintn){inti,iCipher;NodeType*pNew,*pCur;for(i=1;i<=n;i++){printf("第%d個人的密碼為:",i);scanf("%d",&iCipher);pNew=GetNode(i,iCipher);if(*ppHead==NULL){*ppHead=pCur=pNew;pCur->next=*ppHead;}else{pNew->next=pCur->next;pCur->next=pNew;pCur=pNew;}}printf("已完成結(jié)點初始化!\n");}staticvoidStatGame(NodeType**ppHead,intiCipher){intiCounter,iFlag=1,i=1;NodeType*pPrv,*pCur,*pDel;pPrv=pCur=*ppHead;while(pPrv->next!=*ppHead)pPrv=pPrv->next;while(iFlag){for(iCounter=1;iCounter<iCipher;iCounter++){pPrv=pCur;pCur=pCur->next;}if(pPrv==pCur)iFlag=0;pDel=pCur;pPrv->next=pCur->next;pCur=pCur->next;iCipher=pDel->password;printf("第%d個退出的是序列號為%d的人,其密碼為:%d\n",i,pDel->number,pDel->password);free(pDel); ++i; } *ppHead=NULL;}staticvoidPrntList(constNodeType*pHead){constNodeType*pCur=pHead;if(EmptyList(pHead))return;do{printf("第%d個人,密碼:%d\n",pCur->number,pCur->password);pCur=pCur->next;}while(pCur!=pHead);}staticNodeType*GetNode(constintiId,constintiCipher){NodeType*pNew;pNew=(NodeType*)malloc(sizeof(NodeType));if(!pNew){printf("錯誤，內(nèi)存不足!\n");exit(-1);}pNew->number=iId;pNew->password=iCipher;pNew->next=NULL;returnpNew;}staticunsignedEmptyList(constNodeType