数据结构上机实验报告

1、需求分析

　1：用一个循环链表实现n个人按顺时针排成一圈,每个人看作一个节点,每个节点都是一个结构体类型,包含三个域: 序号域(data), 密码域(key),指向下一个人的指针域(next).

　　2：程序开始时由用户任意输入人数n及一个正整数作为报数上限值m,一个正整数作为密码最大值，判断所输密码是否在范围内。然后为依次每一个人指定一个密码

　　3：初始密码为用户外部输入的密码m, 从第一个人开始按顺市针方向自1开始报数.,报道m的时停止,报m的人出列,将他的密码作为新的密码值(m), 从他在顺针方向的下一个人开始重新从1报数,如此下去,直至所有的人全部出列为止.

　　4：本程序最终结果为n 的人的出列顺序

　　5：测试数据: m的初值为1; n =5(即有5个人)57个人的密码依次为:1，2，3,4，5.首先没的值为1,正确的出列顺序应为1，2，4，3，5。

2概要分析

（1）抽象数据类型的定义：

为实现上述程序的功能，可以用整数存储用户的输入。并将用户输入的值存储于线性表中。

算法的基本思想：约瑟夫环问题中的数据是人所在的位置，而这种数据是存在“第一元素、最后元素”，并且存在“唯一的前驱和后继的”，符合线性表的特点。由于需要模拟约瑟夫环的出列问题，可以采用顺序表来实现线性表，完成出列顺序的输出。

核心算法主要分为两步：

1、确定需要删除的位置，2、设置并删除该位置。

已知报数间隔m，我们可以把当前位置加上m获得需要删除的位置，如果获得的位置超过顺序表中实际元素的总长度，则可以通过减去数组的实际长度来修正（即模拟环状计数）。然后把顺序表中的当前指向位置设置为该位置，继而删掉该位置。

反复进行上述确定位置和删除位置的操作，直到顺序表为空。

（2）主程序的流程：

程序由三个模块组成：

（1）输入模块：无提示语句，直接输入总人数n和报数次数m，中间用逗号隔开。

…… …… 余下全文

一、上机实验的问题和要求：

约瑟夫环

问题描述：编号是1,2,…,n(n>0)的n个人按照顺时针方向围坐一圈，每人持有一正整数密码。开始时任选一个正整数作为报数上限值m，从某个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。令n最大值取30。设计一个程序来求出出列顺序，并输出结果。

基本要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各人的编号。

二、程序设计的基本思想，原理和算法描述：

（包括程序的结构，数据结构，输入/输出设计，符号名说明等）

（1）算法的基本思想：

 约瑟夫环问题中的数据是人所在的位置，而这种数据是存在“第一元素、最后元素”，并且存在“唯一的前驱和后继的”，符合线性表的特点。由于需要模拟约瑟夫环的出列问题，可以采用顺序表来实现线性表，完成出列顺序的输出。

核心算法主要分为两步：

1、确定需要删除的位置，

2、设置并删除该位置。

    已知报数间隔m，我们可以把当前位置加上m获得需要删除的位置，如果获得的位置超过顺序表中实际元素的总长度，则可以通过减去数组的实际长度来修正（即模拟环状计数）。然后把顺序表中的当前指向位置设置为该位置，继而删掉该位置。

反复进行上述确定位置和删除位置的操作，直到顺序表为空。

（2）主程序的流程：

程序由三个模块组成：

1、输入模块：无提示语句，直接输入总人数n和报数次数m，中间用逗号隔开。

2、处理模块：将元素储存于顺序表中。在主函数中根据报数间隔确定需要删除的元素的位置，在顺序表中设置该位置并删除该位置，同时输出该位置的值。反复设置并删除直到表空。

3、输出模块：分别在DOS下和文件中，按移除元素的顺序依次显示其位置。

…… …… 余下全文

《数据结构》

实 验 报 告

实 验 课 程：   线性表的应用   

专       业：  **********      

 年级（班级）：  ******          

姓       名：  ***            

学       号：  ******          

实验报告

…… …… 余下全文

工程实践1

项目报告

 20##年12月

成都信息工程学院 计算机学院

一、   问题描述

?    约瑟夫环问题描述：设有n个人围坐在圆桌周围，现从某个位置 i 上的人开始报数，数到 m 的人就站出来。下一个人，即原来的第m+1个位置上的人，又从1开始报数，再是数到m的人站出来。依次重复下去，直到全部的人都站出来，按出列的先后又可得到一个新的序列。要求编制程序，上机验证。

