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

　　鏈表，一個對于學習過C語言的人都是再熟悉不過的概念了，可能很多學習過鏈表的人都覺得鏈表沒什么值得太在意的地方，可是如果你走進linux內核，去看看linux內核里面鏈表的實現方式，你不得不為之驚嘆。可能有人會覺得linux內核鏈表實現方式僅此而已，但是你要知道，如果你沒有見到這樣的實現方式之前，能寫出那樣的鏈表嘛?所以在寫鏈表的文章時，我深知自己不可能用一篇文章來講解完鏈表的知識點，所以我特地分為三個部分(單鏈表、雙鏈表、linux內核鏈表，而其中linux內核鏈表單獨拿出來講是因為它的特殊性，在后面的博客中我們再來細談它)來進行講解，盡可能用簡短的文字描述加上簡單易懂的代碼來向讀者講解我所理解的鏈表，希望我所講的鏈表能都對你有所幫助。接下來言歸正傳，開始我們的鏈表之旅。

　　那么什么是鏈表呢?鏈表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列結點組成，即鏈表中的每個元素，結點可以在運行時動態生成。每個結點均由兩個部分所組成：一個是存儲數據元素的數據域，另一個是存儲相鄰結點地址的指針域。相比于線性表順序結構，鏈表比較方便插入和刪除操作。

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

　　所謂單鏈表，是指數據結點是單向排列的。一個單鏈表結點，其結構類型分為兩部分：

　　1、數據域：用來存儲本身數據

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

　　如下圖所示：

　　注意：如果有圖中的紅色箭頭部分，則變為了單向循環鏈表。

　　那什么又是雙鏈表呢?雙向鏈表其實是單鏈表的改進。當我們對單鏈表進行操作時，有時你要對某個結點的直接前驅進行操作時，又必須從表頭開始查找。這是由單鏈表結點的結構所限制的。因為單鏈表每個結點只有一個存儲直接后繼結點地址的鏈域，那么能不能定義一個既有存儲直接后繼結點地址的鏈域，又有存儲直接前驅結點地址的鏈域的這樣一個雙鏈域結點結構呢?這就是雙向鏈表。

　　在雙向鏈表中，結點除含有數據域外，還有兩個鏈域，一個存儲直接后繼結點地址，一般稱之為右鏈域;一個存儲直接前驅結點地址，一般稱之為左鏈域。

　　如下圖所示：

　　注意：如果有圖中的紅色箭頭部分，則變為了雙向循環鏈表。

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

　　#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("分配內存空間失敗!");

　　exit(0);

　　}

　　h->name[0]='