实验一约瑟夫问题求解
实验一约瑟夫问题求解
1）内容：
约瑟夫(Joseph)问题的一种描述是:编号为1,2,..., n 的n 个人按顺
时针方向围坐一圈, 每人持有一个密码(正整数)。一开始选任一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。
报m的人出列，将它的密码作为新的m值，再从下个人开始新一轮报数，如此反复，直到剩下最后一人则为获胜者。试设计一个程序求出出列顺序。
2）要求：
利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。
3)测试数据:
n=7，7 个人的密码依次为：3，1，7，2，4，8，4 。m的初值为20，则正确的出列顺序应为6，1，4，7，2，3，5。
4）输入输出:
输入数据：建立输入处理输入数据，输入n输入以及每个人的密码；m的初值。
输出形式：建立一个输出函数，输出正确的序列。
实验二停车场问题
1）内容：
设停车场是一个可停放 n 辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的在最北端），若停车场内已经停满 n辆车，那么后来的车只能在场外等候，一旦有车开走，则等候在第一位的车即可开入（这是一个队列设长度为m）；当停车场内某辆车需要开出，则在它之后的车辆必须给它让道，当这辆车驶出停车场后，其他车辆按序入栈。每辆车按时间收费。
2）要求：
以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入数据的序列进行模拟管理。每一组输入数据包括三个数据：汽车的“到达”（’A’表示）或“离去”（’D’表示）信息，汽车标识（牌照号）以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或者便道上的停车位置；若是车辆离去，则输出汽车在停车场停留的时间和应缴纳的费用（便道上不收
费）。栈以顺序结构实现，队列以链表结构实现。
3)测试数据:
设 n＝3，m=4,停车价格为p=2。输入数据为：
(‘A’,101,5),(‘A’,102,10),(‘D’,101,15),(‘A’,103,20),(‘A’,104, 25）,(‘A’,105,30）,(‘D’,102,35）,(‘D’,104,40）,(‘E’,0,0)。其中’A’表示到达，’D’表示离开，’E’表示结束。时间为相对分钟数。
4）输入输出:
输入数据：程序接受5个命令，分别是:到达(‘A’,车牌号,时间)；离去(‘D’,车牌号,时间)；停车场(P,0,0)显示停车场的车；候车场(W,0,0)显示候车场的车;退出(E,0,0)退出程序。
输出数据：对于车辆到达，要输出汽车在停车场内或者便道上的停车位置；对于车辆离去，则输出汽车在停车场停留的时间和应缴纳的费用（便道上不收费）。
实验三关键词检索
1）内容：
实现类似Unix下grep命令的程序。在一个文件中查找某个关键词，并把出现该关键词的行及行号显示出来。
2）要求：
使用C语言的字符串存储结构来实现字符串的操作，编写函数index实现在一个传中查找子串的功能。然后从文件中每次读入一行，作为一个主串看待，然后查找是否存在待查找的关键词（子串），如果有则显示该行内容及行号，否则继续处理下一行。
3)测试数据:
任意一个文本文件，文件中任意一词语作为关键词。
4）输入输出:
输入数据：屏幕输入或命令行给出文本文件名、关键词。
输出数据：屏幕输出文本文件中出现关键词的行及行号。
实验四 huffman编解码
1）内容：
利用 Huffman 编码进行通信可以大大提高信道的利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据进行预先编码，在接收端进行解码。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/解码系统。
2）要求：
一个完整的huffman编解码系统应该具有以下功能：
初始化（I nitialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立Huffman 树，并将它存入hfmTree 中。
编码（E ncoding）。利用已经建好的Huffman树（如果不在内存，则应从文件hfmTree中读取），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。
解码（D ecoding）。利用已经建立好的Huffman树将文件CodeFile中的代码进行解码，结果存入TextFile中。
打印代码文件（Print）。将文件CodeFile以紧凑的格式显示在终端上，每行 50 个代码。同时将此字符形式的编码文件写入文件CodePrint中。
打印Huffman树（T ree Printing）。将已经在内存中的Huffman树以直观的形式（树或者凹入的形式）显示在终端上，同时将此字符形式的Huffman 树写入文件TreePrint中。
3)测试数据:
用下表给出的字符集和频度的实际统计数据建立Huffman树，并对以下报文进行编码和译码：“THIS PROGRAM IS MY FAVORITE”。
4）输入输出:
字符集大小 n，n个字符和 n个权值均从终端读入，初始化后的huffman树存储在hfmTree文件中，待编码文件为ToBeTran,编码结果以文本的方式存储在文件
CodeFile中，解码文件存在TextFile中,打印的编码和赫夫曼树分别存储在
CodePrint和TreePrint文件中。
用户界面可以设计为“菜单”方式：显示上述功能符号，再加上一个退出功能“Q”，表示退出（quit）。用户键入一个选择功能符，此功能执行完毕后再显示此菜单，直至某次用户选择了 Q为止。
实验五管道铺设施工的最佳方案
1）内容：
需要在某个城市n个居民小区之间铺设煤气管道，则在这n个居民小区之间只需要铺设n-1条管道即可。假设任意两个小区之间都可以铺设管道，但由于地理环境不同，所需要的费用也不尽相同。选择最优的方案能使总投资尽可能小，这个问题即为求无向网的最小生成树。
2）要求：
在可能假设的m条管道中，选取n-1条管道，使得既能连通n个小区，又能使总投资最小。每条管道的费用以网中该边的权值形式给出，网的存储采用邻接表的结构。
3)测试数据:
使用下图给出的无线网数据作为程序的输入，求出最佳铺设方案。右侧是给出的参考解。
图3.2 小区煤气管道铺设网及其参考解
4）输入输出:
参考示例中图的创建方式，从键盘或文件读入上图中的无向网，以顶点对(i,j)的形式输出最小生成树的边。
实验六 利用哈希表统计两源程序的相似性
1）内容：
对于两个 C 语言的源程序清单，用哈希表的方法分别统计两程序中使用C 语言关键字的情况，并最终按定量的计算结果，得出两份源程序的相似性。 2）要求与提示：
C 语言关键字的哈希表可以自建，也可以采用下面的哈希函数昨晚参考： Hash(key)=(key 第一个字符序号*100+key 最后一个字符序号)%41
表长m 取43。此题的工作主要是扫描给定的源程序，累计在每个源程序中C 语言关键字出现的频度。为保证查找效率，建议自建哈希表的平均查找长度不大于2。 扫描两个源程序所统计的所有关键字不同频度， 可以得到两个向量。如下面简单的例子所示：
根据程序1和程序2中关键字出现的频度，可提取到两个程序的特征向量X1和X2，其中
X1=(4 3 0 4 3 0 7 0 0 2)T X2=(4 2 0 5 4 0 5 2 0 1)T
一般情况下，可以通过计算向量Xi 和Xj 的相似值来判断对应两个程序的相似性，相似值的判别函数计算公式为:
（3-1） |
|||),(j
i
j
T
i j i X X X X X X S ?=
其中，i T i X X X ?=||
。S(X i ,X j )的值介于[0,1]之间，也称广义余弦，即
S(X i ,X j )=COS θ。X i =X j 时，显见S(X i ,X j )=1，θ=0；X i X j 差别很大时，S(X i ,X j )
接近0，θ接近π/2。如X1=(1 0)T ,X2=(0 1)T ,则S(X i ,X j )=0，θ=π/2。可以用下面的二维的图示来直观地表示向量的相似程度：
图3.3 向量相似度示意图
有些情况下，还需要做进一步的考虑，如下图所示：
图3.4 向量几何距离
从图中看出， 尽管S(X i ,X j )和S(X i ,X k )的值是一样的，但直观上X i 与X k 更相似。因此当S 值接近1 的时候，为避免误判相似性（可能是夹角很小，模值很大的向量），应当再次计算之间的“几何距离” D(X i ,X k )。其计算公式为：
)()(||),(k i T k i k i k i X X X X X X X X D --=-= （3-2）
最后的相似性判别计算可分两步完成：
第一步 用式（3-1）计算S ，把接近 1的保留，抛弃接近0的情况（把不相似的排除）； 第二步 对保留下来的特征向量，再用式（3-2）计算D ，如D 值也比较小，说明两者对应的程序确实可能相似（慎重肯定相似的）。
S 和D 的值达到什么门限才能决定取舍？需要积累经验，选择合适的阈值。 3) 测试数据:
做几个编译和运行都无误的C 程序，程序之间有相近的和差别大的，用上述方法求S ，并对比差异程度。 4）输入输出:
输入为若干个C 源程序，输出为程序间的相似度以及向量的几何距离。
θ
X j
X i
j
X
实验一 约瑟夫环问题
实验一约瑟夫环问题 约瑟夫环问题： 设编号为1，2，3，……，n的n(n>0)个人按顺时针方向围坐一圈，每个人持有一个正整数密码。开始时任选一个正整数做为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m是停止报数，报m的人出列，将他的密码作为新的m值，从他的下一个人开始重新从1报数。如此下去，直到所有人全部出列为止。令n最大值取30。要求设计一个程序模拟此过程，求出出列编号序列。 实现： 用一个不带头结点的单向循环链表表示上述约瑟夫环，结点结构可定义为： typedef sturct node Array { int no; /*编号*/ int key; /*密码域*/ struct node *next; /*指针域*/ } jNode; 注意： 不带头结点的单向循环链表判空条件的处理。 #include
约瑟夫问题数据结构实验报告汇总.
中南民族大学管理学院学生实验报告 实验项目: 约瑟夫问题 课程名称：数据结构 年级： 专业：信息管理与信息系统 指导教师： 实验地点：管理学院综合实验室 完成日期： 小组成员： 2012 学年至2013 学年度第1 学期
一、实验目的 （1）掌握线性表表示和实现； （2）学会定义抽象数据类型； （3）学会分析问题，设计适当的解决方案； 二、实验内容 【问题描述】：编号为1,2,…,n的n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自 1 开始顺序报数，报到m 时停止报数。报m 的人出列，将他的密码作为新的m 值，从他在顺时针方向上的下一个人开始重新从1 报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 【基本要求】：利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 【测试数据】：m 的初值为20；密码：3，1，7，2，4，8，4（正确的结果应为6，1，4，7，2，3，5）。 三、实验步骤 （一）需求分析 对于这个程序来说，首先要确定构造链表时所用的插入方法。当数到m 时一个人就出列，也即删除这个节点，同时建立这个节点的前节点与后节点的联系。由于是循环计数，所以才采用循环列表这个线性表方式。 程序存储结构利用单循环链表存储结构存储约瑟夫数据（即n个人的编码等），模拟约瑟夫的显示过程，按照出列的顺序显示个人的标号。编号为1,2,…,n 的 n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值 m，从第一个人开始按顺时针方向自1 开始顺序报数，报到 m 时停止报数。报 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向上的下一个人开始重新从 1 报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。基本要求是利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。 程序执行的命令（1）构造单向循环链表。 （2）按照出列的顺序引出各个人的标号。 测试数据 m 的初值为 20；密码：3，1，7，2，4，8，4（正确的结果应为 6，1，4，7，2，3，5） （1）、插入：在把元素插入到循环链表中时，由于是采用的头插法，所以我保留了front头结点。在每加入一个节点时，都会直接连接在front后面，从而保证一开始就赋值的rear尾节点不用修改。 伪代码阐释如下：
约瑟夫环实验报告
一．需求分析 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={
约瑟夫环课程设计实验报告
《数据结构》 课程设计报告 课程名称：《数据结构》课程设计课程设计题目：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、测试结果：
约瑟夫环实验报告
课程实验报告 题目：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的人时自动跳过（已出圈），当数
数据结构实验报告(约瑟夫环)
《数据结构》课程实验 实验报告 题目：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
数据结构实验报告—约瑟夫问题求解
《计算机软件技术基础》实验报告 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）。 三、概要设计 为了实现上述功能，应用循环链表来模拟该过程，用结构体来存放其相应的编号和密码
(H)实验1 约瑟夫环问题
实验1 约瑟夫环问题 背景 约瑟夫问题（Josephus Problem）据说著名犹太历史学家Josephus 有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus 及他的朋友躲到一个洞中，39 个犹太人决定宁愿死也不要被敌人到，于是决定了一个自杀方式，41 个人排成一个圆圈，由第1 个人开始报数，每报数到第3 人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从，Josephus 要他的朋友先假装遵从，他将朋友与自己安排在第16 个与第31 个位置，于是逃过了这场死亡游戏。 原题：用户输入M,N 值，N 个人围成一个环，从0 号人开始数,数到M,那个人就退出游戏，直到最后一个人求最后一个剩下的人是几号？ 问题描述 设编号为1-n的n(n>0)个人按顺时针方向围成一圈．首先第1个人从1开始顺时针报数．报m的人(m 为正整数)．令其出列。然后再从他的下一个人开始，重新从1顺时针报数，报m 的人，再令其出列。如此下去，直到圈中所有人出列为止。求出列编号序列。 基本要求 需要基于线性表的基本操作来实现约瑟夫问题 需要利用数组来实现线性表 输入输出格式 输入格式：n，m 输出格式1：在字符界面上输出这n 个数的输出序列 输出格式2：将这n 个数的输出序列写入到文件中 选做内容 （1）使用单链表来实现之 （2）使用循环链表来实现之 测试用例 输入：10，3 输出：3 6 9 2 7 1 8 5 10 4 课后习题 请以O（n）的时间复杂度来实现约瑟夫问题。 源代码和程序 /*算法分析： 1.使用一个数组来存放数列； 2.每出去一人，后面人的序号依次加一，总人数减一，循环结束标志是数组中元素个数为0.
数据结构实验约瑟夫环..
数据结构课程设计题目 1.目的 数据结构是研究数据元素之间的逻辑关系的一门课程，以及数据元素及其关系在计算机中的存储表示和对这些数据所施加的运算。该课程设计的目的是通过课程设计的综合训练，培养分析和编程等实际动手能力，系统掌握数据结构这门课程的主要内容。 2.内容 本次课程设计的内容是用单循环链表模拟约瑟夫环问题，循环链表是一种首尾相接链表，其特点是无须增加存储容量，仅对表的链接方式稍作改变，使表处理更加灵活，约瑟夫环问题就是用单循环链表处理的一个实际应用。通过这个设计实例，了解单链表和单循环链表的相同与不同之处，进一步加深对链表结构类型及链表操作的理解。 约瑟夫环问题的描述是：设编号为1，2，…，n的n个人按顺时针方向围坐一圈，每个人持有一正整数密码。开始时选择一个正整数作为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m时停止报数，报m的人出圈，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新从1报数。如此下去，直到所有人都出圈为止。令n最大值为100。要求设计一个程序模拟此过程，求出出圈的编号序列。 3.设计： 1）对设计内容进行分析
2）逻辑设计 1、循环链表抽象数据类型定义 typedef struct LNode//定义单循环链表中节点的结构 { int num;//编号 int pwd;//password struct LNode *next;//指向下一结点的指针 }LNode; 2、本程序包含一下几个模块 （1）构造结点模块 LNode *createNode(int m_num,int m_pwd) { 图2 约瑟夫环原理演示图
数据结构约瑟夫环实验报告
《数据结构》课程实验报告书 姓名：_____徐鑫_________ 学号：____2116110307____ 专业：____物联网工程____ 班级：_____1604________ 2017 年 10 月 15 日
一、实验目的 1．掌握线性表特性 2．熟练掌握线性表的基本操作 3. 利用线性表设计算法并实现 二、实验内容 1.解决约瑟夫环问题：已知n 个人（以编号1，2，3...n 分别表示）围坐在一张圆桌周围。从编号为k 的人开始报数，数到m 的那个人出列；他的下一个人又从1开始报数，数到m 的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。 2.基本要求：1）根据题目要求设计解决约瑟夫环应用问题的数据结构。 2）要求采用C++编程语言实现设计的算法。 三、设计思路 1. 可将人的顺序简单编号，从1到n ； 构造一个循环链表，可以解决首位相连的问题； 将人的编号插入到结构体的 Data 域中； 遍历人的编号，输出参与的人的编号； 开始报数，从头报数，报到k 的人出局（删除此结点），并释放此结点。直到人数只有一个人时，退出循环，输出获胜的人。 2.存储结构设计 (循环结束条件) 3.算法的核心思想说明 确定需要删除的位置； 设置并删除该位置。
已知报数间隔m，我们可以把当前位置加上m获得需要删除的位置，如果获得的位置超过顺序表中实际元素的总长度，则可以通过减去数组的实际长度来修正修正（即模拟环状计数）。然后把顺序表中的当前指向位置设置为该位置，继而删掉该位置。 反复进行上述确定位置和删除位置的操作，直到顺序表为空。 四、数据结构设计 1.类的声明和定义（要求给出完整的类声明和核心成员函数的定义） #ifndef Joseph_H #define Joseph_H #include
C语言实现约瑟夫环
《约瑟夫环》实验报告 专业：网络工程班级 学号姓名 一、问题描述： 约瑟夫问题的一种描述是：编号为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） 二、程序设计的基本思想，原理和算法描述： 采用结构体定义单链表，格式为：struct Lnode {int number; int password; struct Lnode*next; }Lnode,*p,*q,*head; 其中number是人的排列序号，password是各人所持有的密码值，next是节点指针。Lnode是节点变量，p、q是节点，head是头指针。 程序的代码：定义变量n，i,m,j 输入人的数量n If n<=0或n>30 重新输入n值 当0
约瑟夫环问题 实验报告完整版
实验报告 实验课名称：数据结构实验一 实验名称：约瑟夫环问题 时间 班级000 学号000 姓名神刀公 子 1.问题描述 约瑟夫环问题 （1）问题描述 设有编号为1,2,…,n的n（n＞0）个人围成一个圈，每个人持有一个密码m。从第一个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。 （2）基本要求 建立模型，确定存储结构。 对任意n个人，密码为m，实现约瑟夫环问题。 出圈的顺序可以依次输出，也可以用一个数组存储。 （3）思考： 采用顺序存储结构如何实现约瑟夫环问题？ 如果每个人持有的密码不同，应如何实现约瑟夫环问题？ 2.数据结构设计 由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点。将循环链表的结点定义为如下结构类型：struct Node { int data; //数据域 Node *next; //next指针指向下一个结点 }; 3.算法设计 问题要求建立模型，确定存储结构，之后对任意n个人，密码为m，实现约瑟夫环问题，出圈的顺序可以依次输出，也可以用一个数组存储。
设计流程图如图1.1所示。 开始 输出提示语 输入所需参数 创建链表，计算，得出结果 输出结果 结束 图1.1 设计流程图 （1）创建循环链表 由于内容的要求以及问题的方便，用循环链表作为本次实验的抽象数据类型。申请一个结点作为第一个结点，之后调用creat_list函数将后续结点一次插入链接，构造为循环链表。 NODE *link(int number) { NODE *head=NULL,*p=NULL,*q=NULL; int i=1; head=(struct node*)malloc(sizeof(struct node)); head->value=i; p=head; for(i=2; i<=number; i++)
约瑟夫环问题
实验报告 1.问题描述 设有编号为1,2,…,n的n（n＞0）个人围成一个圈，每个人持有一个密码m。从第一个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。 2.设计思想 首先，设计实现约瑟夫环问题的存储结构。由于约瑟夫环问题本身具有循环性质，考虑采用循环链表，为了统一对表中任意结点的操作，循环链表不带头结点。将循环链表的结点定义为如下结构类型： struct Node { int data; Node *next; }; 其次，建立一个不带头结点的循环链表并由头指针first指示。 最后，设计约瑟夫环问题的算法。 3. 基本要求 ●建立模型，确定存储结构。 ●对任意n个人，密码为m，实现约瑟夫环问题。 ●出圈的顺序可以依次输出，也可以用一个数组存储。 4.算法设计 1.系统里面自己定义了一个fun1函数，用来执行创建循环列表的功能。 YUE * fun1(int n) { YUE *head,*p1,*p2; int i; for(i=1;i<=n;i++) { p1=(YUE *)malloc(S()); if(i==1) head=p1; else p2->next=p1; p1->n=i; p2=p1; }
p1->next=head; return head; } 2.系统里面另外有定义了一个fun2的函数，用来执行满足条件出队列的功能。 int fun2(YUE *p) { YUE *p2; int n; p2=p->next; n=p2->n; p->next=p2->next; free(p2); return n; } 3.在程序的开端，首先定义了一个链表结构。 typedef struct yuesefu { int n; struct yuesefu *next; } YUE; 4.在程序的中间部分，是程序的主函数，用来判断条件的满足与否。 YUE * fun1(int n); int fun2(YUE *p); int main() { int m,i,n,j,s; YUE *p,*p2; printf("n="); scanf("%d",&n); printf("m="); scanf("%d",&m); printf("i=");
约瑟夫环实验报告(3种方法实现)
约瑟夫环的三种实现方法的实验报告 公选题：约瑟夫环（使用一维数组、一维结构体数组、循环链表三种方法完成）一，实验目的 1、学会通过对问题的分析，设计一种合理的数据结构，并进行定义及操作的实现。 2、掌握利用一维数组，结构体，还有循环链表的各种操作来进行具体的实际应用。 3、加强程序设计的能力。 二，实验内容 什么是约瑟夫环？ 约瑟夫环是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。 举例如下； n = 9, k = 1, m = 5 【解答】 出局人的顺序为5, 1, 7, 4, 3, 6, 9, 2, 8。 三，怎么用程序来实现这个实际场景？ 要实现这个场景有多种语言（C，C++，JA V A语言，C#），每一种语言在实现的过程中各有不同，在实现上复杂程度也不同。针对自己目前的水平以及查阅相关资料，做了如下的一些解决方案。 四，三种解决方法（） 1，使用一维数组： #include
{ int x; printf("请输入第%d个元素的值：\n",i+1); scanf("%d",&x); a[i]=x; i++; } printf("所有元素信息如下：\n"); for(int j=0;j
约瑟夫环实验报告
实验一线性表的基本操作及其应用 一、实验目的 1、帮助读者复习C++语言程序设计中的知识。 2、熟悉线性表的逻辑结构。 3、熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉链表的操作为侧重点。 二、实验内容和要求 [问题描述] 约瑟夫（Joseph）问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。 [基本要求] 利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。[测试数据] 由学生任意指定。 如：m的初值为20；n的值为7；密码：3，1，7，2，4，8，4； （正确的输出结果应为6，1，4，7，2，3，5）。 (报告上要求写出多批数据测试结果) [实现提示] 程序运行后首先要求用户输入初始报数上限值m，人数n,(设n≤30)。然后输入各人的密码。 [选作内容] 向上述程序中添加在顺序结构上实现的部分。 三、算法设计 1、主要思想： 首先，设计实现约瑟夫环问题的存储结构。由于约瑟夫环本身具有循环性质，考虑采用循环链表，为了统一对表中任意节点的操作，循环链表不带头结点。循环链表的结点定义为如下结构类型：
typedef struct LNode { int num,pwd; //num存储人的序号，pwd存储人的密码 struct LNode *next; }; 其次，建立一个不带头结点的循环链表并由头指针Head指示。 最后，设计约瑟夫环问题的算法。 2、本程序包含四个模块 1）主函数 void main() { int m,n;//分别为报数上限和人数 printf("\n参数m,n传递报数上限和人数.\n\n请输入m和n：\n"); scanf("%d %d",&m,&n); creatLinkList(n);//带哦用创建链表函数 enterPwd(n);//调用输入密码函数 printf("\n出列的人依次是：\n"); outList(m,n); } 2）创建链表函数creatLinkList()——根据用户输入的人数创建人数相等数量结点的循环链表。 3）输入密码函数enterPwd()——根据用户输入的密码，存入相应结点的数据域pwd； 4）输出出列人的序号函数outList(m,n) 3、核心算法 根据用户输入的报数上限以及人数，在一个循环里面循环和人数相等的次数。这个循环里面还有一个小的循环用于找到每次出列的结点，小循环找到了出列结点的上一个结点。然后记下这个结点，接着去除要出列结点的数据域里的pwd，然后free （）这个结点。开始找下一个出列的结点。 for(i=1;i<=n;i++) //搜索循环链表 { for(a=1;a
约瑟夫环实验报告
实验报告 课程名称：数据结构班级：实验成绩： 实验名称：顺序表和链表的应用学号：批阅教师签字： 实验编号：实验一姓名：实验日期： 指导教师：组号：实验时间： 一、实验目的 （1）掌握线性表的基本操作（插入、删除、查找）以及线性表合并等运算在顺序存储结构、链式存储结构上的实现。重点掌握链式存储结构实现的各种操作。 （2）掌握线性表的链式存储结构的应用。 二、实验内容与实验步骤 （1）实验内容： 实现约瑟夫环，约瑟夫环（Joseph）问题的一种描述是：编号为1、2、3……n的n个人按照顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按照顺时针的方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。设计一个程序求出出列顺序。 （2）抽象数据类型和设计的函数描述，说明解决设想。 首先定义一个链表，用其中的data项存储每个人的编号，用password项存储每个人所持有的密码，并且声明一个指针。之后使用CreatList_CL函数来创建一个循环链表，在其中的data和password中存入编号和密码，最后使最后一个节点的next指向L，使其能够形成循环队列。定义了函数Display来显示链表当中的内容，以确定存储的数据没有错误。定义了函数Delete_L来实现约瑟夫环中依次删除的功能，依次比较，如果某个人所持的密码和m值相等，则删除这个结点，并且输出此时该结点的编号和密码，实现出列的功能。 （3）简短明确地写出实验所采用的存储结构，并加以说明。 该实验我主要采用的是线性表的链式存储结构，首先定义了链表的结构，其中包括data 项和password项，分别存储每个人的编号和所持密码，还声明了指向下一个结点的指针，该指针可以连接各个结点，并且将最后一个结点的指针指向第一个结点使之成为一个循环链表。 三、实验环境 操作系统：Windows 7 调试软件名称：VC++ 版本号：6.0 上机地点：综合楼311 四、实验过程与分析 （1）主要的函数或操作内部的主要算法，分析这个算法的时、空复杂度，并说明设计的巧
题目：约瑟夫环问题
数据结构上机实验报告 02090401 12 雒文杰题目：约瑟夫环问题 一．问题描述 设有n个人围做一圈，现从某个人开始报数，数到m的人出列，接着从出列的下一个人开始重新报数，数到m的人又出列，如此下去，直到所有人都出列为止。试设计确定他们的出列次序序列的程序。 二．基本要求 运用循环单链表解决约瑟夫环问题。 三．算法说明 本程序采用循环单链表的算法来解决约瑟夫环问题：建立一个循环单链表，按顺序查找指定结点，找到后删除，最后打印删除的编号序列。 四．源程序清单 #include {new_node=(clink)malloc(sizeof(cnode)); if(!new_node) return NULL; new_node->data=array[i]; new_node->order=i+1; new_node->next=NULL; before->next=new_node; before=new_node; } new_node->next=head; return head; } void main() {clink head,ptr; int find,j,i,a,list[n]; printf("Please input 'm'\n"); for(i=0;i 《数据结构与算法设计》约瑟夫环实验报告 ——实验一 专业：物联网工程 班级：物联网1班 学号：15180118 姓名：刘沛航 一、实验目的 1、熟悉VC环境，学习使用C语言利用链表的存储结构解决实际的问题。 2、在编程、上机调试的过程中，加深对线性链表这种数据结构的基本概念理解。 3、锻炼较强的思维和动手能力和更加了解编程思想和编程技 巧。 二、实验内容 1、采用单向环表实现约瑟夫环。 请按以下要求编程实现： ①从键盘输入整数m，通过create函数生成一个具有m个结点的 单向环表。环表中的结点编号依次为1，2，……，m。 ②从键盘输入整数s（1<=s<=m）和n，从环表的第s个结点开始 计数为1，当计数到第n个结点时，输出该第n结点对应的编 号，将该结点从环表中消除，从输出结点的下一个结点开始重 新计数到n，这样，不断进行计数，不断进行输出，直到输出 了这个环表的全部结点为止。 例如，m=10，s=3，n=4。则输出序列为：6，10，4，9，5，2，1，3，8，7。 三、程序设计 1、概要设计 为了解决约瑟夫环的问题，我们可以建立单向环表来存储每 个人的信息（该人的编号以及其下一个人的编号），及结点，人后通过查找每个结点，完成相应的操作来解决约瑟夫问题。 （1） 抽象数据类型定义 ADT Joh{ 数据对象：D={|,1,2,,,0}i i a a ElemSet i n n ∈=≥ 数据关系：R1=11{,|,,1,2,,}i i i i a a a a D i n --<>∈= 基本操作： create(&J, n) 操作结果：构造一个有n 个结点的单向环表J 。 show(J) 初始条件：单向环表J 已存在。 操作结果：按顺序在屏幕上输出J 的数据元素。 calculate( J,s,n) 初始条件：单向环表J 已存在，s>0，n>0，s<环表 结点数。 操作结果：返回约瑟夫环的计算结果。 }ADT Joh （2）宏定义 #define NULL 0 #define OK 1 #define ERROR -1 （3）主程序流程数据结构约瑟夫环实验报告