数据结构—约瑟夫环问题(C语言版)

���录

首先什么是约瑟夫环

约瑟夫环实现方式

一、创建结构体变量

二、初始化链表

三、构建循环链表

四、删除链表

 五、完整代码及注释讲解

首先什么是约瑟夫环

约瑟夫环是循环链表中的一个经典问题；题目描述：n 个人围成一圈，从第一个人开始报数,数到 m 的人出列，再由下一个人重新从 1 开始报数，数到 m 的人再出圈，依次类推，直到所有的人都出圈；

假设10个人围成一圈，依次编号1到10，按从小到大顺序报数，报到3的人出局，流程示意图如下

约瑟夫环实现方式

我个人倾向于循环链表；

一、创建结构体变量

typedef struct Node{    int data;  //数据域    struct Node* next;  //指针域}Node;

二、初始化链表

Node* Create(){ Node* head;     head = (Node*)malloc(sizeof(Node));     if (head == NULL) {         exit(1);     }     head->next = NULL;     return head;}

三、构建循环链表

 创建一个临时结点tail，将头结点head赋予tail，插入新结点p，让tail的next指向p，p的next指向head的下一个结点即结点p；同时让tail移到p的位置，为下个结点插入做准备；这样一个循环链表就初步完成了；

代码块

Node* Push(Node* head,Node* tail,int 1){    p->data=i;    tail->next =p;    p->next = head->next;    tail = p;    return head;}

 

 最重要的一件事，每次插入新结点后，要将tail移动到新结点位置！

四、删除链表

 

void Print(Node* head){    Node* q=head;    q->next = p->next;    printf("%d ", p->data);    free(p);    p = q->next;}

 五、完整代码及注释讲解

#include#includetypedef struct Node{    int data;    struct Node* next;}Node;//创建结构体变量Node* Create(){ Node* head;     head = (Node*)malloc(sizeof(Node));     if (head == NULL) {         exit(1);     }     head->next = NULL;     return head;}int main(){     int n, m,i;     Node * tail, * p, * q;     Node* head=Create();     scanf("%d %d", &n, &m);  //输入n个人围一圈及报数m的人出局//判断如果插入的数据为0或者以报数0为出局，则结束操作     if (n == 0 || m == 0) {         return 0;     }     else {         tail = head;  //开始没有数据，故尾结点tail与头结点重合         for ( i = 0; i data = i+1; //以下4步为插入新结点及数据的操作，具体分析请看上面构建循环链表             tail->next =p;             p->next = head->next;             tail = p;         }     }     p =head->next;  //插入完数据后，将最后一个结点的临时结点移到第一个数据处     q =tail;   //然后临时结点到尾结点处     i = 1;     while (p != q) {      //首尾结点是否重合，重合则表示只剩一个数据，结束循环         if (i == m) {     //对报数m的人进行出局操作             q->next = p->next;  //以下四步为删除操作             printf("%d ", p->data);             free(p);     //一定记得将删除链表处的内存释放，以免内存内存泄漏             p = q->next;             i = 1;     //删除后，重新从1开始报数         }         else {   //没有报数到m，则p，q结点都往后移一位             q = p;  //先q移到p的位置             p = q->next;  //然后p移到q的下一个位置             i++;         }     }     printf("%d", p->data);  //打印最后一位出局的人的号数     return 0;}

有什么不足的地方希望个位大佬在评论区多多指点！