精华内容
下载资源
问答
  • 简单的循环链表,c语言编写,希望多多支持
  • 是最简单的约瑟夫环代码 结构简单易懂 保证你会满意的呀
  • 约瑟夫环求解,循环链表的使用,经典问题
  • 约瑟夫环使用循环链表实现,已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌...
  • 主要介绍了C数据结构循环链表实现约瑟夫环的相关资料,需要的朋友可以参考下
  • #include <iostream> #include <stdio.h> #include <stdlib.h> using namespace std;...//创建约瑟夫环循环链表 person* initLink(int n) { person * head=(person*)malloc(sizeof(perso...

    #include <iostream>
    #include <stdio.h>
    
    #include <stdlib.h>
    using namespace std;
    typedef struct node{
        int number;
        struct node *next;
    }person;
    
    //创建约瑟夫环循环链表
    person* initLink(int n)
    {
       person * head=(person*)malloc(sizeof(person));
        head->number=1;
        head->next=NULL;
        person* cyclic=head;
        for(int i=2;i<=n;i++)
        {
            person* body=(person*)malloc(sizeof(person));
            body->number=i;
            body->next=NULL;
            cyclic->next=body;
            cyclic=cyclic->next;
        }
    
        cyclic->next=head;   //首尾相连
        return head;
    }
    
    //从编号K开始数M次,退出
    void findAndKillK(person * head,int k,int m){
        printf("11111111");
        person * tail=head;
        //假如删除第一个节点呢?找到链表第一个结点的上一个结点,为删除操作做准备
    //    while (tail->next!=head) {
    //     tail=tail->next;
    //     }
        
        person * p=head;
    
        //找到编号为 k 的人
        while(p->number!=k)
        {
            tail=p;
            p=p->next;
        }
        //从编号为 k 的人开始,只有符合 p->next==p 时,说明链表中除了 p 结点,所有编号都出列了
        while (p->next!=p)
         {
        
        //找到从 p 报数 1 开始,报 m 的人,并且还要知道数 m-1de 人的位置 tail,方便做删除操作
            for(int i=1;i<m;i++)
            {
                tail=p;
                p=p->next;
            }
    
            tail->next=p->next;
            printf("出列人的编号为:%d\n",p->number);
            free(p);
            p=tail->next;//继续使用 p 指针指向出列编号的下一个编号,游戏继续
        }
        printf("出列人的编号为:%d\n",p->number);
        free(p);
    
    }
    
    int main() {
        int n;
        int k;
        int m;
        cout<<"输入圆桌上的人数 n:"<<endl;
        cin >> n;
        person* head=initLink(n);
        cout << "从第 k 人开始报数(k>1 且 k<"<< n <<")" << endl;
        cin >> k;
        cout << "数到 m 的人出列:"<<endl;
        cin >> m;
        cout<< "n="<< n<<","<<"k="<< k<<","<<"m="<< m<<endl;
        findAndKillK(head, k, m);
        return 0;
    }

     

    展开全文
  • C语言链表与数据结构循环链表实例分析:约瑟夫环知识要求一、循环链表二、约瑟夫环代码实现创建循环链表开始约瑟夫环游戏 知识要求 一、循环链表 循环链表是另一种形式的链式存储结构。它的特点是表中最后一个...

    C语言链表与数据结构 — 循环链表实例分析:约瑟夫环

    知识要求

    一、循环链表

    循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。
    (百度百科)

    二、约瑟夫环

    N 个人围成一圈,每人有一个密码,从第一个人开始从1开始往后报数,报到 M 的那那个人被淘汰出去,假如被淘汰的人的密码是 M1 ,则从被淘汰的人的下一个人开始从1向后报数,报到 M1 的的那个人被海汰出去,假如这个人的密码是 M2 则从被淘汰那个人的下一个人开始从1往后报数,报到 M2 的的那个人被海汰出去、以此类推,最后个被淘汰的人就赢了。

    例如:
    7人参与约瑟夫环游戏( N = 7),七个人的密码分别为 : 3,1 ,7 ,2 ,4 ,8 ,4。初始 M = 20。则淘汰顺序为 ;6,1,4,7,2,3,5。编号为5的玩家获胜。

    代码实现

    创建循环链表

    以C语言为例,以下为创建“约瑟夫环游戏”循环链表的操作:

    struct person * initPerson(int numberOfPerson){
        struct person *head = malloc(sizeof(struct person));//申请内存空间
        int pass;//密码中间变量
        while(1) {
            printf("Please type the 1 person's password(integer and bigger than 1):");
            scanf("%d", &pass);
            //容错
            if (pass < 1) {
                printf("Wrong type of password,please enter again");
            } else {
                break;
            }
        }
        //将头初始化
        head->rank = 1;
        head->password = pass;
        head->next = NULL;
        struct person *mid = malloc(sizeof(struct person));
        mid = head;
        //循环开始创建循环链表
        for(int i = 1;i<numberOfPerson;i++){
            struct person *create = malloc(sizeof(struct person));
            create->rank = i+1;
            int word;
            while(1){
                printf("please enter the %d person's password(integer and bigger than 1):",create->rank);
                scanf("%d", &word);
                if (pass < 1) {
                    printf("Wrong type of password,please enter again");
                } else {
                    break;
                }
            }
            create->password = word;
            create->next = NULL;
            mid ->next = create;
            mid = mid->next;
        }
        //收尾相接
        mid ->next = head;
        return head;
    }
    

    开始约瑟夫环游戏

    void playGame(struct person *head,int startPassword,int numberOfPerson){
        struct person *delete = head;
        int outnumber = 1;
        int total = 0;
        int result;
        //找到前节点
        for(int i = 0 ;i<numberOfPerson+1;i++){
            printf("rank %d pass %d\n",delete->rank,delete->password);
            delete = delete->next;
        }
        for(int i = 0 ;i<numberOfPerson-1;i++){
            delete = delete->next;
        }
        struct person *pre = delete;
        delete = head;
        int start = startPassword;
        int time = 1;
        int bigger = 0;
        while(total != numberOfPerson){
            for(int i = 1;i <= start;i++){
                if(time == start){
                    start = delete->password;
                    printf("The %d outer is rank %d\n",total+1,delete->rank);
                    result = delete->rank;
                    pre->next=delete->next;
                    free(delete);
                    delete=pre->next;
                    total ++;
                    time = 1;
                    break;
                }else{
                    time++;
                    pre = delete;
                    delete = delete->next;
                }
            }
        }
        printf("winner's rank is %d",result);
    }
    
    展开全文
  • n个数据元素构成一个,从环中任意位置开始计数,计到m将该元素从表中取出,重复上述过程,直至表中只剩下一个元素。 提示:用一个无头结点的循环单链表来实现n个元素的存储。 样例: 输入: 10 3 1 //分别为总数,...

    n个数据元素构成一个环,从环中任意位置开始计数,计到m将该元素从表中取出,重复上述过程,直至表中只剩下一个元素。
    提示:用一个无头结点的循环单链表来实现n个元素的存储。

    样例:
    输入:
    10 3 1 //分别为总数,出列的人数到的数字,开始数的人的编号。
    输出:
    3 6 9 2 7 1 8 5 10 4 //按照出列的先后顺序给出的出列的人的编号。

    #include<stdio.h>
    #include<malloc.h>
    #define ERROR 0
    #define OK 1
    typedef  int ElemType; /*定义表元素的类型*/
    typedef struct LNode   /*线性表的单链表存储*/
    {
        ElemType data;
        struct LNode *next;
    } LNode,*LinkList;
    
    LinkList Creat(int t)
    {
        int n;
        LinkList p1,p2,head;
        p1=(LinkList)malloc(sizeof(LNode));
        p2=(LinkList)malloc(sizeof(LNode));
        head = NULL;
        n = 1;
        while(n<=t)
        {
            p1->data = n;
            if(n==1)
                head = p1;
            else
                p2->next = p1;
            p2 = p1;
            if(n!=t)
                p1 = (LinkList)malloc(sizeof(LNode));
            n++;
        }
        p2->next = head;
        return head;
    
    }
    LinkList Start(LinkList L,int k)
    {
        int i;
        i=1;
        while(i!=k)
        {
            L=L->next;
            i++;
        }
        return L;
    
    }
    LinkList Delete(int n,int m,LinkList L)
    {
        int i,j,k;
        LinkList p;
        p=L;
        k=0;
        while(n>1)
        {
            j=0;
            for(i=1+k; i<=n; i++)
            {
                if((i+1)%m==0)
                {
                    printf("%d ",p->next->data);
                    p->next=p->next->next;
                    i++;
                    j++;
    
                }
                p=p->next;
                k=i%m;
            }
            n=n-j;
        }
        printf("%d\n",p->data);
        return p;
    }
    int main()
    {
        int m,n,k;
        scanf("%d%d%d",&n,&m,&k);
        LinkList L,cur;
        L=Creat(n);
        cur=Start(L,k);
        Delete(n,m,cur);
        return 0;
    }
    
    
    展开全文
  • 根据小甲鱼的视频 自己写的约瑟夫环
  • 要求实验四、线性表应用--约瑟夫环问题1 实验目的用循环链表解决约瑟夫问题。2 实验内容约瑟夫问题是一个数学的应用问题:已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为k...

    循环链表的生成

    在之前带有头结点的链表的基础上,构建链表的时候,最后一个结点的指针域指向头结点的后继,即尾结点的后驱为头结点的后继。在之后功能的Coding中,要注意遍历完整个链表一次的标志是到达头结点的后继!

    要求

    实验四、线性表应用--约瑟夫环问题

    1 实验目的

    用循环链表解决约瑟夫问题。

    实验内容

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

    基本要求:利用单向循环链表存储结构模拟此过程,按照出列的顺序输出各人的编号

    实验过程

    1):

    (截图

    2) :

    (截图

    (3

    (截图

     

    源代码

    (附件)

     具体代码如下:

    #include<stdio.h>
    #include<stdlib.h>
    
    //******宏定义参数******
    #define OK 1
    #define NO 0
    #define DATA_MAX_SIZE 20
    
    //******定义数据类型别名******
    typedef int Status;
    typedef char Excelelem;
    typedef int Numelem;
    
    //******声明数据结构******
    typedef struct Node
    {
    	Numelem book;
    	struct Node *next;
    }LNode,*LinkList;
    
    typedef struct
    {
    	Excelelem name[100];
    	Numelem length;
    	LinkList next;
    }HeadList,*HeadLinkList;
    
    //******初始化链表******
    LinkList init(Numelem *n)
    {
    	LinkList Head,p,q;
    	Numelem i;
    	Head=p=NULL;
    	for(i=1;i<=*n;i++)
    	{
    		q=(LinkList)malloc(sizeof(LNode));
    		q->book=i;
    		if(i==1) Head=p=q;
    		else
    		{
    			p->next=q;
    			p=q;
    		}
    	}
    	if(p) p->next=Head;
    	return Head;
    }
    
    HeadLinkList HeadInit(int n)
    {
    	//省略表头信息  Head->name
    	HeadLinkList Head;
    	Head=(HeadLinkList)malloc(sizeof(HeadList));
    	Head->length=n;
    	Head->next=init(&Head->length);
    	return Head;
    }
    
    void DATA_Joseph(HeadLinkList Head,int n,int k)
    {
    	LinkList p=Head->next,q;
    	Excelelem i,cnt=1;
    	if(!Head->length)
    	{
    		printf("该约瑟夫环已无操作元素!\n");
    		return ;
    	}
    	while(n!=p->book)
    	{
    		p=p->next;
    		if(p==Head->next)
    		{
    			printf("不存在编号为%d的入口!\n",n);
    			return ;
    		}
    	}
    	while(1)
    	{
    		for(i=1;i<k;i++)
    			q=p,p=p->next;
    		printf("第%d次时,第%d个元素出环!\n",cnt++,p->book);
    		Head->length--;
    		if(Head->length==0)
    		{
    			Head->next=NULL;
    			free(p);
    			break;
    		}
    		else
    		{
    			q->next=p->next;
    			free(p);
    			p=q->next;
    		}
    	}
    	printf("该约瑟夫环已无操作元素!\n");
    	return ;
    }
    
    int main()
    {
    	HeadLinkList Head;
    	Numelem n,m;
    	printf("**********start!**********\n");
    	printf("请输入约瑟夫环的规模!\n");
    	scanf("%d",&n);
    	Head=HeadInit(n);
    	printf("请输入约瑟夫环的入口!\n");
    	scanf("%d",&m);
    	printf("请输入约瑟夫环每次的出环规模!\n");
    	scanf("%d",&n);
    	printf("请检查约瑟夫环的操作情况!\n");
    	DATA_Joseph(Head,m,n);
    	free(Head);
    	printf("**********End!**********\n");
    	return 0;
    }
    

    总结:

    在约瑟夫环问题中,链表的算法是一种朴素的模拟过程,在之前的顺序表(例如:数组),也可以模拟这个过程,这时就要用取模符号进行实现循环,类似于之后的顺序表循环队列的过程!当然,顺序表模拟的时候可以用个bool来判断该节点是否出环了。

    展开全文
  • 约瑟夫环 据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个...
  • 数据结构——约瑟夫环问题(循环链表题解) //约瑟夫环问题(不考虑y&gt;x) //题设:输入 两个整数x,y,第一个整数代表共有x个人,第二个数代表挨个报数报y次; // 输出 最后一个人的序号 #include&lt;stdio...
  • 已知有5个人围坐在一张圆桌的周围,从编号为3的人开始...(使用循环链表实现约瑟夫环) 代码如下: #include "pch.h" #include<string> #include<fstream> #include<Windows.h> #include <i...
  • 附代码: /**************************************************** * * This is a Circular List class * Created by ZhiYu.Wang * Current time: 2014.5.17 * ************************************************
  • 这是作者在数据结构课程学习过程中,在链表学习部分的一个小小作品
  • 一、循环链表 #include "stdio.h" #include "stdlib.h" typedef struct node { int data; struct node *next; }node; 初始化循环链表 void ds_init(node **pNode) // 初始化循环链表, **pNode:链表上 { int ...
  • 1 //循环链表,链表的尾结点的link域中不是NULL,而是存放了指针链表开始结点的指针 2 ////设p是在循环链表中逐个... 5 //循环链表结构定义 6 typedef int DataType; 7 typedef struct node//循环链表定义 8 { 9
  • 通过循环链表实现约瑟夫环 要求:1)要求设计一个程序模拟次过程,输入总的人数n,所报的出列的数字k,计数开始的位置p; 程序所能达到的功能:构造链表;输入数据;执行报数;储存出列人的序号,删除出列人的信息...
  • 双向链表List.java 接口AbstractList.java双向链表 LinkedList.java双向循环链表 CircleLinkedList.java双向循环链表解决约瑟夫环问题 List.java 接口 public interface List<E> { static final int ELEMENT_...
  • 一、实验原理 约瑟夫问题描述:编号为1,2,……,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数的上限值m,从第一个人开始按... 实现:利用单向循环链表存储结构模拟约瑟
  • 循环链表即表示链表头尾相接,从任意一个结点出发可以访问到任意一个节点,需要注意的是,在循环链表中,头结点即是尾结点 单链表变成循环链表的改进 head->next = head; 当插入节点为头结点的时候 // 先让该...
  • 约瑟夫环双向链表

    2018-04-15 21:21:26
    /*该约瑟夫环使用的是循环链表*/ /*构建结构体*/ typedef struct Node{ int Num; struct Node *next; struct Node *pre; }JoseNode, *PNode, *HNode;//这个结构代表一个数据域和指针域的结点...
  • 忘记说了,这应该算是视频笔记,进正题~~约瑟夫环问题,不知道的同学依然点这里约瑟夫环问题,约瑟夫环问提可以使用数组以及链表这种基础的数据结构来解决,刚开始我觉得循环链表有点难理解,不过学习了之后并且自己...
  • 【C语言】数据结构循环链表解决约瑟夫环问题

    万次阅读 多人点赞 2018-06-25 18:28:54
    循环链表解决约瑟夫环问题 约瑟夫问题 假设有n个人围成一圈,然后对每个人按顺序编号1,2,3,…..,n,规定从1号按顺序开始报数,报到k的人出局,之后下一个人再从1开始报数,报到k的人在出局,一直进行下去...
  • 数据结构--链表--约瑟夫环问题(单向循环链表

    千次阅读 多人点赞 2019-03-14 23:10:51
    问题:一群人站成一个圆圈,从一个人开始报数,...C++代码如下:(参考书籍:数据结构与算法实验指导书) #include &lt;iostream&gt; using namespace std; struct NodeType { int num; char name[20...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 418
精华内容 167
关键字:

约瑟夫环循环链表数据结构

数据结构 订阅