回 帖 发 新 帖 刷新版面

主题:[讨论]关于约瑟夫环的问题

大家好,最近有作业要写关于约瑟夫环的问题,我写完后编译通过,但运行程序时输入人数和每个人的密码后提示段错误,不知怎么回事儿,请大家指点下。
以下是问题的描述:

约瑟夫问题的一种描述是:编号为1,2,……,n的n个人按顺时针方向围坐一圈,每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个人开始按顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有人全部出列为止。试设计一个程序求出出列顺序。

以下是我写的关于这个问题的代码:

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

typedef struct LNode0{
    int num;        //储存每个人的编号
    int passwd;     //储存每个人的密码
}LNode0;

typedef struct LNode{
    LNode0 data;
    struct LNode *next;
}LNode;

void CreatList(LNode *person, int num, int passwd);         //构造链表并给每人赋密码
void PrintList(LNode *person, int num, int passwd);         //进行游戏并打印结果

main(){
    int i, number, password;
    LNode *person;

    printf("Please enter the number of people and the first passwd:");
    scanf("%d %d", &number, &password);

    CreatList(person, number, password);
    PrintList(person, number, password);
}

void CreatList(LNode *person, int num, int passwd){
    //构造链表并给每人赋密码
    LNode *p;
    int i;
    person = (LNode *) malloc(num * sizeof(LNode));

    if (person == NULL){
        printf("No enough memory!\n");
        exit(0);
    }

   p = person;
   printf("Please enter the password of each person(password <= %d):\n", passwd);
   for (i = 0; i < num; i++){
       p->data.num = i + 1;
       scanf("%d", p->data.passwd);

       if (p->data.passwd > passwd || p->data.passwd < 0){
           printf("Input fault password! Please input again!\n");
           i--;
       }
       else
       {
           p = p->next;
       }
   }
   p->next = person;
}

void PrintList(LNode *person, int num, int passwd){
    //进行游戏并打印结果
    LNode *p;       //保存出局的人前一个人的节点
    int i;      //计数器
    
    p = person + passwd - 1;
    printf("Game results are:\n");
    printf("%d\t", (p+1)->data.num);
    p->next = p->next->next;
    passwd = p->next->data.passwd;      //第一个出局的人的密码
    free(p + 1);

    for (i = 1; i <= num; i++){
        p = p + passwd;
        printf("%d\t", (p+1)->data.num);
        p->next = p->next->next;
        passwd = p->next->data.passwd;
        free(p + 1);
    }
}

回复列表 (共7个回复)

沙发

