4.1.記憶體這個大話題

4.1.1/2.程式運作為什麼需要記憶體

4.1.1.1、計算機程式運作的目的

計算機為什麼需要程式設計？程式設計已經編了很多年，已經寫了很多程式，為什麼還需要另外寫程式？計算機有這個新的程式到底為了什麼？

程式的目的是為了去運作，程式運作是為了得到一定的結果。計算機就是用來計算的，所有的計算機程式其實都是在做計算。計算就是在計算資料。是以計算機程式中很重要的部分就是資料。

計算機程式 = 代碼 + 資料 計算機程式運作完得到一個結果，就是說

代碼 + 資料 (經過運作後) = 結果

從宏觀上來了解，代碼就是動作，就是加工資料的動作；資料就是數字，就是被代碼所加工的東西。

那麼可以得出結論：程式運作的目的不外乎2個：結果、過程

用函數來類比：函數的形參就是待加工的資料（函數内還需要一些臨時資料，就是局部變量），函數本體就是代碼，函數的傳回值就是結果，函數體的執行過程就是過程。

int add(int a, int b)
	{
		return a + b;
	}			// 這個函數的執行就是為了得到結果
	void add(int a, int b)
	{
		int c;
		c = a + b;
		printf("c = %d.\n", c);
	}			// 這個函數的執行重在過程（重在過程中的printf），傳回值不需要
	int add(int a, int b)
	{
		int c;
		c = a + b;
		printf("c = %d.\n", c);
		return c;
	}			// 這個函數又重結果又重過程

           

4.1.1.2、計算機程式運作過程

計算機程式的運作過程，其實就是程式中很多個函數相繼運作的過程。程式是由很多個函數組成的，程式的本質就是函數，函數的本質是加工資料的動作。

4.1.1.3、馮諾依曼結構和哈佛結構

馮諾依曼結構是：資料和代碼放在一起。

哈佛結構是：資料和代碼分開存在。

什麼是代碼：函數

什麼是資料：全局變量、局部變量

在S5PV210中運作的linux系統上，運作應用程式時：這時候所有的應用程式的代碼和資料都在DRAM，是以這種結構就是馮諾依曼結構；在單片機中，我們把程式代碼燒寫到Flash（NorFlash）中，然後程式在Flash中原地運作，程式中所涉及到的資料（全局變量、局部變量）不能放在Flash中，必須放在RAM（SRAM）中。這種就叫哈佛結構。

4.1.1.4、動态記憶體DRAM和靜态記憶體SRAM

DRAM是動态記憶體，SRAM是靜态記憶體。詳細細節自己baidu

4.1.1.5、總結：為什麼需要記憶體呢

記憶體是用來存儲可變資料的，資料在程式中表現為全局變量、局部變量等（在gcc中，其實常量也是存儲在記憶體中的）（大部分單片機中，常量是存儲在flash中的，也就是在代碼段），對我們寫程式來說非常重要，對程式運作更是本質相關。

是以記憶體對程式來說幾乎是本質需求。越簡單的程式需要越少的記憶體，而越龐大越複雜的程式需要更多的記憶體。記憶體管理是我們寫程式時很重要的話題。我們以前學過的了解過的很多程式設計的關鍵其實都是為了記憶體，譬如說資料結構（資料結構是研究資料如何組織的，資料是放在記憶體中的）和算法（算法是為了用更優秀更有效的方法來加工資料，既然跟資料有關就離不開記憶體）。

4.1.1.6、深入思考：如何管理記憶體（無OS時，有OS時）

對于計算機來說，記憶體容量越大則可能性越大，是以大家都希望自己的電腦記憶體更大。我們寫程式時如何管理記憶體就成了很大的問題。如果管理不善，可能會造成程式運作消耗過多的記憶體，這樣遲早記憶體都被你這個程式吃光了，當沒有記憶體可用時程式就會崩潰。是以記憶體對程式來說是一種資源，是以管理記憶體對程式來說是一個重要技術和話題。

