上海电力学院
数据结构Java课程设计
题目: 约瑟夫环
学生姓名：
学号：
院系：计算机与信息工程学院
专业年级：软件工程级
2012 年1月13 日
目录
1. 需求分析 (3)
1.1运行环境 (3)
1.2输入的形式和输入的范围 (3)
1.3输出的形式描述 (3)
1.4功能描述 (4)
1.5测试数据 (4)
2. 概要设计 (4)
2.1抽象数据类型定义描述 (4)
2.2功能模块设计 (5)
2.3模块层次调用关系图 (5)
3. 详细设计 (6)
3.1类函数解析 (6)
3.2主函数解析 (8)
4. 调试分析 (9)
4.1所遇问题 (9)
4.2实验心得.................................................................... 错误！未定义书签。
5. 用户使用说明.................................................................. 错误！未定义书签。
5.1每一步操作说明........................................................ 错误！未定义书签。
6. 测试结果.......................................................................... 错误！未定义书签。
7. 附录：程序源代码.......................................................... 错误！未定义书签。
一、需求分析
【问题描述】
约瑟夫（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）。
1、运行环境（软、硬件环境）
开发工具：JDK1.6 eclipse6.0
运行环境：Windows XP及其以上系统
2、输入的形式和输入值的范围
本个实验所输入的值都强制转化为Int数据类型，因为人数一定是个正整数，而每个人所持的密码将会作为下一次循环的步数，所以也一定是一个整数；初始密码也是步数，所以也是一个正整数。在输入值的取值范围上，每人的密码是一个大于零的整数，初始密码也是一个大于零的整数，人数同样也是一个正整数。
3、输出的形式描述
1.可以在以下环境中运行本次实验
①在DOS环境中编译“约瑟夫环.Java”文件
②在Eclipse6.0及其以上编译环境下运行
2.根据文字要求依次输入人数、每人密码、初始密码等一些数据（见图1.
3.2）
（图）1.3.2
4、功能描述
约瑟夫环代码约瑟夫环（Josephus）问题是由古罗马的史学家约瑟夫（Josephus）提出的，他参加并记录了公元66—70年犹太人反抗罗马的起义。约瑟夫作为一个将军，设法守住了裘达伯特城达47天之久，在城市沦陷之后，他和40名死硬的将士在附近的一个洞穴中避难。在那里，这些叛乱者表决说“要投降毋宁死”。于是，约瑟夫建议每个人轮流杀死他旁边的人，而这个顺序是由抽签决定的。约瑟夫有预谋地抓到了最后一签，并且，作为洞穴中的两个幸存者之一，他说服了他原先的牺牲品一起投降了罗马。
本次试验的不同点在于有一个初始密码M、每人又有个密码，在他死后（出局）之后将作为下一个循环的步数，这样以此类推得出最后一个幸存者。这个实验主要是模仿约瑟夫环的意思模拟约瑟夫环。差别在与每人的密码将作为下一个循环步数继续开始另一个约瑟夫环的循环处理。最后得到一个出此链表的数字下标代号。
5、测试数据
①初始密码M=20
②人数为7
③7个人的密码依次为：3，1，7，2，4，8，4
最后得到一个出此链表顺序，用每个链表中元素的下标输出数据。
二、概要设计
1、抽象数据类型定义描述
（对各类的成员及成员函数进行抽象描述）
创建Node和LinkList这两个类，在Node类中定义一些函数，为主程序中调用这些函数所服务；LinkList类Head指针调用SetLink函数，然后遍历结点，一次删除结点，使得指针后移。
在主函数中运用一个For循环作为足要算法，一次实现约瑟夫环的功能。
2、功能模块设计（如主程序模块设计）
先创建了一个linklist对象，然后分别申明inCount和resultIncount这两个私有成员变量。然后通过inCount = Integer.parseInt(input.readLine());把输入的内容转化成INT类型，赋值给inCount。通过一个For循环语句作为其主要算法实现。
Node p = link.head, q = https://www.doczj.com/doc/c04299179.html,st;
int i = 0;//每个人的密码
int j = 0;//人数
for (;;) {i++;
if (i == m) {
i = 0;
m = p.getData();
System.out.print(p.getCount() + " ");
link.removeNode(q);//删除Q节点
p = p.getLink();//Q结点后移
j++;
if (j == inCount)
break;//如果等于总人数就跳出FOR循环
continue;//继续进行下一个循环
}
q = q.getLink();//Q的指针往后移
p = q.getLink();//P等于Q的下一个指针
}
3、模块层次调用关系图
三、详细设计
实现概要设计中定义的所有的类的定义及类中成员函数，并对主要的模块写出伪码算法。
class Node {
private int data[] = new int[2];
private Node link;
private static int count = -1;
public Node(int data) {
this.data[0] = data;
this.data[1] = ++count;
link = null;
}
public void setData(int data) {
this.data[0] = data;
}
public int getData() {
return data[0];
}
public int getCount() {
return data[1];
}
public void setLink(Node link) {
this.link = link;
}
public Node getLink() {
return link;
}
}
在这个结点NODE类中定义了诸如setData、getData、getData、getCount、setLink、getLink等一些函数，为主函数调用这些函数做好准备。这也是前期工作的准备。
class LinkList {
public Node head;
public Node last;
public LinkList(int data) {
head = new Node(data); //Head调用NODE的构造函数，初始化Head
head.setLink(head); //Head调用SetLink的函数
last = head;
}
public String vistAllNode(){ //遍历节点
Node next = head;
String s = new String();
do {
s = s + next.getData() + " ";
//把指针next指向的对象添加到字符串S中
next = next.getLink(); //把指针后移，获取下一个指针} while (next != head);
return s;
}
public boolean removeNode(Node node) { // 去掉node的下一个结点if (node == last) {
head = head.getLink(); //把头指针指向下一个节点
last.setLink(head); //尾指针=头指针} else if (node.getLink() == last) {
last = node;
last.setLink(head); //Last指向头指针} else {
Node tempN = node.getLink();
//申明一个临时的指针TEMPN指向NODE的下一个节点
tempN = tempN.getLink(); //把tempN向后移一个
node.setLink(tempN); //node指向tempN }
return true; //操作成功返回true }
public boolean removeAll() { //此函数的作用是删除所有的节点head.setLink(head); //Head=Head
last = head; //Last=Head
head.setData(0); //head的数据设置为0
return true;
}
public void append(int data) { //此函数的作用是加一个节点Node temp = new Node(data); //申明TEMP节点
last.setLink(temp); //尾指针指向TEMP指针
last = temp; //尾指针指向TEMP指针
last.setLink(head); //尾指针指向头指针
}
}
在LinkList类中申明头尾指针head和last，head和last分别调用Node和setLink函数，在进行结点的遍历和，当删除一个结点之后便产生了指针后移的问题，直到头尾指针相同。
public class约瑟夫环 {
private static LinkList link = new LinkList(0);
//申明一个LinkList 的对象
private static int inCount;
private static int resultInCount; //申明两个变量
public static void main(String[] args) throws IOException { //主函数抛出异常
int enter;
String inputString = new String();
BufferedReader input = new BufferedReader(new InputStreamReader(
System.in)); //定义一个缓冲流对象
System.out.print("这个程序是解决约瑟夫环的问题。\n请输入人数(正整数):");
inCount = Integer.parseInt(input.readLine());
//把输入的内容转化成INT类型，赋值给INCOUNT
System.out.print("请输入初始密码:");
int m = Integer.parseInt(input.readLine());
System.out.println("请输入每个人的密码:");
for(resultInCount= 0; resultInCount< inCount; resultInCount++) {
inputString = input.readLine();
enter = Integer.parseInt(inputString);
link.append(enter);
}//循环输入的内容放到链表中
link.removeNode(https://www.doczj.com/doc/c04299179.html,st); //去掉链表中最后一个节点
Node p = link.head, q = https://www.doczj.com/doc/c04299179.html,st;
int i = 0; //每个人的密码
int j = 0; //人数
for (;;) {
i++;
if (i == m) {
i = 0;
m = p.getData();
System.out.print(p.getCount() + " ");
link.removeNode(q); //删除Q节点
p = p.getLink(); //Q节点后移
j++;
if (j == inCount)
break; //如果等于总人数就跳出FOR循环continue; //继续进行下一个循环
}
q = q.getLink(); //Q的指针往后移
p = q.getLink(); //P等于Q的下一个指针}
}
}
这是一个主函数代码，里面包括一个For循环，从键盘输入总人数和初始的密码，元素的定义通过数组下标输出来，inCount= Integer.parseInt(input.readLine())通过这个方法进行强制类型转换，将其转换成INT类型。再调用函数得到出此链表的的元素的下标。
四、调试分析
1.所遇问题
程序的编写和调试基本正常。遇到的问题主要是：链表的删除，和主要算法的一个循环算法问题，最后在同学们的帮助和我上网找资料和同学们的帮助之下终于解决问题。
本实验采用数据抽象程序设计方法。思路清晰，实现时调试顺利：
1．由于刚开始忽略了该链表没有头结点这样一个特殊性，没有把第一个结点单独拿出来建立，因而出现了一些逻辑上的错误
2．刚开始写的时候很不适应，不知道从何下手，虽然核心算法的设计早就在心中有一个酝酿，但是实际操作起来还是不能很好的运用
3．由于是第一次用“以数据结构为中心”的思想编程，所以并不是很习惯，在主函数中还是充斥着很多基本语句，以后仍要多多练习
4．算法的时空分析
该程序不占用额外空间，因此空间复杂度是O（n）。
2.实验心得体会
此次课程设计通过具体的试验设计操作，巩固了数据结构中关于链表的知识。尤其是通过具体的操作，提高了自己的分析问题、解决问题的能力，将以前以为没有实际意义的东西运用到实际中去，去解决实际问题。开始学着分析算法的优劣，并且选择最优算法解决问题，与此同时，从实践中规范了自己编程语言的书写，获益匪浅。课程设计真的在一定程度上提高了同学们对JAVA学习得积极性。也为今后的JAVA学习打下扎实的基础。此次课程设计对我的目的已经基本达到，在今后的JAVA 学习中我一定不断推敲JAVA，继续在JAVA学习的路上奋斗。
五、用户使用说明
详细列出每一步的操作说明。
当用户编译.JAVA文件后。
1.按照要求输入一个数字。然后按一下回车键会自动跳转到下一个指令。见图5.1
图5.1
2.按照要求输入一个数字。然后按一下回车键会自动跳转到下一个指令。见图5.2
图5.2
3.按照要求输入一个数字。然后按一下回车键之后设置好了第一个人的密码，然后美
输入一个密码都按一下回车键，以此类推。当完成7个人的密码设置之后会自动跳出一个出链表的编号，次即为约瑟夫环的理念。见图5.3和图5.4
图5.4 图5.3 六、测试结果
七、附录：程序设计源代码
import java.io.*;
class Node {
private int data[] = new int[2];
private Node link;
private static int count = -1;
public Node(int data) {
this.data[0] = data;
this.data[1] = ++count;
link = null;
}
public void setData(int data) {
this.data[0] = data;
}
public int getData() {
return data[0];
}
public int getCount() {
return data[1];
}
public void setLink(Node link) {
this.link = link;
}
public Node getLink() {
return link;
}
}
class LinkList {
public Node head;
public Node last;
public LinkList(int data) {
head = new Node(data);
head.setLink(head);
last = head;
}
public String vistAllNode(){
Node next = head;
String s = new String();
do {
s = s + next.getData() + " ";
//把指针next指向的对象添加到字符串S中
next = next.getLink(); //把指针后移，获取下一个指针} while (next != head);
return s;
}
public boolean removeNode(Node node) { // 去掉node的下一个结点if (node == last) {
head = head.getLink(); //把头指针指向下一个节点
last.setLink(head);
} else if (node.getLink() == last) {
last = node;
last.setLink(head);
} else {
Node tempN = node.getLink();
//申明一个临时的指针TempN指向Node的下一个节点
tempN = tempN.getLink();
node.setLink(tempN); //Node指向TempN }
return true;
}
public boolean removeAll() {
head.setLink(head);
last = head;
head.setData(0);
return true;
}
public void append(int data) {//次函数的作用是加一个节点
Node temp = new Node(data);
last.setLink(temp)
last = temp;
last.setLink(head);
}
}
public class约瑟夫环 {
private static LinkList link = new LinkList(0);
//申明一个LinkList 的对象
private static int inCount;
private static int resultInCount;
public static void main(String[] args) throws IOException { //主函数抛出异常
int enter;
String inputString = new String();
BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
System.out.print("这个程序是解决约瑟夫环的问题。\n请输入人数(正整数):");
inCount = Integer.parseInt(input.readLine());
//把输入的内容转化成INT类型，赋值给INCOUNT
System.out.print("请输入初始密码:");
int m = Integer.parseInt(input.readLine());
System.out.println("请输入每个人的密码:");
for(resultInCount= 0; resultInCount< inCount; resultInCount++) {
inputString = input.readLine();
enter = Integer.parseInt(inputString);
link.append(enter);
}
link.removeNode(https://www.doczj.com/doc/c04299179.html,st); //去掉链表中最后一个节点
Node p = link.head, q = https://www.doczj.com/doc/c04299179.html,st;
int i = 0;
int j = 0;
for (;;) {
i++;
if (i == m) {
i = 0;
m = p.getData();
System.out.print(p.getCount() + " ");
link.removeNode(q); //删除Q结点
p = p.getLink(); //Q结点后移
j++;
if (j == inCount)
break;
continue;
}
q = q.getLink(); //Q的指针往后移
p = q.getLink(); //P等于Q的下一个指针}
}
}
沈阳大学
2.3 MASM的介绍 MASM是微软公司开发的汇编开发环境，拥有可视化的开发界面，使开发人员不必再使用DOS环境进行汇编的开发，编译速度快，支持80x86汇编以及Win32Asm是Windows下开发汇编的利器。它与windows平台的磨合程度非常好，但是在其他平台上就有所限制，使用MASM的开发人员必须在windows下进行开发，历经二三十年的发展，目前MASM的版本已升至6.15，支持MMX Pentium、Pentium II、Pentium III及Pentium 4等指令系统。 2.4总体设计功能 本次课程设计的内容是采用汇编语言设计一个运行于计算机的“霓虹灯”的模拟显示 程序，由$及*字符相间，从两侧向中间螺旋汇聚直至形成一个矩形，这就要求该霓虹灯能够动态地进行变化；霓虹灯模拟显示程序主要是进行程序循环调用，可以通过CMP、JMP、JZ、RET等命令进行跳转。由于是霓虹灯的模拟显示，因此在进行程序循环调用前需要进行数据段定义，以使子程序在进行调用时能够根据数据段的定义来执行，最后显示结果。 定时器中断处理程序：计数器中断的次数记录在计数单元count中，由于定时中断的引发速率是每秒18.2次，即计数一次为55ms，当count计数值为18时，sec计数单元加一（为1秒）。 视频显示程序设计：一般由DOS 或BIOS调用来完成。有关显示输出的DOS功能调用不多，而BIOS调用的功能很强，主要包括设置显示方式、光标大小和位置、设置调色板号、显示字符、显示图形等。用INT 10H中断即可建立某种显示方式。用DOS功能调用显示技术，把系统功能调用号送至AH，把程序段规定的入口参数，送至指定的寄存器，然后由中断指令INT 21H来实现调用。 键盘扫描程序设计：利用DOS系统功能调用的01号功能，接受从键盘输入的字符到AL寄存器，以及检测键盘状态，有无输入，并检测输入各值。 2.5详细功能设计 2.5.1主程序功能 主程序通过调用各个子程序来实现清屏，改变图形等功能，具体调用过程如图1所示。 沈阳大学
《数据结构》 课程设计报告 课程名称：《数据结构》课程设计课程设计题目：joseph环 姓名： 院系：计算机学院 专业： 年级： 学号： 指导教师： 2011年12月18日
目录 1 课程设计的目的 (2) 2 需求分析 (2) 3 课程设计报告内容 (3) 1、概要设计 (3) 2、详细设计 (3) 3、调试分析 (x) 4、用户手册 (x) 5、测试结果 (6) 6、程序清单 (7) 4 小结 (10) 1、课程设计的目的 （1）熟练使用C++编写程序，解决实际问题； （2）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； （3）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； （4）提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 2、需求分析 1、问题描述： 编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。 2、要求： 利用不带表头结点的单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。 3、测试数据： m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？ 输出形式：建立一个输出函数，将正确的输出序列
3、课程设计报告内容 概要设计： 在理解了题目后，我先想到的是我们所学的单链表，利用单链表先建立循环链表进行存贮，建立完循环链表后，我将所要编写的函数分为了两块，一块是经过学过的单链表改编的循环链表的基本操作函数，还有一块是运行约瑟夫环的函数。 详细设计： 我先建立一个结构体，与单链表一样，只是多了一个存密码的code域 struct LinkNode { int data; /删除的是尾结点时（不知道为什么我写程序里总是编译出现错误）{ q->next=head; //重新链接 delete a; len--; return out; } else { q->next=a->next; delete a; len--; return out; } } } } 5、测试结果：
) 汇编语言课程实验报告 实验名称 课程设计1 实验环境 硬件平台：Intel Core i5-3210M 操作系统：DOSBox in Windows 软件工具：Turbo C , Debug, MASM 实验内容 《 将实验7中的Power idea公司的数据按照下图所示的格式在屏幕上显示出来。 实验步骤 1.要完成这个实验，首先我们需要编写三个子程序。第一个子程序是可以显示字符串到屏 幕的程序，其汇编代码如下： ;名称：show_str
;功能：在屏幕的指定位置，用指定颜色，显示一个用0结尾的字符串 ;参数：（dh）=行号，（dl）=列号（取值范围0～80），（cl）=颜色，ds：si：该字符串的首地址 ;返回：显示在屏幕上 ￥ show_str: push ax push cx push dx push es push si push di mov ax,0b800h - mov es,ax mov al,160 mul dh add dl,dl mov dh,0 add ax,dx mov di,ax mov ah,cl . show_str_x: mov cl,ds:[si] mov ch,0 jcxz show_str_f mov al,cl mov es:[di],ax inc si inc di 【 inc di jmp show_str_x show_str_f: pop di pop si pop es pop dx pop cx } pop ax ret 2.第二个程序是将word型数据转换为字符串，这样我们才能调用第一个程序将其打印出
一．需求分析 1.约瑟夫环（Joseph）问题的一种描述是：编号为1，2……，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。 2.演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，有用户在键盘上输入演示程序中规定的运算命令，相应的输入数据和运算结果显示在其后。 3.程序执行的命令包括： 1）输入初始密码和人数2）输入所有人的密码3）显示输入的所有人的编号及相应的密码4）输出出列密码及编号5）结束 4.测试数据 (1)m=20, n=7, 7个人的密码依次为3，1，7，2，4，8，4 (2)m=20,n=1 (3)m=20,n=0 前面一组为常规数据，后面两组为边缘数据 二、概要设计 为实现上述功能，应以有序单向循环链表表示约瑟夫环。为此，需要有一个抽象数据类型。该抽象数据类型的定义为： ADT LinkList { 数据对象：D={ ai | ai ∈termset,i=1,2,……n,n>=0}， termset中每个元素包含编号，密码，和一个指向下一节点的指针数据关系：R1={
课程实验报告 题目：2016.4.6 学生姓名：黄玲 学生学号：201408070105 专业班级：智能1401 指导老师：骆嘉伟 完成日期：2016.4.6
一．需求分析 1.本实验基本要求是用数组来实现线性表，再基于线性表的基本操作（插入、删除、修改等）来实现约瑟夫问题 2.由键盘输入总人数n和出列报数m 3.在DOS界面上显示依次出圈的人的编号和最后一个留下的人,在当前文件夹里生成一个文本文件，里面是相同的输出。 4.测试数据： 输入： 10，3 输出： 3 6 9 2 7 1 8 5 10 4//DOS 3 6 9 2 7 1 8 5 10 4//TXT 二．概要设计 §抽象数据类型 为实现上述程序的逻辑功能，应以整数存储用户的输入 用线性表实现，线性表定义如下： ADT LISt 数据对象：整数 基本操作： AList(100);//构建一个最大人数为100的顺序表（数组）来存储人 Next();//指向下一个人 moveStart();//回到第一个人继续数数 Length();//查看圈里还剩多少人 currPos();//查看当前数到人的编号 getValue();//查看当前编号的人是否还在圈内 §程序的流程 以书上的代码案例为参考，编写线性表的ADT在继承线性表的基础上编写顺序表（数组）的类文件编写主函数，创建类的对象，完成程序 三．详细设计 §物理数据类型 将大小为n的数组赋好值，其值为他本身的编号，即数组下标。 §程序思路的具体步骤实现 设一个标志点，在数组中移动，同时报数，当报到m时，当前人的值变为0，出圈，然后继续移动，重新数。当数到值为0的人时自动跳过（已出圈），当数
燕山大学 汇编语言课程设计说明书 题目：计算机钢琴程序 交通灯控制系统 学院（系）：信息科学与工程学院 年级专业： 10级计算机科学2班 学号： 100104010113 学生姓名：马强 学号： 100104010116 学生姓名：夏洋 指导教师：何海涛、邹晓红 完成日期： 2013年7月3日
目录 1.课程设计的目的和意义........................................................................................................... - 2 - 1.1课程设计目的................................................................................................................ - 2 - 1.2课程设计的意义............................................................................................................ - 2 - 2.题目一：计算机钢琴程序....................................................................................................... - 2 - 2.1系统的主要功能............................................................................................................ - 2 - 2.2总体设计方案................................................................................................................ - 2 - 2.2.1扬声器驱动方式................................................................................................. - 2 - 2.2.2延时原理............................................................................................................. - 3 - 2.2.3键盘控制发声程序............................................................................................. - 4 - 2.2.4设计总结............................................................................................................. - 5 - 2.3作品使用说明................................................................................................................ - 6 - 3.题目二：交通灯控制系统....................................................................................................... - 6 - 3.1系统的主要功能............................................................................................................ - 6 - 3.2 系统工作原理............................................................................................................... - 6 - 3.2.1 8259的工作原理................................................................................................ - 6 - 3.2.2 8255A的工作原理：...................................................................................... - 7 - 3.2.3 8253的工作原理：............................................................................................ - 7 - 3.3总体设计方案................................................................................................................ - 7 - 3.3.1程序流程图......................................................................................................... - 8 - 3.3.2接口电路图....................................................................................................... - 11 - 3.4交通灯的设计总结...................................................................................................... - 11 - 4.课程设计心得体会................................................................................................................. - 12 - 5.参考文献................................................................................................................................. - 12 - 6.附录：程序代码..................................................................................................................... - 12 - 6.1计算机钢琴程序代码.................................................................................................. - 12 - 6.2交通灯控制系统代码.................................................................................................. - 14 -
线性表的操作及其应用 一、问题描述 线性表、队列是一种常用的数据结构，有顺序和链式两种存储结构，在实际中应用十分广泛，而链表又分为单链表和循环链表，队列又分为链式队列和循环队列。这些数据结构都可用来解决约瑟夫环问题。约瑟夫环问题是算法设计中的一个经典问题，是顺序编号的一组n个人围坐一圈，从第1个人按一定方向顺序报数，在报到m时该人出列，然后按相同方法继续报数，直到所有人出列。设计算法求约瑟夫环中人员的出列顺序。 二、基本要求 1、选择合适的存储结构，建立线性表； 2、利用顺序存储结构求解约瑟夫环问题； 3、利用单链表和循环链表分别求解约瑟夫环问题； 4、利用队列求解约瑟夫环问题。 三、测试数据 约瑟夫环的测试数据为7，报数为1至3。 四、算法思想 由于用到四种不同的存储结构，它们的算法思想依次是： 1、首先建立一个顺序表模拟整个约瑟夫环，手动输入顺序表长（即参加约瑟夫循环的人数）和循环的次数和表元素。用已经输出总人数和顺序表长作比较，作为外层循环条件。并对每一个输出后的元素重新赋值以为标记。对于每次循环，首先检查顺序表此次是不是我们设立的标记，如果不是则循环次数加1，当达到要求的循环次数时就将循环次数设置为0，输出该元素到屏幕并将总输出元素加1。每次外循环我们都会移到表的下一个位置，作为新的判断条件，每次报到表尾的时候，我们都将重新设置到表尾，作为下次循环的表元素。 2、首先采用链式循环链表建立整个约瑟夫环，手动输入第一次的循环次数和每个人所持下一个循环次数。设立判断指针指向表头，并将该指针是否为空作为外层循环条件。做一个内层循环，将判断指针移动到循环要输出的数，并设立一个前指针指向该指针的前一个位置，输出该元素后，将循环次数重新赋值成该元素。接着判断前指针和判断指针比较，如果相等说明整个表已经输出完毕，否则将删除该位置的元素。 3、用链式队列建立循环约瑟夫环，手动输入人数，第一次的循环次数和每个人所持下一个循环次数。并将每一个元素依次入队列，根据第一次循环次数，建立一个for循环，每一次循环都出队列，如果达到要求的循环次数就输出，否则进队列，这样这个数字就出现在队尾。第一个数输出后，以队列的非空作为循环条件，判断方式如上。 4、用循环队列建立约瑟夫环，将1-7个元素依次进入循环队列，以队列的长度作为与已输出的元素作为判断条件，对每一个输出后的元素重新赋值以为标记。对于每次循环，首先检查该该位置的元素是不是我们设立的标记-1，如果不是则循环次数加1，将队首指针移
课程设计报告 课程名称：数据结构课程设计课程设计题目：约瑟夫环问题 姓名：余明旭 系：计算机科学与技术专业：计算机科学与技术年级：2010级 学号：100310236 指导教师：陈老师 职称：学生
一、需求分析 1、输入的形式和输入值的范围： 本程序中，输入报数上限值n，初始报数者s，初始报数者携带的密码m1，n-2个人携带的密码m（最后一人携带的密码没用），均限定为正整数，输入的形式为一个以“回车符”为结束标志的正整数。 2、输出的形式： 从屏幕显示出列顺序。 3、程序所能够达到的功能： 提供用户从键盘输入，Joseph约瑟夫环的必要数据，并显示出列顺序。4、测试数据： 输入 8 1 4 4 4 4 4 4 4 输出 4 8 5 2 1 3 7 6 一、详细设计 以单向循环链表实现该结构： 1、抽象数据类型的定义为： struct LNode { ElemType data; LNode* next; }; 2、本程序包含以下模块： 主程序模块： Void main() { 初始化； 输入数据； 执行功能； 显示结果； } 各功能模块：实现单链表的各项功能。 Void fun() { } 3、各模块的调用关系：
三、调试分析 程序的编写和调试基本正常，遇到的问题主要是：指针的指向的边界问题，如何每次正确找到出列的人的位置。 解决方法： for(int j=1;j
《数据结构》课程实验 实验报告 题目：Joseph问题求解算法的设计与实现专业：计算机科学与技术 班级： 姓名： 学号： 完成日期：
一、试验内容 约瑟夫（Joseph）问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 二、试验目的 掌握链表的基本操作：插入、删除、查找等运算，能够灵活应用链表这种数据结构。 三、流程图 输入总人数n 创建并初始化 n个结点 输入第一个报 的数key n==0 报数过程 输出出列者 的编号及密 码 结束 n--
四、源程序代码 //Joseph问题求解算法的设计与实现 #include
基础成绩：82分《数据结构》课程实验 实验报告 题目：Joseph问题求解算法的设计与实现 专业：网络工程 班级：网络102 姓名：张晨曦 学号： 102534 完成日期：2012/6/20 一、试验内容
- 约瑟夫（Joseph）问题的一种描述是：编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 二、试验目的 掌握链表的基本操作：插入、删除、查找等运算，能够灵活应用链表这种数据结构。 三、流程图 struct list {
- int num,code; struct list *next; }; void main() { printf("Joseph问题求解算法的设计与实现\n \n"); int i,j,m=1; int key; // 密码. int n; //人数. list *p,*s,*head; head=(list *)malloc(sizeof(list)); //为头结点分配空间. p=head; //使指针指向头节点 printf("输入人的总个数:"); scanf("%d",&n); for(i=1;i<=n;i++) { printf("第%d个人的密码:\n",i); scanf("%d",&key); s=p; p=(list *)malloc(sizeof(list)); //创建新的结点. s->next=p; p->num=i; p->code=key; } p->next=head->next; p=head; head=head->next; free(p); //释放头结点. p=head; printf("\n\n输入初始值:\n"); scanf("%d",&key); printf("\n出列顺序为:\n"); do { j=1; p=head; while(j
计算机与信息工程学院《汇编语言》课程设计四则运算器的设计 专业：计算机科学与技术 班级：控制11-2班 姓名: 倪天天 学号：2011025745 指导教师：郝维来 2013年6月28日
摘要 计算器是最简单的计算工具，简单计算器具有加、减、乘、除四项运算功能。想要用汇编语言实现简单的计算器，就必须通过对数据存储，寄存器的使用，加减乘除相关指令以及模块的调用等汇编语言知识进行运用，以实现一个基本功能完善，界面友好，操作简便易行的计算器。用汇编语言实现简单计算器还涉及到输入输出模块的设计，加减乘除运算的判断以及退出程序的判断的设计。通过对各种指令的合理使用，设计各个功能模块。当实现各个程序模块后，通过程序的调用最终实现一个简单的计算器。 关键词：计算器，汇编语言，四则运算，功能模块
Abstract Calculator is the easiest calculation tools, a simple calculator with addition, subtraction, multiplication, division four arithmetic functions. Want to use assembly language to achieve a simple calculator, you must pass on the data storage, register usage, addition, subtraction, and related instructions such as assembly language module calls the use of knowledge in order to achieve a basic functional, user-friendly, easy to operate easy calculator. Using assembly language to achieve a simple calculator also involves the design of input and output modules, the judgment of arithmetic operations and exit the program to judge design. Through the rational use of various commands, design various functional modules. When implementing various program modules, through a call to the ultimate realization of the program a simple calculator. Keyword:Calculator, assembly language, four arithmetic, functional modules
#include
L->next = p; L = p; } L->next = q->next; free(q); } void PrintList(int x,int n,LinkList L) //输出出列顺序 { LinkList p,q; p = L; for(int i = 1;i <= n;i++) { for(int j = 1;j < x;j++) p = p->next; q = p->next; x = q->cipher; printf("%d ",q->number); p->next = q->next; free(q); } } int main() { printf("=============约瑟夫环==============\n\n\n"); int n,x; LinkList L; L = NULL; InitList(L); //构造空链表 printf("输入初始密码："); scanf("%d",&x); //初始密码为x printf("\n"); printf("输入参与总人数："); scanf("%d",&n); //总共的人数n printf("\n"); CreateList(n,L); //建立好一个约瑟夫环printf("\n\n\n===================================\n\n"); printf("出列编号为："); PrintList(x,n,L); //输出出列顺序 printf("\n\n"); return 0; }
信息学院 数据结构实验报告 学号：姓名：班级 课程名称：数据结构实验名称：约瑟夫环 实验性质：①综合性实验√②设计性实验③验证性实验实验时间：2017.10 试验地点： 本实验所用设备：PC及VS2010 【数据结构】： typedef struct _RingNode { int pos; // 位置 struct _RingNode *next; }RingNode, *RingNodePtr; 【算法思想】： 以单链表实现约瑟夫环 用户输入M,N值，从1至N开始顺序循环数数，每数到M输出该数值，直至全部输出。（约瑟夫环问题Josephus）。以环状链表实现 【算法描述】： void CreateRing(RingNodePtr pHead, int count) { RingNodePtr pCurr = NULL, pPrev = NULL; int i = 1; pPrev = pHead; while(--count > 0) { pCurr = (RingNodePtr)malloc(sizeof(RingNode)); i++; pCurr->pos = i; pPrev->next = pCurr; pPrev = pCurr; } pCurr->next = pHead; // 构成环状链表 }
void PrintRing(RingNodePtr pHead) { RingNodePtr pCurr; printf("%d", pHead->pos); pCurr = pHead->next; while(pCurr != NULL) { if(pCurr->pos == 1) break; printf("\n%d", pCurr->pos); pCurr = pCurr->next; } } void KickFromRing(RingNodePtr pHead, int m) { RingNodePtr pCurr, pPrev; int i = 1; // 计数 pCurr = pPrev = pHead; while(pCurr != NULL) { if (i == m) { // 踢出环 printf("\n%d", pCurr->pos); // 显示出圈循序 pPrev->next = pCurr->next; free(pCurr); pCurr = pPrev->next; i = 1; } pPrev = pCurr; pCurr = pCurr->next; if (pPrev == pCurr) { // 最后一个 printf("\n%d", pCurr->pos); // 显示出圈循序 free(pCurr); break; } i++; } } int main()
农林大学金山学院 课程设计报告 课程名称：汇编语言课程设计 课程设计题目：动画设计“我爱大自然”姓名： 系：信息与机电工程系 专业：电子信息工程 年级：2008级 学号：082230066 指导教师：\ 职称：助教 2009～2010学年第二学期
目录 1 课程设计的目的 (2) 2 课程设计的要求 (2) 3课程设计报告容 (2) 3.1设计思路 (2) 3.2程序流程图 (2) 3.3设计源程序 (5) 3.4动画示意图 (19) 4 总结 (20) 5参考文献 (20) 6评分标准 (21)
动画设计“我爱大自然” 一、课程设计的目的 《汇编语言课程设计》是电子信息工程专业集中实践性环节之一，是学习完《汇编语言》课程后进行的一次全面的综合练习。其目的是： 培养学生熟练掌握汇编语言指令系统，深化和巩固指令系统和编程方法，提高学生的编程应用能力。为将来从事专业工作打下基础，培养良好的职业道德和严谨的工作作风。 二、课程设计的要求 1)具备初步的独立分析和解决问题的能力； 2)初步掌握问题分析、系统设计、程序编码、测试等基本方法和技能； 3)提高综合运用所学的理论知识和方法的能力； 4)训练用系统的观点和软件开发一般规进行软件开发，培养科学的工作方法和作风； 5)设计的题目要求达到一定工作量，并具有一定的深度和难度； 6)编写出课程设计说明书。 三、课程设计报告容 （一）设计思路 “我爱大自然”这个程序中包含了比较多的景物，既有静态的也有动态的，其中还有一段音乐。为了节省存储空间，提高程序设计的效率和质量，使程序简洁、清晰，便于阅读，同时也为了便于修改和扩充，采用子程序设计技术和宏定义，根据程序要实现的若干主要功能及个功能块要调用的公共部分，将程序划分为若干个相对独立的模块，为每个模块编制独立的程序段，最后将这些子程序根据调用关系连成一个整体。 这样，整个程序就被分为几个子程序的有机统一。根据BIOS中断调用原理，设置80×25彩色文本显示方式，分别编写一个子程序显示“I LOVE NATURE,LET US GO AIRING”和一个子程序在屏幕上“画”树。这两个子程序所体现出来的事物都是的。为了实现小鸟
合肥学院 计算机科学与技术系 课程设计报告 2009～2010学年第二学期 课程数据结构与算法 课程设计名称joseph环 学生姓名朱玉庭 学号0804012029 专业班级08计本(2) 指导教师王昆仑、张贯虹 2010 年06月08号
一、问题分析和任务定义： 约瑟夫环是一个数学游戏，根据游戏内容的描述，能够很容易的看出，游戏中的玩家顺时针围坐一圈，能够很容易的发现，这跟本课上的单循环链表非常相似，所以可以通过单循环链表存储结构模拟此过程，当游戏中的玩家出列时，可以通过删除单循环链表中的结点来实现。 二、数据结构的选择和概要设计： 选择带为指针的单循环链表来解决这个问题，先建立一个空链表，然后根据人数生成具有相应结点的单循环链表，知道密码后，通过循环来找到对应的结点，然后将该结点的编号输出，改变密码，最后删除结点，以此类推，知道编码全部输完，即可得到结果序列。 三、详细设计和编码： 本题目是通过单循环链表存储结构来模拟此过程的，首先要先明确该单循环链表中结点的结构类型，定义如下： typedef struct Node { int key; //每个人持有的密码 int num; //这个人的编号 struct Node *next; //指向下一个结点 }Link; 当生成单循环链表时，就需要用到课本上创建单循环链表的有关内容了，可以先通过子函数Link *InitList()建立一个空链表，返回指针L，然后将返回的指针代入子函数Link *Creater(Link *L,int n)的形参中，对循环链表进行初始化，并且也返回一个指针，然后再将这个返回的指针代入到输出函数void Output(Link *L,int n,int m)的形参中，要想根据题目要求完成序列的输出，需要通过两个for循环来实现，第一个循环for(i=1;i<=n;i++) ，因为一个用n个人，所以结果要输出n个编号，这个循环每循环一次输出一个编号即printf("%d ",q->num)，并将该编号下的密码赋值给m 即m=q->key，当循环完毕时正好将编号全部输出，第二个循环for(j=1;j
《计算机软件技术基础》实验报告 I —数据结构 实验一、约瑟夫斯问题求解 一、问题描述 1.实验题目：编号 1,2,....,n的n个人顺时针围坐一圈，每人持有一个密码（正整数）。 开始选择一个正整数作为报数上限m，从第一个人开始顺时针自 1 报数，报到m的人出列，将他的密码作为新的m值，从他在顺时针方向下一个人开始重新从 1 报数，直至所有人全部出列。 2. 基本要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序印出个人的编号。 3. 测试数据： n=7,7 个人的密码依次为：3,1,7,2,4,8, 4.m初值为6（正确的出列顺序 应为 6,1,4,77,2,3）。 二、需求分析 1. 本程序所能达到的基本可能： 该程序基于循环链表来解决约瑟夫问题。用循环链表来模拟n 个人围坐一圈，用链表 中的每一个结点代表一个人和他所代表的密码。在输入初始密码后m，对该链表进行遍历，直到第 m个结点，令该结点的密码值作为新的密码值，后删除该结点。重复上述过程，直至所有的结点被释放空间出列。 2. 输入输出形式及输入值范围： 程序运行后提示用户输入总人数。输入人数 n 后，程序显示提示信息，提示用户输入第 i个人的密码，在输入达到预定次数后自动跳出该循环。程序显示提示信息，提示用户输入 初始密码，密码须为正整数且不大于总人数。 3．输出形式 提示用户输入初始密码，程序执行结束后会输出相应的出列结点的顺序，亦即其编号。 用户输入完毕后，程序自动运行输出运行结果。 4.测试数据要求： 测试数据 n=7，7 个人的密码依次为：3， 1， 7， 2， 4， 8， 4。 m初值为 6（正确的出列 顺序应为6， 1， 4，7， 2， 3， 5）。 三、概要设计 为了实现上述功能，应用循环链表来模拟该过程，用结构体来存放其相应的编号和密码