收藏 分销(赏)

C语言-约瑟夫环问题.doc

上传人:w****g 文档编号:10820595 上传时间:2025-06-18 格式:DOC 页数:4 大小:55.04KB 下载积分:5 金币
下载 相关
C语言-约瑟夫环问题.doc_第1页
第1页 / 共4页
C语言-约瑟夫环问题.doc_第2页
第2页 / 共4页


点击查看更多>>
资源描述
实验一:约瑟夫环问题 一.实验目的: 要求设计一个程序模拟约瑟夫环问题过程,求出出列编号序列。 二.实验内容: 约瑟夫环问题:设编号为1,2,3,……,n的n(n>0)个人按顺时针方向围坐一圈,每个人持有一个正整数密码。开始时任选一个正整数做为报数上限m,从第一个人开始顺时针方向自1起顺序报数,报到m是停止报数,报m的人出列,将他的密码作为新的m值,从他的下一个人开始重新从1报数。如此下去,直到所有人全部出列为止。令n最大值取30。要求设计一个程序模拟此过程,求出出列编号序列。 三.实验过程: 用一个不带头结点的循环链表来处理Josephu 问题:先构成一个有n个结点的单循环链表,然后由k结点起从1开始计数,计到m时,对应结点从链表中删除,把被删除结点的密码作为新的m值,然后再从被删除结点的下一个结点又从1开始计数,直到最后一个结点从链表中删除算法结束。 #include<stdio.h> #include<stdlib.h> #define MAX_NODE_NUM 30 #define TRUE 1 #define FALSE 0 typedef struct NodeType { int number; int password; struct NodeType *next; } NodeType; /* 创建单向循环链表 */ static void CreaList(NodeType **, const int); /* 运行"约瑟夫环"问题 */ static void StatGame(NodeType **, int); /* 打印循环链表 */ static void PrntList(const NodeType *); /* 得到一个结点 */ static NodeType *GetNode(const int, const int); /* 测试链表是否为空, 空为TRUE,非空为FALSE */ static unsigned EmptyList(const NodeType *); int main(void) { int n, m; NodeType *pHead=NULL; while(1) {printf("输入总的人数 n(<=%d):",MAX_NODE_NUM); scanf("%d",&n); printf("初始循环的密码为:"); scanf("%d",&m); if(n>MAX_NODE_NUM) {printf("数字太大,请重新输入!\n"); continue; } else break; } CreaList(&pHead,n); printf("\n打印出原始每个结点的序列号和密码\n"); PrntList(pHead); printf("\n最终每个结点退出的序列号和密码\n"); StatGame(&pHead,m); return 0; } static void CreaList(NodeType **ppHead, const int n) { int i,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("已完成结点初始化!\n"); } static void StatGame(NodeType **ppHead, int iCipher) { int iCounter, 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; } static void PrntList(const NodeType *pHead) { const NodeType *pCur=pHead; if (EmptyList(pHead)) return; do { printf("第%d 个人,密码:%d\n",pCur->number,pCur->password); pCur=pCur->next; } while (pCur!=pHead); } static NodeType *GetNode(const int iId,const int iCipher) { NodeType *pNew; pNew=(NodeType *)malloc(sizeof(NodeType)); if(!pNew) { printf("错误,内存不足!\n"); exit(-1); } pNew->number=iId; pNew->password=iCipher; pNew->next=NULL; return pNew; } static unsigned EmptyList(const NodeType *pHead) { if(!pHead) { printf("列表为空!\n"); return TRUE; } return FALSE; } 4
展开阅读全文

开通  VIP、SVIP  下载更划算
下载10份以上建议开通 VIP 会员
下载20份以上建议开通SVIP会员


开通VIP      成为共赢上传

当前位置:首页 > 通信科技 > 开发语言

移动网页_全站_页脚广告1

关于我们      便捷服务       自信AI       AI导航        关注我们

©2010-2026 宁波自信网络信息技术有限公司  版权所有

客服电话:0574-28810668  投诉电话:18658249818

gongan.png浙公网安备33021202000488号   

icp.png浙ICP备2021020529号-1  |  浙B2-20240490  

关注我们 :微信公众号    抖音    微博    LOFTER 

客服