先從作業系統角度講：作業系統掌握所有的硬體記憶體，因為記憶體很大，是以作業系統把記憶體分成1個1個的頁面（其實就是一塊，一般是4KB），然後以頁面為機關來管理。頁面内用更細小的方式來以位元組為機關管理。作業系統記憶體管理的原理非常麻煩、非常複雜、非常不人性化。那麼對我們這些使用作業系統的人來說，其實不需要了解這些細節。作業系統給我們提供了記憶體管理的一些接口，我們隻需要用API即可管理記憶體。

譬如在C語言中使用malloc free這些接口來管理記憶體。

沒有作業系統時：在沒有作業系統（其實就是裸機程式）中，程式需要直接操作記憶體，程式設計者需要自己計算記憶體的使用和安排。如果程式設計者不小心把記憶體用錯了，錯誤結果需要自己承擔。

再從語言角度來講：不同的語言提供了不同的操作記憶體的接口。

譬如彙編：根本沒有任何記憶體管理，記憶體管理全靠程式員自己，彙編中操作記憶體時直接使用記憶體位址（譬如0xd0020010），非常麻煩；

譬如C語言：C語言中編譯器幫我們管理直接記憶體位址，我們都是通過編譯器提供的變量名等來通路記憶體的，作業系統下如果需要大塊記憶體，可以通過API（malloc free）來通路系統記憶體。裸機程式中需要大塊的記憶體需要自己來定義數組等來解決。

譬如C++語言：C++語言對記憶體的使用進一步封裝。我們可以用new來建立對象（其實就是為對象配置設定記憶體），然後使用完了用delete來删除對象（其實就是釋放記憶體）。是以C++語言對記憶體的管理比C要進階一些，容易一些。但是C++中記憶體的管理還是靠程式員自己來做。如果程式員new了一個對象，但是用完了忘記delete就會造成這個對象占用的記憶體不能釋放，這就是記憶體洩漏。

Java/C#等語言：這些語言不直接操作記憶體，而是通過虛拟機來操作記憶體。這樣虛拟機作為我們程式員的代理，來幫我們處理記憶體的釋放工作。如果我的程式申請了記憶體，使用完成後忘記釋放，則虛拟機會幫我釋放掉這些記憶體。聽起來似乎C# java等語言比C/C++有優勢，但是其實他這個虛拟機回收記憶體是需要付出一定代價的，是以說語言沒有好壞，隻有适應不适應。當我們程式對性能非常在乎的時候（譬如作業系統核心）就會用C/C++語言；當我們對開發程式的速度非常在乎的時候，就會用Java/C#等語言。

4.1.3.位、位元組、半字、字的概念和記憶體位寬

4.1.3.1、什麼是記憶體？（硬體和邏輯兩個角度）

從硬體角度：記憶體實際上是電腦的一個配件（一般叫記憶體條）。根據不同的硬體實作原理還可以把記憶體分成SRAM和DRAM（DRAM又有好多代，譬如最早的SDRAM，後來的DDR1、DDR2·····、LPDDR）

從邏輯角度：記憶體是這樣一種東西，它可以随機通路（随機通路的意思是隻要給一個位址，就可以通路這個記憶體位址）、并且可以讀寫（當然了邏輯上也可以限制其為隻讀或者隻寫）；記憶體在程式設計中天然是用來存放變量的（就是因為有了記憶體，是以C語言才能定義變量，C語言中的一個變量實際就對應記憶體中的一個單元）。

4.1.3.2、記憶體的邏輯抽象圖（記憶體的程式設計模型）

從邏輯角度來講，記憶體實際上是由無限多個記憶體單元格組成的，每個單元格有一個固定的位址叫記憶體位址，這個記憶體位址和這個記憶體單元格唯一對應且永久綁定。

以大樓來類比記憶體是最合适的。邏輯上的記憶體就好象是一棟無限大的大樓，記憶體的單元格就好象大樓中的一個個小房間。每個記憶體單元格的位址就好象每個小房間的房間号。記憶體中存儲的内容就好象住在房間中的人一樣。

邏輯上來說，記憶體可以有無限大（因為數學上編号永遠可以增加，無盡頭）。但是現實中實際的記憶體大小是有限制的，譬如32位的系統（32位系統指的是32位資料線，但是一般位址線也是32位，這個位址線32位決定了記憶體位址隻能有32位二進制，是以邏輯上的大小為2的32次方）記憶體限制就為4G。實際上32位的系統中可用的記憶體是小于等于4G的（譬如我32位CPU裝32位windows，但實際電腦隻有512M記憶體）

