數據結構：初識（數據結構、算法與算法分析）
- 2020 年 7 月 21 日
- 筆記
- dataStructure&Algorithm
1、數據結構初識
（1）程序、數據結構與算法的關係
程序=數據結構+算法
（2）數據
概念：
- 是能夠輸入到計算機的能夠被計算機處理的各種符號的集合
- 信息的載體
- 對客觀事物的抽象化表示
- 能夠被計算機識別、存儲和加工
例如：將用戶的信息抽象為一張二維表，存儲到數據庫中
分類：
- 數值型數據：整數、實數等，能夠進行數值運算
- 非數值型數據：文字、圖像、圖片、聲音等
（3）數據元素和數據項
數據元素：是數據的基本單位，在計算機中通常作為一個整體考慮和處理（例如：學生退學後刪除某一學生的信息），也稱為元素、記錄、結點、頂點
數據項：構成數據元素的不可分割的最小單位，例如：學生的學號
數據、數據元素、數據項的關係：
整張數據表是用戶的數據，用戶的用戶名是數據項、每一個用戶的信息是一個數據元素
（4）數據對象
概念：
是性質相同的數據元素的集合，是數據的一個子集
（5）數據結構
概念：
數據元素之間的關係
數據結構的內容：
- 邏輯結構：數據元素之間的邏輯關係
- 物理結構：數據元素及其關係在內存中的表示
- 數據的運算和實現：對數據元素可以施加的操作以及這些操作在相應的存儲結構上的實現
邏輯結構的分類：
- 線性結構：有且僅有一個開始結點和終端結點，並且所有的結點都最多只有一個直接前驅和直接後繼，例如：線性表、棧、隊列、串
- 非線性結構：一個結點有多個直接前驅和直接後繼，例如：樹、圖
存儲結構
- 順序結構：用一組連續的存儲單元依次存儲數據元素
- 鏈式結構：一組任意的存儲單元來存儲數據，數據之間的邏輯關係用指針來表示，如：鏈表
（6）數據類型和抽象數據類型
數據類型規定了數值的取值範圍以及操作，是一組性質相同的值的集合以及定義在這個集合上的一組操作的總稱
抽象數據類型（ADT abstrace data type）：一個數學模型以及在數學模型（邏輯結構）上的一組操作，不考慮在計算機內的具體存儲與運算的具體實現算法
三要素：
- 數據對象：例如：定義複數的時候有實部和虛部
- 數據關係：例如：x是實部，y是虛部
- 數據操作：定義、銷毀、獲得實部、虛部等
2、算法與算法分析
（1）算法的描述
- 自然語言：用自然語言描述算法的過程
- 流程圖：傳統流程圖、NS流程圖
（2）算法和算法分析
- 算法是解決問題的一種方法或一個過程，考慮如何將輸入轉換為輸出，一個問題可以有多個算法
- 程序是用某一種語言對算法的具體實現
（3）數據結構和算法的關係
- 數據結構是算法的基礎
- 算法的操作對象是數據結構，在設計算法的時候要構建合適這種算法的數據結構
- 數據結構設計主要是選擇數據的存儲方式（數組或鏈表），算法設計是在選定的數據結構上設計一個滿足要求的好的算法
- 數據結構關注的是數據的邏輯結構、存儲結構、基本操作，而算法關注的是如何在數據結構的基礎上解決實際問題
（4）什麼是算法
算法是求解問題的一系列步驟，用來將輸入的數據轉換為輸出結果
（5）算法的重要特性
- 有限性：執行有限步之後結束
- 確定性：每一條指令無二義性
- 可行性：每一條運算都能精確地執行
- 輸入性：一個算法有零個或多個輸入
- 輸出性：一個算法有一個或多個輸入
（6）算法設計的目標
- 正確性：正確地執行預先規定的功能和性能要求
- 可使用性（用戶友好性）：可以很方便地使用
- 可讀性：易於理解
- 健壯性（魯棒性）：提供異常處理，能夠對不合理的數據進行檢查
- 高效率與低存儲：執行時間短的算法效率高，所需的最大存儲容量低的算法好
（7）算法時間效率的度量
- 事後統計：不可取
- 事前分析：一個算法的運行時間是指一個算法在計算機上運行所耗費的時間，大致等於計算機執行一種簡單的操作（賦值、比較等）所需的時間與執行這種簡單操作的次數的乘積。因為每一條語句的執行時間大致相同，因此，可以只計算語句的頻度（語句的次數）//www.cnblogs.com/zhai1997/p/12034257.html時間複雜度是由嵌套最深的語句頻度決定的
（8）空間複雜度
如：數組倒序
