約瑟夫環(huán)

#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;
}
//創(chuàng)建鏈表
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;
}
//約瑟夫環(huán)
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){
      //重新計數(shù)
      password = cur->data;
      count = 0;
      //將cur從head鏈表中移除
      pre->next = cur->next;
      //將cur添加至newList
      Npre->next = cur;
      Npre = cur;
    }else{
      pre = cur;
    }
    cur = cur->next;
    //遍歷至頭節(jié)點
    if(cur == head){
      continue;
    }
    //head鏈表繼續(xù)遍歷
    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;
}
//創(chuàng)建鏈表
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;
}
//約瑟夫環(huán)
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){
      //重新計數(shù)
      count = 0;
      //將cur從head鏈表中移除
      pre->next = cur->next;
      //將cur添加至newList
      Npre->next = cur;
      Npre = cur;
      //當cur指向head的下一個節(jié)點時
      if(cur == head->next)
        head->next = cur->next;
    }
    pre = cur;
    cur = cur->next;
    //遍歷至頭節(jié)點
    if(cur == head){
      continue;
    }
    //head鏈表繼續(xù)遍歷
    count++;
  }
  Npre->next = head->next;
  head->next = head;
  Npre->next = newList;
  return newList;
}

最后編輯于
?著作權歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成,瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明:文章內(nèi)容(如有圖片或視頻亦包括在內(nèi))由作者上傳并發(fā)布,文章內(nèi)容僅代表作者本人觀點,簡書系信息發(fā)布平臺,僅提供信息存儲服務。

相關閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容