4.1.3.3、位和位元組

記憶體單元的大小機關有4個：位（1bit） 位元組（8bit） 半字（一般是16bit）  字（一般是32bit）

在所有的計算機、所有的機器中（不管是32位系統還是16位系統還是以後的64位系統），位永遠都是1bit，位元組永遠都是8bit。

4.1.3.4、字和半字

曆史上曾經出現過16位系統、32位系統、64位系統三種，而且作業系統還有windows、linux、iOS等很多，是以很多的概念在曆史上曾經被混亂的定義過。

建議大家對字、半字、雙字這些概念不要詳細區分，隻要知道這些機關具體有多少位是依賴于平台的。實際工作中在每種平台上先去搞清楚這個平台的定義（字是多少位，半字永遠是字的一半，雙字永遠是字的2倍大小）。

程式設計時一般根本用不到字這個概念，那我們區分這個概念主要是因為有些文檔中會用到這些概念，如果不加差別可能會造成你對程式的誤解。

在linux+ARM這個軟硬體平台上（我們嵌入式核心課的所有課程中），字是32位的。

4.1.3.5、記憶體位寬（硬體和邏輯兩個角度）

從硬體角度講：硬體記憶體的實作本身是有寬度的，也就是說有些記憶體條就是8位的，而有些就是16位的。那麼需要強調的是記憶體晶片之間是可以并聯的，通過并聯後即使8位的記憶體晶片也可以做出來16位或32位的硬體記憶體。

從邏輯角度講：記憶體位寬在邏輯上是任意的，甚至邏輯上存在記憶體位寬是24位的記憶體（但是實際上這種硬體是買不到的，也沒有實際意義）。從邏輯角度來講不管記憶體位寬是多少，我就直接操作即可，對我的操作不構成影響。但是因為你的操作不是純邏輯而是需要硬體去執行的，是以不能為所欲為，是以我們實際的很多操作都是受限于硬體的特性的。譬如24位的記憶體邏輯上和32位的記憶體沒有任何差別，但實際硬體都是32位的，都要按照32位硬體的特性和限制來幹活。

4.1.4.記憶體編址和尋址、記憶體對齊

4.1.4.1、記憶體編址方法

記憶體在邏輯上就是一個一個的格子，這些格子可以用來裝東西（裡面裝的東西就是記憶體中存儲的數），每個格子有一個編号，這個編号就是記憶體位址，這個記憶體位址（一個數字）和這個格子的空間（實質是一個空間）是一一對應且永久綁定的。這就是記憶體的編址方法。

在程式運作時，計算機中CPU實際隻認識記憶體位址，而不關心這個位址所代表的空間在哪裡，怎麼分布這些實體問題。因為硬體設計保證了按照這個位址就一定能找到這個格子，是以說記憶體單元的2個概念：位址和空間是記憶體單元的兩個方面。

4.1.4.2、關鍵：記憶體編址是以位元組為機關的

我随便給一個數字（譬如說7），然後說這個數字是一個記憶體位址，然後問你這個記憶體位址對應的空間多大？這個大小是固定式，就是一個位元組（8bit）。

如果把記憶體比喻位一棟大樓，那麼這個樓裡面的一個一個房間就是一個一個記憶體格子，這個格子的大小是固定的8bit，就好象這個大樓裡面所有的房間戶型是一樣的。

4.1.4.3、記憶體和資料類型的關系

C語言中的基本資料類型有：char short int long float double 

int 整形（整數類型，這個整就展現在它和CPU本身的資料位寬是一樣的）譬如32位的CPU，整形就是32位，int就是32位。

資料類型和記憶體的關系就在于：

資料類型是用來定義變量的，而這些變量需要存儲、運算在記憶體中。是以資料類型必須和記憶體相比對才能獲得最好的性能，否則可能不工作或者效率低下。

在32位系統中定義變量最好用int，因為這樣效率高。原因就在于32位的系統本身配合記憶體等也是32位，這樣的硬體配置天生适合定義32位的int類型變量，效率最高。也能定義8位的char類型變量或者16位的short類型變量，但是實際上通路效率不高。

