工作报告之约瑟夫环实验报告总结.pdf

工作报告之约瑟夫环实验报告总结--第1页

约瑟夫环实验报告总结

【篇一：约瑟夫环实验报告】

实验报告

课程名称：数据结构

实验名称：顺序表和链表的应用

实验编号：实验一

指导教师：

一、实验目的

（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）简短明确地写出实验所采用的存储结构，并加以说明。

工作报告之约瑟夫环实验报告总结--第1页

工作报告之约瑟夫环实验报告总结--第2页

该实验我主要采用的是线性表的链式存储结构，首先定义了链表的

结构，其中包括data项和password项，分别存储每个人的编号和

所持密码，还声明了指向下一个结点的指针，该指针可以连接各个

结点，并且将最后一个结点的指针指向第一个结点使之成为一个循

环链表。

三、实验环境

操作系统：windows7

调试软件名称：vc++

版本号：6.0

上机地点：综合楼311

四、实验过程与分析

（1）主要的函数或操作内部的主要算法，分析这个算法的时、空复

杂度，并说明设计的巧班级：学号：姓名：组号：实验成绩：批

阅教师签字：实验日期：实验时间：

妙之处。

本实验中主要的函数包括创建链表、显示链表内容和出列过程四个

部分。主要函数的代

码如下：

创建链表：

typedefintdatatype;

typedefstructnode//链表的定义

{

datatypedata;

intpassword;

structnode*next;

}listnode,*clinklist;

voidcreatlist_cl(clinklist*l,intn)//创建一个链表

{

int