[已解决]求助关于循环链表约瑟夫环的问题

白轼泽

刚学链表没多久，对于一些操作都不熟。自己做了一个约瑟夫环的代码，题目是这样的
题目描述
        有n人围成一圈，顺序排号。从第1个人开始报数（从1到3报数），凡报到3的人退出圈子，问最后留下的是原来的第几号的那位。
输入
        初始人数n，有多组测试数据，对每一个测试数据，输出一个结果
输出
        最后一人的初始编号
样例输入
3
4
5
10
样例输出
2
1
4
4

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. typedef struct node
   
4. {
   
5.     int data;
   
6.     struct node *next;
   
7. }node;
   
8. typedef struct node *List;
   
9. struct node *Create(List head,int n)
   
10. {
    
11.     List p1=NULL,p2=NULL;
    
12.     int m;
    
13.     for(m=1,p1=head;m<=n;m++)//尾插法，每个结点的data依次为1,2,...,n
    
14.     {
    
15.         p1=(List)malloc(sizeof(node));
    
16.         p1->data=m;
    
17.         p2->next=p1;
    
18.         p2=p1;
    
19.     }
    
20.     p1->next=head->next;//for循环后，p1指向最后一个结点，通过此操作构成循环链表
    
21.     free(head);//释放无用的头结点，使链表构成一个环
    
22.     return p1->next;//返回第一个结点的位置
    
23. }
    
24. struct node *Delete(List l,int n)
    
25. {
    
26.     List p,q;
    
27.     p=l;//p从第一个结点开始
    
28.     for(;n>1;n--)
    
29.     {
    
30.         q=p->next->next;//q为从p开始的第三个元素
    
31.         p->next->next=q->next;//将从p开始的第二个结点与第四个结点衔接
    
32.         p=q->next;//将p改为q后面的元素，即原来的从q开始的第四个元素
    
33.         free(q);//从原来的p开始的删除第三个元素
    
34.     }
    
35.     return l;
    
36. }
    
37. int main()
    
38. {
    
39.     int n;
    
40.     List head,l;
    
41.     while(scanf("%d",&n)!=EOF)
    
42.     {
    
43.         head=(List)malloc(sizeof(node));//创建带头结点的空链表
    
44.         head->next=NULL;
    
45.         l=Create(head,n);
    
46.         //l=Delete(head,n);
    
47.         printf("%d\n",l->data);
    
48.     }
    
49.     return 0;
    
50. }
    
51. 
    

复制代码

但是执行程序之后，我输入一个数据，比如3，这个程序什么都没输出，而且还直接结束了
求助为什么是这样的？
多谢各位了

最佳答案

月排行榜 / 总排行榜

jackz007

2019-2-18 16:05:51

    问题比较多，就不一一赘述，大概改了下，程序的结构基本维持原样，楼主不妨对照原代码比较一下看看。

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. typedef struct node
   
5. {
   
6.     int data                                           ;
   
7.     struct node * next                                 ;
   
8. } node                                                 ;
   
9. 
   
10. typedef struct node * List                             ;
    
11. 
    
12. struct node * Create(int n)
    
13. {
    
14.     List head , p1 = NULL , p2 = NULL                  ;
    
15.     int m                                              ;
    
16.     p1 = (List)malloc(sizeof(node))                    ; // 为首节点分配内存空间
    
17.     p1 -> data = 1                                     ; // 为首节点 data 成员赋值
    
18.     p1 -> next = p1                                    ; // 让首节点指针成员指向自己，形成自闭
    
19.     head = p1                                          ; // 记录首节点
    
20.     for(m = 2 ; m <= n ; m ++) {
    
21.         p2 = (List)malloc(sizeof(node))                ; // p2 新建节点
    
22.         p2 -> data = m                                 ; // 为新节点 data 成员赋值
    
23.         p2 -> next = head                              ; // 让新节点指针成员指向首节点，形成闭环
    
24.         p1 -> next = p2                                ; // 更新前一个节点的指针成员，使其指向新节点
    
25.         p1 = p2                                        ; // 腾出新节点指针，准备插入新节点
    
26.     }
    
27.     return head                                        ; //返回指向首结点的指针
    
28. }
    
29. 
    
30. struct node * Delete(List l , int n)
    
