1、程式=資料的存盤+資料的操作+可以被計算機執行的語言
2、資料：對客觀事物的符號表示，指所有能輸入到計算機中并被計算機程式處理的符號的總稱，
3、資料項：資料的不可分割的最小單位，
4、資料元素：資料的基本單位，一個資料元素可由若干個資料項組成，
5、資料物件：性質相同的資料元素的集合，資料的一個子集，
6、資料的邏輯結構：資料元素之間的邏輯關系，與資料的存盤無關，獨立于計算機，
線性結構（一對一）：線性表
非線性結構：集合、樹形結構（一對多）、圖形結構/網狀結構（多對多）
7、資料的物理結構/存盤結構：資料結構在計算機中的表示/映象，
1）、順序映象：借助元素在存盤器中的相對位置來表示資料元素之間的邏輯關系，對應于順序存盤結構，
2）、非順序映象：借助指示元素存盤地址的指標表示資料元素之間的邏輯關系，對應于鏈式存盤結構，
3）、存盤結構主要有四種：
順序存盤：邏輯上相鄰物理上也相鄰
優點：隨機存取
缺點：只能使用相鄰的一整塊存盤單元，
鏈式存盤：借助指示元素存盤地址的指標表示資料元素之間的邏輯關系
優點：能夠充分利用存盤單元
缺點：因存盤指標而占用額外的存盤空間，只能實作順序存取
索引存盤：附加索引表
優點：檢索速度快
缺點：附加索引表占用較多存盤空間
散列存盤/Hash存盤：根據元素的關鍵字直接計算出元素的存盤位置
8、資料結構：
1）、狹義：
資料結構是專門研究資料存盤的問題
資料存盤包含兩方面：個體存盤+個體關系存盤
廣義：
資料結構既包含資料的存盤也包含資料的操作
對存盤資料的操作就是演算法
2）、形式定義---二元組，Data_structure=(D,S)，D---資料元素的有限集，S---D上關系的有限集，
3）、資料結構=個體+個體的關系，
9、演算法： 解題的方法和步驟
1）、狹義：
演算法是和資料的存盤方式密切相關
廣義：
演算法和資料的存盤方式無關
這就是泛型的思想
2）、衡量演算法的標準
時間復雜度T(N)=O(f(n))
大概程式要執行的次數，而非執行時間
分析時間復雜度時的規則
加法規則：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))
常見的漸進時間復雜度
O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)
空間復雜度S(n)=O(g(n))
演算法執行程序中大概所占用的最大記憶體
演算法原地作業是指演算法所需的輔助空間為常量，
難易程度
健壯性
3）、演算法=對存盤資料的操作，
4）、重要特性：有窮性、確定性、可行性、輸入、輸出
5）、目標/要求：正確性、可讀性、健壯性、效率與低存盤量需求
10、資料的線性存盤結構有幾種
1）、連續存盤【陣列】
優點：存取速度快
缺點：插入洗掉元素很慢，空間通常是有限的，事先知道陣列的長度，需要大塊連續的記憶體塊
2）、離散存盤【鏈表】
優點：空間沒有限制，插入洗掉元素很快
缺點：存取速度慢
11、資料型別：一個值的集合和定義在該值集上的一組操作的總稱，
原子類：值不可分解，eg.C中的基本型別、指標型別、空型別，
結構型別：值由若干成分按某種結構組成，可分解，eg.陣列，
抽象資料型別
12、抽象資料型別(ADT)：指一個數學模型以及定義在該模型上的一組操作，僅取決于它的一組邏輯特性，
按“值”的不同特性分類：
原子型別：變數的值不可分解，
結構型別：固定聚合型別：變數的值由確定數且成分按某種結構組成，
可變聚合型別：變數的值的成分數目不確定，
三元組表示(D,S,P)，D---資料物件，S---D上的關系集，P---對D的基本操作的集合，
13、多型資料型別：值的成分不確定的資料型別，從ADT的角度看，具有相同的資料抽象特性，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/60087.html
標籤：其他
上一篇：動態規劃 - 數字三角形
下一篇：【題解】穿越七色虹