試題
【年真題】
（分）己知一個帶有表頭結點的單鏈表夕結點結構為{data…link假設該鏈表只給出了頭指針list在不改變鏈表的前提下請設計一個盡可能高效的算法查找鏈表中倒數第k個位置上的結點（k為正整數）若查找成功算法輸出該結點的data值並返回否則只返回要求
（）描述算法的基本設計思想
（）描述算法的詳細實現步驟
（）根據設計思想和實現步驟采用程序設計語言描述算法（使用C或C++或JAVA語言實現）關鍵之處請給出簡要注釋
參考答案:
（）算法基本思想如下:從頭至尾遍歷單鏈表並用指針p指向當前結點的前k個結點當遍歷到鏈表的最後一個結點時指針p所指向的結點即為所查找的結點
（）詳細實現步驟增加兩個指針變量和一個整型變量從鏈表頭向後遍歷其中指針p指向當前遍歷的結點指針p指向p所指向結點的前k個結點如果pl之前沒有k個結點那麼p指問表頭結點整型變量i表示當前遍歷了多少個結點當i>k時指針p隨著每次遍歷也問前移動一個結點當遍歷完成時p或者指向表頭結點或者指向鏈表中倒數第k個位置上的結點
（）算法描述
int LocateElement(Linklist istint k)
{
p=list>link;
p=list;
i=;
while(p)
{
pl=pl>link;
i++;
if(i>k)p=p>next; //如果i>k則p也往後移
}
if(p==list)
return ; //說明鏈表沒有k個結點
else
{
printf(%d\np>data);
return ;
}
}
返回《數據結構》考研復習精編
[] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23793.html
