1. 存儲
2. 數據結構
3. 算法
4. 概述

1. 數組
1. 删除
2. 插入
3. 交換
4. 移動
2. 鍊表
1. 單/雙，循環，靜态鍊表
2. 單鍊表逆序
3. 單鍊表的，從尾部輸出（單次遍曆）
4. 求單鍊表的中間節點（不知道鍊表的長度）
5. 單鍊表求得倒數第K個元素
6. 單鍊表插入排序
7. 兩個順序單鍊表的，合并（順序）
8. 兩個單鍊表的，公共點
9. 判讀單鍊表是否帶環
10. 求環的長度
11. 得到環的切入節點
12. 求帶環鍊表的長度
13. 求出環中的任意，節點的最長距離節點
14. 求帶環鍊表的相交點
3. 棧
1. 遞歸
2. 共享棧
3. 斐波那契數列
4. 用兩個棧，實現一個隊列
5. 求最新棧元素，要求時間複雜度是O（1）
6. 一個數組實現兩個棧，本質上就是順序存儲的共享棧
7. 如何實現逆序棧
8. 如何實現棧的排序
9. 内存棧的構成，棧區和堆區的說明
4. 隊列
1. 循環隊列
2. 優先隊列
3. 兩個隊列實現，棧
4. 貓狗隊列

1. KMP模式匹配算法
2. BM算法
3. Sunday算法
4. 最長公共子串

1. 搜索二叉樹
2. 紅黑樹
3. B 樹
4. B-樹
5. 默克爾樹
6. 赫夫曼樹

1. 廣度優先遍曆
2. 深度優先遍曆
3. 最小生成樹-Prim（普利姆算法）
4. 最小生成樹-Kruskal（克魯斯卡爾）
5. 最短路徑-Dijkstra（迪傑特斯拉）
6. 最短路徑-Floyd（弗洛伊德算法）
7. A*路徑搜索算法
8. 關鍵路徑算法

基礎數據結構，總共分為5篇文章，依次來介紹說明，今天介紹第一篇緒論

程序 = 數據結構 算法；

一切程序的來源都是數據之間的關系存儲。

1、數據是什麼呢？

數據，通俗的講就是整型123，字符串ABC等數值類型，以及聲音，圖片，視頻等等，最終以二級制數據存儲到磁盤中；數據是計算機操作的對象，所有可輸入的處理符号，且可被計算機識别的對象都成為數據

數據元素：是一個數據的集合，也成為"記錄"

數據項：一個數據元素由若幹個數據項組成

數據對象：性質相同的數據元素的集合

數據關系：相互之間存在的一種或是多種關系的數據元素集合

2、數據之間的關系有哪些？

無關系

一對一關系

一對多關系

多對多關系

3、算法及與數據結構之間的關系？

算法是解決問題求解步驟的描述，一條條的序列指令的步驟集合；

就像，如何炒一盤菜？

那麼算法就可以理解為“菜譜”，那麼數據結構就可以理解為“食材”，有了食材，有了菜譜，才能做出一份“程序”

接下來分别描述一下，數據結構和算法

數據結構，也就是數據之間的關系，分為結構：邏輯結構和物理結構（也就是如何存儲的）

• 邏輯結構

1. 集合結構 == 無關系
1. 定義：數據元素之間沒有關系，隻是存儲在一個集合
2. 特點：數據元素是平等的
2. 線性結構 == 一對一的關系
1. 定義：數據元素之間是一對一線性關系
2. 特點：每個數據元素都有前驅或是後驅
3. 樹形結構 == 一對多的關系
1. 定義：數據元素之間是一對多的層次關系
2. 特點：數據元素都有一個前驅或多個後驅
4. 圖形結構 == 多對多的關系
1. 定義：數據元素之間是多對多的關系
2. 特點：數據元素之間相互之間

• 存儲結構

又叫做物理結構，是指數據元素的邏輯結構在計算機中的存儲形式。

1. 順序存儲結構
1. 定義：是把數據元素存放在連續的存儲單元裡
2. 例如：創建一個長度為10的整型數組，計算機就在内存中，按照一個整型（4個Btye）所占位置的大小乘以9，開辟一段連續的空間，然後第一個數據元素放在第一個位置，第二個數據放在第二個位置，依次存放
3. 特點：開辟的空間是連續的，索引查詢比較快，會浪費多餘的空間，需要預制數據元素的大小，空間擴展比較麻煩，插入/删除數據元素，則需要大量元素跟着移動
2. 鍊式存儲結構
1. 定義：是把數據元素發在任意的存儲單元裡，每個數據元素中含有其對應邏輯關系的存儲地址，也就是鍊式存儲結構在分配空間的時候不是連續的，當然了也可以是連續的
2. 例如：現在醫院排隊系統，每個人過去先領取一個号，等着叫好，叫到的時候去看病，在等待的時候，可以愛去哪兒去哪兒；“号”就是一個指針存放數據元素的地址，通過“号”找到關聯數據元素的位置
3. 特點：插入/删除數據元素比較靈活，查詢效率較低，數據元素複雜的關系用鍊式存儲可以更好的表示

算法是解決特定問題求解步驟的描述，在計算機中表現為指令的有限序列，并且每條特定指令都表示一個或多個操作

• 特性

1. 正确的輸入和輸出
2. 有窮性
3. 确定性
4. 可行性

• 設計要求

1. 正确性
2. 可讀性
3. 健壯性
4. 時間複雜度低和空間複雜度低

• 時間複雜度

定義：在進行算法分析時，語句總的執行次數T(n)是關于問題規模n的函數，進而分析T(n)随着n的變化情況并确定T(n)的數量級，算法的時間複雜度，就是算法的時間量度T(n)=O(f(n))

常數階 > 對數階 > 線性階 > nLogn階 > 平方階 > 立方階 > 2^n > N! > 指數階

• 空間複雜度

算法空間複雜度是通過計算算法所需的存儲空間實現，算法空間複雜度的計算公式:S(n) = O(f(n))，其中，n為問題的規模，f(n)為語句關于n所占用的存儲空間的函數

例如：求證1 2 3 4 ... 100？

基本的算法，遍曆1到100個數，進行相加，時間複雜度O(n)

換成高斯算法，時間複雜度O(1)

1 2 3 ... 98 99 100 = a;

100 99 98 ... 3 2 1 = a;

上面兩個表達式相加求證：2a =（100 1）* 100

a =（100 1）* 100 / 2

那麼求，∑i = 1 2 3 … n，得出∑i =（n 1）* n/ 2

就好像上面說的算法，就像炒菜的菜譜（算法），在一定的食材（數據）中，如何做出一份又快又好吃的飯菜；

線性表

樹

圖

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!