数据结构考研分类复习真题 第二章 答案[46]

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

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也是对的

顺便提及题目应叙述为非递减有序因为递增是说明各结点数据域不同一个值比一个值大不会存在相同值元素

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []