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