约瑟夫环数据结构（约瑟夫环 c++ 数据结构）

本文目录

• 约瑟夫环 c++ 数据结构
• 关于C语言数据结构的问题（约瑟夫环）
• 数据结构（c语言版）--约瑟夫环
• 约瑟夫环（Joseph）问题数据结构的实验c++编程~
• JAVA还有一个关于约瑟夫环的数据结构实验--我不知道怎么实现计数时跳过标记为null的那个啊！！！
• 谁能用循环队列的数据结构解决约瑟夫环问题
• 数据结构约瑟夫环问题急求程序
• 数据结构试验设计上老师提出了一个问题，关于线性结构的应用，约瑟夫环问题.
• 约瑟夫环 数据结构

约瑟夫环 c++ 数据结构

#include《iostream》
using namespace std;
struct LinkList
{
int number;
LinkList *next;
};
LinkList *CreateList(LinkList *L,int &n,int &m);
void Joseph(LinkList *L,int n,int m);
LinkList *DeleteList(LinkList **L,int i,LinkList *q);
int LengthList(LinkList *L);
void main()
{
LinkList *L;
L=NULL;
int n, m;
cout《《“请输入人数N：“;
cin》》n;
cout《《“请输入所报数M：“;
cin》》m;
L=CreateList(L,n,m);
Joseph(L,n,m);
}
LinkList *CreateList(LinkList *L,int &n,int &m)
{
LinkList *q;
for(int i=1;i《=n;i++)
{
LinkList *p;
p=new LinkList;
p-》number=i;
p-》next=NULL;
if(i==1) L=q=p;
else
{
q-》next=p;
q=q-》next;
}
}
q-》next=L;
return(L);
}

void Joseph(LinkList *L,int n,int m)
{
int k;
cout《《“请输入第一个报数人：“;
cin》》k;
cout《《“\n出列顺序:\n“;

for(int i=1;i《n;i++)
{
LinkList *q = new LinkList;
if(i==1) q=DeleteList(&L,k+m-1,q);
else q=DeleteList(&L,m,q);
cout《《“号数：“《《q-》number《《endl;
delete q;
}
cout《《“号数：“《《L-》number《《endl;;
}

LinkList *DeleteList(LinkList **L,int i,LinkList *q)
{
if(i==1) i+=LengthList(*L);
LinkList *p;
p=*L;
int j=0;
while(j《i-2) {p=p-》next;j++;}
q = p-》next;
p-》next=p-》next-》next;
*L = p-》next;
return(q);
}

int LengthList(LinkList *L)
{
int i=1;
LinkList *p=L-》next;
while(p!=L)
{
i++;
p=p-》next;
}
return(i);
}

关于C语言数据结构的问题（约瑟夫环）

#include《string.h》
#include《ctype.h》
#include《malloc.h》 // malloc()等
#include《limits.h》 // INT_MAX等
#include《stdio.h》 // EOF(=^Z或F6),NULL
#include《stdlib.h》 // atoi()
#include《io.h》 // eof()
#include《math.h》 // floor(),ceil(),abs()
#include《process.h》 // exit()
#include《iostream》 // cout,cin
#include 《conio.h》

// 函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1

///////////////////////////////////////////////////////////////////////////
typedef int Status;

typedef int ElemType;

typedef struct NodeType
{
ElemType data,locate;
NodeType *next;
} NodeType,*LinkType; //结点类型，指针类型

typedef struct OrderedList{

LinkType head; //分别指向线性链表的头结点和尾结点
int size; //指示链表当前的长度
}OrderedList; //有序链表类型

///////////////////////////////////////////////////////////////////////////
bool InitList(OrderedList &L,int n)
{
if(n==0)
return ERROR;

int i;
LinkType q;

if(L.head=((NodeType*)malloc(sizeof(NodeType))))
{
printf(“请输入第1个人的密码:“);
scanf(“%d“,&L.head-》data);
L.size=1;
L.head-》locate=1;
L.head-》next = L.head;
}
else
return ERROR;

q=L.head;
for(i=2;i《=n;i++)
{
if(q-》next=((NodeType*)malloc(sizeof(NodeType))))
{
q=q-》next;
printf(“请输入第%d个人的密码:“,i);
scanf(“%d“,&q-》data);
L.size++;
q-》locate=i;
}
else
return ERROR;
}
q-》next=L.head;

return TRUE;
}

void Joseph(OrderedList &L,int m)
{
LinkType p = L.head;
LinkType q = p;
int i;
printf(“输出顺序如下:“);
while( L.size 》 0 )
{
i = m - 1;
while( i 》 0 )
{
q = p;
p = p-》next;
i--;
}
printf(“第%d个人，密码为:%d\n“,p-》locate,p-》data);
q-》next = p-》next;
free(p);
L.size--;
p = q-》next;
}
}

void main ()
{
int m;
int n;
OrderedList T;

//n表示约瑟夫环中节点个数，m表示报数循环的个数
printf(“请输入n 与 m 的值\n“);
scanf(“%d %d“,&n,&m);
if (n《1||m《1)
{
printf(“对不起，输入有误！“);
exit(OVERFLOW);
}

InitList(T,n);
Joseph(T,m);

getchar();
getchar();
}

数据结构（c语言版）--约瑟夫环

你连一分都不给，大家谁会来帮你回答啊！
呵呵。。。。
我人比较好！
还是给你一个程序：
#include《stdio.h》
#include《stdlib.h》
typedef struct data{ //定义一个结构体“data”
int num; //用于存放人的序号
int val; //用于存放密码
}typedata;
typedef struct node{ //定义一个结构体（结点），其中包含一个数据域和一个指针域
typedata data; //结构体的嵌套
struct node *next;
}listnode;
typedef listnode *linklist;
linklist head;

void main()// 进入主函数
{
int n,i,b,m,j;
linklist head=(listnode *)malloc(sizeof(listnode)); //申请一个空间（头结点 head）
listnode *p,*q; //定义两个可以指向结点的指针
printf(“输入总人数：“);
scanf(“%d“,&n);
q=head; //用指针q指向头结点

for(j=1;j《=n;j++) //本次循环主要是将每一个人的数据（包括序号、密码）存入循环链表中
{
printf(“请输入第%d号同学的密码:\n“,j);
scanf(“%d“,&b);
printf(“\n“);
q-》next=(listnode *)malloc(sizeof(listnode));
//将头结点的next域指向刚生成的一个结点
q=q-》next;
q-》data.val=b; //输入密码
q-》data.num=j; //输入序号
q-》next=head-》next; }
//将尾结点的next域指向第一个结点，构成循环链表
printf(“请任意输入一个数m：“);
scanf(“%d“,&m);
if(m《=0) printf(“输入错误“);
do{

i=1;
while(i!=m){ //将q指针指向所要输出的结点的前一结点
q=q-》next;
i++;
}
p=q-》next; //p指向输出结点
q-》next=p-》next; //将输出结点的前结点的next域指向输出结点的后结点
printf(“num:%d\tval:%d\n“,p-》data.num,p-》data.val); //输出
m=p-》data.val; //取得输出结点的密码
free(p);
}while(q-》next!=q); //只剩最后一个结点时结束
printf(“num:%d\tval:%d\n“,q-》data.num,q-》data.val); //输出最后一个结点
free(q); //释放最后一个结点
free(head); //释放头结点
printf(“约瑟夫环结束，欢迎下次光临~·~\n“);
}
//程序结束。

约瑟夫环（Joseph）问题数据结构的实验c++编程~

