定義：是信息的載體，是描述客觀事實屬性的數、字符及所有能輸入到計算機中并被計算機程序識别和處理的符号的集合

數據的組成：

• 整型、實型等數值類型
• 字符及聲音、圖像、視頻等非數值類型

定義：數據元素是數據的基本單位，通常作為一個整體進行考慮和處理，有一定意義的基本單位，在計算機中通常作為整體處理，也被稱為元素、記錄

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

例子：個人信息表的每一行就是一個數據元素

定義：構成數據元素的不可分割的最小單位，若幹數據項可以組成數據元素。

注：數據項是數據的最小單位

定義：具有相同性質的數據元素的組合，是數據的子集。

例子

定義：抽象數據組織及與之相關的操作

組成：

• 數據對象
• 數據關系
• 基本操作集

抽象數據類型的标準格式：

定義：一個值的集合和定義在此集合上的一組操作的總稱

作用：

• 用來說明變量或表達式的取值範圍
• 說明所能進行的操作

分類：

• 原子類型
• 定義：值不可再分的數據類型
• 例子：int整型
• 結構類型
• 定義：值可以再分為若幹成分(分量)的數據類型
• 例子：int整型
• 抽象數據類型
• 定義：值可以再分為若幹成分(分量)的數據類型
• 例子：int整型

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

數據結構三要素：

• 邏輯結構 對問題抽象後再進行研究
• 存儲結構 對具體細節進行研究
• 數據的運算

邏輯結構是指數據對象中數據元素之間的邏輯關系，即從邏輯關系上描述數據。

1. 線性結構：

定義：結構中的數據元素之間隻存在一對一的關系

例子

2. 非線性結構：

定義：結構中數據元素之間存在非一對一關系

樹形結構

一對多關系

圖形結構

多對多關系

集合

除同屬一個集合外，再無其他關系

​

定義：數據對象在計算機中的存儲表示，也稱為物理結構

數據域：數據元素由若幹個數據項構成時，數據項的表示稱為數據域

數據結構的存儲方法：

1. 順序存儲方法

定義：将邏輯上相鄰的節點存儲在物理位置上也相鄰的存儲單元中，節點之間的關系由存儲單元的鄰接關系來體現

優點：

• 可以實現随機存取（也可以順序存取）
• 每個元素占用最少的空間

缺點：

• 隻能使用相鄰的一整塊存儲單元，可能産生較多的外部碎片

存取結構

• 随機存取：就是存取第N個數據時，不需要訪問前(N-1)個數據，直接就可以對第N個數據操作
• 非随機存取（又稱順序存取）：就是存取第N個數據時，必須先訪問前(N-1)個數據

2 鍊式存儲方法：

定義：不要求邏輯上相鄰的節點在物理位置上也相鄰，借助指示節點存儲地址的指針來表示節點之間的邏輯關系

優點：

• 不會出現碎片現象，能充分利用所有存儲單元

缺點：

• 每個元素因存儲指針而占用額外的存儲空間
• 隻能順序存取

注：

• 節點内存儲單元地址：一定連續
• 相鄰節點存儲空間：不一定連續

3. 索引存儲方法

定義：存儲元素信息時，建立附加的索引表

優點：

• 檢索速度快

缺點：

• 附加的索引表額外占用空間
• 增、删數據時也要修改索引表，會花費更多的時間

注：

• 索引表的每項稱為索引項，索引項的一般形式是<關鍵字，地址>
• 關鍵字：标識唯一一個節點 - 地址：指向上述節點的指針

4. 散列（Hash）存儲方法

定義：根據節點的關鍵字直接計算出該節點的存儲地址，形如location = Hash(key)

優點：

• 檢索、增加和删除節點操作很快

缺點：

• 散列函數不好，會出現元素存儲單元沖突，解決沖突會增加時間和空間開銷

注：

• 該方法本質上是順序存儲方法的擴展
• key：關鍵字
• Hash()：計算地址的方法，散列函數
• location：存儲該節點的地址

定義：施加在數據上的運算，包括運算的定義、實現

注：

• 運算的定義：針對邏輯結構，指出運算的功能
• 運算的實現：針對存儲結構，指出運算的具體操作步驟

定義：算法是對特定問題求解步驟的一種描述，它是指令的有限序列，其中的每條指令表示一個或多個操作

指令能被人或機器等計算裝置執行，可以是計算機指令，也可以是我們平時的語言文字

1. 算法

為了解決某個或某類問題，需要把指令表示成一定的操作序列，操作序列包括一組操作，每一個操作都完成特定的功能

2. 算法例子

把大象裝進冰箱：

• 指令1. 打開冰箱門
• 指令2. 把大象塞進去
• 指令3. 關上冰箱門

1. 有窮性

一個算法必須總是在執行有窮步之後結束，且每一步都必須在有窮時間内完成。

例子： 經常寫出死循環的代碼，這就是不滿足有窮性

2. 确定性

