嵌入式學習筆記：數據結構與算法知識點總結
時間：2018-09-11 來源：未知
下面是我在課堂上總結的數據結構與運算的知識點，不懂的快看看
一、數據結構：研究數據(數據元素)之間的關系。(C研究數值型數據之間的簡單運算， 數據結構 還研究非數值型之間的運算)
1.邏輯結構(關系)：集合、線性關系、樹形關系、圖狀關系(線性和非線性關系)
2.物理結構(物理關系)：邏輯結構在計算機內存中具體實現的方法，有順序、鏈式、 索引、散列等存儲方法
3.數據運算：對數據進行的操作，增、刪、查、改、排序。
數據即信息的載體。
數據元素是數據的基本單位(又稱記錄，Record),由若干個基本項(or字段、域屬性)組成
數據類型是對數據元素取值范圍與運算的限定
相關術語概念：
數據Date 數據類型Date Type 數據元素Date Element
數據結構Date Structure 物理結構(存儲結構)Physical Structure
順序存儲Sequential Storage 鏈式存儲Linked Storage
索引存儲Indexed Storage 散列存儲Hash Storage
形式化語言描述(數學表達式)：
DS=(D,R)D數據元素的集合，R D上關系的集合
根據數據元素間的關系的基本特性有四種基本數據結構：
集合——數據元素間除“同屬于一個集合”外，無其他關系
線性結構——一個對一個，如線性表、棧、隊列
樹形結構——一個對多個，如樹
圖狀結構——多個對多個，如圖(圖是樹的拓展，可有樹構成)
算法Algorithm一個又窮規則(or語句、指令)的有序集合(對程序的優化，易閱讀、調試、維護)
特性：有窮性、確定性、可行性、輸入(0-n)、輸出(1-n)
程序 = 算法 + 數據結構
算法與程序的區別：
1. 算法與計算機無關，程序依賴于具體的計算機語言
2. 算法重點是在解決問題的思路上
算法分析(好壞)：時間復雜度T(n) 空間復雜度D(n)(不考慮,犧牲來成全時間)Time/Space Complexity
語句的頻度：可執行語句程序中重復執行的次數。某語句執行一次耗時t，執行次數f，則該語句總耗時t*f。
量級T(n)=O(n3) 取次數最高的項并去掉系數，作為時間復雜度 。
↑上午 概念
↓下午 線性表 的邏輯和存儲結構、相關算法的實現以及線性表的應用舉例。
線性表Linear List
首先創建表，再插入表，再增刪改查，銷毀。
創建：申請一個結構體
結構體聲明寫在頭文件里面
用gedit編輯.h和.c文件
方便的查找，在挨著表的末尾空間在申請一個空間用來存放表的有效個數or最后一個元素下標。
創建表 ：...待寫
插入數據：1.首先判斷表是否為滿。2.判斷插入的位置是否有效。3.從后往上移動數據元素。 4.插入元素。5.尾指針last+1
刪除數據：1.首先判斷表是否為空。2.判斷刪除的位置是否有效。3.刪除后從前往后移動元 素。4.尾指針last-1。5移動后，之前的最后一個數據，直接忽視不用了，但是 還在。
