．[題目分析] 判斷鏈表中數據是否中心對稱通常使用棧將鏈表的前一半元素依次進棧在處理鏈表的後一半元素時當訪問到鏈表的一個元素後就從棧中彈出一個元素兩元素比較若相等則將鏈表中下一元素與棧中再彈出元素比較直至鏈表到尾這時若棧是空棧則得出鏈表中心對稱的結論;否則當鏈表中一元素與棧中彈出元素不等時結論為鏈表非中心對稱結束算法的執行
int dc(LinkedList hint n)∥h是帶頭結點的n個元素單鏈表鏈表中結點的數據域是字符本算法判斷鏈表是否是中心對稱
{char s[]; int i=;∥i記結點個數 s字符棧
p=h>next;∥p是鏈表的工作指針指向待處理的當前元素
for(i=;i<=n/;i++)∥鏈表前一半元素進棧
{s[i]=p>data;p=p>next;}
i;∥恢復最後的i值
if(n%==)p=p>next;}∥若n是奇數後移過中心結點
while(p!=null && s[i]==p>data){i;p=p>next;}∥測試是否中心對稱
if(p==null)return();∥鏈表中心對稱
else return();∥鏈表不中心對稱
}∥算法結束
[算法討論] 算法中先將鏈表的前一半元素(字符)進棧當n為偶數時前一半和後一半的個數相同;當n為奇數時鏈表中心結點字符不必比較移動鏈表指針到下一字符開始比較比較過程中遇到不相等時立即退出while循環不再進行比較
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23336.html
