~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
開發工具與關鍵技術：資料結構
作者：李宥良
撰寫時間：2020年5月8日
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
1.資料、資料元素、資料項和資料型別資料：所有能被輸入到計算機中，且能被計算機處理的符號的集合。是計算機操作的物件的總稱。
資料元素：資料（集合）中的一個“個體”，資料及結構中討論的基本單位
資料項：資料的不可分割的最小單位。一個資料元素可由若干個資料項組成。
資料型別：在一種程式設計語言中，變數所具有的資料種類。整型、浮點型、字符型等等
2.資料結構——邏輯結構和存盤結構
邏輯結構：資料之間的相互關系。集合 ：結構中的資料元素除了同屬于一種型別外，別無其它關系。
線性結構 ：資料元素之間一對一的關系
樹形結構 ：資料元素之間一對多的關系
圖狀結構或網狀結構 ：結構中的資料元素之間存在多對多的關系
在資料結構中,從邏輯上可以將其分為線性結構和非線性結構物理結構/存盤結構：資料在計算機中的表示。
物理結構是描述資料具體在記憶體中的存盤（如：順序結構、鏈式結構、索引結構、哈希結構）等資料結構的基本操作的設定的最重要的準則是：實作應用程式與存盤結構的獨立。實作應用程式是“邏輯結構”，存盤的是“物理結構”。邏輯結構主要是對該結構操作的設定，物理結構是描述資料具體在記憶體中的存盤（如：順序結構、鏈式結構、索引結構、希哈結構）等。
3.資料型別和抽象資料型別
資料型別：在一種程式設計語言中，變數所具有的資料種類。整型、浮點型、字符型等抽象資料型別：一個數學模型以及定義在該模型上的一組操作。
抽象資料型別可以使我們更容易描述現實世界。例：用線性表描述學生成績表，用樹或圖描述遺傳關系。
關鍵：使用它的人可以只關心它的邏輯特征，不需要了解它的存盤方式。定義它的人同樣不必要關心它如何存盤。
例：線性表這樣的抽象資料型別，其數學模型是：資料元素的集合，該集合內的元素有這樣的關系：除第一個和最后一個外，每個元素有唯一的前趨和唯一的后繼。可以有這樣一些操作：插入一個元素、洗掉一個元素等。
4.抽象資料型別的表示與實作
詳細定義格式：ADT 抽象資料型別名{資料物件：<資料物件的定義>資料關系：<資料關系的定義>基本操作：<基本操作的定義>}ADT 抽象資料型別名
演算法與演算法分析：
1、演算法的定義及特性演算法五個特性： 有窮性、確定性、可行性、輸入、輸出演算法設計要求：正確性、可讀性、健壯性、高效率與低存盤量需求。(好的演算法)
2、評價演算法優劣的基本標準演算法的描述有偽程式、流程圖、N-S結構圖等。E-R圖是物體聯系模型，不是程式的描述方式。設計演算法在執行時間時需要考慮：演算法選用的規模、問題的規模
3、演算法的時間復雜度時間復雜度：演算法的執行時間與原操作執行次數之和成正比。時間復雜度有小到大：O(1)、O(logn)、O(n)、O(nlogn)、O(n2)、O(n3)。冪次時間復雜度有小到大O(2n)、O(n!)、O(nn)
4、演算法的空間復雜度空間復雜度：若輸入資料所占空間只取決于問題本身，和演算法無關，則只需要分析除輸入和程式之外的輔助變數所占額外空間。（1）一個程式不一定滿足有窮性。例作業系統，只要整個系統不遭破壞，它將永遠不會停止，即使沒有作業需要處理，它仍處于動態等待中。因此，作業系統不是一個演算法。（2）程式中的指令必須是機器可執行的，而演算法中的指令則無此限制。演算法代表了對問題的解，而程式則是演算法在計算機上的特定的實作。（3）一個演算法若用程式設計語言來描述，則它就是一個程式。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/57208.html
標籤：非技術區