首先,这是链式表达的顺序表?你person = (LNode *) malloc(num * sizeof(LNode));
就把链表的动态申请的优点给废了,变回连续内存申请了。
链表的内存申请方式为逐结点申请,然后接在前一个结点的地址域内
你现在的写法根本没告诉结点地址域应该指向哪里(其实按照你的写法,也可以逐结点写上p->next=p+1;应该也能看到结果,具体没有调试。
仔细想想数据结构的问题吧

板凳

这是我写的,可以交流一下,主要思想是建立动态循环链表,在循环式的删除:
 #include<stdio.h>
#include<stdlib.h>


 typedef struct node1 
{
    int num;
    int passwd;
}Lnode1;

typedef struct node2
{
     Lnode1 data;
     struct node2 *next;
    
}Lnode2;

   
Lnode2 *p1,*p2,*head;
void creat_lnode(int num2,int passwd2)
{
    p1->data.num=num2;
    p1->data.passwd=passwd2;
    p2=(Lnode2*)malloc(sizeof(Lnode2));
    p1->next=p2;
    p2->next=head;
    p1=p2;
}

void delet_lnode(int m1)
{
    int count;
    for(count=1;count<m1;count++)
    {
        p1=p2;
        p2=p1->next;
    }
    m1=p2->data.passwd;
    printf("%d,%d,%d\n",m1,p2->data.num,p2->data.passwd);   // print: m,p2->data.num,p2->data.passwd
    p1->next=p2->next;
    free(p2);
    p2=p1->next;
    if(m1==1)
    head=NULL;
    delet_lnode(m1);
    while(p1=p2)
    {
        printf("The last of the num:\n");
        printf("%d,%d,%d",m1,p2->data.num,p2->data.passwd);
        free(p1);
        p1=p2=head=NULL;
    }



}


int main(void)
{
    int i,n,num1, passwd1;
    int m;
    p1=head=(Lnode2 *)malloc(sizeof(Lnode2));
    printf("The number of people:");
    scanf("%d",&n);
    printf("The people's num and passwd:\n");
    for(i=1;i<n;i++)
    {
        printf("shu ru\n");
        scanf("%d,%d",&num1, &passwd1);
        creat_lnode(num1, passwd1);
    }
        printf("shu ru\n");
        scanf("%d,%d",&num1,&passwd1);
        p1->data.num=num1;
         p1->data.passwd=passwd1;      //   为最后一个结点

        printf("The first number of m:");
        scanf("%d",&m);
        p2=head;
        delet_lnode(m);
        return 0;
}





        







3 楼


嗯,谢谢!我又看了下数据结构的书,把代码改了下。虽然编译通过了,但最后输出的结果却不对,不知什么问题。以下是修改后的代码。

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

typedef struct LNode0{
    int num;        //储存每个人的编号
    int passwd;     //储存每个人的密码
}LNode0;

typedef struct LNode{
    LNode0 data;
    struct LNode *next;
}LNode;

void CreatList(LNode *person, int num, int maxnum);         //构造链表并给每人赋密码
void PrintList(LNode *person, int num, int passwd);         //进行游戏并打印结果

main(){
    int i, number, password, maxnum;
    LNode *person = (LNode *) malloc(sizeof(LNode));

    printf("Please enter the number of people and the max number to be used:");
    scanf("%d %d", &number, &maxnum);
    password = maxnum;
    printf("Please enter the first loop number:");
    scanf("%d", &password);

    CreatList(person, number, maxnum);
    PrintList(person, number, password);
    
    printf("\n");
}

void CreatList(LNode *person, int num, int maxnum){
    //构造链表并给每人赋密码
    LNode *p = person;
    int i;

    printf("Please enter the password of each person(password <= %d):\n", maxnum);
    for (i = 1; i <= num; i++){
       p->data.num = i;
       scanf(" %d", &(p->data.passwd));
       p->next = (LNode *) malloc(sizeof(LNode));
       p = p->next;
   }
   p->next = person;
   free(p);
}

void PrintList(LNode *person, int num, int passwd){
    //进行游戏并打印结果
    LNode *p = person;       //保存出局的人前一个人的节点
    LNode *tmp;
    int i, j;                //计数器
   
    for (i = 1; i < passwd - 1; i++){
        p = p->next;
    }
    printf("Game results are:\n");
    printf("%d\t", p->next->data.num);
    tmp = p->next;
    p->next = tmp->next;
    passwd = tmp->data.passwd;      //第一个出局的人的密码
    free(tmp);

    for (i = 1; i <= num; i++){
        for (j = 1; j < passwd; j++){
            p = p->next;
        }
        printf("%d\t", p->next->data.num);
        tmp = p->next;
        p->next = tmp->next;
        passwd = tmp->data.passwd;
        free(tmp);
    }
}

4 楼


我在用gcc编译了下,虽然通过了,但把号码和密码输入完成后,最后出现的是不正常的显示,显示的是一堆地址数据,不知问题出在哪里……

5 楼

问题已经解决了,是我在PrintList()函数的问题,下面是最终的代码:

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

typedef struct LNode0{
    int num;        //储存每个人的编号
    int passwd;     //储存每个人的密码
}LNode0;

typedef struct LNode{
    LNode0 data;
    struct LNode *next;
}LNode;

void CreatList(LNode *person, int num, int maxnum);         //构造链表并给每人赋密码
void PrintList(LNode *person, int num, int passwd);         //进行游戏并打印结果

main(){
    int number, password, maxnum;
    LNode *person = (LNode *) malloc(sizeof(LNode));

    printf("Please enter the number of people and the max number to be used:");
    scanf("%d %d", &number, &maxnum);
    password = maxnum;
    printf("Please enter the first loop number:");
    scanf("%d", &password);

    CreatList(person, number, maxnum);
    PrintList(person, number, password);
    
    printf("\n");
}

void CreatList(LNode *person, int num, int maxnum){
    //构造链表并给每人赋密码
    LNode *p = person;
    int i;

    printf("Please enter the password of each person(password <= %d):\n", maxnum);
    for (i = 1; i <= num; i++){
       p->data.num = i;
       scanf(" %d", &(p->data.passwd));

       if (i < num){
           p->next = (LNode *) malloc(sizeof(LNode));
           p = p->next;
       }
    }
   p->next = person;
}

void PrintList(LNode *person, int num, int passwd){
    //进行游戏并打印结果
    LNode *p = person;       //保存出局的人前一个人的节点
    LNode *tmp;
    int i, j;                //计数器
   
    for (i = 1; i < passwd - 1; i++){
        p = p->next;
    }
    printf("Game results are:\n");
    printf("%d\t", p->next->data.num);
    tmp = p->next;
    p->next = tmp->next;
    passwd = tmp->data.passwd;      //第一个出局的人的密码
    free(tmp);

    for (i = 2; i <= num; i++){
        for (j = 1; j < passwd; j++){
            p = p->next;
        }
        printf("%d\t", p->next->data.num);
        tmp = p->next;
        p->next = tmp->next;
        passwd = tmp->data.passwd;
        free(tmp);
    }
}

6 楼

祝贺lz有了提高

7 楼


呵呵,谢谢!

我来回复

您尚未登录,请登录后再回复。点此登录或注册