二、   解决方法

解决约瑟夫环问题的四种方法：

1．循环链表

2．循环队列

3．顺序表

4．置标志

三、    四种方法的算法

1、  循环链表算法

 

2、  循环队列算法

 

3．顺序表

 

4．置标志

 

四、   实验中遇到的问题及心得

在解决顺序表的代码过程中，发现数组是从下标为0的地方开始的。所以起始位置输入的时候，要从0开始数。

而其余的代码却都是从第一个数字从1开始数的。

五、   完整源程序（带注解）

1、循环链表代码：

#include <iostream>

using namespace std;

typedef struct student

{

    int data;

    struct student* next;

}node, *LinkList;

//约瑟夫环

void printfList(LinkList head){

    LinkList p = head;

…… …… 余下全文

实验1约瑟夫环问题

1．  需求分析

（1）   输入的形式和输入值的范围：

每一次输入的值为两个正整数，中间用逗号隔开。

若分别设为n,m，则输入格式为：“n,m”。

不对非法输入做处理，即假设输入都是合法的。

（2）   输出的形式：

输出格式1：在字符界面上输出这n个数的输出序列

输出格式2：将这n个数的输出序列写入到文件中

（3）   程序所能达到的功能：

对于输入的约瑟夫环长度n和间隔m，输出约瑟夫环的出列顺序。

（4）   测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。

正确：

输入：10,3                        

输出：3 6 9 2 7 1 8 5 10 4       

输入：41,3

输出：3 6 9 12 15 18 21 24 27 30 33 36 39 1 5 10 14 19 23 28 32 37 41 7 13 20 26 34 40 8 17 29 38 11 25 2 22 4 35 16 31

错误：

输入：10 3

输出：6 8 7 1 3 4 2 9 5 10

2．  概要设计

（1）抽象数据类型的定义：

为实现上述程序的功能，可以用整数存储用户的输入。并将用户输入的值存储于线性表中。线性表ADT定义如下：

…… …… 余下全文

题目：约瑟夫环问题

班级：姓名：学号：完成日期：2011.12.28

一、需求分析

1.问题描述：设有n个人围坐在一个圆桌周围，现从第s个人开始报数，数到第m的人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，…，如此反复直到所有的人全部出列为止。

2.测试时n=8，s=1，m=4，若初始的顺序为1,2,3,4,5,6,7,8,则问题的解为4,8,5,2,1,3,7,6。

二、概要设计

为实现上述程序功能，应以循环队列表示。循环队列可用数组实现，但由于n是变量，我选择以单向链表实现循环队列。通过移动头结点的指针来实现“重新开始报数”，以循环实现计数。

1.       循环队列的抽象数据类型定义为：

ADT LinkQueue{

数据对象：D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}

数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,…,n}约定其中a1端为队列头，an端为队列尾。

基本操作：

InitQueue(&Q)

操作结果：构造一个空队列Q。

GetHead(Q,&e)

初始条件：Q为非空队列。

操作结果：用e返回Q的队头元素。

EnQueue（&Q,e）

初始条件：队列Q已存在。

操作结果：插入元素e为Q的新的队尾元素。

DeQueue（&Q,&e）

初始条件：Q为非空队列。

操作结果：删除Q的队头元素，并用e返回其值。

}ADT LinkQueue

2．本程序包含3个模块：

1）结点定义模块——对表结点进行定义

2)子函数定义模块——对链表的各操作的定义

3)主程序模块

模块之间的关系为主函数调用子函数模块，子函数调用结点结构。

三、详细设计

1．  头函数、元素类型、结点类型和指针类型

…… …… 余下全文

数据结构实验报告

1.2 约瑟夫环(线性表)

【问题描述】约瑟夫问题的一种描述是：编号为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）

源程序

#include<iostream>

#include<stdio.h>

#include<malloc.h>

using namespace std;

struct node

{

   int no; //代表编号结点的数据

   int code;//代表密码结点的数据

   node *next;//代表后一个结点的地址

};

int main()

{

   int m,n,i,j;

   node *p,*q,*first;

   printf("请输入m的初始值 :\n");

   scanf("%d",&m);

   printf("请输入人数 n:\n");

   scanf("%d",&n);

…… …… 余下全文