约瑟夫斯问题求解与停车场停车问题

《约瑟夫斯问题求解与停车场停车问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《计算机软件技术基础》2013实验报告I—数据结构_031120206_李希文实验一：约瑟夫斯问题求解一、问题描述1、实验题目约瑟夫斯（Josephus）问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序，按出列顺序印出各人编号。2、基本要求利用单向循环链表存储结构模拟此过程，

2、按照出列的顺序印出各人的编号。3、测试数据n=7，7个人的密码依次为：3，1，7，2，4，8，4。m初值为6（正确的出列顺序应为6，1，4，7，2，3，5）。二、需求分析1、本程序利用循环链表结构模拟出约瑟夫斯问题中在任意人数每人任意编号情况下，各编号的出列顺序2、程序运行后显示提示信息，建立输入处理，输入n输入以及每个人的密码；m的初值。控制输入的n、m及个人密码必为正整数。3、建立一个输出函数，程序自动输出正确的序列。三、概要设计为实现上述功能，用单向循环链表存储结构模拟此过程，因此需要有单向循环链表这一数据结构。1、定义一个结点类型来储存

3、每个人编号及密码：typedefintElemType;typedefstructnode{ElemTypemima;intbianhao;《计算机软件技术基础》2013实验报告I—数据结构_031120206_李希文structnode*next;}SLNODE;2、单向循环链表抽象数据类型定义：ADT{数据对象：SLNODE类型数据关系：线性关系基本操作：SLNODE*initlist();//创建空链表voidcreatefromRear(SLNODE*head,intn);//尾插法输入循环链表；利用n来控制输入次数voidDelLin

4、kList(SLNODE*p);/*删除p指针指向结点的后一个结点*/voidxunhuan(SLNODE*head);//循环链表｝3、主程序流程及其模块调用关系1）主函数流程输入起始m调用输出函数，输出出列顺序编号输入n个编号密码输入编号总数n2）模块调用关系主程序模块单向循环链表单元模块：实现单向循环链表的抽象数据类型单向循环链表单元模块主函数模块四、详细设计1、单向循环链表结点类型typedefintElemType;typedefstructnode{ElemTypemima;intbianhao;structnode*next;《计

5、算机软件技术基础》2013实验报告I—数据结构_031120206_李希文}SLNODE;2、实现每个基本操作的伪码//创建空链表SLNODE*initlist(){SLNODE*head;head=(SLNODE*)malloc(sizeof(SLNODE));head->next=NULL;returnhead;}//尾插法输入循环链表；voidcreatefromRear(SLNODE*head,intn)//注意控制n>0;{SLNODE*r,*s;ElemTypex;inti=1;//利用i来控制输入次数r=head;cout<<"输

6、入第"<>x;while(x>0&&i<=n){s=(SLNODE*)malloc(sizeof(SLNODE));s->mima=x;s->bianhao=i;r->next=s;r=s;/*r永远指向链表的最后一个结点*/r->next=NULL;i++;if(i<=n)//控制输入提示语句出现个数{cout<<"输入第"<>x;}}《计算机软件技术基础》2013实验报告I—数据结构_031120206_李希文}//循环链表voidxunhuan(SLNODE*head){SLNODE

7、*r;r=head;while(r->next!=NULL){r=r->next;}r->next=head;}//删除函数；voidDelLinkList(SLNODE*p)/*删除p指针指向结点的后一个结点*/{SLNODE*q;if(p->next!=NULL){q=p->next;/*q指向p的后继结点*/p->next=q->next;/*修改p结点的指针域*/free(q);}/*删除并释放结点*/}3、主函数伪码intmain(){cout<<"实验名称：实验一.约瑟夫斯求解问题"<

8、6"<