| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 830 人关注过本帖
标题:约瑟夫循环单链表 高手看看我的程序 望赐教
只看楼主 加入收藏
S030902508
Rank: 1
等 级:新手上路
帖 子:22
专家分:0
注 册:2010-10-19
结帖率:25%
收藏
 问题点数:0 回复次数:5 
约瑟夫循环单链表 高手看看我的程序 望赐教
   我的程序,但运行错误,麻烦帮我看下哪里有错,谢谢啦!!
  题目是输入n和m,然后从1到n围成一个圈,并从1开始报数,到m时,退出一个数。下一个又从1开始,报到m时退出,以此类推。求最后留下的一个数是多少。
   #include<stdio.h>
#include<stdlib.h>
struct sNode  \建立结构体类型\
{
    int data;  
    struct sNode *next;
};
void Initilist(struct sNode **HL) \初始化一个循环单链表\
{
    *HL=NULL;
}
void InsertLastlist(struct sNode **HL,int x) \将1-n依次插入单链表最后\
{
    struct sNode *newp;\创建一个新节点,用来存储要插入的数字\
       newp=(struct sNode*)malloc(sizeof(struct sNode));
    if(newp==NULL)\如果创建失败,退出运行\
    {
        printf("内存动态空间用完,退出!\n");
            exit(1);
    }
    newp->data=x;\让新节点的数值域等于插入的数字\
    if(*HL==NULL)\当单链表为空的情况\
    {
        *HL=newp;
        newp->next=*HL;
    }
    else\单链表不为空的情况\
    {
        struct sNode *p=*HL;
        while(p->next!=*HL)\查找到单链表的最后一个节点\
            p=p->next;
        p->next=newp;\把新节点插入最后\
        newp=*HL;\令新节点指向第一个节点,构成循环\
    }
}
void Deleteposlist(struct sNode **HL,int x)\删除节点\
{
    int i=1;
    struct sNode *cp=*HL;
    struct sNode *ap=NULL;
    struct sNode *hp=*HL;
    if(cp==NULL||x<=0)
    {
        printf("单链表为空或x值不正确,退出运行!\n");
        exit(1);
    }
    while(1)
    {
        if(i==x) break;\当i=要删除的节点,跳出\
        else
        {
            i++;
            ap=cp;   \ap指向当前节点\
            cp=cp->next;   \cp指向下一个节点\
        }
    }
    if(x==1) \当要删除的是第一个节点时\
    {
        *HL=(*HL)->next;   \令头指针指向第二个节点\
        while(hp->next!=*HL)  
            hp=hp->next;  
        hp->next=*HL;   \另最后一个节点指向新的第一个新节点,即第二个节点\
    }
    else \当要删除的不是第一个结点\
    {
        ap->next=cp->next;  
        if(cp==*HL)  \当cp循环一次后又到第一个节点,此时ap指向最后一个节点\
            *HL=ap->next;  \令头结点指向新的第一个节点\
        free(cp);
    }
}
int main()
{
    int i,j,m,n;
    struct sNode *L;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        j=n-1;
        Initilist(&L);  \初始化循环单链表\
        for(i=1;i<=n;i++)
        InsertLastlist(&L,i);  \将1-n依次插入链表最后\
         i=1;
         while(j) \按规则删除n-1个节点,留下所求的节点\
         {
             if(i%m==0)
             {
               Deleteposlist(&L,i);
               j--;i=1;
             }
             else i++;
         }
    }
    printf("%d\n",L->data); \输出最后剩余的一个节点\
    return 0;
}


[ 本帖最后由 S030902508 于 2010-11-9 12:11 编辑 ]
搜索更多相关主题的帖子: 单链 约瑟夫 
2010-11-09 11:33
outsider_scu
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:3
帖 子:430
专家分:1333
注 册:2010-10-21
收藏
得分:0 
你这种人最可恨。

编程的道路上何其孤独!
2010-11-09 15:49
遮天云
Rank: 11Rank: 11Rank: 11Rank: 11
来 自:农村一小伙
等 级:贵宾
威 望:12
帖 子:1132
专家分:2671
注 册:2010-6-1
收藏
得分:0 
以下是引用outsider_scu在2010-11-9 15:49:53的发言:

你这种人最可恨。

汗,本来我想贴我以前写的两种方法来着,看了你这句话就知道怎么回事了顶你
2010-11-09 15:55
以中
Rank: 3Rank: 3
来 自:长沙
等 级:论坛游侠
帖 子:108
专家分:129
注 册:2010-4-13
收藏
得分:0 
#include <stdio.h>
#include <stdlib.h>

struct student
{
    int num;
    struct student *next;
};

#define LEN sizeof(struct student)

//int n;

struct student *creat(int n)        //创建循环链表
{
    struct student *head = NULL;
    struct student *p1,*p2;
    int j;
    for(j=1;j<=n;j++)
    {
            p1=(struct student *)malloc(LEN);
            p1->num=j;

         if(NULL == head)
            head = p1;
        else
            p2->next = p1;
        p2 = p1;
    }
   
    p1->next = head;
    return(head);
}

