一、引言
1、資料結構（Data structure） 是計算機組織資料和存盤資料的方式； 是指一組相互之間存在一種或多種特定關系的資料的組織方式和它們在計算機內的存盤方式，以及定義在該組資料上的一組操作，
2、計算機解決問題的步驟
建立數學模型 -》設計演算法 -》編程實作演算法
3、資料的邏輯結構 是指資料及資料的組織方式，
4、物理結構（Physical Structure）/存盤結構 指資料結構在機內的表示，資料的邏輯結構在計算機中的實作，
5、資料結構、演算法和程式的關系 演算法+資料結構=程式 (1976年瑞士計算機科學家尼克勞斯·維爾特[Niklaus Wirth]提出)
二、基本概念和術語
資料（Data)：所有能被計算機處理的符號的集合；實際問題中的資料稱為原始資料
資料元素（Data Element）：是資料這個集合中的一個個體即資料的基本單位，
資料項（Data Item）：資料元素常常還可分為若干個資料項，資料項是資料具有意義的最小單位；在資料庫中，資料項又稱為欄位/域，它是資料的不可分割的最小標識單位
邏輯結構的種類
- 集合：任意兩個結點之間都沒有鄰接關系，組織形式松散，
- 線性結構：結點按邏輯關系依次排列形成一條“鏈”，結點之間一個一個依次相鄰接，
- 樹形結構：具有分支、層次特性，上層的結點可以和下層多個結點相鄰接，但下層結點只能和上層的一個結點相鄰接，
- 圖結構：最復雜，任何兩個結點都可以相鄰接
資料的存盤結構： 資料在計算機內的表示形式，
存盤結構的主要部分：
- 存盤結點（每個存盤結點存放一個資料元素） 資料元素之間關聯方式的表示，
- 資料結構的存盤=資料元素的存盤+元素邏輯關系的存盤，
4種存盤結構
- 順序存盤方式
- 鏈式存盤方式
- 索引存盤方式
- 散列存盤方式
***********************順序結構************************
- 順序存盤方式：借助資料元素的相對存盤位置來表示資料的邏輯結構；
- 線性表的順序存盤方法：將表中的結點一次存放在計算機記憶體中一組連續的存盤單元中，
- 順序的方法: 將元素存盤到一片連續的存盤區，
特點： 預先分配好長度，需要預估存盤資料需要的存盤量； 插入和洗掉需要移動其他元素； 存取快捷，是隨機存取結構，
************************鏈式結構************************
- 鏈式存盤方式：借助資料元素地址的指標表示資料的邏輯結構
- 這種結構是給結點附加一個指標欄位，指出其后繼節點的位置， 即存放結點的存盤單元分為兩部分: 資料項，指標項
特點： 動態分配，不需要預先確定記憶體分配； 插入和洗掉不需要移動其他元素； 非隨機存取結構
************************索引存盤方式：*************************
索引存盤方式：借助索引表中的索引指示各存盤節點的存盤位置，
***********************散列存盤方式：****************************
散列存盤方式：用散列函式指示各節點的存盤位置，
運算： 指在某種邏輯結構上施加的操作，即對邏輯結構的加工， 加工型運算：其操作改變原邏輯結構的值；如：結點個數，結點內容等， 參考型運算：其操作不改變原邏輯結構的值，基本運算： 建立 查找 讀取 插入 洗掉
三、 演算法及描述
演算法： 演算法規定了求解給定型別問題所需的所有“處理步驟”及執行順序，使給定型別問題能在有限時間內被機械的求解，
演算法必須使用某種語言描述：
- 程式
- 介于自然語言和程式設計語言的偽代碼
- 非形式演算法（自然語言）
- 框圖(N-S圖)
一個演算法是對特定問題求解步驟的一種描述，它是指令的有窮序列，
演算法具有以下特性：
- 有窮性: 一個演算法總是在執行有窮步后結束，
- 確定性: 演算法的每一步都必須是明確地定義的，
可行性: 演算法中的每一步都是可以通過已經實作的操作來完成的，
輸入: 一個演算法有零個或者多個輸入，這些輸入取自于特定的物件集合，
輸出：一個演算法有一個或者多個輸出，它們是與輸入有特定關系的量
四、 演算法分析
演算法的設計應滿足：
- 正確性：對于合法的輸入產生符合要求的輸出，
- 易讀性：演算法應該易讀、便于交流， 這也是保證演算法正確性的前提；添加注釋也是一種增加可讀性的辦法，
- 健壯性：當輸入非法資料時， 演算法還能做出適當的反應而不會崩潰， 如輸出錯誤資訊；演算法中應該考慮適當的錯誤處理，
- 時空性：指演算法的時間復雜度和空間復雜度，演算法分析主要分析演算法的時間復雜度和空間復雜度，目的是提高演算法的效率
選擇最優演算法的2個度量：
- 時間復雜度：演算法運行時需要的總步數，通常是問題規模的函式，
- 空間復雜度：演算法執行時所占用的存盤空間，通常是問題規模的函式，
確定演算法的計算量：
- 合理地選擇一種或幾種操作作為“標準操作”， 無特殊說明，默認以賦值陳述句作為標準操作，
- 確定每個演算法共執行多少次標準操作，并將此次數規定為該演算法的計算量，
- 演算法的最壞情況時間復雜度：以演算法在所有輸入下的計算量的最大值作為演算法的計算量，
- 演算法的平均情況時間復雜度：以演算法在所有輸入下的計算量的加權平均值作為演算法的計算量，
- 最壞情況時間復雜度和平均情況時間復雜度統稱為時間復雜度，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/44312.html
標籤：架構設計
下一篇：Springboot Activiti6 作業流 集成代碼生成器 shiro 權限 vue.js html 跨域 前后分離