C語言 鏈表的概念

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

下圖所示為一個(gè)單向鏈表的形式：

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

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

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

從上圖可以看出：

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

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

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

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

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

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

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

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

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

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

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

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

struct: node 

{

    long num;

    sturct student *next

};

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

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

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

struct student

{

    int no;

    char name [10]; 

    char sex;

    int age;

    struct student *next;

);