1.1 序存储结构的存储结构和实现

二、综合应用题

　　1．综合应用题题目部分
　　● 习题1：设顺序表va中的数据元素递增有序，试编写一个算法，将x插入到顺序表的适当位置上，以保持该表的有序性。
　　● 习题2：试写一个算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1,a2,…,an）逆置为（an,an-1,…,a1）。
　　● 习题3：已知长度为n的线性表A采用顺序存储结构，请编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为item的数据元素。（O(1)表示算法的辅助空间为常量）。
　　● 习题4：顺序存储的线性表A，其数据元素为整型，试编写一个算法，将表A拆成B和C两个表，使表A中元素值大于等于0的元素放入B，小于0的元素放入C中，要求：
　　（1）表B和C另外设置存储空间；
　　（2）表B和C不另外设置，而利用表A的空间。
　　● 习题5：已知A、B、C为3个递增有序的线性表，现要求对表A做如下操作：删去那些既在表B又在表C中出现的元素。试对顺序表编写实现上述操作的算法。
　　2．综合应用题的答案与分析
　　若无明确说明，综合应用题中涉及的线性表顺序存储结构，假定其数据结构均为：

　　习题1分析：
　　这道题目考查线性表顺序存储结构的插入操作，这里的重点是如何找到元素x应该插入的位置。要注意题中给出的已知条件为数据元素有序递增，利用这一已知条件，对线性表顺序存储结构的插入操作稍做修改即可得出相应的算法。
　　算法的基本思想是：从表的最后一个元素开始，从后往前进行扫描，若该元素值大于等于x，则将该元素后移一位，这样就可找到元素x应该插入的位置。该题的算法如下：

　　习题2分析：
　　这一题的特色在于在实现原表的逆置时，需要利用原表的存储空间。实现方法也比较简单，即将原表的第一个元素和最后一个元素相交换，第二个元素和倒数第二个元素相交换……依此类推，直到最后一个元素。

　　习题3分析：
　　该题目考查对线性表删除操作的理解，一般情况下，对线性表的元素进行删除操作时，都涉及了元素移动的问题，因此，在线性表中删除一个元素的时间复杂度为O(n)。
　　在本题中，要删除表中所有值为item的元素，即对表中的每个元素都要进行一次扫描，且时间复杂度必须为O(n)，此时必然不能进行元素移动的操作，而只能用另外的元素来替换被删除的元素。这里可以考虑两种情况：一种是不考虑元素的相对顺序，即被删除后的线性表中的元素的相对位置可以发生变化；另一种是被删除后元素的相对位置不变。
　　考虑相对位置可以发生变化的情况，在一趟扫描过程中，若找到值为item的元素，则用表中的最后一个元素替换。其算法如下：

　　删除操作后其余元素的相对位置不变的情况应如何考虑呢？请读者自己思考并写出相应的算法。
　　习题4分析：
　　本题依旧考查对线性表基本操作的理解。将表A拆分成表B和表C，若表B和表C不利用原来的存储空间，则此题比较简单。可以对表A的所有元素依次进行扫描，若元素值大于等于0，则将该元素放入线性表B；若元素值小于0，则将其放入线性表C。算法如下：

　　若将表A拆分成表B和表C时，需要利用原有的存储空间，此时又该如何考虑呢？事实上，此时就是对表A重新进行排序，且将所有小于0的元素放在表A的前半部分，而所有大于等于0的元素放在表A的后半部分。此时可采用快速排序的思想，但枢轴记录的值并不作为元素比较的标准，而是用元素值是否为负数作为比较的标准，只需一趟快速排序即可完成本题的要求。其算法如下：

　　作为对本题的扩展，若线性表中有负数、零和正数3种类型，并按照负数、零、正数的顺序重排线性表时应该如何处理呢？请读者自己思考并写出相应的算法。
　　习题5分析：
　　本题考查对于线性表操作的综合运用。本题的前提条件依旧是3个线性表递增有序，要完成题目的要求，必须首先依次找出在表B和表C中同时出现的元素值，再将表A中的该元素删除。要特别注意的是，在本题目中没有特别指明表中的元素值各不相同，因此这里要考虑表A中有连续多个要被删除元素的情况。

　　3．训练自测表（如表1-2所示）

表1-2 应用题练习自测表