注册 登录
编程论坛 数据结构与算法

约瑟夫环

cczxsong 发布于 2017-10-04 17:29, 2021 次点击
#include <stdio.h>  
#include <stdlib.h>  

#define OK      1  
#define ERROR   0  
#define TRUE    1  
#define FALSE   0  
 
typedef struct LNode{  
   int     num ;  //序号
   int     code;  //密码         
   LNode *next;                  
}LNode, *LinkList;

/**********************************/
//建立新的单循环链表,并输入各个节点的值
int createList(LinkList &L,int n)
{

    if(n<=0)return ERROR;
   
    LinkList tail,s;
    L=(LinkList)malloc(sizeof(LNode));//首节点
    L->num=1;
    scanf("%d ",&L->code);
    tail=L;
    for(int i=2;i<=n;++i){
        s=(LinkList)malloc(sizeof(LNode));
        s->num=i;
        scanf("%d",&s->code);
        s->next=NULL;
        tail->next=s;
        tail=s;
    }
    tail->next=L;
    return OK;
}
/****************************/
// 从已有的链表中删除指定的num值的节点
int deletList(LinkList &L,int i){
    LinkList e=L,r;

    while(e->next->num!=i){
        e=e->next;
    }
    if(e->next->num==i){
        r=e->next;
        e->next=r->next;
     //  L=e->next;
        free(r);
        return OK;
    }
    else return ERROR;   
}


/*****************************/
//具体操作步骤
void  printResurt(LinkList &L,int m,int n){
    LinkList p=L,q;
    int temp=m;
    for(int i=0;i<n;i++){
        for(int j=1;j<temp;j++){
            p=p->next;
        }
        printf("%d ",p->num);
        q=p->next;  
        temp=p->code;
        deletList(L,p->num);//删掉p节点
        p=q;
    }
}

/***************************/
//输出链表中的所有数据
void DispList(LinkList &L){
    LinkList p=L;
    while(p!=NULL){
        printf("%d  ",p->code);
        p=p->next;
    }
    printf("\n");
}
/************************************/
//主函数
int main(){
    int m=0,n=0;
    LinkList L;
    printf("请输入指定初始报数上限值:");
    scanf("%d",&m);
    printf("请输入人数:");
    scanf("%d",&n);
//    L=(LinkList)malloc(sizeof(LNode));
    printf("请依次输入每个人的密码:");
    createList(L,n);
//    deletList(L,4);
//    deletList(L,1);
//    DispList(L);
    printResurt(L,m,n);
    return 0;
}

不知道错到哪里了,他删除第一个节点就会出错
2 回复
#2
xzlxzlxzl2017-10-05 13:37
简单看了下,题主代码有两处逻辑错误:
1,DispList函数,用于显示循环链表所有数据,可是遍历链表的结束条件是“while(p!=NULL)”,很显然,循环链表不会出现NULL,这样就会死循环,不停显示链表数据,代码修改如下即可:
程序代码:
//输出链表中的所有数据
void DispList(LinkList &L){
    LinkList p=L;
    do
    {
        printf("%d ",p->code);
        p=p->next;
    }while(p!=L);
    printf("\n");
}


2,在printResurt函数中,由于找到符合条件的节点需要删除,因此很有可能把标注链表切入点的节点也删除,导致切入点L成为野指针,程序就会出错,代码修改如下可不导致错误,但好像结果不对,题主自己去修改吧:
程序代码:
void  printResurt(LinkList &L,int m,int n){
    LinkList p=L,q;
    int temp=m;
    for(int i=0;i<n;i++){
        for(int j=1;j<temp;j++){
            p=p->next;
        }
        printf("%d ",p->num);
        q=p->next;  
        temp=p->code;
        deletList(L,p->num);//删掉p节点
        L=p=q;
    }
}
#3
askunix2017-10-09 12:51
1