在很多32位環境下，我們實際定義bool類型變量（實際隻需要1個bit就夠了）都是用int來實作bool的。也就是說我們定義一個bool b1;時，編譯器實際幫我們配置設定了32位的記憶體來存儲這個bool變量b1。編譯器這麼做實際上浪費了31位的記憶體，但是好處是效率高。

問題：實際程式設計時要以省記憶體為大還是要以運作效率為重？答案是不定的，看具體情況。很多年前記憶體很貴機器上記憶體都很少，那時候寫代碼以省記憶體為主。現在随着半導體技術的發展記憶體變得很便宜了，現在的機器都是高配，不在乎省一點記憶體，而效率和使用者體驗變成了關鍵。是以現在寫程式大部分都是以效率為重。

4.1.4.4、記憶體對齊

我們在C中int a;定義一個int類型變量，在記憶體中就必須配置設定4個位元組來存儲這個a。有這麼2種不同記憶體配置設定思路和政策：

第一種：0 1 2 3 對齊通路

第二種：1 2 3 4 或者 2 3 4 5 或者 3 4 5 6 非對齊通路

記憶體的對齊通路不是邏輯的問題，是硬體的問題。從硬體角度來說，32位的記憶體它 0 1 2 3四個單元本身邏輯上就有相關性，這4個位元組組合起來當作一個int硬體上就是合适的，效率就高。

對齊通路很配合硬體，是以效率很高；非對齊通路因為和硬體本身不搭配，是以效率不高。（因為相容性的問題，一般硬體也都提供非對齊通路，但是效率要低很多。）

4.1.4.5、從記憶體編址看數組的意義

4.1.5.C語言如何操作記憶體

4.1.5.1、C語言對記憶體位址的封裝（用變量名來通路記憶體、資料類型的含義、函數名的含義）

譬如在C語言中 int a; a = 5; a += 4; // a == 9;

結合記憶體來解析C語言語句的本質：

int a; // 編譯器幫我們申請了1個int類型的記憶體格子（長度是4位元組，位址是确定的，但是隻有編譯器知道，我們是不知道的，也不需要知道。），并且把符号a和這個格子綁定。

a = 5; // 編譯器發現我們要給a指派，就會把這個值5丢到符号a綁定的那個記憶體格子中。

a += 4; // 編譯器發現我們要給a加值，a += 4 等效于 a = a + 4;編譯器會先把a原來的值讀出來，然後給這個值加4，再把加之後的和寫入a裡面去。

C語言中資料類型的本質含義是：表示一個記憶體格子的長度和解析方法。

資料類型決定長度的含義：我們一個記憶體位址（0x30000000），本來這個位址隻代表1個位元組的長度，但是實際上我們可以通過給他一個類型(int)，讓他有了長度(4)，這樣這個代表記憶體位址的數字(0x30000000)就能表示從這個數字(0x30000000)開頭的連續的n(4)個位元組的記憶體格子了(0x30000000 + 0x30000001 + 0x30000002 + 0x30000003)。

資料類型決定解析方法的含義：譬如我有一個記憶體位址（0x30000000），我們可以通過給這個記憶體位址不同的類型來指定這個記憶體單元格子中二進制數的解析方法。譬如我 (int)0x30000000，含義就是(0x30000000 + 0x30000001 + 0x30000002 + 0x30000003)這4個位元組連起來共同存儲的是一個int型資料；那麼我(float)0x30000000，含義就是(0x30000000 + 0x30000001 + 0x30000002 + 0x30000003)這4個位元組連起來共同存儲的是一個float型資料；

之前講過一個很重要的概念：記憶體單元格子的編址機關是位元組。

(int *)0;

(float *)0;

(short)0;

(char)0;

int a; // int a;時編譯器會自動給a配置設定一個記憶體位址，譬如說是0x12345678

(int *)a; // 等價于(int *)0x12345678

(float *)a;

C語言中，函數就是一段代碼的封裝。函數名的實質就是這一段代碼的首位址。是以說函數名的本質也是一個記憶體位址。

4.1.5.2、用指針來間接通路記憶體