31. {
    
32.     List p , q                                         ;
    
33.     int k                                              ;
    
34.     p = l                                              ; //p从第一个结点开始
    
35.     k = n                                              ;
    
36.     while(k > 2) {
    
37.         q = p -> next -> next                          ; // q - 待删除节点
    
38.         p -> next -> next = q -> next                  ; // 节点桥接，跨过被删除节点
    
39.         p = q -> next                                  ; // 下次从已删除掉节点的下一个节点开始计数
    
40.         free(q)                                        ; // 释放被删除节点所占用的内存空间
    
41.         k --                                           ; // 节点计数减 1
    
42.     }
    
43.     return p -> next                                   ;
    
44. }
    
45. 
    
46. main(void)
    
47. {
    
48.     int n                                              ;
    
49.     List head , l                                      ;
    
50.     while(scanf("%d", & n) != EOF) {
    
51.         l = Create(n)                                  ;
    
52.         l = Delete(l , n)                              ;
    
53.         printf("%d\n" , l -> data)                     ;
    
54.     }
    
55. }
    

复制代码

跳转到最佳答案楼层

jackz007

    问题比较多，就不一一赘述，大概改了下，程序的结构基本维持原样，楼主不妨对照原代码比较一下看看。

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. typedef struct node
   
5. {
   
6.     int data                                           ;
   
7.     struct node * next                                 ;
   
8. } node                                                 ;
   
9. 
   
10. typedef struct node * List                             ;
    
11. 
    
12. struct node * Create(int n)
    
13. {
    
14.     List head , p1 = NULL , p2 = NULL                  ;
    
15.     int m                                              ;
    
16.     p1 = (List)malloc(sizeof(node))                    ; // 为首节点分配内存空间
    
17.     p1 -> data = 1                                     ; // 为首节点 data 成员赋值
    
18.     p1 -> next = p1                                    ; // 让首节点指针成员指向自己，形成自闭
    
19.     head = p1                                          ; // 记录首节点
    
20.     for(m = 2 ; m <= n ; m ++) {
    
21.         p2 = (List)malloc(sizeof(node))                ; // p2 新建节点
    
22.         p2 -> data = m                                 ; // 为新节点 data 成员赋值
    
23.         p2 -> next = head                              ; // 让新节点指针成员指向首节点，形成闭环
    
24.         p1 -> next = p2                                ; // 更新前一个节点的指针成员，使其指向新节点
    
25.         p1 = p2                                        ; // 腾出新节点指针，准备插入新节点
    
26.     }
    
27.     return head                                        ; //返回指向首结点的指针
    
28. }
    
29. 
    
30. struct node * Delete(List l , int n)
    
31. {
    
32.     List p , q                                         ;
    
33.     int k                                              ;
    
34.     p = l                                              ; //p从第一个结点开始
    
35.     k = n                                              ;
    
36.     while(k > 2) {
    
37.         q = p -> next -> next                          ; // q - 待删除节点
    
38.         p -> next -> next = q -> next                  ; // 节点桥接，跨过被删除节点
    
39.         p = q -> next                                  ; // 下次从已删除掉节点的下一个节点开始计数
    
40.         free(q)                                        ; // 释放被删除节点所占用的内存空间
    
41.         k --                                           ; // 节点计数减 1
    
42.     }
    
43.     return p -> next                                   ;
    
44. }
    
45. 
    
46. main(void)
    
47. {
    
48.     int n                                              ;
    
49.     List head , l                                      ;
    
50.     while(scanf("%d", & n) != EOF) {
    
51.         l = Create(n)                                  ;
    
52.         l = Delete(l , n)                              ;
    
53.         printf("%d\n" , l -> data)                     ;
    
54.     }
    
55. }
    

复制代码

白轼泽

jackz007 发表于 2019-2-18 16:05
问题比较多，就不一一赘述，大概改了下，程序的结构基本维持原样，楼主不妨对照原代码比较一下看看。
...

多谢指点了，不过我还想问一下，我是看着视频里的，把无用的头节点释放了，这一步出错了吗？还是说我的创建链表的函数出了问题？
另外我对你的删除部分的代码做了点优化

1. List Delete(List l , int n)
   
2. {
   
3.     List p , q;
   
4.     p = l;                              //p从第一个结点开始
   
5.     for(;n > 1;n --)               //n是节点计数器，每次删除一个结点之后都减一
   
6.     {
   
7.         q = p -> next -> next;          // q为从p开始的第三个元素，是待删除节点
   
8.         p -> next -> next = q -> next;  // 节点桥接，跨过被删除节点
   
9.         p = q -> next;                  // 下次从已删除掉节点的下一个节点开始计数
   
10.         free(q);                        // 释放被删除节点所占用的内存空间
    
11.     }
    
12.     return p;
    
13. }

复制代码