struct student *del(struct student *head, int n)        //删除满足要求的结点
{
    struct student *p1,*p2,*pfree;
    int i = 1;
   
    if(head==NULL)
    {
        printf("\nlist null!\n");
        return(head);
    }
   
    p1=head;

    while(p1->next != p1)            
    {
        ++i;
        p2 = p1;
        p1 = p1->next;
        if(i % 3 == 0)
        {
            pfree = p1;
            printf("%d\n",p1->num);
            p2->next = p1->next;//开始删除能被三整除的节点
            free(pfree);
            p1 = p2;
        }
        /*free(p2);*/
    }
    return p1;
}

void print(struct student *head, int n)      

  //因为是循环链表所以只能借助i来控制
{
    struct student *p;
    int i = 0;
    printf("\nNow,These %d records are:\n",n);
    p=head;
    if(head!=NULL)
    for(i = 0; i < n; i++ )
    {
        printf("%d",p->num);
       p=p->next;
     }
}

int main()
{
    int n;
    struct student *head;
   
    printf("input  n:\n");
    scanf_s("%d",&n);
   
    head =creat(n);
    print(head, n);
    printf("\nnow begin to delete number three.\n");
    head=del(head,n);
      printf("\nnow begin to show the last number.\n");  
      printf("The last num is %d!\n",head->num);
    free(head);
    return 0;
}
这是为3个一循环时的情况,你自己看一下,做个参考吧!

道之所存,师之所存。
2010-11-10 11:54
S030902508
Rank: 1
等 级:新手上路
帖 子:22
专家分:0
注 册:2010-10-19
收藏
得分:0 
回复 4楼 以中
真的很感谢您。
2010-11-10 18:14
以中
Rank: 3Rank: 3
来 自:长沙
等 级:论坛游侠
帖 子:108
专家分:129
注 册:2010-4-13
收藏
得分:0 
#include<stdio.h>
#include<stdlib.h>
struct sNode /* 建立结构体类型*/
{
    int data;  
    struct sNode *next;
};
void Initilist(struct sNode **HL) /*\初始化一个循环单链表\*/
{
    *HL=NULL;
}
void InsertLastlist(struct sNode **HL,int x) /*\将1-n新节点依次插入循环链表里\*/
{
    struct sNode *newp;
      static struct sNode *p;/*\创建一个新节点,用来存储要插入的数字\*/
       newp=(struct sNode*)malloc(sizeof(struct sNode));
    if(newp==NULL)/*\如果创建失败,退出运行\*/
    {
        printf("内存动态空间用完,退出!\n");
            exit(1);
    }
    newp->data=x;/*\让新节点的数值域等于插入的数字\*/
    if(*HL==NULL)/*\当单链表为空的情况\*/
    {
        *HL=newp;
        newp->next=*HL;
           p=*HL;
        //p=*HL;
        
    }
    else/*\单链表不为空的情况\*/
    {
   
      
      
         p->next=newp;/*\把新节点插入最后\*/
        newp->next=*HL;/*\令新节点指向第一个节点,构成循环\*/
         p=newp;
    }
}
struct sNode *Deleteposlist(struct sNode *HL,struct sNode *x)/*\删除节点\*/
{
    struct sNode *pfree,*p1,*p2;
    if(HL==NULL)
    {
        printf("单链表为空,退出运行!\n");
        return(HL);
    }
    p1=--x;      
    p2 = p1;
    p1 = p1->next;
    pfree = p1;
    printf("Delete number %d\n",p1->data);
    p2->next = p1->next;//开始删除能被三整除的节点
    free(pfree);
    p1 = p2;
    free(p2);
    return p1;
}
void print(struct sNode **HL,int n)
{
  struct sNode *p;
  int i=0;
  printf("\nNow,These %d records are:\n",n);
  p=*HL;
  if(*HL!=NULL)
      for(i=0;i<n;i++)
      {
          printf("%d",p->data);
          p=p->next;
      }
}
int main()
{
    int i,j,m,n;
    struct sNode *L,*p;
while(scanf_s("%d,%d",&n,&m)!=EOF)
{
           j=n-1;
        Initilist(&L); /* \初始化循环单链表\*/
        for(i=1;i<=n;i++)
        InsertLastlist(&L,i);  /*\将1-n依次插入链表最后\*/
        print(&L,n);
        printf("\nnow begin to delete number %d.\n",m);
        p=L;
         while(j) /*\按规则删除n-1个节点,留下所求的节点\*/
         {
               printf("The num is %d!\n",p->data);
             if((*p).data%m==0)
             {
                /*  printf(" num  %d!\n",m);*/
                 printf("The delete num is %d!\n",(*p).data);
                 L=Deleteposlist(L,p);
               j--;
             }
             p++;
         }
 
         printf("The last num is %d!\n",L->data); /*\输出最后剩余的一个节点\*/
    return 0;
}
}
S030902508按照你的意思我改了一下,但能力有限,没能调试出来,真对不起。

道之所存,师之所存。
2010-11-14 10:30
快速回复:约瑟夫循环单链表 高手看看我的程序 望赐教
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.030659 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved