2. 计算机
  3. 阅读以下说明和C语言函数，将应填入(n)。 【说明】 已知包含头结点(不存储元素)的单链表的元素已经按照非递减方式排序，函数 compress(NODE*head)的功能是去掉其中重复的元素，使得链表中的元素互不相同。 处理过程中，当元素重复出

阅读以下说明和C语言函数，将应填入(n)。 【说明】 已知包含头结点(不存储元素)的单链表的元素已经按照非递减方式排序，函数 compress(NODE*head)的功能是去掉其中重复的元素，使得链表中的元素互不相同。 处理过程中，当元素重复出

admin2009-01-20  104
问题 阅读以下说明和C语言函数，将应填入(n)。
【说明】
   已知包含头结点(不存储元素)的单链表的元素已经按照非递减方式排序，函数 compress(NODE*head)的功能是去掉其中重复的元素，使得链表中的元素互不相同。
   处理过程中，当元素重复出现时，保留元素第一次出现所在的结点。
   图2-1(a)、(b)是经函数compress()处理前后的链表结构示例图。
   
   链表的结点类型定义如下：
   typedef struct Node{
     int data；
     struct Node *next；
   }NODE；
   【C语言函数】
   void compress(NODE *head)
   {  NODE *ptr，*q；
      ptr= (1)；  /*取得第一个元素结点的指针*/
      while( (2)&& ptr-＞next)  {
      q=ptr-＞next；
      while(q&&(3))  {  /*处理重复元素*/
         (4)q-＞next；
         free(q)；
         q=ptr-＞next；
      }
      (5) ptr-＞next；
   }/*end of while */
   }/*end of compress*/
选项
答案(1)head-＞next (2)ptr (3)q-＞data == ptr-＞data 或ptr-＞next-＞data==ptr-＞data，或其等价表示 (4)ptr-＞next (5)ptr
解析 本题考查基本程序设计能力。
   链表上的查找、插入和删除运算是常见的考点。本题要求去掉链表中的重复元素，使得链表中的元素互不相同，显然是对链表进行查找和删除操作。
   对于元素已经按照非递减方式排序的单链表，删除其中重复的元素，可以采用两种思路。
   1．顺序地遍历链表，对于逻辑上相邻的两个元素，比较它们是否相同，若相同，则删除后一个元素的结点，直到表尾。代码如下：
   ptr=head-＞next；                            /*取得第一个元素结点的指针*/
     while  (ptr && ptr-＞next){               /*指针ptr指示出重复序列的第一个元素结点*/
       q=ptr-＞next；
       while(q && ptr-＞data==q-＞data)  {    /*处理重复元素*/
         ptr-＞next=q-＞next；                /*将结点从链表中删除*/
         free(q)；
         q=ptr-＞next；                       /*继续扫描后继元素*/
       }
       ptr=ptr-＞next；
   }   
   2．对于每一组重复元素，先找到其中的第一个结点，然后向后查找，直到出现一个相异元素时为止，此时保留重复元素的第一个结点，其余结点则从链表中删除。
   ptr=head-＞next；                                    /*取得第一个元素结点的指针*/
      while  (ptr && ptr-＞next)  {                        /*指针ptr指示出重复序列的第一个元素结点*/
         q=ptr-＞next；
         while(q && ptr-＞data==q-＞data)                     /*查找重复元素*/
           q=q-＞next；
         s=ptr-＞next；                                       /*需要删除的第一个结点*/
         ptr-＞next=q；                                       /*保留重复序列的第一个结点，将其余结点从链表中删除*/
         while  (s && s!=q}  {                                /*逐个释放被删除结点的空间*/
         t = s-＞next；    free(s)；    s = t；
      }
      ptr=ptr-＞next；
   }
   题目中采用的是第一种思路。
转载请注明原文地址:https://www.kaotiyun.com/show/MsjZ777K
本试题收录于： 程序员下午应用技术考试题库软考初级分类
0

程序员下午应用技术考试

软考初级

相关试题推荐
随机试题
最新回复(0)