線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

  線性表從物理結(jié)構(gòu)上分，有順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)兩種。既然有了順序存儲(chǔ)結(jié)構(gòu)，又何必再有一個(gè)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)呢？原因就在于，順序存儲(chǔ)結(jié)構(gòu)在存儲(chǔ)大量的元素，對(duì)這些元素進(jìn)行插入或這刪除操作時(shí)，會(huì)浪費(fèi)大量的時(shí)間。因?yàn)?，采用順序存?chǔ)結(jié)構(gòu)，這些元素的地址都是相鄰的，如果刪除或者插入一個(gè)元素，則需對(duì)其后的所有元素進(jìn)行移動(dòng)，故非常的浪費(fèi)運(yùn)行時(shí)間，運(yùn)行效率不高。

  鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)卻避免了這樣的問題。因?yàn)?，鏈?zhǔn)酱鎯?chǔ)并不需要去關(guān)心元素存在哪個(gè)位置，也就是說，鏈?zhǔn)酱鎯?chǔ)可以讓元素存于內(nèi)存的任意位置，而我只要知道元素的地址即可。如下圖所示：

這種存儲(chǔ)方式就完全不需要各個(gè)元素是相鄰的位置，只需要知道每一個(gè)元素的地址即可。通過上圖可以發(fā)現(xiàn)，采用了鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的元素之間互相串聯(lián)，就像是一個(gè)表，所以，將這種形式稱為鏈表。那么，可以將每一個(gè)數(shù)據(jù)所占的單元叫做，結(jié)點(diǎn)。因?yàn)?，我們不僅需要知道存儲(chǔ)的元素值，還需要知道元素的地址，因此，一個(gè)結(jié)點(diǎn)就是由一個(gè)數(shù)據(jù)和存放數(shù)據(jù)的地址，兩部分組成。

  那么，總結(jié)一下就是，鏈表是由一個(gè)個(gè)結(jié)點(diǎn)構(gòu)成，而每一個(gè)結(jié)點(diǎn)是由一個(gè)存放數(shù)據(jù)的數(shù)據(jù)域和一個(gè)存放數(shù)據(jù)地址的地址域構(gòu)成。

  這個(gè)地址域存放的并不是當(dāng)前元素的地址，而是，下一個(gè)元素的地址。

代碼如下：

typedef struct Node{
    
    ElemType data;
    struct Node *next;

}Node;

typedef struct Node *LinkList;