约瑟夫环问题实验报告_约瑟夫环问题_5个人约瑟夫环(2)

该课程设计的目的是通过课程设计的综合训练，以培养分析和编程等实际动手能力，是系统掌握数据结构这门课程的主要内容。本次课程设计的内容是用单循环链表模拟约瑟夫环问题，循环链表是一种首尾相接的链表，其特点是无须增加存储容量，仅对表的链接方式稍作改变，使表处理更加灵活。约瑟夫环问题就是用单循环链表处理的一个实际应用。通过这个设计实例，了解单链表和单循环链表的相同与不同之处，进一步加深对链表结构类型及链表操作的理解。通过该课程设计，能运用所学知识，上机解决一些实际问题，了解并初步掌握设计，实现较大程序的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。第一章 问题分析约瑟夫环问题描述的是：设编号为1，2，…，n的n（n 0）个人按顺时针方向围坐一圈，每个人持有一个正整数密码。开始时选择一个正整数作为报数上限m，从第一个人开始顺时针方向自1起按顺序报数，报到m时停止报数，报m的人出圈，将他的密码作为新的m值，从他的顺时针方向上的下一个人起重新从1报数。如此下去，直到所有人都出圈为止。令n最大值为100。要求设计一个程序模拟此过程，求出出圈的编号序列。约瑟夫环问题

具体描述如图1和图2所示：图1 约瑟夫环问题图解图2 约瑟夫环原理演示图第二章 逻辑设计2.1 循环链表抽象数据类型定义typedef struct LNode//定义单循环链表中结点的结构int num;//编号int pwd;//passwordstruct LNode *next;//指向下一结点的指针LNode;2.2本程序包含的模块设计（1）构造结点模块LNode *createNode int m_num,int m_pwdLNode *p;p LNode * malloc sizeof LNode ;//生成一个结点p- num m_num;//把实参赋给相应的数据域p- pwd m_pwd;p- next NULL;//指针域为空return p;（2）创建链表模块void createList LNode *ppHead,int n（3）出队处理模块void jose LNode *ppHead,int m_pwd（4）约瑟夫环说明输出模块void instruction（5）菜单模块void menu（6）主函数模块int main（）函数的调用关系图如图3所示：图3 约瑟夫环函数调用关系图第三章 详细设计3.1 主函数图4 主函数数据流程图根据图4，主函数程序如下：int mainint n,m,x;LNode *ppHead NULL;menu ;for ;;printf "\n请选择要执行的操作：" ;scanf "%d",&x ;system "cls" ;switch xcase 1:printf "**********************************************\n" ;printf "约瑟夫环:\n" ;printf " 编号为1,2,3,4…,n的n个人按顺时针方向围坐一圈,每人持有一个密码 正整数 .一开始任选一个正整数作为报数的上限值m,从第一个人开始按顺时针方向自1开始按顺序报数,报到m时停止.报m的人出列，将他的密码m作为新的m值,从他的顺时针方向上的下一人开始重新从1报数,如此下去,直到所有人全部出列为止.编程打印出列顺序.\n" ;printf "**********************************************\n" ;main ;break;case 2:printf "请输入总人数n：\n" ;scanf "%d",&n ;printf "请输入开始上限数m:" ;scanf "%d",&m ;createList &ppHead,n ;printf "\n" ;printf "出队顺序：\n" ;jose ppHead,m ;printf "\n约瑟夫环游戏结束!\n" ;main ;break;case 0:exit 0 ;default:system "cls" ;printf "\n您选择的操作有误，请重新选择...\n " ;main ;return 0;3.2 链表的创建图5 创建链表函数的数据流程图/*创建单向循环链表ppHead，参加人数个数为n，并输入每人的密码值，若建立失败则生成头结点，让cur指向他，若建立成功则插入结点P，cur指向的数据元素为p,后续为"空"的结点，再把P插入循环链表ppHead中*/根据图5，创建链表函数程序如下：void createList LNode **ppHead,int nint i,m_pwd;LNode *p,*cur;//cur:浮标指针for i 1;i n;i++printf "输入第%d个人的密码：",i ;scanf "%d",&m_pwd ;//输入持有密码p createNode i,m_pwd ;//调用构造结点函数if *ppHead NULL //如果头结点为空*ppHead cur p;//生成头结点，让cur指向他cur- next *ppHead;//cur的指针域指向自身else//如果不为空，则插入结点p- next cur- next;cur- next p;cur p;//cur指向新插入结点printf "完成创建！\n" ; //提示链表创建完成3.3 出队处理图6 出对函数的数据流程图/*p指向要删除结点的前一个结点，ppHead指向要删除的结点，使p ppHead，ppHead再指向要删除结点的下一个结点，使p和ppHead链接，输出p指向结点的编号和密码值，释放ppHead，如此循环，直至把所有结点都打印和删除为止！*/根据图6，出队函数程序如下：void jose LNode *ppHead,int m_pwdint i,j;LNode *p;//定义指针变量for i 1;p! ppHead;i++for j 1;j m_pwd;++jp ppHead;//p赋值为ppHead，p指向要删除结点的前一个结点ppHead ppHead- next;//ppHead指向下一个元素p- next ppHead- next;//p结点与头结点链接i ppHead- pwd;//i赋值为ppHead- pwdj ppHead- num;//j赋值为ppHead- num，j为要删除的密码值printf "第%d个人出列，密码：%d\n",j,i ;m_pwd ppHead- pwd;//m_pwd赋值为ppHead- pwdfree ppHead ;//释放头结点ppHead p- next;//ppHead重新赋值给p- next,即释放前的ppHead- pwd指针//删除报数结点i ppHead- pwd;//i赋值为ppHead- pwdj ppHead- num;//j赋值为ppHead- numprintf "最后一个出列是%d号，密码是:%d\n",j,i ;free ppHead ;//释放头结点3.4 约瑟夫环说明模块void instructionprintf "**********************************************\n" ;printf "约瑟夫环:\n" ;printf " 编号为1,2,3,4…,n的n个人按顺时针方向围坐一圈,每人持有一个密码 正整数 .一开始任选一个正整数作为报数的上限值m,从第一个人开始按顺时针方向自1开始按顺序报数,报到m时停止.报m的人出列，将他的密码m作为新的m值,从他的顺时针方向上的下一人开始重新从1报数,如此下去,直到所有人全部出列为止.编程打印出列顺序.\n" ;printf "**********************************************\n" ;3.5菜单模块void menuprintf "*****************约瑟夫环***********************\n" ;printf "\n" ;printf " [1]约瑟夫环问题的阐述 \n" ;printf " [2]按要求求解约瑟夫环 \n" ;printf " [0]退出 \n" ;printf "**************** 欢迎使用！*********************\n" ;第四章 程序调试与测试1. 调用模块时，结点结构的调用与其他模块产生冲突，导致每一行都出现两个错误，加入子函数的声明后，错误消失。

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-32361-2.html