嵌入式系統軟體設計中的資料結構
第一章
散列存盤:依據資料元素的關鍵字直接計算出該元素的存盤位置，基本思想在于：以資料元素的關鍵字K為自變數，通過一個確定的函式關系（散列函式），計算出相應的函式值，把這個值作為資料元素的存盤地址，將資料元素存入該地址所指的存盤位置上，
演算法的特征：有窮性、確定性、可行性、有輸入、有輸出;
演算法的高效率體現在對于演算法的執行時間要盡可能的短，對于存盤空間的占用要盡可能的少，即做到既省時又省空間，
演算法的時間復雜度， \(T(n) = O(f(n))\)
一般來說，f(n)是和演算法執行次數增長率相同（理解為演算法執行次數運算式中最快上升的函式項）的關于n的函式，特例，交換兩變數值有三個陳述句：
temp = i; i = j; j = temp;
執行時間是一個與n無關的常數，其演算法的時間復雜度是常數階，則 \(T（n） = O(1)\)
演算法的空間復雜度
演算法的存盤空間指的是演算法執行程序中所需要的最大存盤空間，演算法執行程序中需要的存盤空間包括三個部分：輸入資料所占空間；程式本身所占空間（不同演算法之間不會有很大差別）；輔助變數所占空間和額外占用空間（重點分析）；定義演算法的空間復雜度為：\(S（n）= O(g(n))\) ，隨著問題的規模增大，演算法運行所需要的空間增長率和\(g(n)\)的增長率相同，
嵌入式系統比較流行的定義是，以應用為中心，以計算機技術為基礎，軟體硬體可裁剪，適應應用系統對功能、可靠性、成本、體積、功耗嚴格要求的專用計算機系統，高檔嵌入式系統CPU為32位以上，資訊處理量比較大，但是價格昂貴，低檔嵌入式系統為16位以下（主要是8位），在生產中用的比較多，適用于
- 資料規模較小、采用簡單資料結構（線性表）
- 采用RAM資源占用較少的演算法（可能導致演算法效率下降，能實作功能）
- 采用程式代碼簡單的演算法，可以減小ROM開銷
第二章 線性表 -- 最簡單、最常用的一種線性結構
線性表是\(n\)個資料元素的有限序列，記為(\(a_{1},a_{2},...,a_{n}\))，其基本運算包括：置空表、求長度、取節點、定位、插入、洗掉，
順序表
順序表是將線性表中的節點按照邏輯順序（邏輯順序和物理順序一致）依次存放在一組地址連續的存盤單元中，一般情況下，線性表中的所有節點的型別是相同的，即每個節點占用的空間是相同的，在編程之前，可事先分配一個足夠的連續記憶體空間\(max * L\)，其中，\(L\)是節點的大小，\(max\)是最大的節點數；例，用一維陣列及結構體來定義順序表
#define max 1024
typedef int datatype; //定義節點元素的資料型別
typedef struct
{
datatype data[max]; //第一個節點是data[0]
int last; //最后一個節點的下標
}sequencelist;
順序表的插入操作：(在第i個節點處插入x)
int insert(sequencelist *L, datatype x, int i)
{
int j;
if( L-> last >= max)
{
return(0); //空間溢位
}
else if( i < 1 || i > L -> last + 2 ) // 判斷i是不是合法
{
return(0); //插入位置非法
}
else
{
for (j = L->last; j >= i - 1; j++ ) // 第i個數在表中的下標為i-1
{
L -> data[j+1] = L -> data[j];
}
L -> data[i-1] = x;
L -> last = L -> last + 1;
}
return(1); //插入成功，回傳1
}
順序表的洗掉操作：（洗掉第i個節點）
int delate(sequencelist *L, int i)
{
int j;
if(L->last > max)
{
return(0); // 空間溢位
}
else if (i < 0 || i > L-> last + 1)
{
return(0);//非法洗掉
}
else
{
for( j = i; j <= last; j++ )
{
L->data[j-1] = L->data[j];
}
L->last = L->last - 1;
}
return(1);
}
順序表的優點在于能夠方便地存取表中的任意一個點，但是，除了其運算不方便，運算效率較低之外，由于其所占空間必須是連續空間，節點數并不固定，預先分配空間的時候難以確定合適的記憶體，容易造成記憶體不足或者記憶體浪費，
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/285463.html
標籤：嵌入式
上一篇：痞子衡嵌入式：串行NOR Flash的Continuous read模式下軟復位后i.MXRT無法啟動問題解決方案之SW Reset