表的應用(鏈表補充) -开发者知识库

表的應用(鏈表補充) -开发者知识库,第1张

#鏈表的應用

#書中鏈表的應用舉出了三個例子:多項式ADT(使用鏈表來存儲多項式並進行與之相關的操作),第二則是“基數排序”,可以理解為“桶排序”的升級版,即:先確定一個基,先把要排列的數按最低位進行桶排序,然后是倒數第二高的位,直到最高位位置為止,這個實現起來不難,值得注意的是,前邊對低位的排序保證了后邊排序高位時進入桶的順序是從低到高(有興趣的可以自己實現一下試試,不了解桶排序的也應該去百度一下)。

#在我看來應該還是第三個更為有趣:多重表。相對於前兩種,這用應用可能更加偏向實用。眾所周知,有一維數組,就有高維數組,相應的,與一維的鏈表相應的,也有多重鏈表:下邊放出多重表的實現圖

表的應用(鏈表補充) -开发者知识库,第2张

容易看出,它是一個由多組循環鏈表構成的二維結構,我們用表頭作為坐標軸上的點,兩組鏈表構成了x,y軸。如果某個元素同時具有Cn,Sm兩種屬性,那么就創造一個新的結點,將它添加到以Cn為表頭和以Sm為表頭的鏈表的交點。而使用循環鏈表則使得沿坐標軸的查找操作變得更加方便。

和一維鏈表一樣,使用多重鏈表的目的是節約空間,在使用多維數組空間利用率比較低的時候,多重表將是一個不錯的選擇。

#在本節末,本書提出了鏈表的另一種實現方法:游標實現。

游標實現的優勢是避免了使用malloc函數和free函數,從而適應了那些無法使用指針的語言。它的缺點則是必須知道鏈表的容量,從而確定制作多大的游標(一個未放入值的鏈表)模擬的malloc函數和free函數就是通過在游標中存取節點實現的。感興趣的讀者可以自己實現以下,再此便不再贅述。

#棧:

棧是一種特殊的表,它只允許對首元素進行操作,因此常用於解決“后進先出”類型的問題。

棧的實現可以根據上述黑體字對表的實現進行改寫得到,因此不再多做描述。

#隊列:

隊列也是一種特殊的表,不同的是它允許對隊首和隊尾兩個元素進行操作,它常用於解決“先進先出”的問題。

隊列的實現亦不復雜,請讀者自行腦補!


P.S. :其實棧和隊列是數據結構中相當重要的一部分,不過我之前打的稿子沒保存,所以丟掉了,又懶得重新打。。。。。。

另一方面,關於棧和隊列,介紹的博客並不在少,還請各位看官出門右拐,自行百度好了。

最后,c 的STL庫中其實包含了隊列和棧的實現,可以極其方便的調用,因此我們大都不直接寫出來,本章的意義,也只在於引導大家去理解這兩種數據結構,真正用的時候,還是STL來的方便啊!

最佳答案:

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复