關于類型（不管是普通變量類型int float等，還是指針類型int *   float *等），隻要記住：

類型隻是對後面數字或者符号（代表的是記憶體位址）所表征的記憶體的一種長度規定和解析方法規定而已。

C語言中的指針，全名叫指針變量，指針變量其實很普通變量沒有任何差別。譬如int a和int *p其實沒有任何差別，a和p都代表一個記憶體位址（譬如是0x20000000），但是這個記憶體位址（0x20000000）的長度和解析方法不同。a是int型是以a的長度是4位元組，解析方法是按照int的規定來的；p是int *類型，是以長度是4位元組，解析方法是int *的規定來的（0x20000000開頭的連續4位元組中存儲了1個位址，這個位址所代表的記憶體單元中存放的是一個int類型的數）。

4.1.5.3、指針類型的含義

如上

4.1.5.4、用數組來管理記憶體

數組管理記憶體和變量其實沒有本質差別，隻是符号的解析方法不同。（普通變量、數組、指針變量其實都沒有本質差别，都是對記憶體位址的解析，隻是解析方法不一樣）。

int a; // 編譯器配置設定4位元組長度給a，并且把首位址和符号a綁定起來。

int b[10]; // 編譯器配置設定40個位元組長度給b，并且把首元素首位址和符号b綁定起來。

數組中第一個元素（a[0]）就稱為首元素；每一個元素類型都是int，是以長度都是4，其中第一個位元組的位址就稱為首位址；首元素a[0]的首位址就稱為首元素首位址。

4.1.6.記憶體管理之結構體

4.1.6.1、資料結構這門學問的意義

資料結構就是研究資料如何組織（在記憶體中排布），如何加工的學問。

4.1.6.2、最簡單的資料結構：數組

為什麼要有數組？因為程式中有好多個類型相同、意義相關的變量需要管理，這時候如果用單獨的變量來做程式看起來比較亂，用數組來管理會更好管理。

譬如 int ages[20];

4.1.6.3、數組的優勢和缺陷

優勢：數組比較簡單，通路用下标，可以随機通路。

缺陷：1 數組中所有元素類型必須相同；2 數組大小必須定義時給出，而且一旦确定不能再改。

4.1.6.4、結構體隆重登場

結構體發明出來就是為了解決數組的第一個缺陷：數組中所有元素類型必須相同

我們要管理3個學生的年齡（int類型），怎麼辦？

第一種解法：用數組 int ages[3];

第二種解法：用結構體

struct ages

{

int age1;

int age2;

int age3;

};

struct ages age;

分析總結：在這個示例中，數組要比結構體好。但是不能得出結論說數組就比結構體好，在包中元素類型不同時就隻能用結構體而不能用數組了。

struct people

{

int age; // 人的年齡

char name[20];// 人的姓名

int height; // 人的身高

};

因為people的各個元素類型不完全相同，是以必須用結構體，沒法用數組。

4.1.6.5、題外話：結構體内嵌指針實作面向對象

面向過程與面向對象。

總的來說：C語言是面向過程的，但是C語言寫出的linux系統是面向對象的。

非面向對象的語言，不一定不能實作面向對象的代碼。隻是說用面向對象的語言來實作面向對象要更加簡單一些、直覺一些、無腦一些。

用C++、Java等面向對象的語言來實作面向對象簡單一些，因為語言本身幫我們做了很多事情；但是用C來實作面向對象很麻煩，看起來也不容易了解，

這就是為什麼大多數人學過C語言卻看不懂linux核心代碼的原因。

struct s
{
int age; // 普通變量
void (*pFunc)(void);// 函數指針，指向 void func(void)這類的函數
};
           

使用這樣的結構體就可以實作面向對象。

這樣包含了函數指針的結構體就類似于面向對象中的class，結構體中的變量類似于class中的成員變量，結構體中的函數指針類似于class中的成員方法。

4.1.7、記憶體管理之棧（stack）

4.1.7.1、什麼是棧

棧是一種資料結構，C語言中使用棧來儲存局部變量。棧是被發明出來管理記憶體的。

1.4.7.2、棧管理記憶體的特點（小記憶體、自動化）

