C語言 鏈表的概念

鏈表是一種重要的數(shù)據(jù)結(jié)構(gòu)，鏈表中的元素在物理空間上并不連續(xù)，鏈表的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。

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

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

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

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

從上圖可以看出：

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

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

    鏈表中各結(jié)點(diǎn)在內(nèi)存中存放的位置并不像數(shù)組那樣是連續(xù)的，而是任意的。如果想查找鏈表中的某—個結(jié)點(diǎn)，必須從鏈表的頭指針?biāo)赶虻牡谝粋€結(jié)點(diǎn)開始順序查找。

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

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

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

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

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

從結(jié)構(gòu)上看，鏈表是一個結(jié)構(gòu)體類型，該結(jié)構(gòu)體類型中至少包含兩個成員：

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

    ?指向下一個結(jié)點(diǎn)的地址：該成員是一個本結(jié)構(gòu)體類型的指針。

所以，可以設(shè)計(jì)一個簡單的結(jié)構(gòu)體類型如下：

struct: node 

{

    long num;

    sturct student *next

};

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

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

    圖中的結(jié)構(gòu)可以定義如下：

struct student

{

    int no;

    char name [10]; 

    char sex;

    int age;

    struct student *next;

);