C语言循环单链表解决约瑟夫问题
 #include <stdio.h>
#include <stdlib.h>

typedef int Elemtype;
typedef struct LNode
{
    Elemtype data;
    struct LNode *next;
}LNode,*LinkList;

void createlist(LinkList *head,int n)
{
    int i;
    LinkList p,q;
    *head=(LinkList)malloc(sizeof(LNode));
    (*head)->next=*head;
    p=(*head)->next;
    for(i=0;i<n;i++)
    {
        q=(LinkList)malloc(sizeof(LNode));
        q->data=i+1;
        q->next=p;
        p->next=(*head);
        p=q;//这句代码用处是什么呢?
        printf("%d\n",q->data);
    }
}

void yuesefuList(LinkList head,int n,int m,int k)
{
    int i,rec=0;
    LinkList p,q;
    p=head->next;
    if(m>n)
    {
        printf("error!");
    }
    for(i=1;i<m;i++)
    {
        p=p->next;
        printf("%d\n",p->data);
        if(p->next==head->next)
            p=p->next;
    }

    //开始报数
    while(rec!=n){
    for(i=0;i<k;i++)
    {
        p=p->next;
        if(p->next==head->next)
           p=p->next;
    }
    printf("%d ",p->data);
    //delete
    q=p->next;
    p->next=q->next;
    free(p);
    rec++;
    p=q->next;
    }
}
int main()
{
    LinkList head;
    int n,m,k;
    printf("please enter the number of person\n");
    printf("n=");
    scanf("%d",&n);
    printf("please enter the location of beginning\n");
    printf("m=");
    scanf("%d",&m);
    printf("please enter the number of gap\n");
    printf("k=");
    scanf("%d",&k);
    createlist(&head,n);
    //inputlist(head,n);
    yuesefuList(head,n,m,k);
    return 0;
}

约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。

大概思路是建立一个循环链表,先遍历到开始位置,通过while循环找到下一个结点,输出结点的数据域
通过了编译,但是输出结果是乱七八糟的数字。。。
求大神教教小弟orz

0

1个回答

1、你的链表创建的不对,你的建表方式使得最后两个节点为一个循环;
2、报数过程也有问题,遇到头结点要空开;并且过程逻辑好像不对
下面是改好的代码,没有测试太多例子
#include
#include

typedef int Elemtype;
typedef struct LNode
{
Elemtype data;
struct LNode *next;
}LNode,*LinkList;

void createlist(LinkList head,int n)
{
int i;
LinkList p,q;
*head=(LinkList)malloc(sizeof(LNode));
(*head)->next=*head;
p=(*head)->next;//p相当于尾指针
/*for(i=0;i {
q=(LinkList)malloc(sizeof(LNode));
q->data=i+1;
q->next=p;//这里面既要注意顺序问题,又要注意逻辑上是否正确
p->next=(*head);
p=q;//这句代码用处是什么呢?
printf("%d\n",q->data);
}
/
for(i=0;i {
q=(LinkList)malloc(sizeof(LNode));
q->data=i+1;
p->next=q;
p=q;//使p指向最后一个节点
p->next=(*head);
//printf("%d\n",q->data);
}
}

void yuesefuList(LinkList head,int n,int m,int k)
{
int i,rec=0;
LinkList p,q;
p=head;
if(m>n)
{
printf("error!");
}
//将p永远指向报1的前一个人
//找到第m-1个人的位置,从下一个人开始报数
for(i=1;i {
p=p->next;
printf("%d\n",p->data);
/*if(p->next==head->next)
p=p->next;*///上面已经处理了m>n的情况
}

//开始报数
while(rec!=n){
    q=p->next;//q指向报1的 
for(i=1;i<k;i++)//报数报到k的人出列,为了方便找报k-1的人 
{
    p=q;
    q=q->next;//q指向报i+1的人 
    if(q==head)//由于加了头结点,当循环到头结点时需要移动到下一个节点  
       {q=q->next;p=p->next;}//此时q记录的是报到k的人的前一个人       
}
//本次循环之后,p指向报k-1的,q指向报k的 
//delete
printf("%d \n",q->data);
p->next=q->next;
free(q);
rec++;
}

}
int main()
{
LinkList head;
int n,m,k;
printf("please enter the number of person\n");
printf("n=");
scanf("%d",&n);
printf("please enter the location of beginning\n");
printf("m=");
scanf("%d",&m);
printf("please enter the number of gap\n");
printf("k=");
scanf("%d",&k);
createlist(&head,n);
//inputlist(head,n);
yuesefuList(head,n,m,k);
return 0;
}

