講解第1章的內(nèi)容 18—26頁

講解第2章的內(nèi)容27--36頁

重點:

1、掌握算法復(fù)雜度的計算【難點、重點】

2、線性表的邏輯結(jié)構(gòu)

3、線性表的存儲結(jié)構(gòu)-順序結(jié)構(gòu)

4、線性表順序存儲結(jié)構(gòu)的實現(xiàn)【重點】

練習(xí)內(nèi)容:

25頁習(xí)題2:分析以下各程序段，并用大O記號表示其執(zhí)行時間。

師說:

具有“一對一”邏輯關(guān)系的數(shù)據(jù)，最佳的存儲方式是使用線性表。那么，什么是線性表呢?
線性表，全名為線性存儲結(jié)構(gòu)。使用線性表存儲數(shù)據(jù)的方式可以這樣理解，即“把所有數(shù)據(jù)用一根線兒串起來，再存儲到物理空間中”。

如圖 1 所示，這是一組具有“一對一”關(guān)系的數(shù)據(jù)，我們接下來采用線性表將其儲存到物理空間中。首先，用“一根線兒”把它們按照順序“串”起來，如圖 2 所示:

圖 2 中，左側(cè)是“串”起來的數(shù)據(jù)，右側(cè)是空閑的物理空間。把這“一串兒”數(shù)據(jù)放置到物理空間，我們可以選擇以下兩種方式，如圖 3 所示。

圖 3 兩種線性存儲結(jié)構(gòu)

圖 3a) 是多數(shù)人想到的存儲方式，而圖 3b) 卻少有人想到。我們知道，數(shù)據(jù)存儲的成功與否，取決于是否能將數(shù)據(jù)完整地復(fù)原成它本來的樣子。如果把圖 3a) 和圖 3b) 線的一頭扯起，你會發(fā)現(xiàn)數(shù)據(jù)的位置依舊沒有發(fā)生改變（和圖 1 一樣）。因此可以認(rèn)定，這兩種存儲方式都是正確的。

將具有“一對一”關(guān)系的數(shù)據(jù)“線性”地存儲到物理空間中，這種存儲結(jié)構(gòu)就稱為線性存儲結(jié)構(gòu)（簡稱線性表）。

雖然線性結(jié)構(gòu)是最簡單且最廣泛的一種數(shù)據(jù)結(jié)構(gòu)，但往往簡單中也可以設(shè)計出巧妙的算法，騰訊公司2014年的一道面試題:“快速找到未知長度單鏈表的中間節(jié)點”；2021年某公司春招的一道面試題“為什么redis字典一般不用線性表實現(xiàn)?”等等，大家可以自己思考一下，你會如何完成，然后百度一下其他人的思路，對比一下。

面試會出哪些經(jīng)典算法題?

https://www.zhihu.com/question/34814570

推薦閱讀:

學(xué)習(xí)線性表，高深又燒腦?莫怕，手把手教你終結(jié)煩惱?。ň€性表:順序存儲結(jié)構(gòu)）