数据结构 | 每日一练（65）

数据结构

合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下

——老子

1

每日一练

1．在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素。例如：（7，10，10，21，30，42，42，42，51，70）将变作（7，10，21，30，42，51，70），分析算法的时间复杂度。

正确答案

ps：||代表注释

1.[题目分析] 在递增有序的线性表中，删除数值相同的元素，要知道被删除元素结点的前驱结点。

LinkedList DelSame（LinkedList la）∥la是递增有序的单链表，本算法去掉数值相同的元素，使表中不再有重复的元素。

{pre=la->next；∥pre是p所指向的前驱结点的指针。

p=pre->next；∥p是工作指针。设链表中至少有一个结点。

while（p!=null）

if（p->data==pre->data） ∥处理相同元素值的结点

{u=p；p=p->next；free（u）；} ∥释放相同元素值的结点

else {pre->next=p；pre=p；p=p->next；} ∥处理前驱，后继元素值不同

pre->next=p；∥置链表尾。

}∥DelSame

[算法讨论] 算法中假设链表至少有一个结点，即初始时pre不为空，否则p->next无意义。算法中最后pre->next=p是必须的，因为可能链表最后有数据域值相同的结点，这些结点均被删除，指针后移使p=null而退出 while循环，所以应有pre->next=p使链表有尾。若链表尾部没数据域相同的结点，pre和p为前驱和后继，pre->next=p也是对的。顺便提及，题目应叙述为非递减有序，因为“递增”是说明各结点数据域不同，一个值比一个值大，不会存在相同值元素。