C語言 鏈表的概念

鏈表是一種重要的數(shù)據(jù)結構，鏈表中的元素在物理空間上并不連續(xù)，鏈表的邏輯順序是通過鏈表中的指針鏈接次序實現(xiàn)的。

下圖所示為一個單向鏈表的形式：

所謂鏈表是指若干個數(shù)據(jù)項按一定的原則連接起來，物理上不連續(xù)的序列。每個數(shù)據(jù)項稱為結點，每個結點都是由兩部分組成：

    ?數(shù)據(jù)域：用來存儲用戶實際的數(shù)據(jù)。

    ?地址域（指向下一個結點的指針）：依靠這些指針將所有的數(shù)據(jù)項連接成一個鏈表。

從上圖可以看出：

    鏈表中第一個結點稱為頭指針head，頭指針中不存放具體數(shù)據(jù)，只存放鏈表的第一個結點的地址。

    head指向第一個結點，第一個結點又指向第二個結點……一直到最后一個結點。最后一個結點不再指向其他結點，稱為表尾，表尾的地址域中放一個NULL，表示鏈表到此結束。

    鏈表中各結點在內(nèi)存中存放的位置并不像數(shù)組那樣是連續(xù)的，而是任意的。如果想查找鏈表中的某—個結點，必須從鏈表的頭指針所指向的第一個結點開始順序查找。

鏈表與數(shù)組的區(qū)別是：

    ?數(shù)組的元素個數(shù)在定義時就固定下來了，而鏈表的結點個數(shù)可根據(jù)需要進行增減。

    ?數(shù)組中元素在內(nèi)存中的存儲位置是連續(xù)存放的，而鏈表的各個結點的存儲位置則是不連續(xù)的。

    ?數(shù)組元素的存儲單元在數(shù)組定義時分配，鏈表結點的存儲單元在程序執(zhí)行時根據(jù)需要動態(tài)向系統(tǒng)申請或釋放。

    ?數(shù)組中的元素順序關系由元素在內(nèi)存中存儲位置確定，鏈表中的結點順序關系由結點所包含的指針來體現(xiàn)。

從結構上看，鏈表是一個結構體類型，該結構體類型中至少包含兩個成員：

    ?具體數(shù)據(jù)（可以是整型、浮點型、字符型、字符串）。

    ?指向下一個結點的地址：該成員是一個本結構體類型的指針。

所以，可以設計一個簡單的結構體類型如下：

struct: node 

{

    long num;

    sturct student *next

};

數(shù)據(jù)域也可以是比較復雜的類型，如圖所示的鏈表：

    鏈表的頭指針指向的地址為2044，按照頭指針的指向可找到內(nèi)存地址為2044的鏈表的第一個結 點。要想查找第二個結點，按照第一個結點的地址域存放的地址找到內(nèi)存地址為0676的第二個結點。依次順序查找，可以找到鏈表中的每一個結點，直到最后一個結點的地址域為“NULL”，表示這是鏈表尾。

    圖中的結構可以定義如下：

struct student

{

    int no;

    char name [10]; 

    char sex;

    int age;

    struct student *next;

);