算法與數(shù)據(jù)結(jié)構(gòu)前置知識(1)—c語言指針

??前段時間自己開始寫一個事件驅(qū)動web服務(wù)器，由于使用的是c語言，發(fā)現(xiàn)所有數(shù)據(jù)結(jié)構(gòu)都需要自己從0開始實現(xiàn)，在寫的過程中并不是很順利揍移，由此萌生了寫這一系列文章的想法，也是對數(shù)據(jù)結(jié)構(gòu)和算法回顧反肋。

??后續(xù)代碼主要使用c語言實現(xiàn)那伐，也正是因為這樣，前面花了3篇文章來回顧c語言的必要知識。至于為什么使用c語言我有一些自己的看法罕邀，這里我講兩個主要的原因畅形。第一，c語言更接近底層诉探，操作系統(tǒng)的底層實際上也是一個個數(shù)據(jù)結(jié)構(gòu)和算法堆砌而成的日熬，使用c語言實現(xiàn)可以更好的窺視系統(tǒng)底層運行原理。第二肾胯，c語言原生支持指針竖席，對于鏈表、樹敬肚、圖這類數(shù)據(jù)結(jié)構(gòu)使用指針更能事倍功半怕敬。當(dāng)然，除了c語言我還會根據(jù)數(shù)據(jù)結(jié)構(gòu)的實際特點使用其它語言實現(xiàn)比如python帘皿、java、go畸陡，并且對比它們之前的差異鹰溜。

1. 指針的聲明

int *p = NULL;

上面聲明了一個指針p，p表示指針變量丁恭，值是所在內(nèi)存的地址曹动。

要注意指針一定要進(jìn)行初始化，一般我們使用NULL來初始化指針變量牲览，NULL表示不指向任何地址的指針墓陈，上面的聲明如下圖：

圖：1-1

下面我們對p進(jìn)行賦值：

int a = 100; p = &a;

這時候就變成下面這樣，如圖：

圖：1-2

來看一下下面的聲明

int* a,b;

a是一個int類型指針變量第献，b是一個int類型的變量贡必。通常情況下，在聲明指針的時候一般會把'*'放到變量名的一側(cè)庸毫，例如：
int *a,b;
這樣在我們閱讀的時候能夠減少一些歧義仔拟。

考慮下面的聲明：

int *func();

上面的聲明會先執(zhí)行()，所以上面的聲明表示函數(shù)返回一個int型指針飒赃。

接著看下面的聲明：

int (*func)();

上面的聲明會先執(zhí)行(*func)表示某個類型的指針利花，接著執(zhí)行()，表示一個返回值為int的函數(shù)指針载佳，這也是函數(shù)指針最簡單的聲明炒事。關(guān)于函數(shù)指針，我們后面再詳細(xì)說明蔫慧。

2. 指針的使用

我們使用'*'操作符來對指針解引用挠乳，例如：

int *a = NULL; 
int b = 100; 
a = &b;

上面a=100表示將a所在地址的值修改為100。''表示對指針變量解引用，很多書上都是這么說的欲侮，對于沒怎么使用過指針的人來講還是太抽象了崭闲。我們通過下面的圖來理解，見圖2-1

圖：2-1

我們還可以對指針進(jìn)行加減運算威蕉，例如：

a++; 
a--; 
a += 1; 
a -= 1;

這在c語言中都是合法的刁俭，要注意的是對于上面的指針變量a來說，a++和a--都會導(dǎo)致不可預(yù)料的結(jié)果韧涨，我們在對內(nèi)存進(jìn)行加減操作的時候一定要有明確的邊界條件牍戚。對內(nèi)存地址變量+1表示往后移動對應(yīng)類型的長度，比如說我們在32位機(jī)器上聲明一個int類型的指針虑粥，那么對指針變量進(jìn)行+1操作實際上對于地址變量來講是加了8個字節(jié)的長度如孝，這點要注意。

3. 數(shù)組與指針

數(shù)組與指針的關(guān)系一直是學(xué)習(xí)指針的一個難點娩贷，來看下面兩個聲明：

int a[10]; 
int *p = NULL;

a是一個長度為10元素類型為整型的數(shù)組第晰，p是一個不指向任何地址的整型指針。如果聽到有人說數(shù)組等同于指針這種說法要小心了彬祖，這種說法是不完全對的茁瘦。例如我們考慮下面的情況：

文件1：

int a[10];

文件2：

extern int *a;

上面我們在文件1中定義了一個長度為10元素類型為整型的數(shù)組a，在文件2中給出一個a的聲明int *a储笑。直覺上甜熔，我們會把文件1中的a和文件2中的a都當(dāng)成一個指針，因為它們都保存了一個內(nèi)存地址突倍。但實際上腔稀，上面這種做法是錯誤的。

