论坛 › 数据结构与算法 › 约瑟夫环问题求助丫！

斜杠青少年 发表于 2019-3-20 13:32:13

约瑟夫环问题求助丫！

有人能解释一下：m%=n这一步吗？？？看了很久还是没搞懂这一步{:5_94:}
#include<stdio.h>
#include<stdlib.h>

typedef struct node{
        int data;
        struct node *next;
}node;


node *create(int n)
{
    node *current = NULL, *head,*newNode;
          int i = 1;
    head = (node*)malloc(sizeof (node ));
    current = head;

    if( 0 != n )
    {
      while( i <= n )
      {
            newNode = (node *)malloc(sizeof (node));
            newNode->data = i++;    // 为循环链表初始化，第一个结点为1，第二个结点为2。
            current->next = newNode;
            current = current->next;
      }
      current->next = head->next;
    }

    free(head);

    return current->next ;
}

int main(){

        node *create(int n);
        int n=41,m=3,i;
        node *temp;//中间变量
        node *p=create(n);
   
        m%=n;//*********************************************************************
   
        while(p!=p->next){
                for(i=1;i<m-1;i++){
                        p=p->next;
                }
                printf("%d\n",p->next->data);
                temp=p->next;
                p->next=temp->next;
                free(temp);
                p=p->next;
        }
        printf("%d\n",p->next->data);
        return 0;

}

jackz007 发表于 2019-3-20 14:17:30

本帖最后由 jackz007 于 2019-3-20 14:42 编辑

      m % = n ; // 就是 m = m % n，如果除数大于被除数，答案直接等于被除数，在本例中，3 % 41 = 3，也就是说，操作过后，m 的值等于 3

斜杠青少年 发表于 2019-3-20 15:08:25

可是m已经赋了初值为3了啊{:5_99:}

斜杠青少年 发表于 2019-3-20 15:08:59

jackz007 发表于 2019-3-20 14:17



可是m已经赋了初值为3了啊{:5_99:}

jackz007 发表于 2019-3-20 16:54:07

本帖最后由 jackz007 于 2019-3-20 17:53 编辑

斜杠青少年 发表于 2019-3-20 15:08
可是m已经赋了初值为3了啊

    这条语句看上去确实多余，楼主可以忽略它。

    我对楼主的代码作了些许改动，阅读起来会略微清晰一些，请楼主测试指正：

#include<stdio.h>
#include<stdlib.h>

typedef struct node {
      int data         ;
      struct node * next ;
} node                     ;


node * create(const int n)
{
      node * head , * p1 , * p2               ;
      int i                                     ;

      p1 = head = NULL                        ;
      for(i = 0 ; i < n ; i ++) {
                p2 = (node *)malloc(sizeof(node)) ; // 为新节点分配内存空间
                p2 -> data = i + 1                ; // 为新节点赋值
                p2 -> next = head               ; // 让新节点链接到首节点，形成闭环
                if(! i) head = p2               ; // 如果是第一个节点，赋值给 head
                else p1 -> next = p2            ; // 否则让前一个节点的指针链接到新节点
                p1 = p2                           ; // 准备纳入下一个新的节点
      }
      return head                               ;
}

void JosephCircle(const int m , const int n)
{
      int i , k                                                   ;
      node * p , * temp                                             ;

      p = create(n)                                                 ;
      k = n                                                         ;
      while(k >= m) {                                                 // 循环条件：剩余节点数大于等于循环周期
                for(i = 1 ; i < m - 1 ; i ++) p = p -> next         ; // 找到待删除节点的前一个节点
                temp = p -> next                                    ; // 定位到待删除节点
                p -> next = temp -> next                              ; // 删除节点
                free(temp)                                          ; // 释放内存
                p = p -> next                                       ; // p 指向下一次操作的起始节点
                k --                                                ; // 剩余节点减 1
       }
       printf("%4d : m = %d , n = %4d\n" , p -> next -> data , m , n) ; // 打印出最终剩余节点的数值
       while(p -> next != p) {                                          // 彻底释放剩余节点占用内存
               temp = p -> next                                       ; // 彻底释放剩余节点占用内存
               p -> next = temp -> next                               ; // 彻底释放剩余节点占用内存
               free(temp)                                             ; // 彻底释放剩余节点占用内存
       }
       free(p)                                                      ; // 彻底释放剩余节点占用内存
}

int main(void)
{
      JosephCircle(3 , 3);
      JosephCircle(3 , 4);
      JosephCircle(3 , 5);
      JosephCircle(3 , 10) ;
      JosephCircle(3 , 41) ;
}

查看完整版本: 约瑟夫环问题求助丫！