數據結構(Data structure):是電腦組織數據和存儲數據的方式，是指一組相互之間存在一種或多種特定關係的數據的組織方式和它們在電腦內的存儲方式，以及定義在該組數據上的一組操作。 ...
一、引言
數據結構(Data structure):是電腦組織數據和存儲數據的方式，是指一組相互之間存在一種或多種特定關係的數據的組織方式和它們在電腦內的存儲方式，以及定義在該組數據上的一組操作。
數據結構：數據的邏輯結構+數據的存儲結構+數據的基本運算
電腦解決問題的步驟：
- 1、建立數學模型
- 2、設計求解演算法
- 3、編程實現演算法(運用各種電腦語言實現演算法)
1976年瑞士電腦科學家尼克勞斯·維爾特[Niklaus Wirth]提出：演算法+數據結構=程式
二、基本概念和術語
數據(Data)：所有能被電腦處理的符號的集合。實際問題中的數據稱為原始數據
數據元素(Data Element):是數據這個集合中的一個個體即數據的基本單位。
數據項(Data Item)：數據元素常常還可分為若幹個數據項，數據項是數據具有意義的最小單位；資料庫中，數據項又稱為欄位/域,它是數據的不可分割的最小標識單位。
1、數據的邏輯結構：數據的邏輯結構是指數據及數據的組織方式，是一種數學模型；指數據元素之間的結構關係
數據的邏輯結構(D, {R}) 可分為下列幾種: D = {d1,d2, …, dn}
- ◆ 集合: 數據元素同“屬於一個集合”。R = { }。任意兩個結點之間都沒有鄰接關係，組織形式鬆散
- ◆ 線性結構: R= {(d1, d2), (d2, d3), …, (dn-1, dn)}，即除起始節點和終端結點d1、dn外，每個節點有一個前驅和一個後繼；結點按邏輯關係依次排列形成一條“鏈”，結點之間一個一個依次相鄰接。
- ◆ 樹形結構: (D, {R}) 構成樹，即每個元素最多有一個前驅，可以有多個後繼；具有分支、層次特性，上層的結點可以和下層多個結點相鄰接，但下層結點只能和上層的一個結點相鄰接
- ◆ 圖結構: (D, {R})構成一個圖；最複雜，任何兩個結點都可以相鄰接。
2、數據的存儲結構(物理結構)：數據的存儲結構是指數據的邏輯結構在電腦中的表示，數據的存儲結構分為順序存儲結構和鏈接存儲結構兩種。
存儲結構的主要部分：
- 存儲結點：每個存儲結點存放一個數據元素
- 元素邏輯關係：數據元素之間關聯方式的表示
數據結構的存儲=數據元素的存儲+元素邏輯關係的存儲
元素關聯關係的存儲方式主要有：
- 順序存儲方式：指所有存儲節點存放在一個連續的存儲區里，利用節點在存儲器中的相對位置來表示元素之間的邏輯關係
- 鏈式存儲方式：指每個存儲點除了包含一個數據元素外，還包含指針，每個指針指向一個與本節點有邏輯關係的節點，用指針表示數據元素之間的邏輯關係
- 索引存儲方式
- 散列存儲方式
=============順序存儲方式=================
順序存儲方式：藉助數據元素的相對存儲位置來表示數據的邏輯結構；
線性表的順序存儲方法：將表中的結點一次存放在電腦記憶體中一組連續的存儲單元中。
順序的方法: 將元素存儲到一片連續的存儲區
特點：
- 1、 預先分配好長度，需要預估存儲數據需要的存儲量；
- 2、插入和刪除需要移動其他元素；
- 3、存取快捷，是隨機存取結構。
=============鏈式存儲方式=================
鏈式存儲方式：藉助數據元素地址的指針表示數據的邏輯結構；這種結構是給結點附加一個指針欄位，指出其後繼節點的位置，即存放結點的存儲單元分為兩部分:數據項和指針項
特點：
- 動態分配，不需要預先確定記憶體分配；
- 插入和刪除不需要移動其他元素；
- 非隨機存取結構
===========索引存儲方式===============
索引存儲方式：藉助索引表中的索引指示各存儲節點的存儲位置。
===========散列存儲方式===============
散列存儲方式：用散列函數指示各節點的存儲位置。
3、運算
運算：指在某種邏輯結構上施加的操作，即對邏輯結構的加工。
加工型運算：其操作改變原邏輯結構的值；如：結點個數，結點內容等。
引用型運算：其操作不改變原邏輯結構的值。
基本運算：建立(創建)、查找 、讀取 、插入 、刪除
三、演算法及描述
演算法：演算法規定了求解給定類型問題所需的所有“處理步驟”及執行順序，使給定類型問題能在有限時間內被機械的求解。
演算法必須使用某種語言描述：
- 程式
- 介於自然語言和程式設計語言的偽代碼
- 非形式演算法（自然語言）
- 框圖(N-S圖)
一個演算法是對特定問題求解步驟的一種描述，它是指令的有窮序列。
演算法具有以下特性：
- ① 有窮性: 一個演算法總是在執行有窮步後結束。
- ② 確定性: 演算法的每一步都必須是明確地定義的。
- ③ 可行性: 演算法中的每一步都是可以通過已經實現的操作來完成的。
- ④ 輸入: 一個演算法有零個或者多個輸入，這些輸入取自於特定的對象集合。
- ⑤ 輸出：一個演算法有一個或者多個輸出，它們是與輸入有特定關係的量。
四、演算法分析
演算法的設計應滿足：
- ① 正確性：對於合法的輸入產生符合要求的輸出。
- ② 易讀性：演算法應該易讀、便於交流， 這也是保證演算法正確性的前提；添加註釋也是一種增加可讀性的辦法。
- ③ 健壯性：當輸入非法數據時， 演算法還能做出適當的反應而不會崩潰，如輸出錯誤信息；演算法中應該考慮適當的錯誤處理。
- ④ 時空性：指演算法的時間複雜度和空間複雜度，演算法分析主要分析演算法的時間複雜度和空間複雜度，目的是提高演算法的效率。
最優演算法的2個度量：
- 時間複雜度：演算法運行時需要的總步數，通常是問題規模的函數。
- 空間複雜度：演算法執行時所占用的存儲空間，通常是問題規模的函數
確定演算法的計算量:
- 合理地選擇一種或幾種操作作為“標準操作”，無特殊說明，預設以賦值語句作為標準操作；確定每個演算法共執行多少次標準操作，並將此次數規定為該演算法的計算量。
- 演算法的最壞情況時間複雜度：以演算法在所有輸入下的計算量的最大值作為演算法的計算量。
- 演算法的平均情況時間複雜度：以演算法在所有輸入下的計算量的加權平均值作為演算法的計算量。
- 最壞情況時間複雜度和平均情況時間複雜度統稱為時間複雜度
================時間複雜度================
運行該代碼需要1秒 ，時間複雜度記作O(1)
運行該代碼需要n*1秒 時間複雜度記作O(n)
運行該代碼需要n*n*1秒 時間複雜度記作O(n*n);
================空間複雜度===============
空間複雜度:是對一個演算法在運行過程中臨時占用存儲空間大小的量度;估算演算法空間複雜度時，一般只分析輔助變數所占用的空間。
一個演算法在執行期間所需要的存儲空間量包括以下部分：
- 程式代碼所占用的空間；
- 輸入數據所占用的空間；
- 輔助變數所占用的空間；
