C語言的那些小秘密之鏈表（一）

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

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

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

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

　　1、數(shù)據(jù)域：用來存儲本身數(shù)據(jù)

　　2、指針域：用來存儲下一個結(jié)點(diǎn)地址或者說指向其直接后繼的指針。

　　如下圖所示：

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

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

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

　　如下圖所示：

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

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

　　#include

　　#include

　　#include

　　#include

　　#define N 3

　　#undef _EXAM_ASSERT_TEST_ //禁用

　　//#define _EXAM_ASSERT_TEST_ //啟用

　　#ifdef _EXAM_ASSERT_TEST_ //啟用斷言測試

　　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 // 禁用斷言測試

　　#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]='