约瑟夫环

#include<stdio.h>
typedef struct Node{
  int data;
  int id;
  struct Node *next;
}node;

#define SIZE sizeof(node)

node *initList();
void creatList(node *head, int n);
void printList(node *head);
node *jose(node *head,int password);
void printList_id(node *head);

int main(){
  int n,m;
  scanf("%d%d", &n, &m);
  node *head = initList();
  creatList(head,n);
  node *newhead = jose(head,m);
  printList_id(newhead);
}

//链表初始化
node *initList(){
  node *p;
  p = (node*)malloc(SIZE);
  p->next = p;
  return p;
}
//创建链表
void creatList(node *head, int n){
  node *new;
  node *pre;
  pre = head;
  int i = 1;
  while (n--) {
    new = (node*)malloc(SIZE);
    scanf("%d",&new->data);
    new->id = i;
    i++;
    pre->next = new;
    new->next = head;
    pre = new;
  }
}
//打印链表
void printList(node *head){
  node *cur = head->next;
  int i=0;
  while (cur != head) {
    i++;
    printf("i=%d,data=%d\n", i, cur->data);
    cur = cur->next;
  }
}

//打印链表id
void printList_id(node *head){
  node *cur = head->next;
  while (cur != head) {
    printf("%d ",cur->id);
    cur = cur->next;
  }
}
//判断空
int isEmptyList(node *head){
  if(head->next == head)
    return 1;
  return 0;
}
//约瑟夫环
node *jose(node *head,int password){
  node *newList = initList();
  node *pre = head;
  node *cur = head->next;
  node *Npre = newList;
  int count = 1;
  while (!isEmptyList(head)) {
    if(count == password){
      //重新计数
      password = cur->data;
      count = 0;
      //将cur从head链表中移除
      pre->next = cur->next;
      //将cur添加至newList
      Npre->next = cur;
      Npre = cur;
    }else{
      pre = cur;
    }
    cur = cur->next;
    //遍历至头节点
    if(cur == head){
      continue;
    }
    //head链表继续遍历
    count++;
  }
  Npre->next = head->next;
  head->next = head;
  Npre->next = newList;
  return newList;
}

#include<stdio.h>
typedef struct Node{
  int id;
  struct Node *next;
}node;

#define SIZE sizeof(node)

node *initList();
void creatList(node *head, int n);
node *jose(int n,int m);
void printList_id(node *head);

int main(){
  int n,m;
  scanf("%d%d", &n, &m);
  node *newhead = jose(n,m);
  printList_id(newhead);
}

//链表初始化
node *initList(){
  node *p;
  p = (node*)malloc(SIZE);
  p->next = p;
  return p;
}
//创建链表
void creatList(node *head, int n){
  node *new;
  node *pre;
  pre = head;
  int i = 1;
  while (n--) {
    new = (node*)malloc(SIZE);
    new->id = i;
    i++;
    pre->next = new;
    new->next = head;
    pre = new;
  }
}
//打印链表id
void printList_id(node *head){
  node *cur = head->next;
  while (cur != head) {
    printf("%d ",cur->id);
    cur = cur->next;
  }
}
//判断空
int isEmptyList(node *head){
  if(head->next == head)
    return 1;
  return 0;
}
//约瑟夫环
node *jose(int n,int m){
  node *newList = initList();
  node *head = initList();
  creatList(head,n);
  node *pre = head;
  node *cur = head->next;
  node *Npre = newList;
  int count = 1;
  while (!isEmptyList(head)) {
    if(count == m){
      //重新计数
      count = 0;
      //将cur从head链表中移除
      pre->next = cur->next;
      //将cur添加至newList
      Npre->next = cur;
      Npre = cur;
      //当cur指向head的下一个节点时
      if(cur == head->next)
        head->next = cur->next;
    }
    pre = cur;
    cur = cur->next;
    //遍历至头节点
    if(cur == head){
      continue;
    }
    //head链表继续遍历
    count++;
  }
  Npre->next = head->next;
  head->next = head;
  Npre->next = newList;
  return newList;
}

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 公式法循环 公式法递归 链表法
    安然_fc00阅读 299评论 0 0
  • 复习一下关于约瑟夫环的实现原理: 如果用C来写的话,也会有许多的方法,比如1:采用链表(双向链表)2:递归3:队列...
    碧影江白阅读 2,211评论 0 3
  • 什么是约瑟夫环呢?约瑟夫环(约瑟夫问题)是一个数学的应用问题:已知n个人(以编号1,2,3...n分别表示)围坐在...
    孙静静阅读 1,235评论 1 3
  • 题目描述:约瑟夫环每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老...
    juexin阅读 526评论 0 0
  • 扑克牌的顺子 一副牌里随机抽5张牌,大小王看作任意的数字,判断是不是顺子。方法一:先快速排序,然后比较大小和是否相...
    icecrea阅读 1,148评论 0 0