C語(yǔ)言的那些小秘密之鏈表（一）

　　鏈表，一個(gè)對(duì)于學(xué)習(xí)過(guò)C語(yǔ)言的人都是再熟悉不過(guò)的概念了，可能很多學(xué)習(xí)過(guò)鏈表的人都覺得鏈表沒什么值得太在意的地方，可是如果你走進(jìn)linux內(nèi)核，去看看linux內(nèi)核里面鏈表的實(shí)現(xiàn)方式，你不得不為之驚嘆。可能有人會(huì)覺得linux內(nèi)核鏈表實(shí)現(xiàn)方式僅此而已，但是你要知道，如果你沒有見到這樣的實(shí)現(xiàn)方式之前，能寫出那樣的鏈表嘛?所以在寫鏈表的文章時(shí)，我深知自己不可能用一篇文章來(lái)講解完鏈表的知識(shí)點(diǎn)，所以我特地分為三個(gè)部分(單鏈表、雙鏈表、linux內(nèi)核鏈表，而其中l(wèi)inux內(nèi)核鏈表單獨(dú)拿出來(lái)講是因?yàn)樗奶厥庑?，在后面的博客中我們?cè)賮?lái)細(xì)談它)來(lái)進(jìn)行講解，盡可能用簡(jiǎn)短的文字描述加上簡(jiǎn)單易懂的代碼來(lái)向讀者講解我所理解的鏈表，希望我所講的鏈表能都對(duì)你有所幫助。接下來(lái)言歸正傳，開始我們的鏈表之旅。

　　那么什么是鏈表呢?鏈表是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的。鏈表由一系列結(jié)點(diǎn)組成，即鏈表中的每個(gè)元素，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。每個(gè)結(jié)點(diǎn)均由兩個(gè)部分所組成：一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域，另一個(gè)是存儲(chǔ)相鄰結(jié)點(diǎn)地址的指針域。相比于線性表順序結(jié)構(gòu)，鏈表比較方便插入和刪除操作。

　　對(duì)于鏈表我們可以將其分為單鏈表、雙向鏈表和循環(huán)鏈表等。首先我們先講講單鏈表。

　　所謂單鏈表，是指數(shù)據(jù)結(jié)點(diǎn)是單向排列的。一個(gè)單鏈表結(jié)點(diǎn)，其結(jié)構(gòu)類型分為兩部分：

　　1、數(shù)據(jù)域：用來(lái)存儲(chǔ)本身數(shù)據(jù)

　　2、指針域：用來(lái)存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址或者說(shuō)指向其直接后繼的指針。

　　如下圖所示：

　　注意：如果有圖中的紅色箭頭部分，則變?yōu)榱藛蜗蜓h(huán)鏈表。

　　那什么又是雙鏈表呢?雙向鏈表其實(shí)是單鏈表的改進(jìn)。當(dāng)我們對(duì)單鏈表進(jìn)行操作時(shí)，有時(shí)你要對(duì)某個(gè)結(jié)點(diǎn)的直接前驅(qū)進(jìn)行操作時(shí)，又必須從表頭開始查找。這是由單鏈表結(jié)點(diǎn)的結(jié)構(gòu)所限制的。因?yàn)閱捂湵砻總€(gè)結(jié)點(diǎn)只有一個(gè)存儲(chǔ)直接后繼結(jié)點(diǎn)地址的鏈域，那么能不能定義一個(gè)既有存儲(chǔ)直接后繼結(jié)點(diǎn)地址的鏈域，又有存儲(chǔ)直接前驅(qū)結(jié)點(diǎn)地址的鏈域的這樣一個(gè)雙鏈域結(jié)點(diǎn)結(jié)構(gòu)呢?這就是雙向鏈表。

　　在雙向鏈表中，結(jié)點(diǎn)除含有數(shù)據(jù)域外，還有兩個(gè)鏈域，一個(gè)存儲(chǔ)直接后繼結(jié)點(diǎn)地址，一般稱之為右鏈域;一個(gè)存儲(chǔ)直接前驅(qū)結(jié)點(diǎn)地址，一般稱之為左鏈域。

　　如下圖所示：

　　注意：如果有圖中的紅色箭頭部分，則變?yōu)榱穗p向循環(huán)鏈表。

　　看完了上面的介紹之后，我想讀者對(duì)于鏈表算是有了一個(gè)大致的了解。那么接下來(lái)我們的任務(wù)就是學(xué)習(xí)如何使用鏈表，我們從最簡(jiǎn)單的代碼開始，教會(huì)讀者來(lái)學(xué)習(xí)使用鏈表，首先我們來(lái)看一個(gè)單鏈表的創(chuàng)建。為了便于講解，我在此就把所有的代碼放到一個(gè)源文件中來(lái)執(zhí)行了，當(dāng)然讀者在實(shí)際編寫代碼的過(guò)程中不管是為了維護(hù)還是閱讀都應(yīng)該使用頭文件，而不要在一個(gè)源文件中一條龍似地寫到底。

　　#include

　　#include

　　#include

　　#include

　　#define N 3

　　#undef _EXAM_ASSERT_TEST_ //禁用

　　//#define _EXAM_ASSERT_TEST_ //啟用

　　#ifdef _EXAM_ASSERT_TEST_ //啟用斷言測(cè)試

　　void assert_report( const char * file_name, const char * function_name, unsigned int line_no )

　　{

　　printf( "n[EXAM]Error Report file_name: %s, function_name: %s, line %un",

　　file_name, function_name, line_no );

　　abort();

　　}

　　#define ASSERT_REPORT( condition )

　　do{

　　if ( condition )

　　NULL;

　　else

　　assert_report( __FILE__, __func__, __LINE__ );

　　}while(0)

　　#else // 禁用斷言測(cè)試

　　#define ASSERT_REPORT( condition ) NULL

　　#endif /* end of ASSERT */

　　typedef enum _SListReturn

　　{

　　SLIST_RETURN_OK

　　}SListReturn;

　　typedef struct node

　　{

　　char name[10];

　　int score;

　　struct node *link;

　　}stud;

　　stud * creat(int n)

　　{

　　stud *p,*h,*s;

　　int i;

　　if((h=(stud *)malloc(sizeof(stud)))==NULL)

　　{

　　printf("分配內(nèi)存空間失敗!");

　　exit(0);

　　}

　　h->name[0]='