《数据结构与算法设计》
实验报告
——实验一
学院：自动化学院
班级：06111001
学号：1120101525
姓名：王冬
一、 实验目的
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=
数据关系：R1=
基本操作：
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）主程序流程
（4） 模块调用关系
程序分为下述模块：
1）主函数模块——执行输入调用其他的功能函数
2）创建环表模块——创建单向环表
3）计算处理模块——计算出要出列的标号并输出
4）显示模块——输出建立好的环表
调用关系如下：
主函数模块
创建环表模块
显示模块
计算处理模块
2、详细设计
(1)数据类型设计
typedef int ElemType; //元素类型
typedef struct {
ElemType data;
struct Joh *next;
}Joh, *LinkList,*p; //结点类型，指针类型
(2)操作算法
Status create(LinkList &J,int n){
//创建一个有n个结点的单向环表
if(n<=0)
return ERROR; //n<0错误
J=(LinkList)malloc(sizeof(J));
J->data=1;
J->next=J;//建立第一个结点
for(int i=n;i>1;--i){
p=(LinkList)malloc(sizeof(J));
p->data=i;
p->next=J->next;J->next=p;//插入到表头
}
return OK;
}//create
void show(LinkList J){//主要的操作函数
//顺序输出环表J的结点
p=J;
printf("%d ",p->data);
p=p->next;
while(p!=J){ //循环终止条件
printf("%d ",p->data);
p=p->next;
}
}//show
void calculate(LinkList J,int s,int n){
p=J;
Joh *head=p; //声明结点
while(p->data!=s){
p=p->next;
head=p;
}//寻找起始结点
while(p->next!=p){ //终止条件
for(int i=0;i<n-1;i++){
head=p; //保存前置节点
p=p->next;
}
printf("%d ",p->data);
head->next=p->next; //删除已输出结点
p=head->next;
}
if(n!=1)
printf("%d\n",p->data);
else
printf("\n");
}//calculate
(3)主函数代码
int main(){//主函数
Joh *J;int m,s,n;
printf("The num of node is:");
scanf("%d",&m);
create(J,m); //创建单向环表J
show(J); //输出J的数据
printf("\n");
printf("The first node which you want is:");
scanf("%d",&s);
printf("The internal which you want is:");
scanf("%d",&n);
calculate(J,s,n); //计算并输出结果
return 0;
}//main
四、程序调试分析
1、细节决定成败，编程最需要的是严谨，如何的严谨都不过分，往往检查了半天发现错误发生在某个括号，分号，引号，或者数据类型上。在写主要操作函数caculate（）时，在终止条件的书写处不是很清楚，导致我浪费了很多时间。
2、还有一点很大的感触就是，在自己绞尽脑汁都解决不了遇到的问题时，一个很好的手段就是询问同学，寻求其帮助，就比如我在想函数终止条件时，同学一句简单的话语就让我如梦初醒。这不是什么丢脸的事情，相反的，在快速解决问题的同时，还会收获友谊，不是一举两得吗。我想，这也是合作学习的真谛吧。
五、用户使用说明
1、本程序的运行环境为Windows操作系统下的Microsoft Visual C++ 6.0。
2、在VC环境下打开程序后，按要求键入要求的数字，以等号或空格断开，敲击“回车符”，即可以显示要求的结果。
3、按下任意键以继续。
六、程序运行结果
测试用例1：
输入：m=10,s=3，n=4 输出：6，10，4，9，5，2，1，3，8，7
测试用例2：
输入：m=13，s=4，n=3 输出：6，9，12，2 ，5，10 ，1， 7 ，13 ，8 ，4 ，11 ，3
七、程序清单
#define NULL 0
#define OK 1
#define ERROR 0
typedef int Status;
typedef int ElemType;
typedef struct {//结点类型
ElemType data;
struct Joh *next;
}Joh,*LinkList;//定义约瑟夫结构
Joh *p;
#include"stdio.h"
#include"stdlib.h"
Status create(LinkList &J,int n){
if(n<=0)
return ERROR;
J=(LinkList)malloc(sizeof(J));
J->data=1;
J->next=J;//建立第一个结点
for(int i=n;i>1;--i){
p=(LinkList)malloc(sizeof(J));//申请空间
p->data=i;
p->next=J->next;J->next=p;//插入到表头
}
return OK;
}//构造函数
void show(LinkList J){
p=J;
printf("%d ",p->data);
p=p->next;
while(p!=J){ //循环结束条件
printf("%d ",p->data);
p=p->next;
}
}//显示函数
void calculate(LinkList J,int s,int n){
p=J;
Joh *head=p;
while(p->data!=s){
p=p->next;
head=p;
}//寻找起始结点
while(p->next!=p){
for(int i=0;i<n-1;i++){
head=p; //保存前置结点
p=p->next;
}
printf("%d ",p->data);
head->next=p->next; //删除已输出结点
p=head->next;
}
if(n!=1)
printf("%d\n",p->data);
else
printf("\n");
}//主体计算函数
int main()
{
Joh *J;int m,s,n;
printf("The num of node is（m=）:");
scanf("%d",&m);
create(J,m); //创建单向环表J
show(J); //显示J的数据内容
printf("The first node which you want is（s=0）:");
scanf("%d",&s);
printf("The internal which you want is(n=):");
scanf("%d",&n);
calculate(J,s,n); //计算并输出最后结果
return 0;
}
第二篇：C++约瑟夫环实验报告
数据结构集中上机
试验报告
学院： 计算机科学与技术 专业：计算机科学与技术
学号：111111111111 班级：（6） 姓名： 莫莫莫
20010.10.7
joseph环上机实验报告
实验名称：joseph环
题目要求的约瑟夫环操作：编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。
实验要求：1~）利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。
2~）建立输入处理输入数据，输入每个人的密码，建立单循环链表。
3~）测试数据：m的初值为6，n=7 ,7个人的密码依次为3，1，7，2，4，8，4，首先m=6,则正确的输出是什么？
实验过程：
1.基本算法以及分析：
本程序主要是以建立单循环链表的形式，建立起一个约瑟夫环，然后根据之前创立的结点，输入结点里的一些数据，如下
struct Joseph
{
long number;
Joseph* next;
float score;
};程序有主函数开始，首先，提示输入每个环上所带的密码。然后，开始调用Joseph*Create()函数，利用单循环链表建立起约瑟夫环， pEnd->next=head;就是将最后一个结点的后继指向头结点，函数结尾 return( head); 将约瑟夫环的头指针返回，并将它赋值head，依次录入各节点的密码值，然后主函数继续调用 Delete函数，实现如下功能：
编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。
2.程序源代码：
约瑟夫环
#include<iostream>
using namespace std;
struct Joseph
{
long number;
Joseph * next;
float score;
};
Joseph* head;
Joseph*Create()
{
int k=1;
Joseph*ps; //当前要插入的结点
Joseph*pEnd; //链尾指针
ps=new Joseph; //为当前要插入的结点分配空间
cin>>ps->score;
ps->number=k++;
head=NULL; //初始化链表，开始时链表为空
pEnd=ps;
while(ps->score!=0) //以输入的学生号为0作为结束条件
{
if(head==NULL) //当前插入的结点为链表的第一个结点
head=ps;
else
pEnd->next=ps;
pEnd=ps;
ps=new Joseph;
cin>>ps->score;
ps->number=k++;
}
pEnd->next=head;
delete ps; //释放结点成员number为0的结点所占的内存
return (head);
}
void Delete(Joseph *q,int m)
{
Joseph *p;
Joseph *pGuard;
pGuard=q;
p=new Joseph;
p->next=pGuard;
while(pGuard->next!=pGuard) //循环判断，若只剩下最后一个节点，则循环结束
{
for(int i=1;i<m;i++) //开始顺序报数
{
p=pGuard;
pGuard=pGuard->next;
}
p->next=pGuard->next;
cout<<pGuard->number <<" have been deleted\n"<<endl; //输出循环删除的结点
m=pGuard->score; //将节点密码作为新的m值
delete(pGuard);
pGuard=p->next;
}
cout<<pGuard->number <<" have been deleted\n"<<endl; //输出最后删除的结点
}
void main()
{
cout<<"请依次输入每个人的密码：";
head=Create();
Delete(head,6);
}
3.运行结果
初始密码6，输入七个人的密码，以0作为结束条件
输入密码：3 1 7 2 4 8 4
输出结果：6 1 4 7 2 3 5
4
此程序目前的缺点在于，结点密码数据类型定义的存储类型是int型，不能超过-2147483648～2147483648，一旦超过则程序输出结果有误，另一个缺点就是程序运行当中，一旦中途输入出现错误，则无法返回，必须将当前操作结束等到下个主函数的循环开始，或者直接退出重新运行此程序。优点则在于程序运行速度较快，不会出现输出结果有误的问题