1.3 章真题解析

1.3.2 综合应用题

　　例题17
　　顺序存储的线性表A，其数据元素为整型，试编写一算法，将A拆成B和C两个表，使A中元素值大于等于0的存入B，小于0的存入C中。
　　要求：（1）表B和C另外设置存储空间；（2）表B和C不另外设置，而利用A的空间。
　　例题17分析
　　第一个要求实现很简单，只需扫描一遍A，依次判断A中的每个元素并做相应操作即可；第二个要求需要在A的头尾各设一个指针，分别从头部和尾部开始扫描。算法描述如下：
　　
　　例题18
　　设一单链表，结点由整数数据和指针项组成，计算链表中数据只出现一次的结点个数，要求空间复杂度为O(1)，编写程序，并写出算法思想。
　　例题18分析
　　可以从头开始遍历链表，对于当前遍历的元素p，用另外一个指针，从它后面一个元素开始遍历链表，如果发现有结点的数据值和p的数据值一样，就置重复标记为true，并删除该结点。否则，如果没有发现有结点的数据值和p的数据值一样，将非重复元素的计数器加1。具体算法描述如下：
　　
　　例题19
　　设计算法，判断一个带头结点的双向循环链表DL(dulinklist)是否对称相等。例如，表（25，34，25）和表（25，3，25）为对称的。其中结点结构为struct node{elemtype data; node *Llink,rlink;}。
　　例题19分析
　　分别设置左右指针，从两边向中间移动，同时判断是否对称。当左右两指针碰头或交叉时终止。算法描述如下：
　　
　　例题20
　　已知A、B、C为三个递增有序的线性表，现要求对表A做如下操作：删除那些既在表B，又在表C中出现的元素。试对顺序表编写实现上述操作的算法。
　　例题20分析
　　要完成题目的要求，首先必须依次找出在表B和表C中同时出现的元素值，再将表A中的该元素删除。要特别注意的是，本题中没有特别指明表中的元素值各不相同，因此，要考虑表A中有连续多个要被删除元素的情况。算法描述如下：