|
|
教學公告
講解第1章的內容 18—26頁
講解第2章的內容27--36頁
重點:
1、掌握算法復雜度的計算【難點、重點】
2、線性表的邏輯結構
3、線性表的存儲結構-順序結構
4、線性表順序存儲結構的實現(xiàn)【重點】
練習內容:
25頁習題2:分析以下各程序段，并用大O記號表示其執(zhí)行時間。
師說:
具有“一對一”邏輯關系的數(shù)據(jù)，最佳的存儲方式是使用線性表。那么，什么是線性表呢?
線性表，全名為線性存儲結構。使用線性表存儲數(shù)據(jù)的方式可以這樣理解，即“把所有數(shù)據(jù)用一根線兒串起來，再存儲到物理空間中”。
如圖 1 所示，這是一組具有“一對一”關系的數(shù)據(jù)，我們接下來采用線性表將其儲存到物理空間中。首先，用“一根線兒”把它們按照順序“串”起來，如圖 2 所示:
圖 2 中，左側是“串”起來的數(shù)據(jù)，右側是空閑的物理空間。把這“一串兒”數(shù)據(jù)放置到物理空間，我們可以選擇以下兩種方式，如圖 3 所示。
圖 3 兩種線性存儲結構
圖 3a) 是多數(shù)人想到的存儲方式，而圖 3b) 卻少有人想到。我們知道，數(shù)據(jù)存儲的成功與否，取決于是否能將數(shù)據(jù)完整地復原成它本來的樣子。如果把圖 3a) 和圖 3b) 線的一頭扯起，你會發(fā)現(xiàn)數(shù)據(jù)的位置依舊沒有發(fā)生改變（和圖 1 一樣）。因此可以認定，這兩種存儲方式都是正確的。
將具有“一對一”關系的數(shù)據(jù)“線性”地存儲到物理空間中，這種存儲結構就稱為線性存儲結構（簡稱線性表）。
雖然線性結構是最簡單且最廣泛的一種數(shù)據(jù)結構，但往往簡單中也可以設計出巧妙的算法，騰訊公司2014年的一道面試題:“快速找到未知長度單鏈表的中間節(jié)點”；2021年某公司春招的一道面試題“為什么redis字典一般不用線性表實現(xiàn)?”等等，大家可以自己思考一下，你會如何完成，然后百度一下其他人的思路，對比一下。
面試會出哪些經典算法題?
https://www.zhihu.com/question/34814570
推薦閱讀:
