．[題目分析] 在由正整數序列組成的有序單鏈表中數據遞增有序允許相等整數存在確定比正整數x大的數有幾個屬於計數問題相同數只計一次要求記住前驅前驅和後繼值不同時移動前驅指針進行計數將比正整數x小的數按遞減排序屬於單鏈表的逆置問題比正整數x大的偶數從表中刪除屬於單鏈表中結點的刪除必須記住其前驅以使鏈表不斷鏈算法結束時鏈表中結點的排列是小於x的數按遞減排列接著是x(若有的話)最後是大於x的奇數
void exam(LinkedList laint x)∥la是遞增有序單鏈表數據域為正整數本算法確定比x大的數有幾個;將比x小的數按遞減排序並將比x大的偶數從鏈表中刪除)
{p=la>next;q=p;∥p為工作指針 q指向最小值元素其可能的後繼將是>=x的第一個元素
pre=la;∥pre為p的前驅結點指針
k=;∥計數(比x大的數)
la>next=null;∥置空單鏈表表頭結點
while(p && p>data<x)∥先解決比x小的數按遞減次序排列
{r=p>next;∥暫存後繼
p>next=la>next;∥逆置
la>next=p;
p=r;∥恢復當前指針退出循環時r指向值>=x的結點
}
q>next=p; pre=q;∥pre指向結點的前驅結點
while(p>data==x){pre=p; p=p>next;}∥從小於x到大於x可能經過等於x
while(p)∥以下結點的數據域的值均大於x
{k++; x=p>data;∥下面仍用x表示數據域的值計數
if(x % ==)∥刪偶數
{while (p>data==x)
{u=p;p=p>next;free(u);}
pre>next=p;∥拉上鏈
}
else∥處理奇數
while (p>data==x)∥相同數只記一次
{pre>next=p;pre=p;p=p>next;}
}∥while(p)
printf(比值%d大的數有%d個\nxk);
}∥算法exam結束
[算法討論] 本題要求用最少的時間和最小的空間本算法中最少的時間體現在鏈表指針不回溯最小空間是利用了幾個變量在查比x大的數時必須找到第一個比x大的數所在結點(因等於x的數可能有也可能多個也可能沒有)之後計數據的第一次出現同時刪去偶數
順便指出題目設有按遞增次序的有序單鏈表所給例子序列與題目的論述並不一致
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23323.html
