大学数据结构实验(二.链表的应用二)

大学程序实验.数据结构.链表的应用二.约瑟夫环问题

• ​​0 目录​​
• ​​2 链表的应用​​

• ​​2.2 约瑟夫环问题​​

• ​​2.2.1 题目​​
• ​​2.2.2 源码​​
• ​​1.1.3 下载​​

• ​​2 下一章​​

0 目录

2 链表的应用

2.2 约瑟夫环问题

2.2.1 题目

问题描述：有编号为1, 2…n 的 n 个人按顺时针方向围坐一圈，每人持有一个正整数密码。开始给定一个正整数 m，从第s个人按顺时针方向自1开始报数，报到m者出列，不再参加报数，这时将出列者的密码作为m，从出列者顺时针方向的下一人开始重新自1开始报数。如此下去，直到所有人都出列。试设计算法，输出出列者的序列。
实验要求: 采用链式存储结构实现，可以用循环链表。

2.2.2 源码

// 约瑟夫环链表.cpp : Defines the entry point for the console application.
//
/***********************************************************************
* 头文件包含
***********************************************************************/
#include "stdafx.h"
#include "stdlib.h"
#include "stdio.h"
#include "malloc.h"

/***********************************************************************
* 本地宏定义
***********************************************************************/
#define N 4
#define S 3
#define M 3
#define OK 1
#define ERROR 0

typedef int ElemType;
typedef int Status;

typedef struct Node
{
ElemType num;
ElemType key;
struct Node *next;
}LinkList;

/*********************************************************************
* 函 数 名 : main
* 函数功能 : 主函数
* 参数列表 :
* 函数输出 :
*********************************************************************/
Status main()
{
LinkList *L;

Status ListMenu();
Status ListCheck();
LinkList *creat();
Status ListRank(LinkList *L);

int result;
ListMenu();
result=ListCheck();

if(result)
{
printf("检测完成!\n");
printf("\n");
L=creat();
ListRank(L);
}
else
{
printf("请输入正确的M或N值!");
}

return OK;
}

/*********************************************************************
* 函 数 名 : ListMenu
* 函数功能 : 目录函数
* 参数列表 :
* 函数输出 :
*********************************************************************/
Status ListMenu()
{
printf("***********约瑟夫环*********** \n");

return OK;
}

/*********************************************************************
* 函 数 名 : main
* 函数功能 : 主函数
* 参数列表 :
* 函数输出 :
*********************************************************************/
Status ListCheck()
{
printf("数据检测：\n");

if(N<=1)
{
printf("输入的总人数有误!\n");
return ERROR;
}
else if((S<1)||(S>N))
{
printf("输入初始值有误!\n");
return ERROR;
}
else if(M<0)
{
printf("输入上限值有误!\n");
return ERROR;
}
else
{
printf("参加人数:%3d\n",N);
printf("开始位次:%3d\n",S);
printf("上报数值:%3d\n",M);
}

return OK;
}

/*********************************************************************
* 函 数 名 : creat
* 函数功能 : 创建函数
* 参数列表 :
* 函数输出 :
*********************************************************************/
LinkList *creat()
{
LinkList *p,*q,*head;
int i=1;
head=p=(LinkList *)malloc(sizeof(LinkList));

printf("正在随机生成%d个同学的整数密码:\n",N);
p->num=i;
printf("第1个人的密码:");
printf("%d\n",p->key=rand()%N+1);

for(i=2;i<=N;i++)
{
q=(LinkList *)malloc(sizeof(LinkList));
if(q==0)
{
return(0);
}

printf("第%d个人的密码:",i);
printf("%d\n",q->key=rand()%N+1);

q->num=i;
p->next=q;
p=q;
}

p->next=head;
return head;
}

/*********************************************************************
* 函 数 名 : ListRank
* 函数功能 : 功能函数
* 参数列表 :
* 函数输出 :
*********************************************************************/
Status ListRank(LinkList *L)
{
int i,value=M;
LinkList *p=L,*q,*s;

printf("出列顺序为:");

for(i=1;i<S;i++)
{
p=p->next;
}

while(p->next!=p)
{
for(i=1;i<value;i++)
{
q=p;
p=p->next;
}

printf("%3d",p->num);
value=p->key;
s=p;

q->next=p->next;
p=p->next;
free(s);
}

printf("%3d",p->num);
printf("\n");

return OK;
}

1.1.3 下载

链接地址: ​​2.2_约瑟夫环链表.cpp​​

2 下一章

博客地址: ​​大学数据结构实验(三.栈和队列的应用一)​​