算法系列15天速成——第七天 線性表【上】

人活在社會上不可能孤立，比如跟美女有着千絲萬縷的關系，有的是一對一，有的是一對多，有的是多對多。

哈哈，我們的資料也一樣，存在這三種基本關系，用術語來說就是:

<1>  線性關系。

<2>  樹形關系。

<3>  網狀關系。

一： 線性表

      1 概念：

                 線性表也就是關系戶中最簡單的一種關系，一對一。

                  如：學生學号的集合就是一個線性表。

      2 特征：

                 ① 有且隻有一個“首元素“。

                 ② 有且隻有一個“末元素”。

                 ③ 除“末元素”外，其餘元素均有唯一的後繼元素。

                 ④ 除“首元素”外，其餘元素均有唯一的前驅元素。

     3 存儲劃分：

                  ① 如果把線性表用“順序存儲”，那麼就是“順序表”。

                  ② 如果把線性表用“鍊式存儲”，那麼就是“連結清單”。

     4  常用操作：添加，删除，插入，查找，周遊，統計。

今天主要就說說“線性表”的“順序存儲”。

那麼下面就簡單的淺析一下這個操作的原理和複雜度。

     <1> 初始化順序表：  

                           這個操作其實還是蠻簡單的，設定length=0，也就是O(1)的時間。

     <2> 求順序表長度：  

                           這個不解釋，O(1)的時間。

     <3> 添加節點：      

                           因為是順序表，是以添加的節點直接會放到數組的末尾，時間也是O(1)的。

     <4> 插入節點：

                           這個還是有點小麻煩的，主要也就是說分兩種情況：

                                    ①：當插入節點在數組的最後，那麼這個“插入”其實就是”添加“操作，時間當然是O(1)。

                                    ②：當插入節點在數組的開頭，那就悲催了，被插入節點的後續元素都要向後移動一位，

                                          　　也就讓整個數組一陣痙攣，效率低下可想而知，時間複雜度退化為O(n)。

      <5> 删除節點：      

                             這個跟“插入”的道理是一樣的，也要分兩個情況，

                                     ①：當删除的元素在數組的最後，不用移位，謝天謝地，時間為O(1)。

                                     ②： 當删除的元素在數組的開頭，删除節點處的元素都要統統向前移位，同樣也是一陣痙攣，

                                           　   時間複雜度也退化為O(n)。

      <6> 按序号查找節點：

                               大家都知道，順序表的存儲位址是連續的，是以第N個元素位址公式為：（N-1）X 資料存儲長度。

                                        哈哈，這就是順序表得瑟的地方，查找的時間複雜度為O(1)。

      <7> 按關鍵字查找：  

                                 嗯，這個在日常開發中用的最多的，那麼就避免不了将key的值在我們的list中查找，前期也說過，

                                        最快的查找是O(1),當然他是用空間來換取時間的，最慢的查找是O(n)，那麼這裡我們就一個for

                                        循環搞定，時間複雜度為O(n)。

說了這麼多，目的就是預先評估算法的執行效率，給我們帶來一手的參考資料，做到真正的運籌帷幄，決勝千裡之外。

這也是我們學習算法的目的，到時候不會讓我們說tnd，程式歇菜了，我也歇菜了。

好，現在是上代碼時間。

運作結果：