先進後出 FILO first in last out 棧

先進先出 FIFO   first in first out   隊列

棧的特點是入口即出口，隻有一個口，另一個口是堵死的。是以先進去的必須後出來。

隊列的特點是入口和出口都有，必須從入口進去，從出口出來，是以先進去的必須先出來，否則就堵住後面的。

1.4.7.3、棧的應用舉例：局部變量

C語言中的局部變量是用棧來實作的。

我們在C中定義一個局部變量時（int a），編譯器會在棧中配置設定一段空間（4位元組）給這個局部變量用（配置設定時棧頂指針會移動給出空間，給局部變量a用的意思就是，

将這4位元組的棧記憶體的記憶體位址和我們定義的局部變量名a給關聯起來），對應棧的操作是入棧。

注意：這裡棧指針的移動和記憶體配置設定是自動的（棧自己完成，不用我們寫代碼去操作）。

然後等我們函數退出的時候，局部變量要滅亡。對應棧的操作是彈棧（出棧）。出棧時也是棧頂指針移動将棧空間中與a關聯的那4個位元組空間釋放。這個動作也是自動的，也不用人寫代碼幹預。

棧的優點：棧管理記憶體，好處是友善，配置設定和最後回收都不用程式員操心，C語言自動完成。

分析一個細節：C語言中，定義局部變量時如果未初始化，則值是随機的，為什麼？

定義局部變量，其實就是在棧中通過移動棧指針來給程式提供一個記憶體空間和這個局部變量名綁定。因為這段記憶體空間在棧上，

而棧記憶體是反複使用的（髒的，上次用完沒清零的），是以說使用棧來實作的局部變量定義時如果不顯式初始化，值就是髒的。如果你顯式初始化怎麼樣？

C語言是通過一個小手段來實作局部變量的初始化的。

int a = 15; // 局部變量定義時初始化

C語言編譯器會自動把這行轉成：

int a; // 局部變量定義

a = 15; // 普通的指派語句

1.4.7.4、棧的限制（預定棧大小不靈活，怕溢出）

首先，棧是有大小的。是以棧記憶體大小不好設定。如果太小怕溢出，太大怕浪費記憶體。（這個缺點有點像數組）

其次，棧的溢出危害很大，一定要避免。是以我們在C語言中定義局部變量時不能定義太多或者太大

（譬如不能定義局部變量時 int a[10000]; 使用遞歸來解決問題時一定要注意遞歸收斂）

4.1.8、記憶體管理之堆

4.1.8.1、什麼是堆

堆（heap）是一種記憶體管理方式。記憶體管理對作業系統來說是一件非常複雜的事情，因為首先記憶體容量很大，其次記憶體需求在時間和大小塊上沒有規律（作業系統上運作着的幾十、幾百、幾千個程序随時都會申請或者釋放記憶體，申請或者釋放的記憶體塊大小随意）。

堆這種記憶體管理方式特點就是自由（随時申請、釋放；大小塊随意）。堆記憶體是作業系統劃歸給堆管理器（作業系統中的一段代碼，屬于作業系統的記憶體管理單元）來管理的，然後向使用者（使用者程序）提供API（malloc和free）來使用堆記憶體。

我們什麼時候使用堆記憶體？需要記憶體容量比較大時，需要反複使用及釋放時，很多資料結構（譬如連結清單）的實作都要使用堆記憶體。

4.1.8.2、堆管理記憶體的特點（大塊記憶體、手工配置設定&使用&釋放）

特點一：容量不限（正常使用的需求容量都能滿足）。

特點二：申請及釋放都需要手工進行，手工進行的含義就是需要程式員寫代碼明确進行申請malloc及釋放free。如果程式員申請記憶體并使用後未釋放，這段記憶體就丢失了（在堆管理器的記錄中，這段記憶體仍然屬于你這個程序，但是程序自己又以為這段記憶體已經不用了，再用的時候又會去申請新的記憶體塊，這就叫吃記憶體），稱為記憶體洩漏。在C/C++語言中，記憶體洩漏是最嚴重的程式bug，這也是别人認為Java/C#等語言比C/C++優秀的地方。

4.1.8.3、C語言操作堆記憶體的接口（malloc free）

