探索路@線性表><
博主特別喜歡與人討論問題,歡迎大家有不會的積極提問哈。
有實力的大大們路過幫忙提提意見,感激涕零 ><
版權宣告:本文為博主原創文章,未經博主允許不得轉載,轉載請註明原地址;原文地址:ofollow,noindex">https://www.jianshu.com/p/3797ec06f522
原創始於 《18.10.19/ 簡書/MyOwlCity》;
線性表 :n個具有相同特性的資料元素的集
順序表 :一般陣列實現。從起始地址,佔據一段連續的空間。物理位置上有序,位序明顯
連結串列 :通常指標實現,也可陣列實現(如靜態連結串列)。邏輯上有序,較順序表而言“位置”明顯
1. 類比
升國旗、向國旗行注目禮,中學的我們,每週一,都會在廣場上“嚴陣以待”,伴著國歌,目視國旗徐徐升起,迎接美好新星期的開始。
-
典型順序表:
每個班級站成一排,將排頭高舉班級 LOGO 的同學當作“起始位置”,直到末尾,是一個連續的空間,具有明顯可見的“位序”——0 1 2 3 4 5...
-
邏輯有序
"禮畢,解散,各班有秩序帶回”,不一會,隊形破碎,人與人交匯在一起,如同散在地上的一把穀米,在空間上雜亂無章。但是從被班主任定好的站隊順序角度來看,在邏輯上他們仍然是有序的,只不過丟掉了物理位置上的有序性><
-
典型連結串列
思考一下,每次升旗排隊時,為了防止插錯位置,我們習慣性的把前一個位置的同學當作標誌,每次只要站在他後面就好了。這時除了排頭(也就是排頭大大的前面為空了><),每個人都“心有所指”,即自己的前一個位置。
班主任為了注意到全體的小動作,站在最後面。這時,將班主任看作頭指標,末尾的同學當作第一個結點(猜想這位同學此時心裡兩萬匹#$%&馬在奔騰><),排頭的同學看作尾結點。
活動結束,班級解散,這時又是一片混亂,但是憑藉著每個人心中所指,仍然可以根據某個同學確定出下一個同學的位置,無疑鏈式結構呈現腦海>< -
意外
假設你們班級的人都好懶,真的只是老老實實的記住了自己前一個位置的同學,某個星期一你前面的同學生病請假回家了,這時在排隊的過程中你無法確定自己的前頭是誰,就要倒大黴了。但是生病的同學早就考慮到了這一點,回家之前將他前頭的人告訴了你,你才“倖免於難”,否則就很難受了><
2. 連結串列的分派(名門大派)
- 靜態連結串列
- 單向/雙向double linked list
- 有/無 頭結點
- 迴圈/非迴圈circular linked list
3. 兩者的優/缺點
- SqList 查詢、取值快速
- LinkList 插入、刪除快速
4. 區分DestroyList、ClearList
- 清空:刪除儲存的值,保留開闢的空間(不一定全部保留的)
- 銷燬:刪除儲存的值,並銷燬開闢的空間(一定是半個空間都不留)
5. 受限線性表
- 棧與佇列
參考書目:
《大話資料結構》
《資料結構 嚴蔚敏》