Josephy(循环链表的运用)

    Josephy 问题: 假设有N个人坐在圆桌周围,从第S个人开始报数,报到M的出列,
     然后再从下一个人开始报数,数到M的人出列¨¨¨如此重复,直到所有的人都出
     列为止。要求出列的先后顺序输出每个人的信息 

 # include<stdio.h>
# include<stdlib.h>
typedef int datatype;
typedef struct cnode
{
   datatype data;
   struct cnode *next;
}clistnode;
typedef clistnode *clinklist;
clinklist head;
void Joseph(int n,int m,int s)
{
  int i,j,flag;
  clinklist creatclinklist(int);     /*  函数申明 :元素前插法创建循环链表,长度限定为N  */
  void print(clinklist head,int);
  clistnode *p,*q,*r,*t;
  head=creatclinklist(n);
  print(head,n);    /*  将循环链表的元素按顺序打印出来   */
  q=head;
  if(s>n) printf("error!n");
     flag=s%n;              /*   把指针q移动到第 S个结点,并把它给指针p,尽量减少指针移动的次数!   */
  for(i=1;i<flag;i++)
  q=q->next;
  p=q->next;
  printf("%d个结点出队的顺序依次是;n",n);
  for(i=1;i<=n;i++)   /*   把i记为删除的结点个数  */
  {
    j=1;
    flag=m%(n-i+1);    /*  把指针p移动到第M个结点,尽量减少指针移动的次数!尽量使每次移动次数
                           不超过n次!时间复杂度O(n),提高该程序的执行效率! */
    if(!flag) /* 不知道该移动几步!特殊处理一些结点!  */
   {
      j=1;
      while(j<m)
      {
          r=p;
                 p=p->next;
          if(p==head)
                  continue;
                 j++;
      }
    }

时间: 2024-10-01 12:27:56

Josephy(循环链表的运用)的相关文章

只有一个指针指向队尾元素的循环链表表示的队列怎么求长度

问题描述 只有一个指针指向队尾元素的循环链表表示的队列怎么求长度 创建一个带头节点的循环链表表示的队列,并且只有一个指针指向队尾元素 解决方案 先保存当前的节点,然后循环调next,并计数,直到next等于保存的那个

数据结构(C#):循环链表

循环链表可以是单链表,也可以是双链表.链表的尾节点的后继节点指向头结点便成了循环链表. 我们在这里继承双链表实现循环链表,当到达双链表的表尾时,让游标指向第0个节点:当到达双链表 的开头时,让游标指向结尾节点,这样就实现了循环双链表.结尾用一个经典的约瑟夫问题来作循环链表 的应用示例. 1.循环链表代码: /* * File : CircularlyLinkedList.cs * Author : Zhenxing Zhou * Date : 2008-12-07 * Blog : http:/

大话数据结构四:线性表的链式存储结构(单向循环链表)

1. 单向循环链表:将单链表尾结点的指针端由空指针改为指向头结点,使整个单链表形成一个环,这种头尾相接的单链表称为单向循环链表.   2. 单向循环链表和单链表实现的区别: 1.)添加一个结点到单向循环链表末尾时,必须使其最后一个结点的指针指向表头结点,而不是象单链表那样置为null. 2.)判断是否到达表尾时,单向循环链表可以判断该结点是否指向头结点,单链表只需要知道是否为null.   3.Java实现单向循环链表: // 单向循环链表 public class CircularLinked

C++双向循环链表的操作与实现

双向循环链表的操作与实现-- 网上关于这方面的挺多,由于自己以前上课没好好学数据结构,现在重新认识数据结构,以下是自己写的基于C++的双向循环链表的创建及其一些操作与实现(于VC下通过),没用模板, 也没用类,所以比较适合有一点C++语言基础入门者,但可移植不够.有什么bug的话,欢迎指出. 或有什么问题也可以联系我. made by virgil (2009.2.8) MSN:hangyu_628@hotmail.com) #include <iostream> #include <c

数据结构教程 第九课 循环链表与双向链表

本课主题: 循环链表与双向链表 教学目的: 掌握循环链表的概念,掌握双向链表的的表示与实现 教学重点: 双向链表的表示与实现 教学难点: 双向链表的存储表示 授课内容: 一.复习线性链表的存储结构 二.循环链表的存储结构 循环链表是加一种形式的链式存储结构.它的特点是表中最后一个结点的指针域指向头结点. 循环链表的操作和线性链表基本一致,差别仅在于算法中的循环条件不是p或p->next是否为空,而是它们是否等于头指针. 三.双向链表的存储结构 提问:单向链表的缺点是什么? 提示:如何寻找结点的直

数据结构教程 第十二课 实验二 循环链表实验

本课主题: 实验二 循环链表实验 教学目的: 掌握单向链表的实现方法 教学重点: 单向链表的存储表示及操作 教学难点: 单向链表的操作实现 授课内容: 一.单向链表的存储表示 C源程序 #include<stdio.h> #include<malloc.h> #include<conio.h> #define ERROR 0 #define OK 1 #define EQUAL 1 #define OVERFLOW -1 #define LIST_INIT_SIZE 1

java双向循环链表

  代码如下   package com.xlst.util; import java.util.HashMap; import java.util.Map; import java.util.UUID; /** * 双向循环链表 * 完成时间:2012.9.28 * 版本1.0 * @author xlst * */ public class BothwayLoopLinked { /** * 存放链表长度的 map * * 如果简单使用 static int 型的 size 基本类型变量,则

java双向循环链表实现程序

  例1  代码如下   package com.xlst.util;    import java.util.HashMap;  import java.util.Map;  import java.util.UUID;    /**   * 双向循环链表   * 完成时间:2012.9.28   * 版本1.0   * @author xlst   *   */  public class BothwayLoopLinked {      /**       * 存放链表长度的 map   

求解答-试编写一个算法,找出一个循环链表中的最小值。我是新手,编了一个程序,不知错在哪

问题描述 试编写一个算法,找出一个循环链表中的最小值.我是新手,编了一个程序,不知错在哪 #includeusing namespace std; class LinkNode{ int data; LinkNode *link; LinkNode(int d=0LinkNode *l=0){data=d;link=l;}}; class List{private: LinkNode *first; int n;public: List() { first=new LinkNode; first