例2-9 编写算法删除单链表中"多余"的数据元素，即使操作之后的单链表中所有元素的值都不相同。解题分析：
可以和顺序表采用同样算法，即设想新建一个链表，然后顺序考察原链表中每一个结点的数据元素，在"新表"中进行查找，如果有相同的则舍弃之，否则就插入到新表中。
算法2.21void purge_L(SLink &L )
{
// 删除单链表L中的冗余元素，即使操作之后的单链表中只保留
// 操作之前表中所有值都不相同的元素
p = L->next;
L->next = NULL;; // 设新表为空表
while ( p ) // 顺序考察原表中每个元素
{
succ = p->next; // 记下结点 *p 的后继
q = L->next; // q 指向新表的第一个结点
while( q && p->data!=q->data ) q = q->next;
// 在新表中查询是否存在和p->data相同的元素
if ( !q ) // 将结点 *p 插入到新的表中
{
p->next = L->next;
L->next = p;
}
else delete p; // 释放结点 *p
p = succ;
} // for
} // purge_L
此算法的时间复杂度为O (ListLength2(L))。
|
|||
|
假设已知链表中的数据元素为(5,2,5,3,3,4,2,5,7,5,4,3),则经算法2.21操作之后的链表表示的线性表是什么？
|
|||
|
由于对原表中每个元素都需要在新的链表中进行查询，因此最坏情况下的时间复杂度仍为平方级的，和顺序表相同，正好说明这个时间复杂度是由算法决定的。