算法學習筆記（一）

有兩種思想,像珠寶商放在天鵝絨上的寶石一樣濯濯生輝,一個是微積分,另一個就是算法。微積分以及在微積分基礎上建立起來的數學分析體系造就了現代科學，而算法則造就了現代世界。                                        ——《算法的出現》

基本數據結構

1、線形數據結構

(1)    數組: “串”(如:數據串, 二進制串)

(2)    鏈表:  單鏈表:數據+下一個元素的地址指針

         雙鏈表:上一個元素的地址指針+數據+下一個元素的地址指針

 注:數組與鏈表的區別:訪問方式不同,數組是直接單個訪問,鏈表是循鏈訪問。

(3)    線性列表:

棧：   “后進先出”（LIFO）->“一疊盤子”

       插入和刪除操作都在尾端-> 棧頂

隊列: “先進先出”(FIFO)-> “顧客隊列”

            刪除->隊頭->出隊

            插入->隊尾->入隊

優先隊列: (任務)->找出或最大元素，插入一個新元素->堆

2、圖

    無向圖

    有向圖

    區別：是否頂點對(u,v)和頂點對(v,u)相同

    定義：圖G=<V,E>

          V 是一個有限集合，其元素為頂點

          E 是一個有限集合，其元素為一對頂點，為邊。

          注：是否禁止圈，0<=|E|<=|V|(|V|-1)/2

   根據邊數多少:完全圈，稠密圈，稀疏圈。

   圖的表示:

          鄰接矩陣：一個n*n的布爾矩陣

          鄰接鏈表：鄰接矩陣中值為1的列

   加權圈：給邊賦值(權重/成本)

   路徑和環：

          路徑：始于u止于v的鄰接頂點序列

               簡單路徑：a,c,e,f 長度為3

               非簡單路徑:a,c,e,c,f 長度為4

          注：對于有向圖->有向路徑

   連通性：是否連通->取決于是否出現連通分量

   無環圖：不含回路

3、樹(連通無回路圖)

    森林(無回路但不一定連通，其連通分量為樹)

    有根樹：(應用)描述層次關系

    狀態空間樹：回溯和分支界限

    區分/分辨：祖先，真祖先，父母，子女，兄弟，葉節點，父節點，子孫，子樹。

 頂點的深度

 樹的高度

4、有序樹

     二叉樹，二叉查找樹，多路查找樹。

     注：先子女后兄弟表示法

5、集合與字典

    表示集合的方法：位向量，線性列表結構

    抽象數據類型：數據項的抽象對象集合和一系列對這些對象所做的操作

    集合合并問題