阅读以下说明和C函数,填补C函数中的空缺(1)~(5),将解答写在答题纸的对应栏内。 【说明】 约瑟夫问题如下所述:有n个人(编号为1~n)围成一圈,从第一个人开始,按照顺时针方向从1开始计数到m(即数到第m个人),让其出圈,然后再从其顺时

admin2013-07-03  35

问题 阅读以下说明和C函数,填补C函数中的空缺(1)~(5),将解答写在答题纸的对应栏内。
    【说明】
    约瑟夫问题如下所述:有n个人(编号为1~n)围成一圈,从第一个人开始,按照顺时针方向从1开始计数到m(即数到第m个人),让其出圈,然后再从其顺时针方向的下一个人开始,依次计数到m并让其出圈,重复这个过程,直到所有人都出圈,试给出出圈者的顺序。
    以n=5,m=3为例,其中圈顺序为3,1,5,2,4,过程如下图所示。
   
下面的函数Joseph()在单向循环链表表示的基础上输出出圈的过程。n为5时的单向循环链表结构如下图所示。
   
链表的结合类型定义如下:
Typedef struct Node
{    int no;
    struct Node*next:
}node,*LinkList;
函数Joseph(LinkList tail,int n,int m)的处理思路如下:
(1)用k计数,每次都从0开始,当计数到m一1时结束本次计数;
(2)通过指针p查找出圈者所对应的结点,当K的值等于m一1时,P应指向出圈者对应结点的前驱结点;
(3)通过删除结点表示出圈处理;
(4)当m大于圈中剩余人数时,为了避免重复计数,用模运算修改m的值;
(5)计数和删除操作完成后再恢复m的原值。
   【C函数】
    void Joseph(LinkList tail,int n,int m)
    {
    LinkList p,q;
    int k,i,old_m=m;
    p=tail;
    for(i=n;i>l;i- -)    /*i表示圈中剩余人数*/
    {
        m=m%i;           /*避免重复计数*/
    if(0=m)  m=  (1)  
    k=0;
    while(k<  (2)  )
    {  (3)  ;k++;}
    printf(”%d\n”,  (4)  );    /*输出出圈者的编号*/
    q=p->next;
      (5)  =q->next;                /*删除出圈者对应的结点*/
    free(q);
    M=old_m;
    }
    printf(“%d\n”,p->No);
    }

选项

答案(1)i (2)m—1 (3)p=p->next (4)p->next->No (5)p->next

解析 本题考查数据结构中经典的约瑟夫问题。题目中涉及的考点主要有链表运算和程序逻辑,分析程序时首先要明确各个变量所其的作用和代表的含义,并按照语句组分析各段代码的功能,从而完成空缺处的代码填写。
    根据题目中Joseph函数处理思路(4)的描述,m=m%i语句可避免计数过程重复。但这里需要考虑一种特殊情况,即m为0的情况。此时对应的情况应该是正好要数到目前所在位置的前一个人。由于单向循环链表的指针特点,还需要逐个结点进行遍历,则当罔中还剩下i个人时,最多计数到i。因此,(1)处应填入i。
    程序段接下来的while循环用于在单循环链表中扫描结点并完成计数。由于计数器k从0开始计数,冈此while循环得循环条件应为k    (3)处用于实现链表各结点的遍历。由于在链表中利用指针p指向结点并进行遍历,因此,(3)处应填入p=p一≥>next。
    (4)处用于实现输出出圈者的编号。根据题目中Jo-seph函数处理思路(2)的描述,当k的值等于m一1时,p应指向出圈者对应结点的前驱结点。因此,p->next所指向的结点是要被删除的结点,其编号为p->next->No。因此,(4)处应填入p->next->No。
    (5)处用于实现删除出圈者对应的结点。删除p所指结点的后继结点的处理思路为:使指针q指向p所指结点的后继结点,即q=p->next,然后使p所指结点的next指针指向(1所指结点的后继结点,即p->next=q->next,这是典型的在链表中删除结点的方法。因此,(5)处应填入p->next。
转载请注明原文地址:https://kaotiyun.com/show/lnjZ777K
0

最新回复(0)