电子大神的日记本,供应链专家的功夫茶盘,在这里记录、分享与共鸣。

登录以开始

循环链表求解约瑟夫环

一、上机实验的问题和要求:

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

利用单向循环链表存储结构模拟此过程,按照出列的顺序印出各人的编号。

二、程序设计的基本思想,原理和算法描述:

(包括程序的结构,数据结构,输入/输出设计,符号名说明等)

   此程序实现的方法是建立一个没有表头结点循环链表,然后对循环链表进行相关操作,模拟整个报数及出列过程。

             将每个人的信息用一个结点存储,包括三个信息,一是他的编号number,二是 

     他持有的密码 code,三是指向下一结点的指针。其中编号是一开始按照相邻顺序编号   

     的,密码可以设置,需要输入数值。

                  typedef struct LNode

              {

                   int number;          //编号

                    int code;            //持有密码

                    struct LNode *next;   //指向下一结点的指针

              }LNode,*LinkList;

主要过程由以下两个函数实现

   void CreateList(LinkList &L,int &n);          //创建循环链表

   void Joseph(LinkList &L,int &n);             //约瑟夫环解决方案

其中约瑟夫环解决方案比较复杂,后面具体介绍。

主函数为

       void main(void)

       {  

           LinkList L;

            int n;

          printf("请输入人数:");    

          scanf("%d",&n);       //设置人数        

            CreateList(L,n);          //创建循环链表

            Joseph(L,n);        //约瑟夫环解决方案

       }

    

首先要创建循环链表,在确定人数基础上编号,并输入每个人的密码,连接成一个循环链表,头指针 L 指向编号为 1 号的结点。

/**********************************************************************

                            创建循环链表

**********************************************************************/

void CreateList(LinkList &L,int &n)

{

printf("将这%d个人编号为1-%d号。\n请依次输入这%d个人的密码:",n,n,n); 

    LinkList q;

for(int i=1;i<=n;i++)

{

LinkList p=(LinkList)malloc(sizeof(LNode));  //创建新结点用p指向它

p->number=i;                                 //编号

scanf("%d",&p->code);                        //输入持有密码

        p->next=NULL;

if(i==1) L=q=p; //若是第一个结点,直接用头指针指向它

else              

{

q->next=p;   //将p指向的结点加入链表

    q=q->next;  //q始终保持指向最后的结点

}

}

q->next=L;  //q指向的最后的结点指针域指向头结点,则成为循环链表

}

约瑟夫环解决方案具体实现方案:

第一次报数 默认为 从1 号开始报数,需设置报数上限值m ,报m 的人出列,然后从出列的人后面一个人开始下一轮报数,且报数上限值m变为出列的人持有密码。

第一次由头指针 L 开始向后数到第 m-1 个结点,删掉 第 m-1 个结点的后继结点,即第 m 个结点,(可由一个指针q 反馈回第m 个结点,以便读取被删除结点的信息),这时 第 m-1 个结点 直接指向第 m+1 个结点,同时让头指针 L 也指向第 m+1 个结点。因为下一轮报数时将从第 m+1 个结点开始,即还是 L指向的结点开始。

第二轮报数首先将m值修改为刚刚被删除结点的持有密码,即m=q->code 再进行和第一轮报数相同的操作。

以后每轮报数如次反复执行,直到所有结点被删除结束。

这个过程需要一个删除函数来实现,函数功能是

   删除以头指针L开始第i个结点,q返回结点指针,并改变头指针位置为下一轮报数的第一个结点。

/**********************************************************************

             删除以L为头第i个结点,q返回结点指针,改变头指针位置

**********************************************************************/

void DeleteList(LinkList &L,int i,LinkList &q) 

{

    if(i==1) DeleteList(L,i+LengthList(L),q);//i=1时需要特殊处理

   else

   {

   LinkList p=L; 

   int j=0;

   while(jnext;j++;} //p指向第i-1个结点,即被删除结点的前驱结点 

   q=p->next;                    //p指向被删除结点,返回信息

   p->next=p->next->next;        //删除第i个结点

   L=p->next;                    //修改头指针

    }

}

其中i=1时情况比较特殊,需要特殊处理,因为i=1时表示要删除头指针本身指向的结点,无法直接找到其前驱结点。可以改为删除第i+LengthList(L)个结点,同样也是删除头指针本身指向的结点,但需要加一个求表长的函数。

/**********************************************************************

                            约瑟夫环解决方案

**********************************************************************/

void Joseph(LinkList &L,int &n)  

{

    int m;

printf("请输入第一个报数上限值:");//设置第一轮报数上限值

scanf("%d",&m);

printf("\n出列顺序:\n");

LinkList q;

for(int i=1;inumber,q->code);//打印相关信息

        m=q->code; //修改报数上限值为被删除结点的密码值

free(q);   

}

    printf("%d.\t%d号\t他的密码为:%d\n",n,L->number,L->code);

}

三、源程序及注释:

#include<stdio.h>

#include<malloc.h>

typedef struct LNode

{

int number;          //编号

int code;            //持有密码

struct LNode *next;  //指向下一结点的指针

}LNode,*LinkList;

void CreateList(LinkList &L,int &n);             //创建循环链表

void Joseph(LinkList &L,int &n);                 //约瑟夫环解决方案

void DeleteList(LinkList &L,int i,LinkList &q);  //删除以L为头第i个结点,返回结点

                                                 //指针,改变表头位置

int LengthList(LinkList L);                      //求循环链表长度

/**********************************************************************

                            主函数

**********************************************************************/

void main(void)

{  

LinkList L;

int n;

printf("请输入人数:");

scanf("%d",&n);              //设置人数

    CreateList(L,n);             //创建循环链表

    Joseph(L,n);                 //约瑟夫环解决方案

}

/**********************************************************************

                            创建循环链表

**********************************************************************/

void CreateList(LinkList &L,int &n)

{

printf("将这%d个人编号为1-%d号。\n请依次输入这%d个人的密码:",n,n,n); 

    LinkList q;

for(int i=1;i<=n;i++)

{

LinkList p=(LinkList)malloc(sizeof(LNode));  //创建新结点用p指向它

p->number=i;                                 //编号

scanf("%d",&p->code);                        //输入持有密码

        p->next=NULL;

if(i==1) L=q=p; //若是第一个结点,直接用头指针指向它

else              

{

q

博主
王天
王天's Blog
王天
点击跳转