三、幾種鏈表的實現

1、靜態鏈表

單鏈表的劣勢：
?單鏈表的實現嚴重依賴指針！
?數據元素中必須包含一個額外的指針域！
?沒有指針的程序設計語言無法實現！
由于單鏈表存在以上的劣勢，因此可以對順序表加以改進，從而通過索引查找下一個元素，達到鏈表相同的效果，這就是靜態鏈表。
靜態鏈表的定義：
?順序表數組中的元素由兩個數據域組成：data和next
?data域用于存儲數據
?next域用于存儲下一個元素在數組中的下標

靜態鏈表的邏輯結構
?靜態鏈表是在順序表的基礎上利用數組實現的單鏈表！

靜態鏈表相關定義

/*結點結構體定義*/
typedef struct _tag_StaticListNode{
    unsigned int data;
    int next;
}TStaticListNode;

/* 靜態鏈表結構體定義 */
typedef struct _tag_StaticList{
    int capatity;
    TStaticListNode header;
    TStaticListNode node[];
}TStaticList; 

獲取第pos個元素操作
?判斷線性表是否合法
?判斷位置是否合法
?由表頭開始通過next域移動pos次后，當前元素的next域即要獲取元素在數組中的下標

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

插入元素到位置pos的算法
?判斷線性表是否合法
?判斷插入位置是否合法
?在數組中查找空閑位置index
?由表頭開始通過next域移動pos次后，當前元素的next域為要插入的位置
?將新元素插入
?線性表長度加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個元素的算法
?判斷線性表是否合法
?判斷插入位置是否合法
?獲取第pos個元素
?將第pos個元素從鏈表中刪除
?線性表長度減1

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

靜態鏈表的總結
?靜態鏈表其實是單鏈表的另一種實現方式
?靜態鏈表的實現“媒介”不是指針而是數組
?靜態鏈表主要用于不支持指針的程序設計語言中
?靜態鏈表的實現是一種內存管理的簡易方法
?其完整實現代碼在附件中03_StaticList文件夾

2、循環鏈表

單鏈表的局限
?單鏈表可以用于表示任意的線性關系
?有些線性關系是循環的，即沒有隊尾元素
?對單項鏈表進行改進即可得到循環鏈表，其定義為：將單鏈表中最后一個數據元素的next指針指向第一個元素

循環鏈表擁有單鏈表的所有操作
?創建鏈表
?銷毀鏈表
?獲取鏈表長度
?清空鏈表
?獲取第pos個元素操作
?插入元素到位置pos
?刪除位置pos處的元素
并且在循環鏈表中可以定義一個游標：
?在循環鏈表中可以定義一個“當前”指針，這個指針通常稱為游標，可以通過這個游標來遍歷鏈表中的所有元素。

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

循環鏈表小結：
?循環鏈表只是在單鏈表的基礎上做了一個加強
?循環鏈表可以完全取代單鏈表的使用
?循環鏈表的Next和Current操作可以高效的遍歷鏈表中的所有元素
?循環鏈表的實現代碼在附件中04_CircleList文件夾

3、雙向鏈表

單鏈表的局限
?單鏈表的結點都只有一個指向下一個結點的指針
?單鏈表的數據元素無法直接訪問其前驅元素
?逆序訪問單鏈表中的元素是極其耗時的操作
因此對單項鏈表，加以改進可以得到雙向鏈表：在單鏈表的結點中增加一個指向其前驅的pre指針

雙向鏈表擁有單鏈表的所有操作
?創建鏈表
?銷毀鏈表
?獲取鏈表長度
?清空鏈表
?獲取第pos個元素操作
?插入元素到位置pos
?刪除位置pos處的元素
雙向鏈表的插入操作

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

雙向鏈表的刪除操作

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

雙向鏈表的新操作
?獲取當前游標指向的數據元素
?將游標重置指向鏈表中的第一個數據元素
?將游標移動指向到鏈表中的下一個數據元素
?將游標移動指向到鏈表中的上一個數據元素
?直接指定刪除鏈表中的某個數據元素
雙向鏈表小結
?雙向鏈表在單鏈表的基礎上增加了指向前驅的指針
?功能上雙向鏈表可以完全取代單鏈表的使用
?雙向鏈表的Next，Pre和Current操作可以高效的遍歷鏈表中的所有元素
?雙向表的實現代碼在附件中05_DLinkList文件夾
靜態鏈表和雙向鏈表的改進
靜態鏈表的改進：將數組中的空閑結點鏈接成空閑鏈表,實現代碼在附件中06_StaticList_imp文件夾

雙向鏈表的改進:雙向循環鏈表,實現代碼在附件中07_DCircleLinkList文件夾

所有鏈表的完整實現：附件