為了說明上述問題羽历，我們需要弄明白c語言中的兩個術(shù)語定義和聲明焊虏。在上述例子中，文件1中的 int a[10]表示定義秕磷，定義是需要占用內(nèi)存空間的炕淮。文件2中的extern int *a表示是聲明，不分配內(nèi)存空間跳夭，編譯器編譯的時候會找到定義的實體也就是文件1中的a涂圆，我們可以把定義想象成古時候的皇帝，把聲明想象成欽差大臣币叹，并且他們的意志完全一樣润歉，但欽差大臣本身不可能像皇帝一樣掌控皇權(quán)，他只是代表了皇帝的意志颈抚。這里的皇權(quán)就相當(dāng)于定義中分配的地址空間踩衩。

搞明白了定義和聲明的意思嚼鹉，下面我們來分析一下上面的例子為什么是錯誤的。為了搞明白驱富，我們要先搞清楚數(shù)組和指針使用的時候中間發(fā)生了什么锚赤。

考慮下面的情況:

char a[10] = "hello world!"; 
a[1]; 
char *b = "hello world!"; 
b[1];

對于a[1]來講，直接訪問初始地址的內(nèi)容e褐鸥，如下圖：

圖：3-1

對于b[1]來講线脚，是先將提取b所保存的地址然后把地址加1個字符的長度，拿到存儲字符e所在的地址叫榕，然后取地址里的內(nèi)容e浑侥，如下圖：

圖：3-2

那么問題就來了，我們看第一個例子晰绎，定義為int a[10]寓落，聲明為int *a會發(fā)生什么，當(dāng)我們對聲明的a(int *a)進(jìn)行a[1]訪問的時候荞下，會先提取a的地址伶选，然后加一個字符長度，再取計算后地址里的內(nèi)容尖昏。但是定義里面a是一個數(shù)組考蕾，我們使用a[1]去訪問的時候拿到的是字符e，并不是一個地址会宪，這個時候編譯器就會報錯。

上面說明了數(shù)組和指針在使用時候的的區(qū)別蚯窥，這也說明了為什么數(shù)組等同于指針這種說法是不正確的掸鹅。下面對數(shù)組和指針的區(qū)別總結(jié)如下：

1. 數(shù)組是編譯器隨機(jī)分配的內(nèi)存地址，不能修改拦赠，而指針的地址是可以修改的巍沙。

2. 數(shù)組保存的是數(shù)據(jù)，指針保存的是數(shù)據(jù)的指針荷鼠。

3. 數(shù)組a[1]表示直接訪問數(shù)據(jù)句携，指針a[1]表示先提取a的地址，然后將地址加一個單位長度允乐，最后取計算后地址里的內(nèi)容矮嫉。

當(dāng)然，數(shù)組和指針還有一其它一些細(xì)微的差別牍疏，但是只要掌握了以上的內(nèi)容蠢笋，應(yīng)該能將數(shù)組和指針的關(guān)系搞明白了。

4. 結(jié)構(gòu)指針

結(jié)構(gòu)指針和普通指針并沒有什么區(qū)別鳞陨，只是在使用上有一些擴(kuò)展昨寞。

例如：

typedef struct _TEST{ 
  int age; 
  char *name; 
} test; 
test t = {20, "張三"}; 
test *t2 = &t; 
int age = (*t2).age; 
char *name = (*t2).name; 
(*t2).age = 30;

要注意的是，使用指針的訪問結(jié)構(gòu)成員的時候要將操作符放在括號內(nèi)，操作符的優(yōu)先級低于.操作符援岩。

結(jié)構(gòu)還提供了一種方便操作符->來操作結(jié)構(gòu)指針歼狼，例如：

t2->age = 30; 
int age = t2->age;

由于結(jié)構(gòu)占用的內(nèi)存空間是結(jié)構(gòu)內(nèi)部所有元素之和，所以在將結(jié)構(gòu)當(dāng)作函數(shù)參數(shù)的時候我們一般都使用結(jié)構(gòu)指針享怀，可以回顧結(jié)構(gòu)那一節(jié)羽峰。

5. 函數(shù)指針

在第一節(jié)我們說到聲明函數(shù)指針的簡單聲明：

int (*fn)();

表示返回值為int的函數(shù)指針，但這個函數(shù)是沒有參數(shù)的凹蜈，下面我們來看一下函數(shù)指針的使用方法及注意事項限寞。

5.1. 聲明函數(shù)指針

int (*func01)(int); 
int (*func02)(int, char*); 
char* (*func03)(int, char*);

圖：5-1

5.2. 函數(shù)指針的使用

調(diào)用：

func_name(name, 23) // 或者 (*func_name)(name, 23)

傳參：

find(func_name); // 或者 find(&func_name);

5.3. 函數(shù)指針數(shù)組

創(chuàng)建：

void (*func_arr[])(char*, int);