嵌入式程序員要學習的 經典數據結構
時間：2019-07-30 來源：創客學院，韓老師
1.什么是數據結構？
如果我們現在要整理圖書，有一堆書， 怎么整理呢？最簡單一種一個挨著一個放；或者給圖書分類，按照大分類再細分類整合；或者直接細分拆成很多類，每一類之間肯定會有很多的關系；但是有沒有想過這個書是要放在哪里的？要在什么環境下保存？這就需要給每種整理方法換個角度考慮，是都放在一個書架的一層呢，還是放在不同的書架隔層，又或者是放在圖書館里不同的書架上；這個提到的整理圖書討論的東西，就是數據結構將要研究的東西。回歸到咱們程序員，就需要把上面研究的整理方法和存放形式可以通過計算機記錄下來，因為畢竟我們整理圖書的目的是管理和使用圖書方便。所以歸根結底我們要把這種抽象的數據和數據間的關系反應給計算，用編程語言實現。那么我們可以知道：數據結構研究數據之間的關系！
2.為什么學習數據結構？
詳細研究數據間的管理機制，形成數據結構模型，遇到實際情況可以借鑒使用，這樣我們可以更快的應用到程序編程，設計和編寫出更優秀的軟件，且本質上是提高工程質量！
3.數據結構學什么？
大家應該知道一個經典的思想：程序 = 數據結構 + 算法；
那咱們來談談之間的關系，和嵌入式程序員要注意的點。咱們是嵌入式程序員，要注重的是嵌入式編程思維，也就是要注重實踐性。所以學習的重點是數據結構的管理數據思想；算法是算法工程師去深入學習的，是研究性質的方法論，咱們很少遇到復雜的算法應用。咱們因此學習一些經典的數據結構中涉及的算法就已經夠用了，以后有興趣可以繼續專門深入了解算法這門學科；注意目前階段的學習中心在哪里。
數據結構研究三個角度：邏輯關系、存儲關系、運算關系。
以下圖示表明了三大角度在數據結構中的研究關系：
邏輯關系是抽象的研究數據間關系，存儲關系就需要將這種關系對應到物理存儲，運算關系是在物理存儲后確定后需要研究的數據的應用操作；
4.幾個經典的線性結構：
(1)順序表
上圖為一個還沒有存儲有效數據的空表。存儲空間是數組，記錄有效數據最后更新位置的是整型last，整體表結構為一個結構體；
結構代碼模型如下：
#define MAXSIZE 10
typedef int datatype;
typedef int postype;
struct list{
datatype data[N];
postype last;
}；
(2)單向鏈表
上圖為有頭結點且不斷增加新數據結點的單向鏈表。存儲空間是一個結構體，結構體內需要有一個數據域和一個指針域，數據域存儲需要存儲的數據， 指針域要記錄下一個數據結點的首地址；
結構代碼模型如下：
typedef int datatype;
typedef struct node {
datatype data;
struct node * next;
}Linknode, *Linklist;
(3)雙向循環鏈表
上圖為有頭結點且有n個數據結點的雙向循環鏈表。存儲空間是一個結構體，結構體內需要有一個數據域和兩個指針域，數據域存儲需要存儲的數據， 第一個指針域要記錄前一個數據結點的首地址，第二個指針域要記錄后一個數據結點的首地址；
結構代碼模型如下：
typedef int datatype;
typedef struct node{
datatype data;
struct node *prior;
struct node *next;
}DLinkNode, * DLinkList;
(4)線性結構的應用結構：
①棧--先進后出，后進先出
1)順序棧：
上圖為有n個數據存儲空間的順序棧。結構體是一個棧結構，結構體內需要有一個數據域和兩個整型標記，數據域是數組存儲需要存儲的數據， 第一個標記top要記錄最后一個入棧數據的數組下標，第二個標記len要記錄整個存儲空間的大小，方便知曉棧的存儲能力；
結構代碼模型如下：
typedef int datatype;
typedef struct node{
datatype *data;
int maxlen;
int top;
}SeqStack，*SeqStack_t;
2)鏈式棧
上圖為有頭結點和n個數據存儲空間的鏈式棧。結構體是一個數據結點，結構體內需要有一個數據域和一個指針域，數據域是數組存儲需要存儲的數據， 指針域要記錄前一個入棧結點的首地址，棧頂為鏈表頭結點后第一個數據結點；
結構代碼模型如下：
typedef int datatype;
typedef struct node{
datatype data;
struct lstacknode * next;
}LinkStacknode, *LinkStacknode_t;
②隊列--先進先出，后進后出
1)順序隊列
上圖為有n個數據存儲空間的順序隊列，需要注意的是這只是個理想模型，實際使用需要舍棄一個存儲空間，用于判斷空表滿表，只使用n-1個存儲空間。結構體是一個順序隊列，結構體內需要有數組作為數據存儲空間， 兩個標記， 第一個標記記錄隊頭數據所在位置的前一個位置的數組下標，第二個標記記錄隊尾數據所在位置的數組下標；
結構代碼模型如下：
#define N 10
typedef int datatype;
typedef struct seqqueue{
datatype data[N];
int front, rear;
}SeqQueue, *SeqQueue_t;
2)鏈式隊列
上圖為有頭結點和n個數據存儲空間的鏈式隊列。鏈式隊列有兩個結構體模型，數據結點是第一個結構體，這個結構體內需要有一個數據域和一個指針域，數據域是數組存儲需要存儲的數據， 指針域要記錄后一個入棧隊結點的首地址；第二個結構體是隊列模型，結構體內需要兩個指針域，指針類型為第一個結構體類型的指針，一個指針front記錄隊列的隊頭結點首地址，隊頭為鏈表頭結點后第一個數據結點，另一個指針rear記錄隊列的隊尾結點首地址，隊尾為鏈表最后一個數據結點。
結構代碼模型如下：
typedef int datatype;
typedef struct node{
datatype data;
struct linkqueuenode *next;
}Queuenode, *Queuenode_t;
typedef struct linkqueue{
linkqueue_pnode front,rear;
}LinkQueue, *LinkQueue_t;
在數據結構中還有其他非線性的數據模型，篇幅有限，這里就不列舉了，下次再聊。上面的結構應用很廣泛哦，感興趣的話一定要去研究實踐！
