數據結構考研分類復習真題 第二章 答案[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也是對的

　　順便提及題目應敘述為非遞減有序因為遞增是說明各結點數據域不同一個值比一個值大不會存在相同值元素

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

From:http://tw.wingwit.com/Article/program/sjjg/201311/23328.html