#include
using
namespace
std;//每个人的号码和密码。struct
people{
int
NO;
int
pass;}node;template
class
Link{private:
static
Link*
freelist;//静态数据成员的头接点。public:
struct
people
element;
Link*
next;
Link(people
elemval,Link*
nextval=NULL)
{
element.NO=elemval.NO;
element.pass=elemval.pass;
next=nextval;
}
Link(Link*
nextval=NULL)
{
next=nextval;
}
void*
operator
new(size_t);//
重载new
函数。
void
operator
delete(void*);//重载delete函数。};template
class
LList{private:
Link
*head;
Link
*tail;
Link
*fence;
void
init()
{
head=tail=fence=new
Link;
tail-》next=head-》next;
//生成链表是要把它的头接点和尾接点连接起来构成循环链表。
//因为有一个空的头接点。所以要把他的尾接点接到头接点的下一个指针。
}
void
removeall()
{
while(head!=NULL)
{
fence=head;
fence=fence-》next;
delete
fence;
}
}public:
LList()
{
init();
}
~LList()
{
removeall();
}
bool
insert(const
people&
T);
bool
remove(Elem&);
void
getOut(int&,int&);
void
prev();
bool
append(const
people&
T);};太长了。。。。去这里看
http://blog.programfan.com/article.asp?id=23037

JAVA还有一个关于约瑟夫环的数据结构实验--我不知道怎么实现计数时跳过标记为null的那个啊！！！

经典的约瑟夫环问题其实就是一个循环链表，从头元素H开始往下数到指定的元素E，你的问题里需要在找到元素E以后加一个判断语句，如果元素E为空则当前指针移动到下一个元素直到元素不为空为止。
Java集合类里的LinkedList可以用来作为循环链表，它综合了数组和链表的优点，可以在常数级别的时间复杂度内进行元素的检索、插入、删除。

谁能用循环队列的数据结构解决约瑟夫环问题

实验一：约瑟夫环实现：
一、 实验目的：加强学生对于线性链表的理解，掌握约瑟夫环这个常用模型的建立方法。
二、 实验设想：以无头结点的循环链表来实现其环状结构。
三、 代码实现：
#include“stdio.h“
#include“stdlib.h“
#define FIRST 1
#define LAMP 2
typedef struct Lnode{
char data;
struct Lnode *next;
} *cylist;
void creat(cylist &L){
char a,b;
cylist p;
cylist s;
L=(cylist)malloc(sizeof(struct Lnode));
L-》next=L;
printf(“请输入环内人员，以#结束:“);
scanf(“%c“,&a);
L-》data=a;
p=L;
scanf(“%c“,&b);
while(b!=’#’){
s=(cylist)malloc(sizeof(struct Lnode));
p-》next=s;
s-》next=L;
s-》data=b;
p=p-》next;
scanf(“%c“,&b);
}
}
void opera(cylist &L,int n,int m){
int i;
cylist p,s;
p=L;
for(i=1;i《n;i++)
p=p-》next;
n=1;
while(p-》next!=p){
if(m-n==1)
{
s=p-》next;
printf(“%c “,s-》data);
p-》next=s-》next;
free(s);
n=0;
}
p=p-》next;
n++;
}
L=p;
}

void main(){
cylist L;
creat(L);
printf(“从第“);
printf(“%d“,FIRST);
printf(“个位置开始报数，数到“);
printf(“%d“,LAMP);
printf(“出列的序列是：“);
opera(L,FIRST,LAMP);
}
四、调试结果：

数据结构约瑟夫环问题急求程序

#include《stdio.h》
#include《stdlib.h》

struct listNode{
int data;
struct listNode *nextPtr;
};

typedef struct listNode LISTNODE;
typedef LISTNODE * LISTNODEPTR;/*LISTNODEPTR：指向LISTNODE指针*/

LISTNODEPTR createList(int n);
void selectKing(LISTNODEPTR headPtr1,int n);
void printList(LISTNODEPTR currentPtr);/*打印链表*/
void destroyList(LISTNODEPTR headPtr);/*释放链表各个结点*/

int main()
{
LISTNODEPTR headPtr1=NULL,headPtr2=NULL;
int count,monkeys;
int n;

printf(“input the amount of monkeys:“);
scanf(“%d“,&monkeys); /*猴子个数*/
printf(“input the count number:“);
scanf(“%d“,&count); /*count＝3，表示每次数到3的猴子出局*/

headPtr1=createList(monkeys);/*创建循环链表*/

selectKing(headPtr1,count);/*选大王。headPtr1指向循环链表。headPtr2指向由淘汰猴子组成地链表*/

system(“PAUSE“);
return 0;
}

/*创建循环链表，容纳n个猴子。返回指向链表头结点的指针*/
LISTNODEPTR createList(int n)
{
LISTNODEPTR headPtr=NULL,tailPtr,currentPtr;
int i;

for(i=1;i《=n;i++){
currentPtr=(LISTNODEPTR)malloc(sizeof(LISTNODE));
if(currentPtr==NULL)
printf(“memory malloc wrong\n“);
else{
currentPtr-》data=i;
currentPtr-》nextPtr=NULL;

if(headPtr==NULL){/*若是作为头结点*/
headPtr=currentPtr;
tailPtr=currentPtr;
}
else{/*将结点追加到链表末尾*/
tailPtr-》nextPtr=currentPtr;
tailPtr=currentPtr;
}
}
}

tailPtr-》nextPtr=headPtr;/*形成循环链表*/

return headPtr;
}

/*从headPtr1指向的循环链表中选大王，数到n的猴子淘汰，将依次淘汰出来的猴子插入到headPtr2指向的链表中*/
void selectKing(LISTNODEPTR headPtr1,int n)/*n》=2*/
{
LISTNODEPTR prePtr1=NULL,currentPtr1,headPtr2=NULL,tailPtr2;
int count;

count=1;
currentPtr1=headPtr1;

while(currentPtr1!=currentPtr1-》nextPtr){
/*往后数一个猴子*/
prePtr1=currentPtr1;
currentPtr1=currentPtr1-》nextPtr;
count++;

/*若数到n，则淘汰currentPtr指向的猴子*/
if(count%n==0){
/*从headPtr1指向链表中拆下currentPtr指向的结点*/
prePtr1-》nextPtr=currentPtr1-》nextPtr;
currentPtr1-》nextPtr=NULL;

/*将currentPtr1指向的结点插入到headPtr2指向链表中*/
if(headPtr2==NULL){/*若headPtr2指向的为空链表*/
headPtr2=currentPtr1;
tailPtr2=currentPtr1;
}
else{ /*将拆下来的结点组装到headPtr2指向的链表上*/
tailPtr2-》nextPtr=currentPtr1;
tailPtr2=tailPtr2-》nextPtr;
}

/*currentPtr1指向上一个结点，为下一次数数做准备*/
currentPtr1=prePtr1;
}
}

printf(“大王是：%d\n“,currentPtr1-》data);
printf(“淘汰的猴子是：“);
printList(headPtr2);

/*释放链表*/
destroyList(headPtr2);
free(currentPtr1);
}

/*函数功能：遍历链表，打印链表中各结点的值。
参数说明：指向结点的指针，接收链表头接点的值*/
void printList(LISTNODEPTR currentPtr)
{
if (currentPtr==NULL)
printf(“the list is empty\n“);
else{
printf(“the list is:\n“);
while(currentPtr!=NULL){
printf(“%d---》“,currentPtr-》data);
currentPtr=currentPtr-》nextPtr; /*currentPtr指向下一个结点*/
}
printf(“NULL\n\n“);
}
}

void destroyList(LISTNODEPTR headPtr)
{
LISTNODEPTR tempPtr;
while (headPtr!=NULL){
tempPtr=headPtr;
headPtr=headPtr-》nextPtr;
free(tempPtr);
}
}

数据结构试验设计上老师提出了一个问题，关于线性结构的应用，约瑟夫环问题.

运用顺序表：(在vs2008上编写的）
#include《stdio.h》
typedef struct
{ int data;
}seqlist;
main()
{
int n=0,m=0,s=0,i=0,j=0,k=0,s1=0,w=0;
seqlist L;
printf(“please input n: “);
scanf(“%d“,&n);
printf(“please input m: “);
scanf(“%d“,&m);
printf(“please input s: “);
scanf(“%d“,&s);L.data=0;
for(i=1;i《=n;i++)
{
L.data[i]=i;
}
s1=s;
for(i=n;i》=2;i--)
{
s1=(s1+m-1)%i;
if(s1==0)
s1=i;
w=L.data[s1];
for(j=s1;j《=i-1;j++)
L.data[j]=L.data[j+1];
L.data[i]=w;
}
for(k=1;k《=n/2;k++)
{
w=L.data[k];
L.data[k]=L.data[n-k+1];
L.data[n-k+1]=w;
}
for(i=1;i《=n;i++)
printf(“ %d “,L.data[i]);
getch();
}

约瑟夫环 数据结构

你看看这个如何
#include 《stdio.h》
#include《stdlib.h》
typedef struct LNode
{
int data;
struct LNode *next;
}LNode,*LinkList;
void Create(LinkList &L,int n)
{//创建不带头结点的循环链表，从1开始自动编号
int i;
LinkList p,q;
for(i=1;i《=n;i++)
{
p=(LinkList)malloc(sizeof(LNode));
p-》data=i;//编号
if(L==NULL)L=q=p;
else
{
q-》next=p;
q=p;
}
}
q-》next=L;//构成循环链表
}
void Joseph(LinkList &L,int n,int s,int m)
{//解约瑟夫环，输出出局序列
int i=1,j=1;//j表示报数号
LinkList p=L,q;
printf(“出局人的编号序列：\n“);
while(i++《s)p=p-》next;//移动到开始报数的编号结点
i=1;
while(n》0)
{
if(j==m-1)//报数到m-1时，准备删除下个结点（即报数到m的人）
{
q=p-》next;//q所指的结点即是要删除的
printf(“%d\t“,q-》data);
if(i++%10==0)printf(“\n“);//每行输出10个数据
p-》next=q-》next;//删除结点（出局）
free(q);
p=p-》next;j=1;//重新开始报数
n--;
}
else
{
j++;
p=p-》next;
}
}
printf(“\n“);
}
void main()
{
LinkList L=NULL;
int N,s,m;//总人数N、开始报数的编号s和出局所报的数字m
printf(“输入N,s,m:\n“);
scanf(“%d%d%d“,&N,&s,&m);
Create(L,N);
Joseph(L,N,s,m);
}