嵌入式軟件數據結構的特點
時間：2023-09-07 來源：華清遠見
一、數據結構內容概述
數據結構是計算機存儲、組織數據的方式。數據結構是指相互之間存在一種或多種特定關系的數據元素的集合。數據結構反映數據的內部構成，即數據由哪部分構成，以什么方式構成，以及數據元素之間呈現的結構。數據結構常用的邏輯結構有四種：集合結構(數據元素之間沒有關系)、線性結構(數據元素之間存在一對一的關系)、樹形結構(數據元素之間存在一對多的關系)、圖形形結構(數據元素之間存在多對多的關系)。數據結構常用的存儲結構：順序存儲(使用任意一段連續存儲空間存儲數據)、鏈式存儲(使用任意的空間存儲數據)、索引存儲(采用索引表和數據文件共同實現的索引查找方法)、散列存儲(簡稱為哈希表，借助于散列函數，以及數組形式創建的哈希表共同實現的查找算法)。
二、線性表的順序存儲
對與順序存儲來說，順序存儲是借助于數組實現的，使用下標查找十分迅速，但計算機內存有限，故數組的長度有限，數組初始化就需要聲明數組的長度。實際應用當中的數據往往十分龐大；無序數組的查找最壞情況需要遍歷整個數組；后來人們提出了二分查找，二分查找要求數組的構造一定有序，二分法查找解決了普通數組查找復雜度過高的問題。任何一種數組無法解決的問題就是插入、刪除操作比較復雜（插入、刪除需根據數組下標來操作），原因是因為順序表的插入和刪除需要移動大量元素，所耗費時間復雜度是O(n), 因此，在一個增刪查改比較頻繁的數據結構中，數組不會被優先考慮。所以順序存儲常用來實現按下標實現查找的修改操作。
2.1 順序表插入
線性表的插入運算是指在表的第i (1≤i≤n+1)個位置，插入一個新元素x，使長度為n的線性表變成長度為n+1的線性表，用順序表作為線性表的存儲結構時，由于結點的物理順序必須和結點的邏輯順序保持一致，因此我們必須將原表中位置n-1，n-2，…，i-1上的結點，依次后移到位置n，n-1，…，i上，空出第i-1個位置，然后在該位置上插入新結點x。當i=n+1時，是指在線性表的末尾插入結點，所以無需移動結點，直接將x插入表的末尾即可。最好的情況：當i=n+1時（插入尾元素），移動次數為0；最壞的情況：當i=1時（插入第一個元素），移動次數為n；平均情況：在位置i插入新元素x，需要將ai～an的元素均后移一次，移動次數為n-i+1。假設在等概率下pi（pi=1/(n+1)），移動元素的平均次數為：n/2,插入算法的主要時間花費在元素移動上，所以算法平均時間復雜度為O(n)。
2.2 順序表刪除
線性表的刪除運算是指從表中刪除第i(1<=i<=n)個元素，刪除后使原表長n的線性表(a1,a2…..ai-1.ai.ai+1,…an)變為n-1的線性表(a1,a2…..ai-1.ai+1,…an)，數據元素ai-1,ai+1之間邏輯關系發生變化。和插入運算類似，為了在存儲結構上反應這種邏輯結構上的變化，也必須移動元素的位置，當i=n，由于刪除的最后一個元素，不需要移動元素，一般情況下，若刪除第i個元素，將需要將第i+1至第n個元素依次向前移動一個位置到i,i+1…n-1上，平均時間復雜度是O(n)，刪除過程如下：
2.3 順序表按值查找
線性表安置查找是指在線性表中查找與給定值x相等的數據元素，可以從第一個元素a1一次和x比較，如果找到第一個和x相等的元素，則返回在線性表中的序號，表示查找成功；如果查邊整個線性表都沒有和x相等的元素，則返回0，表示查找失敗。
三、線性表的鏈式存儲
由于順序存儲在操作數據時不適用于插入和刪除，以及數組的局限只能適用于數據量較小的情況，那么為了解決這個問題，則使用鏈式存儲解決提前預估存儲空間，并且插入和刪除不需要移動大量元素，但是普通鏈表由于它的結構特點被證明根本不適合進行查找和修改數據。鏈表的操作形式有很多，比如單向鏈表、單向循環鏈表、雙向鏈表、雙向循環鏈表。常借助于約瑟夫環的思想實現循環播