堆記憶體釋放時最簡單，直接調用free釋放即可。 void free(void *ptr);

堆記憶體申請時，有3個可選擇的類似功能的函數：malloc, calloc, realloc

void *malloc(size_t size);

void *calloc(size_t nmemb, size_t size); // nmemb個單元，每個單元size位元組

void *realloc(void *ptr, size_t size); // 改變原來申請的空間的大小的

譬如要申請10個int元素的記憶體：

malloc(40); malloc(10*sizeof(int));

calloc(10, 4); calloc(10, sizeof(int));

數組定義時必須同時給出數組元素個數（數組大小），而且一旦定義再無法更改。在Java等進階語言中，有一些文法技巧可以更改數組大小，但其實這隻是一種障眼法。它的工作原理是：先重新建立一個新的數組大小為要更改後的數組，然後将原數組的所有元素複制進新的數組，然後釋放掉原數組，最後傳回新的數組給使用者；

堆記憶體申請時必須給定大小，然後一旦申請完成大小不變，如果要變隻能通過realloc接口。realloc的實作原理類似于上面說的Java中的可變大小的數組的方式。

4.1.8.4、堆的優勢和劣勢（管理大塊記憶體、靈活、容易記憶體洩漏）

優勢：靈活；

劣勢：需要程式員去處理各種細節，是以容易出錯，嚴重依賴于程式員的水準。

4.1.9、複雜資料結構

4.1.9.1、連結清單、哈希表、二叉樹、圖等

連結清單是最重要的，連結清單在linux核心中使用非常多，驅動、應用編寫很多時候都需要使用連結清單。是以對連結清單必須掌握，掌握到：會自己定義結構體來實作連結清單、會寫連結清單的節點插入（前插、後插）、節點删除、節點查找、節點周遊等。（至于像逆序這些很少用，掌握了前面那幾個這個也不難）。

哈希表不是很常用，一般不需要自己寫實作，而直接使用别人實作的哈希表比較多。對我們來說最重要的是要明白哈希表的原理、進而知道哈希表的特點，進而知道什麼時候該用哈希表，當看到别人用了哈希表的時候要明白别人為什麼要用哈希表、合适不合适？有沒有更好的選擇？

二叉樹、圖等。對于這些複雜資料結構，不要太當回事。這些複雜資料結構用到的機率很小（在嵌入式開發中），其實這些資料結構被發明出來就是為了解決特定問題的，你不處理特定問題根本用不到這些，沒必要去研究。

4.1.9.2、為什麼需要更複雜的資料結構

因為現實中的實際問題是多種多樣的，問題的複雜度不同，是以需要解決問題的算法和資料結構也不同。是以當你處理什麼複雜度的問題，就去研究針對性解決的資料結構和算法；當你沒有遇到此類問題（或者你工作的領域根本跟這個就沒關系）時就不要去管了。

4.1.9.3、資料結構和算法的關系

資料結構的發明都是為了配合一定的算法；算法是為了處理具體問題，算法的實作依賴于相應的資料結構。

目前我們說的算法和純數學是不同的（算法是基于數學的，大學計算機系研究所學生博士生很多大學都是數學相關專業的），因為計算機算法要求以數學算法為指導，并且結合計算機本身的特點來改進，最終實作一個在計算機上可以運作的算法（意思就是用代碼可以表示的算法）。

4.1.9.4、應該怎樣學習這部分？

從上面表述大家應該明白以下事實：

1. 資料結構和算法是相輔相成的，要一起研究。

2. 資料結構和算法對嵌入式來說不全是重點，不要盲目的跑去研究這個。

3. 一般在實際應用中，實作資料結構和算法的人和使用資料結構和算法的人是分開的。實際中有一部分人的工作就是研究資料結構和算法，并且試圖用代碼來實作這些算法（表現為庫）；其他做真正工作的人要做的就是了解、明白這些算法和資料結構的意義、優劣、特征，然後在合适的時候選擇合适的資料結構和算法來解決自己碰到的實際問題。

舉個例子：linux核心在字元裝置驅動管理時，使用了哈希表（hash table，散清單）。是以字元裝置驅動的很多特點都和哈希表的特點有關。