資料結構與算法三天時間夠嗎？2021.01.19晚-？？ 對了 記得總結部落格項目怎麼做的，自己整理下；

資料結構與算法理論學習之線性表

• 邏輯結構
• • 資料結構的基本概念
  • 資料的邏輯結構
  • • 1. 線性結構
    • • 1.1 線性表
      • 1.2 線性表的存儲結構
      • 1.3 線性表的算法
      • 1.4 特殊的線性表棧
      • 1.5 特殊的線性表隊列
      • 1.6 特殊的線性表串
    • 2. 樹型結構
    • 3. 圖狀結構
    • 4.算法分析
• 總結

資料與算法内容分為三個部分，邏輯結構、存儲結構、算法。

邏輯結構

邏輯結構：資料與資料之間的關系

資料結構的基本概念

1. 按照某種邏輯關系組織起來的一批資料，如線性表、樹、圖；
2. 存儲結構：按照一定方式放在計算機中：如數組、連結清單；
3. 算法：在這組資料上定義了運算的集合：如插入、删除、查找、排序等；

資料的邏輯結構

1. 線性結構

元素之間的關系是一對一的；

1.1 線性表

上面的元素a1,a2,…,an等可以是複雜資料項；

1.2 線性表的存儲結構

順序存儲結構-----順序表

元素位址計算，其中len是每個元素所需空間大小

非順序存儲結構-鍊式存儲結構------鍊式表

• 單連結清單

  

  非順序存儲，實體位置不一定相鄰；

  在bc之間插入x,通過指針指向來進行插入；

  

• 單向循環清單

  

• 雙向連結清單

  在雙向連結清單中，結點都有兩個指針域，一個用于存放前繼結點位址，一個用于存放後繼結點位址；

  

• 雙向循環連結清單

  

• 靜态連結清單（前面幾種都是動态連結清單）

  類似于數組，但是也有兩部分組成，資料和位址，如下圖所示

  

1.3 線性表的算法

順序存儲結構的算法

• 插入算法

  插入算法的思想

  

  

  對于插入算法的時間複雜度與插入資料的位置有關，平均時間複雜度為O(n);

  插入算法1:将資料出入到有序清單的合适位置，首先要查找到插入位置，然後做插入操作；插入資料之後有序清單要任然有序

• 删除算法

  删除線性表中的第i個元素，并且傳回删除的資料值；

  算法思想：

  

  

  删除算法元素平均移動次數是表長的一半；删除算法平均時間複雜度O(n)

  删除算法1

  

  非順序存儲結構的算法
• 定位算法

1. 單向連結清單的定位

   功能：在連結清單中查找第i個結點，若存在傳回第i個結點位址，否則傳回null空；

   算法思想：從頭結點開始逐個查找并計數，直到找到第i個結點為止；

   算法分析：定位算法執行，平均移動表長一半，算法時間複雜度為O(n);

   

• 單連結清單的插入算法

1. 功能：線上性表第i處插入其數值為x新結點；
2. 算法思想：找到第i-1個結點，在第i-1個結點後面插入新的結點；
3. 算法分析：單連結清單插入隻需要更改後繼結點；

• 雙向連結清單的插入算法

1. 功能：在雙向連結清單的第i個結點（p結點）插入新的結點s；
2. 算法思想：需要更改四個指針指向，要更改s的前驅，後繼指針；

   

• 删除算法

1. 單連結清單的删除算法

   功能：删除單連結清單的第i個結點，(p指向第i-1個結點)；

   算法思想:單向連結清單删除隻需要更改後繼指針；

2. 雙向連結清單的删除算法

   功能：删除第i個結點(p結點)；

   算法思想：需要找到第i個結點P；

   

   連結清單的應用

• 多項式相加

  

1.4 特殊的線性表棧

棧是特殊的線性表，是操作受限的線性表，是一種先進後出的線性表；

• 棧的順序存儲結構：

  判斷棧滿，棧空條件；

  

• 棧的四種操作

  入棧

  

  出棧

  判斷棧滿

  判斷棧空

• 棧的鍊式存儲結構

  

  鍊式存儲結構棧進棧算法思想

  

  鍊式存儲結構棧出棧算法思想

  

• 棧的應用

  例子1

  

  

  例子2

  

1.5 特殊的線性表隊列

• 隊列的基本概念

  隊列是先進先出的，在表的一端(隊尾)進行插入，另外一端(對頭)進行删除；相比于棧，棧一種入棧序列可以對應多種出棧序列，隊列一種入隊序列就隻有一種出隊序列，如入隊序列1,2,3,4，對應的出隊序列就是1,2,3,4；

  

  隊列的幾種基本運算

  

• 循環隊列（順序存儲）

  循環隊列解決了兩個問題一個是假溢出問題一個是提高了效率

  循環隊列指針移動問題；

  

  循環隊列條件判斷問題：

  

  入隊算法需要先判斷隊列是否已滿，出隊算法需要判斷隊列是否為空；

  算法分析：T(n)=O(1);

• 鍊式隊列（非順序存儲）

  

  在隊尾入隊，隊首出隊：隊首出隊如下

  

• 隊列的應用

  循環隊列例子：報數問題

  

  算法思想：

  

1.6 特殊的線性表串

• 串的基本概念

  串是一種特殊的線性表；

  

  

  

  

• 串的模式比對

1. BF算法（樸素算法）

   

   

   

   算法分析

   最好的情況時間複雜度為O(m),其中m是子串的長度；

   最壞情況時間複雜度為O(mn),其中n是主串長度；

   平均時間複雜度也是O(mn);

   

2. KMP算法

   

   

3. 串的應用

   

2. 樹型結構

元素之間的關系一對多；樹型結構如圖所示

3. 圖狀結構

元素之間關系多對多的；圖狀結構如圖所示

4.算法分析

1. 算法時間複雜度

   算法中各語句執行時間總和；時間複雜度類型如下

   

2. 算法空間複雜度

總結

提示：這裡對文章進行總結：

例如：以上就是今天要講的内容，本文僅僅簡單介紹了pandas的使用，而pandas提供了大量能使我們快速便捷地處理資料的函數和方法。