北京理⼯⼤学《数据结构与算法设计》实验报告实验⼀《数据结构与算法设计》
实验报告
——实验⼀
学院：
班级：
学号：
姓名：
⼀、实验⽬的
1.通过实验实践、巩固线性表的相关操作；
2.熟悉VC环境，加强编程、调试的练习；
3.⽤C语⾔编写函数，实现循环链表的建⽴、插⼊、删除、取数据等基本操作；
4.理论知识与实际问题相结合，利⽤上述基本操作实现约瑟夫环。
⼆、实验内容
1、采⽤单向环表实现约瑟夫环。
请按以下要求编程实现：
①从键盘输⼊整数m，通过create函数⽣成⼀个具有m个结点的单向环表。环表中的
结点编号依次为1，2，……，m。
②从键盘输⼊整数s（1<=s<=m）和n，从环表的第s个结点开始计数为1，当计数到
第n个结点时，输出该第n结点对应的编号，将该结点从环表中消除，从输出结点
的下⼀个结点开始重新计数到n，这样，不断进⾏计数，不断进⾏输出，直到输出
了这个环表的全部结点为⽌。
三、程序设计
1、概要设计
为实现上述程序功能，应⽤单向环表寄存编号，为此需要建⽴⼀个抽象数据类型：单向环表。
（1）、单向环表的抽象数据类型定义为：
ADT Joseph{
数据对象：D={ai|ai∈ElemSet,i=1,2,3……,n,n≥0}
数据关系：R1={ |ai∈D,i=1,2,……,n}
基本操作：
create(&L,n)
操作结果：构造⼀个有n个结点的单向环表L。
show(L)
初始条件：单向环表L已存在。
操作结果：按顺序在屏幕上输出L的数据元素。
Josephf( L,m,s,n)
初始条件：单向环表L已存在， s>0,n>0，s
操作结果：返回约瑟夫环的计算结果。
}ADT Joseph
（2）、主程序流程
主程序⾸先调⽤create(&L,n)函数，创建含有m个节点的单向环表L，然后调⽤show(L)函数，顺序输出链表中的数据，最后调⽤Josephf( L,m,s,n)函数，依次输出报的数。
（3）、函数调⽤关系图
2、详细设计
(1)、数据类型设计
typedef int ElemType; //定义元素类型
typedef struct Lnode{
ElemType data;
struct Lnode *next;
}Lnode,*Linklist; //定义节点类型，指针类型
（2）、操作算法程序实现：
void create(Linklist &L,int m)
{
//⽣成⼀个具有m个结点的单向环表，环表中的结点编号依次为1，2，……，m Linklist h,p;
L=(Linklist)malloc(sizeof(Lnode));
L->data = 1;
h=L;
for(int i=2;i<=m;i++)
{
p = (Linklist)malloc(sizeof(Lnode));
数据结构与算法c++版 pdfp->data = i; //⽣成新节点，数据为节点编号
h->next = p;
h = p; //插⼊链表
}
h->next = L; //形成循环链表
}
void show(Linklist L,int m)
{
//从第⼀个节点开始依次输出节点编号
printf("The numbers of the list are: \n"); //提⽰⽤户
h=L;
for(int i=1;i<=m;i++)
{
printf("%d ",h->data);
h = h->next;
}
printf("\n");
}
void Josephf(Linklist &L,int m,int s,int n)
{
//实现约瑟夫环
Linklist h,q;
h = L;
q = L;
while(h->data != s) //定位开始的节点
h = h->next;
while(q->next!=h) //定位在开始位置的上⼀个节点q = q->next; for(int j=1;j<=m;j++)
{
int i=1;
while(i
{
q=q->next;
i++;
}
printf("%d ",q->next->data); //依次输出报号为n的节点
q->next = q->next->next; //删除已输出节点
}
printf("\n");
}
（3）、主程序的代码实现：
int main()
{
int s,m,n;
printf("请输⼊节点数m：\n"); scanf("%d",&m);
create(L,m); //建⽴循环链表show(L,m); //输出链表数据printf("请输⼊起始位置s：\n"); scanf("%d",&s);
printf("请输⼊报的数n：\n"); scanf("%d",&n);
Josephf(L,m,s,n); //输出所报数字

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。