每一條指令必須有确切的含義，相同的輸入隻能得出相同的輸出，讀者對其理解不會産生二義性

3. 可行性

算法中描述的操作都可以通過已經實現的基本運算執行有限次來實現

4. 輸入

有零個或多個輸入，這些輸入取自于某個特定的對象的集合

5. 輸出

輸出是算法進行信息加工後得到的結果，無輸出的算法是沒有意義的

1. 正确性

算法能正确地解決求解問題

正确的層次：

1. 算法程序沒有語法錯誤
2. 算法程序對于合法的輸入數據能夠産生滿足要求的輸出結果
3. 算法程序對于非法的輸入數據能夠得出滿足規格說明的結果
4. 算法程序對于精心選擇的，甚至刁難的測試數據都有滿足要求的輸出結果

層次1要求最低，層析4是最困難的，我們幾乎不可能逐一驗證所有的輸入都得到正确的結果，一般情況下，把層次3作為一個算法是否正确的标準

2. 可讀性

有助于人們閱讀、理解和交流

3. 健壯性

輸入非法數據時，算法能适當地做出反應或進行處理，而不是産生莫名其妙的錯誤

4. 高效率與低存儲量需求

效率：指時間，效率越高越好，時間短的算法效率高。 存儲量：指空間，存儲量越低越好，指算法在執行過程中需要的最大存儲空間。

• 時間複雜度
• 空間複雜度

1. 事後統計方法

主要是通過設計好的測試程序和數據，利用計算機計時器對不同算法編制的程序的運行時間進行比較，從而确定算法效率的高低

缺陷

• 必須依據算法事先編制好程序，通常需要花費大量的時間和精力
• 時間的比較依賴計算機硬件和軟件等環境因素，有時會掩蓋算法本身的優劣
• 所用的操作系統、編譯器、運行框架等軟件的不同，也可以影響它們的結果
• 程序的運行時間往往還與測試數據的規模有很大的關系，效率高的算法在小的測試數據面前往往得不到體驗

2. 事前分析估算方法

在計算機程序編制前，依據統計方法對算法進行估算

程序在計算機上運行時所消耗的時間取決于下列因素：

1. 算法采用的策略和方法 —— 算法好壞的根本
2. 編譯産生的代碼質量 —— 由軟件來支持
3. 問題的輸入規模
4. 機器執行指令的速度

1. 頻度

定義：一個語句在算法中被重複執行的次數

2. T(n)

定義：算法中所有語句的頻度之和

• n：表示該算法問題的規模
• T(n)是該算法問題規模n的函數
• 分析時間複雜度，主要是分析T(n)的數量級

3. 算法的基本運算

定義：最深處循環内語句

算法的基本運算的頻度與T(n)同數量級

4. 算法時間複雜度

定義：用算法的基本運算的頻度f(n)來分析

算法時間複雜度标記：T(n)=O(f(n))

1. O：T(n)的數量級
2. 常見階的叫法 O(1)：常數階；O(2)：線性階；O(logn)：對數階；O(n²)：平方階
3. 常見T(n)的大小關系 O(1)≤O(log₂(n))≤O(n)≤O(n·log₂(n))≤O(n²)≤O(n³)≤O(2ⁿ)≤O(n!)≤O(nⁿ)
4. 複雜度計算規則

• 加法規則 T(n)=T1(n) T2(n)=O(f(n)) O(g(n))=O(max(f(n),g(n)))
• 乘法規則 T(n)=T1(n)T2(n)=O(f(n))O(g(n))=O(f(n)*g(n))

5. 影響時間複雜度的因素

• 問題規模n
• 輸入數據的性質（輸入數據的初始狀态）

6. 最壞情況與平均情況

• 最壞時間複雜度 定義：最壞情況下的時間複雜度
• 平均時間複雜度 定義：所有輸入等概率的情況下，算法期望運行的時間
• 最好時間複雜度 定義：最好情況下的時間複雜度

算法的空間複雜度：記為S(n)，表示該算法所消耗的空間，它是問題規模n的函數

漸進空間複雜度：簡稱為空間複雜度，記為S(n)=O(g(n))

分析空間複雜度，隻需分析除輸入和程序之外的額外空間

1. 觀察法（循環主體中變量與循環條件無關）

（1）計算方法：通過列舉、歸納得出

（2）分類：

• 遞歸類：遞歸程序一般使用公式進行遞推 T(n)=1 T(n-1)=1 1 T(n-2)=···=n-1 T(1)即T(n)=O(n)
• 非遞歸類 直接計數

（3）例子

• 遞歸類

時間複雜度為O(n)

• 非遞歸類

時間複雜度為O(n²)

2. 設循環次數t方法（循環主體中變量與循環條件有關）

（1）計算方法：設t次結束 （2）例子

​時間複雜度為O(log₂(n))

制作不易，有幫助的話還希望能給個 一鍵三連 支持下，謝謝大家。

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