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

白轼泽

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

#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
    int data;
    struct node *next;
}node;
typedef struct node *List;
struct node *Create(List head,int n)
{
    List p1=NULL,p2=NULL;
    int m;
    for(m=1,p1=head;m<=n;m++)//尾插法，每个结点的data依次为1,2,...,n
    {
        p1=(List)malloc(sizeof(node));
        p1->data=m;
        p2->next=p1;
        p2=p1;
    }
    p1->next=head->next;//for循环后，p1指向最后一个结点，通过此操作构成循环链表
    free(head);//释放无用的头结点，使链表构成一个环
    return p1->next;//返回第一个结点的位置
}
struct node *Delete(List l,int n)
{
    List p,q;
    p=l;//p从第一个结点开始
    for(;n>1;n--)
    {
        q=p->next->next;//q为从p开始的第三个元素
        p->next->next=q->next;//将从p开始的第二个结点与第四个结点衔接
        p=q->next;//将p改为q后面的元素，即原来的从q开始的第四个元素
        free(q);//从原来的p开始的删除第三个元素
    }
    return l;
}
int main()
{
    int n;
    List head,l;
    while(scanf("%d",&n)!=EOF)
    {
        head=(List)malloc(sizeof(node));//创建带头结点的空链表
        head->next=NULL;
        l=Create(head,n);
        //l=Delete(head,n);
        printf("%d\n",l->data);
    }
    return 0;
}

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

最佳答案

月排行榜 / 总排行榜

jackz007

2019-2-18 16:05:51

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

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

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

typedef struct node * List                             ;

struct node * Create(int n)
{
    List head , p1 = NULL , p2 = NULL                  ;
    int m                                              ;
    p1 = (List)malloc(sizeof(node))                    ; // 为首节点分配内存空间
    p1 -> data = 1                                     ; // 为首节点 data 成员赋值
    p1 -> next = p1                                    ; // 让首节点指针成员指向自己，形成自闭
    head = p1                                          ; // 记录首节点
    for(m = 2 ; m <= n ; m ++) {
        p2 = (List)malloc(sizeof(node))                ; // p2 新建节点
        p2 -> data = m                                 ; // 为新节点 data 成员赋值
        p2 -> next = head                              ; // 让新节点指针成员指向首节点，形成闭环
        p1 -> next = p2                                ; // 更新前一个节点的指针成员，使其指向新节点
        p1 = p2                                        ; // 腾出新节点指针，准备插入新节点
    }
    return head                                        ; //返回指向首结点的指针
}

struct node * Delete(List l , int n)
{
    List p , q                                         ;
    int k                                              ;
    p = l                                              ; //p从第一个结点开始
    k = n                                              ;
    while(k > 2) {
        q = p -> next -> next                          ; // q - 待删除节点
        p -> next -> next = q -> next                  ; // 节点桥接，跨过被删除节点
        p = q -> next                                  ; // 下次从已删除掉节点的下一个节点开始计数
        free(q)                                        ; // 释放被删除节点所占用的内存空间
        k --                                           ; // 节点计数减 1
    }
    return p -> next                                   ;
}

main(void)
{
    int n                                              ;
    List head , l                                      ;
    while(scanf("%d", & n) != EOF) {
        l = Create(n)                                  ;
        l = Delete(l , n)                              ;
        printf("%d\n" , l -> data)                     ;
    }
}

跳转到最佳答案楼层

jackz007

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

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

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

typedef struct node * List                             ;

struct node * Create(int n)
{
    List head , p1 = NULL , p2 = NULL                  ;
    int m                                              ;
    p1 = (List)malloc(sizeof(node))                    ; // 为首节点分配内存空间
    p1 -> data = 1                                     ; // 为首节点 data 成员赋值
    p1 -> next = p1                                    ; // 让首节点指针成员指向自己，形成自闭
    head = p1                                          ; // 记录首节点
    for(m = 2 ; m <= n ; m ++) {
        p2 = (List)malloc(sizeof(node))                ; // p2 新建节点
        p2 -> data = m                                 ; // 为新节点 data 成员赋值
        p2 -> next = head                              ; // 让新节点指针成员指向首节点，形成闭环
        p1 -> next = p2                                ; // 更新前一个节点的指针成员，使其指向新节点
        p1 = p2                                        ; // 腾出新节点指针，准备插入新节点
    }
    return head                                        ; //返回指向首结点的指针
}

struct node * Delete(List l , int n)
{
    List p , q                                         ;
    int k                                              ;
    p = l                                              ; //p从第一个结点开始
    k = n                                              ;
    while(k > 2) {
        q = p -> next -> next                          ; // q - 待删除节点
        p -> next -> next = q -> next                  ; // 节点桥接，跨过被删除节点
        p = q -> next                                  ; // 下次从已删除掉节点的下一个节点开始计数
        free(q)                                        ; // 释放被删除节点所占用的内存空间
        k --                                           ; // 节点计数减 1
    }
    return p -> next                                   ;
}

main(void)
{
    int n                                              ;
    List head , l                                      ;
    while(scanf("%d", & n) != EOF) {
        l = Create(n)                                  ;
        l = Delete(l , n)                              ;
        printf("%d\n" , l -> data)                     ;
    }
}

白轼泽

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

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

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