2.2.3 顺序表其它算法举例 例2-6　编写算法删除顺序表中"多余"的数据元素，即使操作之后的顺序表中所有元素的值都不相同。 算法2.12 　　void purge_Sq( SqList &L ) 　{ 　　// 删除顺序表L中的冗余元素，即使操作之后的顺序表中只保留 　　// 操作之前表中所有值都不相同的元素 　　k = -1; 　　　　　　　　　　　　// k 指示新表的表尾 　　for (i=0; i<L.length; ++i)　　 // 顺序考察表中每个元素 　　{ 　　　j=0; 　　　while(j<=k && L.elem[j]!=L.elem[i]) 　　　　++j;　　　　　　　　// 在新表中查询是否存在和L.elem[i]相同的元素 　　　if ( k==-1 || j>k )　// k=-1 表明当前考察的是第一个元素 　　　　L.elem[++k] = L.elem[i]; 　　} // for 　　L.length = k+1;　　　　　　　　// 修改表长 　} // purge_Sq 　　此算法的时间复杂度为O (ListLength2(L)) 　分析： 　　算法中的基本操作为"比较"，控制结构为两重循环，外循环的执行次数和顺序表的表长相同，内循环的执行次数则不超过表长。此外，"比较"操作相对于"移动"操作所需的时间也少。 　　从这个题的算法可以得到一些有益的启示，某种情况下，"删除"操作也可利用"插入"来实现。

解题分析： 　容易想到此题的一个简单算法是： 　　对表中任一个元素，令 j 从 i+1 到 n，将和 进行比较，若相等，则从顺序表中删除该元素，即令从 j+1 到 n 的元素均向前移动一个位置。 　　由于顺序存储结构的特点，在删除元素时必然会引起一连串的元素向前移动，但在上述算法中"每发现一个和 相同的元素，立即将在它之后的元素向前移动一个位置"的做法，将会使那些值和 不同的元素重复多次移动操作，而每次都只移动一个位置（试设想在此元素之后还有很多和 值相同的元素）。算法的时间复杂度将是O (n2)（n为表长）。 　　但如果不是从"删除"而是从"插入"来考虑问题，这个题的解法就会有不同的结果。 　 　　设想另建立一个顺序表，表中只包含原表中所有值不同的元素，则算法思想和例2-2相同，对原顺序表中每一个当前考察的数据元素，在"新表"中进行查找，如果有相同的则舍弃之，否则就插入到"新表"中。由于问题的实质是"删除"，因此所谓"新表"，在存储结构上并非是新建的表，它和原表可以共享存储空间，只须新建一个指针来指示其表尾的当前位置即可。