列表

详情


阅读以下说明和C函数,填补C函数中的空缺(1)~(5),将解答写在答题纸的对应栏内。
【说明】
函数SetDiff(LA,LB)的功能是将LA与LB中的共有元素从LA中删除,使得LA中仅保留与LB不同的元素,而LB不变,LA和LB为含头结点的单链表的头指针。
例如,单链表LA、LB的示例如下图中的(a)、(b)所示,删除与LB共有的元素后的LA如下图中的(c)所示。

 
链表的结点类型定义如下:
   typedef struct Node {
       int data;
       struct Node *next;
   }Node, *LinkList;
函数SetDiff(LinkList LA, LinkList LB)的处理思路如下:
(1)从LA的第一个元素结点开始,令LA的第一个元素为当前元素。
(2)在LB中进行顺序查找,查找与LA的当前元素相同者,方法是令LA的当前元素先与LB的第一个元素进行比较,若相等,则结束在LB中的查找过程,否则继续与LB的下一个元素比较,重复以上过程,直到LB中的某一个元素与LA的当前元素相等(表明查找成功),或者到达LB的表尾(表明查找失败)为止。
(3)结束在LB表的一次查找后,若在LB中发现了与LA的当前元素相同者,则删除LA的当前元素,否则保留LA的当前元素。
(4)取LA的下一个元素为当前元素,重复(2)、(3),直到LA的表尾。

【C函数】
       void SetDiff (LinkList LA, LinkList LB)
       {
       LinkList pre, pa, pb;
       /* pa用于指向单链表LA的当前元素结点,pre指向pa所指元素的前驱 */
       /* pb用于指向单链表LB的元素结点 */
        (1) ;  /* 开始时令pa指向LA的第一个元素 */
       pre=LA;
       while (pa)  {
            pb=LB->next;
       /* 在LB中查找与LA的当前元素相同者,直到找到或者到达表尾 */
          while( (2) )  {
              if (pa->data==pb->data)
                 break;
                (3) ;
          }
         
          if (!pb)  {
          /* 若在LB中没有找到与LA中当前元素相同者,则继续考察LA的后续元素 */
                 pre=pa;
                 pa=pa->next;
             }
             else{
          /* 若在LB中找到与LA的当前元素相同者,则删除LA的当前元素 */
                 pre->next= (4) ;
                 free (pa);
                 pa= (5) ;
          }
}
}

参考答案:

(1)pa=LA->next
(2)pb,或pb!=0,或pb!=NULL
(3)pb=pb->next
(4)pa->next
(5)pre->next

详细解析:

    本题考查C程序设计基本技术及指针的应用。
    题目中涉及的考点主要有链表的查找、删除运算以及程序逻辑,分析程序时首先要明确各个变量所起的作用,并按照语句组分析各段代码的功能,从而完成空缺处的代码填充。
    根据注释,空(1)处应为指针变量pa赋值,使其指向LA链表的第一个元素结点,由于LA为指向头结点的指针,因此空(1)处应填入“pa=LA->next”。
    以指针pa的值为循环条件的以下循环语句用于遍历LA的每一个元素。
    while (pa)  {
    …
    }
    对于LA中的每一个元素pa->data,需要在LB中查找是否存在与其相同者,代码段为:
    pb=LB->next;
    /* 在LB中查找与LA的当前元素相同者,直到找到或者到达表尾 */
      while( (2) )  {
        if (pa->data==pb->data)
          break;
         (3) ;
    }
    显然,通过“pb=LB->next”已经令pb指向了LB的第一个元素,接下来的while语句就用于和LB的元素pb->data逐个比较,显然,空(2)处应填入“pb”,表明pb为非空指针,使得循环体中进行“pa->data==pb->data”运算时,pb指针是有效的。在该循环中,若找到了两个链表的共有元素,则用break跳出循环,此时pb正指向LB中的该共有元素;否则继续在LB中查找,那就需要在空(3)处填入“pb=pb->next”。
    在LB结束查找后,如果找到了与pa->data相同的元素,则之前已经令pb指向它;若是没有找到,则pb是空指针。
    因此,接下来根据pb的值判断是否需要删除LA的当前元素。若不删除,则执行语句组“pre=pa; pa=pa->next;”,继续考察LA的后续元素;若需删除(pa指向的结点),则相关指针的指向如下图所示。
    
    显然,pre已经指向pa所指结点的前驱,要删除pa所指结点,只要将pre->next设置为指向pa所指结点的后继结点即可,即令pre->next= pa->next。因此,在free(pa)之后需重新设置pa的指向,即令pa= pre->next,为继续处理后续元素做好准备。对应地,空(4)应填入“pa->next”,空(5)应填入“pre->next”。

上一题