三、幾種鏈表的實(shí)現(xiàn)

1、靜態(tài)鏈表

單鏈表的劣勢(shì)：
?單鏈表的實(shí)現(xiàn)嚴(yán)重依賴指針！
?數(shù)據(jù)元素中必須包含一個(gè)額外的指針域！
?沒有指針的程序設(shè)計(jì)語(yǔ)言無(wú)法實(shí)現(xiàn)！
由于單鏈表存在以上的劣勢(shì)，因此可以對(duì)順序表加以改進(jìn)，從而通過索引查找下一個(gè)元素，達(dá)到鏈表相同的效果，這就是靜態(tài)鏈表。
靜態(tài)鏈表的定義：
?順序表數(shù)組中的元素由兩個(gè)數(shù)據(jù)域組成：data和next
?data域用于存儲(chǔ)數(shù)據(jù)
?next域用于存儲(chǔ)下一個(gè)元素在數(shù)組中的下標(biāo)

靜態(tài)鏈表的邏輯結(jié)構(gòu)
?靜態(tài)鏈表是在順序表的基礎(chǔ)上利用數(shù)組實(shí)現(xiàn)的單鏈表！

靜態(tài)鏈表相關(guān)定義

/*結(jié)點(diǎn)結(jié)構(gòu)體定義*/
typedef struct _tag_StaticListNode{
    unsigned int data;
    int next;
}TStaticListNode;

/* 靜態(tài)鏈表結(jié)構(gòu)體定義 */
typedef struct _tag_StaticList{
    int capatity;
    TStaticListNode header;
    TStaticListNode node[];
}TStaticList; 

獲取第pos個(gè)元素操作
?判斷線性表是否合法
?判斷位置是否合法
?由表頭開始通過next域移動(dòng)pos次后，當(dāng)前元素的next域即要獲取元素在數(shù)組中的下標(biāo)

slist->node[0] = slist->header;                   
for(i=0; i<pos; i++)   
{
            current = slist->node[current].next;
}
obj = slist->node[current].next;

插入元素到位置pos的算法
?判斷線性表是否合法
?判斷插入位置是否合法
?在數(shù)組中查找空閑位置index
?由表頭開始通過next域移動(dòng)pos次后，當(dāng)前元素的next域?yàn)橐迦氲奈恢?br/>?將新元素插入
?線性表長(zhǎng)度加1

for(i=0; (i<pos)&&(slist->node[current].next != 0); i++)   
{
    current = slist->node[current].next;
}
slist->node[index].next = slist->node[current].next;    
slist->node[current].next = index;

刪除第pos個(gè)元素的算法
?判斷線性表是否合法
?判斷插入位置是否合法
?獲取第pos個(gè)元素
?將第pos個(gè)元素從鏈表中刪除
?線性表長(zhǎng)度減1

obj = slist->node[current].next;          
slist->node[current].next = slist->node[obj].next;

靜態(tài)鏈表的總結(jié)
?靜態(tài)鏈表其實(shí)是單鏈表的另一種實(shí)現(xiàn)方式
?靜態(tài)鏈表的實(shí)現(xiàn)“媒介”不是指針而是數(shù)組
?靜態(tài)鏈表主要用于不支持指針的程序設(shè)計(jì)語(yǔ)言中
?靜態(tài)鏈表的實(shí)現(xiàn)是一種內(nèi)存管理的簡(jiǎn)易方法
?其完整實(shí)現(xiàn)代碼在附件中03_StaticList文件夾

2、循環(huán)鏈表

單鏈表的局限
?單鏈表可以用于表示任意的線性關(guān)系
?有些線性關(guān)系是循環(huán)的，即沒有隊(duì)尾元素
?對(duì)單項(xiàng)鏈表進(jìn)行改進(jìn)即可得到循環(huán)鏈表，其定義為：將單鏈表中最后一個(gè)數(shù)據(jù)元素的next指針指向第一個(gè)元素

循環(huán)鏈表?yè)碛袉捂湵淼乃胁僮?/strong>
?創(chuàng)建鏈表
?銷毀鏈表
?獲取鏈表長(zhǎng)度
?清空鏈表
?獲取第pos個(gè)元素操作
?插入元素到位置pos
?刪除位置pos處的元素
并且在循環(huán)鏈表中可以定義一個(gè)游標(biāo)：
?在循環(huán)鏈表中可以定義一個(gè)“當(dāng)前”指針，這個(gè)指針通常稱為游標(biāo)，可以通過這個(gè)游標(biāo)來(lái)遍歷鏈表中的所有元素。

循環(huán)鏈表的新操作
?獲取當(dāng)前游標(biāo)指向的數(shù)據(jù)元素
?將游標(biāo)重置指向鏈表中的第一個(gè)數(shù)據(jù)元素
?將游標(biāo)移動(dòng)指向到鏈表中的下一個(gè)數(shù)據(jù)元素
?直接指定刪除鏈表中的某個(gè)數(shù)據(jù)元素
添加游標(biāo)后的循環(huán)鏈表，就可以解決更為復(fù)雜的問題，同比如約瑟夫問題。
?n 個(gè)人圍成一個(gè)圓圈，首先第 1 個(gè)人從 1 開始一個(gè)人一個(gè)人順時(shí)針報(bào)數(shù)，報(bào)到第 m 個(gè)人，令其出列。然后再?gòu)南乱?個(gè)人開始從 1 順時(shí)針報(bào)數(shù)，報(bào)到第 m 個(gè)人，再令其出列，…，如此下去，求出列順序。

循環(huán)鏈表小結(jié)：
?循環(huán)鏈表只是在單鏈表的基礎(chǔ)上做了一個(gè)加強(qiáng)
?循環(huán)鏈表可以完全取代單鏈表的使用
?循環(huán)鏈表的Next和Current操作可以高效的遍歷鏈表中的所有元素
?循環(huán)鏈表的實(shí)現(xiàn)代碼在附件中04_CircleList文件夾

current->next = node;
node->next = next;
next->pre = node;
node->pre = current;

current->next = next;
next->pre = current;