0
weixin_41807114
Grey000 回复weixin_43191340: 尾指针是指这个链表最后一个节点,在创建链表的过程中是指(如果用尾插法的话就是指新增的那个节点)
10 个月之前 回复
weixin_41807114
Grey000 回复weixin_43191340: 这个是指创建单链表的过程中的吗?
10 个月之前 回复
weixin_43191340
那边的薯片半价阿 而且p->next=q和p=q这两句作用不是一样吗
10 个月之前 回复
weixin_43191340
那边的薯片半价阿 对不起,我还想问问您,您说p是尾指针,为什么令这个尾指针指向链表最后一个结点后,又在这个尾指针里放上头结点的地址就构成循环链表了呢?我觉得没有链成环呀,尾指针放了头结点的 地址那之前指向最后一个结点不就不作数了
10 个月之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
C语言利用循环单链表解决约瑟夫问题
Description  编号是1,2,……,n的n个人按照顺时针方向围坐一圈,每个人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他的顺时针方向的下一个人开始重新从1报数,如此下去,直到所有人全部出列为止。请设计一个程序输出出列顺序。 提示:存储结构采用不带头结点的循环单链表,...
循环单链表,解决约瑟夫问题
约瑟夫问题: 编号为1~N的N个人按顺时针方向围坐一圈,每人持有一个密码(正整数),开始任选一个正整数作为报数上限值M,从第1个人按顺时针方向自1开始顺序报数,报到M时停止报数。报M的人出列,将他的密码作为新的M值,从他顺时针方向上的下一个人开始从1报数,如此下去,直至所有人全部出列为止。 解析: 显然当有人退出圆圈后,报数的工作要从下一个人开始继续,而剩下的人仍然围成一个圆圈,因此可以使用...
用循环单链表解决约瑟夫问题
http://www.oschina.net/code/snippet_188162_9893
用循环单链表实现约瑟夫环(c语言)
源代码如下,采用Dev编译通过,成功运行,默认数到三出局。 主函数: main.c文件#include <stdio.h> #include "head.h" #include "1.h" int main() { Linklist L; int n; printf("请输入约瑟夫环中的人数:"); scanf("%d",&n); Createlist(
约瑟夫问题 循环单链表解法
m_prear  是指向单链表的尾部的指针。m_prear  ->m_next 是指向头指针。  函数YSF就是对约瑟夫问题的求解方法函数。#include using namespace std; #include "stdlib.h" #define N 13 template class node { public: node() { m_next=NULL; } ~no
约瑟夫问题的C语言解决
约瑟夫问题的C语言解决 大一时写的 没技术含量 简单易懂
约瑟夫问题的循环单链表实现
        大二我们开始学数据结构了,幸好暑假在家好好看了下,现在学的不是特别吃力,一份耕耘,一份收获。呵呵。约瑟夫问题大家都清楚吧,数据结构书本后面有道题目就是讲它。在下一看,兴趣来了,就思考了一会儿。然后就敲程序。#include #include #include 我先包含三个头文件,前两个就不用说了吧,后面一个time后文件,我是想让它自动生成密码,省得自己输入
约瑟夫环问题---循环单链表
约瑟夫环问题是比较经典的问题,原来做的题目是依次输出数字,而原来的循环链表结构不改变,今天遇到一道题是要求按照顺序重新组成一个循环单链表。 题目:一些人围坐一圈报数,形成一个循环单链表,当报数是m或m的倍数时出将节点从单链表中删除,重新加入新的循环单链表,最后形成一个新的循环单链表。 structNode { intdata; Node*...
约瑟夫环问题(循环单链表)
#include&amp;lt;iostream&amp;gt;using namespace std;struct Xlist{    int data;    Xlist *next;};void foundList(Xlist *&amp;amp;lista,int n){    lista=new Xlist;    lista-&amp;gt;next=lista;    Xlist *la;    lista-&amp;gt...
约瑟夫问题的解答(循环单链表)
// 循环链表.cpp : 定义控制台应用程序的入口点。 //约瑟夫问题的解答 /* 约瑟夫问题的原理: 编号为1~N的N个人按顺时针方向围坐一圈,每人持有 一个密码(正整数),开始任选一个正整数作为报数上限值M, 从第1个人按顺时针方向自
第四次博客:循环单链表解决约瑟夫环问题
#include &lt;stdio.h&gt;#include &lt;stdlib.h&gt;typedef struct aa{int data;struct aa *next;}Link;int n; Link * CreateLink(Link *L){Link *p,*q;int i;printf("请输入人数:");scanf("%d",&amp;n);for(i=1;i...
运用循环单链表解决约瑟夫环问题
#include &amp;lt;iostream&amp;gt;  using namespace std;  struct node//构造结点{      node(int a):data(a),next(NULL){}  //为结点初始化(分配空间)       int data;      node *next;  };   class josephus  {  public:      josephu...
如何用循环单链表解决约瑟夫问题?
约瑟夫问题: 人们站在一个等待被处决的圈子里。 计数从圆圈中的指定点开始,并沿指定方向围绕圆圈进行。 在跳过指定数量的人之后,执行下一个人。 对剩下的人重复该过程,从下一个人开始,朝同一方向跳过相同数量的人,直到只剩下一个人,并被释放。 问题即,给定人数、起点、方向和要跳过的数字,选择初始圆圈中的位置以避免被处决。 历史: Josephus有过的故事:39 个犹太人与Josephus及他的...
3.10 约瑟夫环问题--循环单链表解决
/*************************************************************** *约瑟夫环问题 *问题描述:N个人做成一圈,从第K个人开始报数游戏(从0开始报数), 报M的出列,最后剩下的一个人获胜 *算法: 循环单链表(无头节点) *新建单链表: 返回value最小的节点当作"head",新建过程即是插入过程 *删除(出列操
数据结构(三):循环单链表解决约瑟夫问题
#include<iostream> using namespace std; //小孩结点类型 struct Child{ int no; //小孩编号 Child* next; //指针域,指向下一个指针 };//设计运算算法 class Joseph { int n, m; Child *h; //首结点指针 public: Jos
使用循环单链表解决约瑟夫环问题
#include #include #include using namespace std; typedef struct LNode{ int data; struct LNode* link; }LNode,*LinkList; void JOSEPHUS(int n,int k,int m){//n为总人数,k为第一个开始报数的人,m为出列者报的数 LinkList p,r,
c++ 数据结构 用循环单链表解决约瑟夫问题
循环链表为单链表的变形,与单链表的区别在于循环链表的尾结点的指针域不是空,存放的是首结点的地址,因此判断表空的条件不是first->Link==NULL;而是first->Link==first; 约瑟夫问题的求解关键为把围坐一圈的人抽象成循环单链表的数据结构。
循环单链表的实现,解决约瑟夫丢手帕问题
<!DOCTYPE unspecified PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd"> <html> <head><title>php--循环单链表的实现,解决约瑟夫丢手帕问题</title></head> <body> <?php class Child{ public $no;
实战数据结构(4)_循环单链表解决约瑟夫问题
/************************************************************************/ /* author: lynnbest 2013.8.24 约瑟夫问题: 有n个人,编号为1,2,3...n围成一个圆圈,按照顺时针方向从编号为k的人 开始报数,报数为m的人出列,她的下一个人重新开始从1报数,数到m的人出列 如此重复下去,知道所
约瑟夫环(约瑟夫问题) 采用循环单链表实现
// yuesefuWenti.cpp : 定义控制台应用程序的入口点。 /* 约瑟夫环(约瑟夫问题)是一个数学的应用问题: 已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。 从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数, 数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。 通常解决这类问题时我们把编号从0~n-1,最后结果+
约瑟夫环问题(循环单链表的实现)
约瑟夫环问题                  1,问题描述:                 设有偏号为1,2,3..............N的n个人围成一个圆,每个人都持有一个密码m从第一个人开始,报数到第m                  时停止报数。报m的人出圈,再从下一个人重新开始报数, 报到m的是停止报数,报m的出圈.................
C语言线性表之循环单链表
#include #include int typeOfLinkList; typedef struct LNode{ int data; struct LNode *next; }LNode, *LoopLinkList; /* 基本算法(遍历) */ void show(LNode *L, int n) { int in = 0; printf(" S
【C语言数据结构】循环单链表
CircleLinkList.h 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
C语言-----循环单链表
#include<stdio.h> #include<stdlib.h> #include<string.h> typedef struct node{ char name[32]; struct node *next; }no; unsigned int len=sizeof(no); no* CreatList(unsigned int num){ int i;
c语言循环单链表
c循环单链表
约瑟夫环问题(Josephus) —— 循环单链表
约瑟夫环问题 —— 循环单链表
循环单链表实现约瑟夫环问题
问题: 编号为1,2,3,,,n的n个人按顺时针围坐一起,每人有一个正整数密码。一开始任选一个整数作为报数上限值m,从第一个人开始按顺时针向自1开始顺序报数,报到m的停止,出列,并把出列的人手中的密码作为新的m值,从接下来的下一个人接着从一开始报数,依次所有人出列 利用单向循环链表实现,按照数列的顺序的打印个人的编号 例如,m=6; n=7; 7个人的密码分别为 3 1 7 2 4 8
【数据结构】 循环单链表 约瑟夫回环问题
123
约瑟夫问题 算法 数据结构 循环单链表
// MARK: - 约瑟夫问题 // 链表节点 class Node: NSObject { var next: Node? var value: Int? } // 人的编号 var i = 1 // 头节点 let headNode = Node() headNode.value = 1 // 总人数 let m = 12 // 创建循环单链表 func genera...
约瑟夫问题(C语言)
约瑟夫问题:N个人围成一圈,从第一个人开始报数,数到M的人出圈;再由下一个人开始报数,数到M的人出圈;…输出依次出圈的人的编号。N,M由键盘输入。 代码如下: /* 编写者:Zero 编写时间:2018年 */ #include&amp;lt;stdio.h&amp;gt; #define N 50 int main() { int a[N],m,n,x,i,count = 0; ...
C语言 约瑟夫问题
维基百科说明: 约瑟夫问题(有时也称为约瑟夫斯置换),是一个出现在计算机科学和数学中的问题。在计算机编程的算法中,类似问题又称为约瑟夫环。 人们站在一个等待被处决的圈子里。 计数从圆圈中的指定点开始,并沿指定方向围绕圆圈进行。 在跳过指定数量的人之后,执行下一个人。 对剩下的人重复该过程,从下一个人开始,朝同一方向跳过相同数量的人,直到只剩下一个人,并被释放。 #include &lt;s...
【C语言】约瑟夫问题
约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。例如:m=3,数到3的人就出队列,下一个人接着从1开始计数#include &amp;lt;stdio.h&amp;gt; #define ALL 100 ...
c语言约瑟夫问题
本程序使用循环链表实现约瑟夫问题,使用c语言编写,简单的演示了约瑟夫问题。
约瑟夫问题C语言 .
约瑟夫问题C语言
约瑟夫环_循环单链表
/*  * 问题描述:  *     编号为1,2,...,n 的n 个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。  *     一开始任选一个正整数作为报数上限值 m,从第一个人开始。按顺时针方向自 1 开始顺序报数,报到m 时停止报数。  *     报m的人出列,将他的密码作为新的m 值, 从他在顺时针方向上的下一个人开始重新从1 报数,如此下去,直至所有人全部出列为止。  */ ...
约瑟夫环(循环单链表)
问题描述: 41个人排成一个圆圈,有第1个开始报数,每报数到第3个人该人就必须自杀,然后再由下一个人重新报数,直到所有人都自杀身亡为止。 示例图: public class JosephusList { class Node{ int data; Node next; } Node head; Node rear; /*...
c语言循环链表,解决约瑟夫问题
c语言循环链表,一开始用头结点作为开端,创建一连串的节点,到最后一个节点的next指向head的下一个节点可以么。代码如下,虚心求教。n#includen#includen#define N 6n#define M 5nstruct peoplenn int num;n struct people *next;n;nstruct people *head,*last,*p,*history,*now;nint i,j;nint main()nn head=malloc(sizeof(struct people));n head->num=0;n head->next=NULL;n last=head;n history=head;n n for(i=1;inum=i;n p->next=NULL;n last->next=p;n last=p;n n n history=head;n now=head->next;n while(now!=NULL)n n printf("%d",now->num);n history=now;n now=now->next;n n n last->next=head->next;n n history=last;n now=last->next;n while(now->next!=NULL)n n for(j=1;jnext;n n p=now->next;n free(now);n now=p;n history->next=now; n n printf("%d",now->num);n return 0; n
C语言解决约瑟夫问题算法
据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始,越过k-2个人
如何用c语言解决约瑟夫问题
#include &lt;stdio.h&gt; int main() { int n,m,i,s=0; scanf("%d%d",&amp;n,&amp;m); for (i=2;i&lt;=n;i++){ s=(s+m)%i; } printf ("%d",s+1); return 0; }
C语言用链表解决约瑟夫问题
C语言用链表解决约瑟夫问题
相关热词 c#串口测试应用程序 c# 匹配 正则表达式 c#防止窗体重绘 c#读写txt文件 c#挖地雷源代码 c#弹框选项 c# 移除 队列 c# 密码写入配置文件 c# 获取可用内存大小 c# 嵌入excel编辑