轉(zhuǎn)自：http://blog.csdn.net/oreo_go/article/details/52116214

一盖喷、線性表的定義

線性表：零個(gè)或多個(gè)數(shù)據(jù)元素的有限序列炮沐。

幾個(gè)關(guān)鍵的地方。
首先它是一個(gè)序列峰弹。也就是說店量，元素之間是有順序的，若元素存在多個(gè)鞠呈，則第一個(gè)元素?zé)o前驅(qū)融师，最后一個(gè)元素?zé)o后繼，其他每個(gè)元素都只有一個(gè)前驅(qū)和后繼蚁吝。

然后旱爆，線性表強(qiáng)調(diào)是有限的舀射。事實(shí)上，在計(jì)算機(jī)中處理的對(duì)象都是有限的怀伦，那種無限的數(shù)列后控，只存在于數(shù)學(xué)的概念中。

如果用數(shù)學(xué)語言來定義空镜。可如下：
**若將線性表記為(a1捌朴，…吴攒，ai-1，ai砂蔽，ai+1洼怔，…，an)左驾，則表中ai-1領(lǐng)先于ai镣隶，ai領(lǐng)先于ai+1，稱ai-1是ai的直接前驅(qū)元素诡右，ai+1是ai的直接后繼元素安岂。當(dāng)i = 1，2帆吻，…域那，n-1時(shí)，ai有且僅有一個(gè)直接后繼猜煮，當(dāng)i = 2 , 3 , … , n時(shí)次员，ai有且僅有一個(gè)直接前驅(qū)。 **

所以線性表元素的個(gè)數(shù)n(n ≥ 0)定義為線性表長(zhǎng)度王带，當(dāng)n=0時(shí)淑蔚，稱為空表。

在非空表中的每個(gè)數(shù)據(jù)元素都有一個(gè)確定的位置愕撰，如a1是第一個(gè)數(shù)據(jù)元素刹衫，an是最后一個(gè)數(shù)據(jù)元素，ai是第i個(gè)數(shù)據(jù)元素盟戏，稱i為數(shù)據(jù)元素ai在線性表中的位序绪妹。

舉幾個(gè)例子，來判斷是否是線性表柿究。
第一個(gè)：一年的星座列表邮旷，是不是線性表呢？

答：當(dāng)然是蝇摸，星座通常都是白羊座開頭婶肩，雙魚座收尾办陷，當(dāng)中的星座都有前驅(qū)后繼，而且一共才12個(gè)律歼，所以完全符合線性表的定義民镜。

第二個(gè)：公司的組織交媾，總經(jīng)理管理幾個(gè)總監(jiān)险毁，每個(gè)總監(jiān)管理幾個(gè)經(jīng)理制圈，每個(gè)經(jīng)理管理各自的下述和員工。這樣的組織架構(gòu)是不是線性關(guān)系呢畔况？

答：不是鲸鹦，為什么不是呢？因?yàn)槊恳粋€(gè)元素跷跪，都有不止一個(gè)后繼馋嗜，所以它不是線性表。

第三個(gè)：班級(jí)同學(xué)的友誼關(guān)系吵瞻，是不是線性表呢葛菇？

答：不是，因?yàn)槊總€(gè)人都可以和多個(gè)同學(xué)建立友誼橡羞，不滿足線性的定義眯停。

第四個(gè)：班級(jí)同學(xué)的點(diǎn)名冊(cè)，是不是線性表卿泽？是不是點(diǎn)名冊(cè)庵朝？

答：是，這和剛才的友誼關(guān)系是完全不同的又厉，因?yàn)樗怯邢扌蛄芯鸥矟M足類型相同特點(diǎn)，這個(gè)點(diǎn)名冊(cè)中覆致，每個(gè)元素除學(xué)生的學(xué)號(hào)外侄旬，還可以有同學(xué)的姓名、性別煌妈、出生年月什么的儡羔，這其實(shí)就是我們之前將的數(shù)據(jù)項(xiàng)。在較復(fù)雜的線性表中璧诵，一個(gè)數(shù)據(jù)元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成汰蜘。

二、線性表的抽象數(shù)據(jù)類型

線性表的抽象數(shù)據(jù)類型定義如下：

ADT 線性表(List)
Data
    線性表的數(shù)據(jù)對(duì)象集合為{a1,a2,....,an},每個(gè)元素的類型均為DataType之宿。其中除了族操，第一個(gè)元素a1外，每一個(gè)元素有且只有一個(gè)直接前驅(qū)元素，除最后一個(gè)元素an外色难，每一個(gè)元素有且只有一個(gè)直接后繼元素泼舱。數(shù)據(jù)元素之間的關(guān)系是一對(duì)一的關(guān)系。

Operation
    InitList(*L):初始化操作枷莉，建立一個(gè)空的線性表娇昙。
    ListEmpty(L):若線性表為空，返回true笤妙，否則返回false冒掌。
    ClearList(*L):線性表清空。
    GetElem(L,i,*e):將線性表L中第i個(gè)位置元素返回給e蹲盘。
    LocateElem(L,e):在線性表L中查找與給定值e相等的元素宋渔，如果
        查找成功,返回該元素在表中的序列號(hào)；否則辜限，返回0表示失敗。
    ListInsert(*L,i,e):在線性表的第i個(gè)位置插入元素e严蓖。
    ListDelete(*L,i,*e):刪除線性表L中的第i個(gè)元素薄嫡，并用e返回其值
    ListLength(L):返回線性表L的元素個(gè)數(shù)。

對(duì)于不同的應(yīng)用颗胡，線性表的操作時(shí)不同的毫深，上述操作時(shí)最基本的，問題中設(shè)計(jì)的關(guān)于線性表的更復(fù)雜操作毒姨，完全可以用這些基本操作的組合來實(shí)現(xiàn)哑蔫。

比如，要實(shí)現(xiàn)兩個(gè)線性表集合A和B的并集操作弧呐。即要使得集合A = A ∪ B闸迷，說白了，就是把存在集合B中但并不存在中的數(shù)據(jù)元素插到A中即可俘枫。

仔細(xì)分析一下這個(gè)操作腥沽，發(fā)現(xiàn)我們只要循環(huán)集合B中的元素，判斷是否存在A中鸠蚪，若不存在今阳，則插到A中即可。思路應(yīng)該是很容易想到的茅信。

假設(shè)我們La表示集合A盾舌，Lb表示集合B，則實(shí)現(xiàn)代碼如下：

//將所有的在線性表Lb中但不在La中的元素插入到La中
void unionL(List *La , List Lb)
{
    int La_len,Lb_len,i;
    ElemType e;
    La_len = ListLength(*La);
    Lb_len = ListLength(*Lb);
    for(i = 0 ;i ≤ Lb;i++)
    {
        GetElem(Lb,i,*e);//取出Lb中第i個(gè)數(shù)據(jù)元素賦給e
        if(!LocateElem(*La,e))//La中不存在和e元素相同的數(shù)據(jù)元素
        {
            ListInsert(La,++La_len,e);//插入
        }
    }
}

這里我們對(duì)于union操作蘸鲸，用到了前面線性表基本操作ListLength妖谴、GetElem、LocateElem酌摇，ListLength等窖维，可見榆综，對(duì)于復(fù)雜的個(gè)性化的操作，其實(shí)就是把基本操作組合起來實(shí)現(xiàn)的铸史。

三鼻疮、線性表的順序存儲(chǔ)結(jié)構(gòu)

1.順序存儲(chǔ)定義

說了這么多的線性表，我們來看線性表的物理結(jié)構(gòu)第一種——順序存儲(chǔ)結(jié)構(gòu)琳轿。

線性表的順序存儲(chǔ)結(jié)構(gòu)判沟，指定的是用一段地址連續(xù)的存儲(chǔ)單元一次存儲(chǔ)線性表的數(shù)據(jù)元素。

2.順序存儲(chǔ)方式

線性表的順序存儲(chǔ)方式崭篡，說白了挪哄，就是在內(nèi)存中找了一塊地方，把一定內(nèi)存空間占了琉闪，然后把相同數(shù)據(jù)類型的數(shù)據(jù)元素一次存在在里面迹炼。既然線性表的數(shù)據(jù)元素的類型都相同，所以用C語言的一維數(shù)組來實(shí)現(xiàn)順序存儲(chǔ)結(jié)構(gòu)颠毙，即把第一個(gè)數(shù)據(jù)元素存儲(chǔ)到數(shù)組下表為0的位置中斯入，接著把線性表相鄰的元素存儲(chǔ)在數(shù)組中相鄰的位置。

為了建立一個(gè)線性表蛀蜜，要在內(nèi)存中找一塊地刻两，于是這塊地的第一個(gè)位置就非常關(guān)鍵，它是存儲(chǔ)空間的起始位置滴某。

線性表中磅摹，我們估算這個(gè)線性表的最大存儲(chǔ)容量，建立一個(gè)數(shù)組霎奢，數(shù)組的長(zhǎng)度就是最大存儲(chǔ)容量户誓。

我們已經(jīng)有了起始位置，也有了最大的容量幕侠，于是我們可以在里面增加數(shù)據(jù)了厅克。隨著數(shù)據(jù)的插入，我們線性表的長(zhǎng)度開始變大橙依，不過線性表的當(dāng)前長(zhǎng)度不能超過存儲(chǔ)容量证舟，即數(shù)組的長(zhǎng)度。

來看線性表的順序存儲(chǔ)的結(jié)構(gòu)代碼窗骑。

 #define MAXSIZE 20 //存儲(chǔ)空間初始分配量
 typedef int ElemType;//ElemType根據(jù)實(shí)際情況而定女责，這里假設(shè)為int
 typedef struct
 {
     ElemType data[MAXSIZE];//數(shù)組存儲(chǔ)數(shù)據(jù)元素,最大值為MAXSIZE
     int length;//線性表當(dāng)前長(zhǎng)度
 }SqList;

這里我們發(fā)現(xiàn)描述順序存儲(chǔ)結(jié)構(gòu)需要三個(gè)屬性：
①存儲(chǔ)空間的起始位置：數(shù)組data，它的存儲(chǔ)位置就是存儲(chǔ)空間的存儲(chǔ)位置创译。

②線性表的最大存儲(chǔ)容量：數(shù)組長(zhǎng)度MaxSize抵知。

③線性表的當(dāng)前長(zhǎng)度：length。

3.數(shù)組長(zhǎng)度與線性表長(zhǎng)度區(qū)別

數(shù)組長(zhǎng)度是存放線性表的存儲(chǔ)空間的長(zhǎng)度，存儲(chǔ)空間分配完一般是不變的刷喜。

線性表長(zhǎng)度是線性表中元素?cái)?shù)據(jù)的個(gè)數(shù)残制，隨著線性表插入和刪除操作的進(jìn)行，這個(gè)量是變化的掖疮。

在任意時(shí)刻初茶，線性表的長(zhǎng)度應(yīng)該小于等于數(shù)組的長(zhǎng)度。

4.地址計(jì)算方法

線性表的起始是從1開始的浊闪，可數(shù)組卻是從0開始第一個(gè)下標(biāo)的恼布，于是線性表中第i個(gè)元素，存儲(chǔ)在數(shù)組下標(biāo)為i - 1的位置搁宾。

用數(shù)組存儲(chǔ)順序表意味著要分配固定長(zhǎng)度的數(shù)組空間折汞，由于線性表中可以進(jìn)行插入和刪除操作，因此分配的數(shù)組空間要大于等于當(dāng)前線性表的長(zhǎng)度盖腿。

由于每個(gè)數(shù)據(jù)元素爽待，不管他是整型、實(shí)型還是字符型翩腐，它都是需要占用一定的存儲(chǔ)空間的鸟款。假設(shè)占用的是c個(gè)存儲(chǔ)單元，那么線性表中第i + 1個(gè)元素的存儲(chǔ)位置和第i個(gè)數(shù)據(jù)元素的存儲(chǔ)位置滿足下列關(guān)系（LOC表示獲得存儲(chǔ)位置的函數(shù)）栗菜。

LOC(ai+1) = LOC(ai) + c

所以對(duì)于第i個(gè)數(shù)據(jù)元素ai的存儲(chǔ)位置可以由a1推算得出：

LOC(ai) = LOC(ai) + (i - 1) * c

通過這個(gè)公式，隨時(shí)可以算出線性表中任意位置的地址蹄梢，不管他是第一個(gè)還是最后一個(gè)疙筹，都是相同的事件。那么我們對(duì)每個(gè)線性表位置的存入或者取出數(shù)據(jù)禁炒，對(duì)于計(jì)算機(jī)來說都是相等的時(shí)間而咆，也就是一個(gè)常數(shù)，因此我們算法中學(xué)到的時(shí)間復(fù)雜度的概念來說幕袱，它的存取時(shí)間的性能為O(1)暴备。我們通常把具有這一特點(diǎn)的存儲(chǔ)結(jié)構(gòu)稱為隨機(jī)存取結(jié)構(gòu)。

四们豌、順序存儲(chǔ)結(jié)構(gòu)的插入與刪除

1.獲得元素操作

對(duì)于線性表的順序存儲(chǔ)結(jié)構(gòu)來說涯捻，我們要實(shí)現(xiàn)GetElem操作，即將線性表L中的第i個(gè)位置元素返回望迎，其實(shí)是非常簡(jiǎn)單的障癌。就程序而言，只要第i個(gè)元素在下標(biāo)范圍內(nèi)辩尊，就是把數(shù)組第i - 1下表值返回即可涛浙。
來看代碼：

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
//Status是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等
//初始條件：順序線性表L已經(jīng)存在轿亮，1 ≤ i ≤ ListLength(L)
//操作結(jié)果：用e返回L中第i個(gè)元素的值
Status GetElem(SqList L,int i,ElemType *e)
{
    if(L.length == 0 || i < 1 || i > L.length)
        return ERROR;
    *e = L.data[i - 1];
    return OK;
}

注意這里返回值類型Status是一個(gè)整型疮薇，返回OK代表1，ERROR代表0我注。

2.插入操作

剛才我們也談到按咒，這里的時(shí)間復(fù)雜度為O(1)。我們現(xiàn)在來考慮，如果我們要實(shí)現(xiàn)ListInsert(*L，i钓账，e)逛裤，即在線性表L中第i個(gè)位置插入新元素e，應(yīng)該如何操作趣些？

插入算法的思路：

①如果插入位置不合理，拋出異常；

②如果線性表長(zhǎng)度大于等于數(shù)組長(zhǎng)度剿另，則拋出異常或動(dòng)態(tài)增加容量贬蛙；

③從最后一個(gè)元素開始向前遍歷到第i個(gè)元素雨女，分別將它們都向后移一位；

④將要插入元素填入位置i處阳准；

⑤表長(zhǎng)加1氛堕。
實(shí)現(xiàn)代碼如下：

//初始條件:順序線性表L已存在,1 ≤ i ≤ ListLength(L)
//操作結(jié)果:在L的第i個(gè)位置插入新的數(shù)據(jù)元素e,L的長(zhǎng)度加1
Status ListInsert(SqList *L,int i,ElemType e)
{
    int k;
    if(L->length == MAXSIZE)//當(dāng)線性表已滿
        return ERROR;
    if(i < 1 || i >L->length + 1)//當(dāng)i不在范圍內(nèi)時(shí)
    {
        return ERROR;
    }
    if(i <= L->length)//若插入數(shù)據(jù)位置不在表尾
    {
        for(k = L->length-1;k > i-1;k--)
        {
            L->data[k + 1] = L->data[k];
        }
    }
    L->data[i - 1] = e;//將新元素插入
    L->length++;
    return OK;
}

3.刪除操作

刪除算法的思路：
①如果刪除位置不合理，拋出異常野蝇；

②取出刪除元素讼稚；

③從刪除元素位置開始遍歷到最后一個(gè)元素位置，分別將它們向前移動(dòng)一個(gè)位置绕沈；

④表長(zhǎng)減1锐想。

實(shí)現(xiàn)代碼如下：

//初始條件:順序線性表L已經(jīng)存在，1 <= i <= ListLength(L)
//操作結(jié)果:刪除L的第i個(gè)元素,并用e返回其值,L的長(zhǎng)度減1
Status ListDelete(SqList *L ,int i , ElemType *e)
{
    int k;
    if(L->length == 0)//線性表為空
        return ERROR;
    if(i < 1 || i > L->length)//刪除位置不正確
        return ERROR;
    *e = L->data[I];
    if(i < L->length)
    {
        for(k = i;k < L->length;k++)
            L->data[k - 1] = L->data[k];
    }
    L->length--;
    return OK;
}

現(xiàn)在乍狐，我們來分析一下赠摇，插入和刪除的事件復(fù)雜度。
現(xiàn)在我們來看最好的情況浅蚪，如果一個(gè)元素要插入到最后一個(gè)位置藕帜，或者刪除最后一個(gè)位置，此時(shí)時(shí)間復(fù)雜度為O(1)惜傲，因?yàn)椴恍枰苿?dòng)元素的耘戚。

最壞的情況呢，如果元素要插入到第一個(gè)位置或者刪除第一個(gè)元素操漠，此時(shí)時(shí)間復(fù)雜度是多少呢收津？那就意味著所有元素向后或者向前饿这，所以這個(gè)時(shí)間復(fù)雜度為O(n)。

至于平均的情況撞秋，由于元素插入到第i個(gè)位置长捧，或者刪除第i個(gè)元素，需要移動(dòng)n - i個(gè)元素吻贿，每個(gè)位置插入或刪除元素的可能性是相同的串结，也就是位置靠前，移動(dòng)元素多舅列，位置靠后肌割，移動(dòng)元素少。最終平均移動(dòng)次數(shù)和最中間那個(gè)元素的移動(dòng)次數(shù)相等帐要，為(n - 1)/ 2把敞。

根據(jù)時(shí)間復(fù)雜度的推導(dǎo)，平均時(shí)間復(fù)雜度還是O(n)榨惠。

這說明說明奋早？線性表的順序存儲(chǔ)結(jié)構(gòu)，在存赠橙、讀數(shù)據(jù)時(shí)耽装，不管是哪個(gè)位置，時(shí)間復(fù)雜度都是O(1)期揪；而插入或刪除時(shí)掉奄，時(shí)間復(fù)雜度都是O(n)。這就說明凤薛，它比較適合元素個(gè)數(shù)不太變化姓建，而更多是存取數(shù)據(jù)的應(yīng)用。

4線性表順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)
①無須為表中元素之間的邏輯關(guān)系而增加額外的存儲(chǔ)空間

②可以快速地存取表中任一位置的元素

缺點(diǎn)
①插入和刪除需要移動(dòng)大量元素

②當(dāng)線性表長(zhǎng)度變化較大時(shí)枉侧，難以確定存儲(chǔ)空間的容量

③造成存儲(chǔ)空間的“碎片”

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

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

線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素狂芋，這組存儲(chǔ)單元可以是連續(xù)的榨馁，也可以是不連續(xù)的。這就意味著帜矾，這些元素可以存在內(nèi)存未被占用的任意位置翼虫。

以前在順序結(jié)構(gòu)中，每個(gè)元素?cái)?shù)據(jù)只需要存儲(chǔ)數(shù)據(jù)元素信息就可以了÷庞現(xiàn)在在鏈?zhǔn)浇Y(jié)構(gòu)中珍剑，除了要存數(shù)據(jù)元素信息外，還要存儲(chǔ)它的后繼元素的存儲(chǔ)地址死陆。

因此招拙，為了表示每個(gè)數(shù)據(jù)元素ai與其直接后級(jí)元素ai+1之間的邏輯關(guān)系唧瘾，對(duì)數(shù)據(jù)元素ai來說，除了存儲(chǔ)其本身的信息之外别凤，還需存儲(chǔ)一個(gè)指示其直接后繼的信息（即直接后繼的存儲(chǔ)位置）饰序。我們把存儲(chǔ)數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域，把存儲(chǔ)直接后繼位置的域稱為指針域规哪。指針域中存儲(chǔ)的信息稱作指針或鏈求豫。這兩部分信息組成數(shù)據(jù)元素ai的存儲(chǔ)映像，稱為結(jié)點(diǎn)(Node)诉稍。

n個(gè)結(jié)點(diǎn)(ai的存儲(chǔ)映像)鏈結(jié)成一個(gè)鏈表蝠嘉，即為線性表(a1,a2,….,an)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，因?yàn)榇随湵淼拿總€(gè)結(jié)點(diǎn)中只包含一個(gè)指針域杯巨，所以叫做單鏈表蚤告。單鏈表正是通過每個(gè)結(jié)點(diǎn)的指針域?qū)⒕€性表的數(shù)據(jù)元素按其邏輯次序鏈接在一起。

對(duì)于線性表來說舔箭，總得有個(gè)頭有個(gè)尾罩缴，鏈表也不例外。我們把鏈表中第一個(gè)結(jié)點(diǎn)的存儲(chǔ)位置叫做頭指針层扶，那么整個(gè)鏈表的存取就必須是從頭指針開始進(jìn)行了箫章。之后的每一個(gè)結(jié)點(diǎn)，其實(shí)就是上一個(gè)的后繼指針指向的位置镜会。

最后一個(gè)檬寂，當(dāng)然意味著直接后繼不存在了，所以我們規(guī)定戳表，線性鏈表的最后一個(gè)結(jié)點(diǎn)指針為“空”（通常用NULL或“^”符號(hào)表示）桶至。

有時(shí)，我們?yōu)榱烁臃奖愕貙?duì)鏈表進(jìn)行操作匾旭，會(huì)在單鏈表的第一個(gè)結(jié)點(diǎn)前附設(shè)一個(gè)結(jié)點(diǎn)镣屹，稱為頭結(jié)點(diǎn)。頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲(chǔ)任何信息价涝，也可以存儲(chǔ)如線性表的長(zhǎng)度等附加信息女蜈，頭結(jié)點(diǎn)的指針域存儲(chǔ)指向第一個(gè)結(jié)點(diǎn)的指針。

2.頭指針與頭結(jié)點(diǎn)的異同

頭指針與頭結(jié)點(diǎn)的異同點(diǎn)色瘩。
頭指針
① 頭指針是指鏈表指向第一個(gè)結(jié)點(diǎn)的指針伪窖，若鏈表有頭結(jié)點(diǎn)，則是指向頭結(jié)點(diǎn)的指針

②頭指針具有標(biāo)識(shí)作用居兆，所以常用頭指針冠以鏈表的名字

③無論鏈表是否為空覆山，頭指針均不為空。頭指針是鏈表的必要元素泥栖。

頭結(jié)點(diǎn)
①頭結(jié)點(diǎn)是為了操作的統(tǒng)一和方便而設(shè)立的簇宽，放在第一元素的結(jié)點(diǎn)之間勋篓，其數(shù)據(jù)域一般無意義。

②有了頭結(jié)點(diǎn)魏割，對(duì)在第一元素結(jié)點(diǎn)前插入結(jié)點(diǎn)生巡，其操作與其它結(jié)點(diǎn)的操作就統(tǒng)一了。

③頭結(jié)點(diǎn)不一定是鏈表必須要素见妒。

3.線性鏈表式存儲(chǔ)結(jié)構(gòu)代碼描述

若線性鏈表為空表孤荣，則頭結(jié)點(diǎn)的指針域?yàn)椤翱铡薄?/p>

單鏈表中，我們?cè)贑語言中可用結(jié)構(gòu)指針來描述须揣。

//線性表的單鏈表存儲(chǔ)結(jié)構(gòu)
typedef struct Node
{
    ElemType data;
    struct Node *next;
}Node;
typedef struct Node *LinkList;//定義LinkList

在這個(gè)結(jié)構(gòu)定義中盐股，我們也就知道，結(jié)點(diǎn)由存放數(shù)據(jù)元素的數(shù)據(jù)域和存放后繼結(jié)點(diǎn)地址的指針域組成耻卡。 假設(shè)p是指向線性表第i個(gè)元素的指針疯汁，則該結(jié)點(diǎn)ai的數(shù)據(jù)域我們可以用p->data來表示，p->data的值是一個(gè)數(shù)據(jù)元素卵酪，結(jié)點(diǎn)ai的指針可以用p->next來表示幌蚊，p->next的值是一個(gè)指針。p->next指向誰呢溃卡？當(dāng)然是指向第i + 1個(gè)元素溢豆，即指向ai+1。也就是說p->data = ai瘸羡，那么p->next->data=ai+1

六漩仙、單鏈表的讀取

在線性表的順序存儲(chǔ)結(jié)構(gòu)中，我們要計(jì)算任意一個(gè)元素的存儲(chǔ)位置使很容易的犹赖。但在單鏈表中队他，由于第i個(gè)元素到底在哪？沒辦法一開始就知道峻村，必須從頭開始找麸折。因此，對(duì)于單鏈表實(shí)現(xiàn)獲取第i個(gè)元素的操作GetElem粘昨，在算法上垢啼，相對(duì)麻煩一些。

獲得鏈表第i個(gè)數(shù)據(jù)的算法思路：
1. 聲明一個(gè)指針p指向鏈表第一個(gè)結(jié)點(diǎn)雾棺，初始化j從1開始膊夹。
2. 當(dāng)j < i 時(shí)衬浑，就遍歷鏈表捌浩，讓p的指針向后移動(dòng)，不斷指向下一結(jié)點(diǎn)工秩，j累加1;
3. 若鏈表末尾p為空尸饺，則說明第i個(gè)結(jié)點(diǎn)不存在进统；
4. 否則查找成功，返回結(jié)點(diǎn)p的數(shù)據(jù)浪听。
實(shí)現(xiàn)代碼如下：

//初始條件:順序線性表L已存在,1 ≤ i ≤ ListLength(L)
//操作結(jié)果:用e返回L中第i個(gè)數(shù)據(jù)元素的值
Status GetElem(LinkList L,int i,ElemType *e)
{
    int j;
    LinkList p;//聲明一指針
    p = L->next;//讓p指向鏈表L的第一個(gè)結(jié)點(diǎn)
    j = 1;//j為計(jì)數(shù)器
    while(p && j < i)//p不為空且計(jì)數(shù)器j還沒有等于i時(shí)螟碎，循環(huán)繼續(xù)
    {
        p = p->next;//讓p指向下也結(jié)點(diǎn)
        ++j;
    }
    if(p || j > i)
        return ERROR;//第i個(gè)結(jié)點(diǎn)不存在
    *e = p->data;//取第i個(gè)結(jié)點(diǎn)的數(shù)據(jù)
    return OK;
}

說白了，就是從頭開始找迹栓，直到第i個(gè)結(jié)點(diǎn)為止掉分。由于這個(gè)算法復(fù)雜度取決于i的位置，當(dāng)i = 1時(shí)克伊，不需要變量酥郭，而當(dāng)i = n時(shí)則遍歷n - 1次才可以。因此最壞情況的時(shí)間復(fù)雜度是O(n)愿吹。

由于單鏈表的結(jié)構(gòu)沒有定義表長(zhǎng)不从，所以不知道事先循環(huán)多少次，因此也就不方便使用for來控制循環(huán)犁跪。其主要核心思想是“工作指針后移”椿息，這其實(shí)也是很多算法常用技術(shù)。

八坷衍、單鏈表的插入與刪除

1.單鏈表的插入

假設(shè)存儲(chǔ)元素e的結(jié)點(diǎn)為s寝优，要實(shí)現(xiàn)結(jié)點(diǎn)p、p->next和s之間的邏輯關(guān)系的變化枫耳，只需要將s插到結(jié)點(diǎn)p和p->next之間即可倡勇。
根本不需要驚動(dòng)其他結(jié)點(diǎn)，只需要讓s->next和p->next的指針做一點(diǎn)改變嘉涌。

//下面兩句不可交換順序
s->next = p->next;
p->next = s;

單鏈表第i個(gè)數(shù)據(jù)插入結(jié)點(diǎn)的算法思路：
1. 聲明一指針p指向鏈表頭結(jié)點(diǎn)妻熊，初始化j從1開始;
2. 當(dāng)j < i時(shí)，就遍歷鏈表仑最，讓p的指針向后移動(dòng)扔役，不斷指向下一結(jié)點(diǎn),j累加1
3. 若到鏈表末尾p為空，則說明第i個(gè)結(jié)點(diǎn)不存在;
4. 若查找成功警医，在系統(tǒng)中生成一個(gè)空節(jié)點(diǎn)s亿胸；
5. 將數(shù)據(jù)元素e賦給s->data；
6. 單鏈表的插入標(biāo)準(zhǔn)語句s->next = p->next; p->next = s;
7. 返回成功

實(shí)現(xiàn)代碼算法如下：

//初始條件:順序線性表L已存在,1≤i≤ListLength(L)
//操作結(jié)果:在L中第i個(gè)結(jié)點(diǎn)位置之前插入新的數(shù)據(jù)元素,L的長(zhǎng)度加1
Status ListInsert(LinkList *L , int i , ElemType e)
{
    int j = 1;
    LinkList p,s;
    p = *L;
    while( p && j < i) //尋找第I個(gè)結(jié)點(diǎn)
    {
        p = p->next;
        ++j;
    }
    if( !p || j > 1)
    {
        return ERROR;//第i個(gè)結(jié)點(diǎn)不存在
    }
    s = (LinkList)malloc(sizeof(Node));//生成新結(jié)點(diǎn)
    s->data = e;
    s->next = p->next;//將p的后繼結(jié)點(diǎn)賦值給s的后繼
    p->next = s;//將s賦給p的后繼
    return OK;
}

在這段算法代碼中预皇，我們用到了C語言的malloc標(biāo)準(zhǔn)函數(shù)侈玄，它的作用就是生成一個(gè)新的結(jié)點(diǎn)，其類型與Node是一樣的吟温，其實(shí)質(zhì)就是在內(nèi)存中開辟了一段空間序仙，用了存放數(shù)據(jù)e的s結(jié)點(diǎn)。

2.單鏈表的刪除

現(xiàn)在我們?cè)賮砜磫捂湵淼膭h除鲁豪。設(shè)存儲(chǔ)元素ai的結(jié)點(diǎn)為q潘悼，要實(shí)現(xiàn)將結(jié)點(diǎn)q刪除單鏈表的操作律秃，其實(shí)就是將它的前繼結(jié)點(diǎn)的指針繞過，指向他的后繼結(jié)點(diǎn)即可治唤。

我們所要做的棒动，實(shí)際上就是一步，p->next = p->next->next;宾添，用q來取代p->next即是：

q = p->next;
p->next = q->next;

也就是說把p的后繼結(jié)點(diǎn)改成p的后繼的后繼結(jié)點(diǎn)船惨。

單鏈表第i個(gè)數(shù)據(jù)刪除結(jié)點(diǎn)的算法思路：
1. 聲明一指針p指向鏈表頭指針，初始化j從1開始缕陕；
2. 當(dāng)j < i時(shí)掷漱，就遍歷鏈表，讓p的指針向后移動(dòng)榄檬，不斷指向下一個(gè)結(jié)點(diǎn)卜范，i累加1；
3. 若到鏈表末尾p為空鹿榜，則說明第i個(gè)結(jié)點(diǎn)不存在海雪；
4. 否則查找成功，將欲刪除的結(jié)點(diǎn)p->next 賦給q舱殿；
5. 單鏈表的刪除標(biāo)準(zhǔn)與p->next = q->next奥裸；
6. 將q結(jié)點(diǎn)中的數(shù)據(jù)賦給e，作為返回;
7. 釋放q結(jié)點(diǎn)
8. 返回成功

實(shí)現(xiàn)代碼算法如下：

//初始條件:順序線性表L已存在,1≤ i ≤ListLength(L)
//操作結(jié)果:刪除L的i個(gè)結(jié)點(diǎn),并用e返回其值,L的長(zhǎng)度減1
Status ListDelete(LinkList *L,int i,ElemType *e)
{
    int j;
    Link p,q;
    p = *L;
    j = 1;
    while(p->next && j < i)//遍歷尋找第i - 1個(gè)結(jié)點(diǎn)
    {
        p = p->next;
        ++j;
    }
    if( !(p->next) || j > i)
        return ERROR;//第i個(gè)結(jié)點(diǎn)不存在
    q = p->next;
    p->next = q->next;//將q的后繼賦給p的后繼
    *e = q->data;//將q結(jié)點(diǎn)中的數(shù)據(jù)給e
    free(q);//讓系統(tǒng)回收此結(jié)點(diǎn)沪袭，釋放內(nèi)存
    return OK;
}

分析一下剛才我們講解的單鏈表插入和刪除算法湾宙，我們發(fā)現(xiàn)，它們其實(shí)都是由兩部分組成：第一部分就是遍歷查找第i個(gè)結(jié)點(diǎn)冈绊；第二部分就是插入和刪除結(jié)點(diǎn)侠鳄。

從整個(gè)算法來說，我們很容易推導(dǎo)出：它們的時(shí)間復(fù)雜度都是O(n)死宣。
如果我們不知道第i個(gè)結(jié)點(diǎn)的指針位置伟恶，單鏈表數(shù)據(jù)結(jié)構(gòu)在插入和刪除操作上，與線下順序存儲(chǔ)結(jié)構(gòu)是沒有太大優(yōu)勢(shì)的毅该。但如果博秫，我們希望從第i個(gè)位置，插入10個(gè)結(jié)點(diǎn)眶掌，對(duì)于順序結(jié)構(gòu)意味著挡育，每次都要移動(dòng)n - i個(gè)結(jié)點(diǎn)，每次都是O(n)朴爬。而單鏈表即寒，我們只需在第一次時(shí)，找到第i個(gè)位置的指針，此時(shí)為O(n)蒿叠，接下來只是簡(jiǎn)單地通過賦值移動(dòng)指針而已，事件復(fù)雜度為O(1)蚣常。
顯然市咽，對(duì)于插入和刪除數(shù)據(jù)越頻繁的操作，單鏈表的優(yōu)勢(shì)就越明顯抵蚊。

八施绎、單鏈表的整表創(chuàng)建

順序存儲(chǔ)結(jié)構(gòu)的創(chuàng)建，其實(shí)就是一個(gè)數(shù)組的初始化贞绳，即聲明一個(gè)類型和大小的數(shù)組并賦值的過程谷醉。而單鏈表和順序存儲(chǔ)結(jié)構(gòu)就不一樣，它不像順序存儲(chǔ)結(jié)構(gòu)這么幾種冈闭，它可以很散俱尼，是一種動(dòng)態(tài)結(jié)構(gòu)。對(duì)于每個(gè)鏈表來說萎攒，它所占用空間的大小和位置使不需要預(yù)先分配劃定的遇八，可以根據(jù)系統(tǒng)的情況和實(shí)際的需求即可生成。

所以創(chuàng)建單鏈表的過程就是一個(gè)動(dòng)態(tài)生成鏈表的過程耍休。即從“空表”的初始狀態(tài)起刃永，一次建立各元素結(jié)點(diǎn)，并逐個(gè)插入鏈表羊精。
單鏈表整表創(chuàng)建的思路算法：

1. 聲明一指針p和計(jì)數(shù)器變量1斯够；

2. 初始化一空鏈表；

3. 讓L的頭結(jié)點(diǎn)的指針指向NULL喧锦，即建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表读规；

4. 循環(huán)：

   生成一新結(jié)點(diǎn)賦值給p;
   隨機(jī)生成一數(shù)字賦給p的數(shù)據(jù)域p->data;
   將p插到頭結(jié)點(diǎn)與前一個(gè)新節(jié)點(diǎn)之間的位置。

實(shí)現(xiàn)代碼如下：

//隨機(jī)產(chǎn)生n個(gè)元素的值燃少，建立帶表頭結(jié)點(diǎn)的單鏈表線性表L(頭插法)
void CreateListHead(LinkList *L,int n)
{
    LinkList p;
    int I;
    srand(time(0));//初始化隨機(jī)數(shù)種子
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;//先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表
    for(i = 0;i < n;i++)
    {
        p = (LinkList)malloc(sizoef(Node));//生成新的結(jié)點(diǎn)
        p->data = rand() % 100 + 1;//隨機(jī)生成100以內(nèi)的數(shù)字
        p->next = (*L)->next;
        (*L)->next = p; //插入到表頭
    }
}

這段代碼里掖桦，我們始終讓新結(jié)點(diǎn)在第一的位置上，我們把這種算法簡(jiǎn)稱為頭插法供汛。

可事實(shí)上枪汪，我們還可以把新結(jié)點(diǎn)放在最后。這才是排隊(duì)時(shí)的正常思維怔昨。我們每次新結(jié)點(diǎn)都插在終端結(jié)點(diǎn)的后面雀久，這種算法稱之為尾插。

實(shí)現(xiàn)代碼算法如下：

//隨機(jī)產(chǎn)生n個(gè)元素的值,建立帶表頭結(jié)點(diǎn)的單鏈線性表L(尾插法)
void CreateListTail(LinkList *L,int n)
{
    LinkList p,r;
    int I;
    srand(time(0));//初始化隨機(jī)數(shù)種子
    *L = (LinkList)malloc(sizeof(Node));//為整個(gè)線性表
    r = *L;//r為指向尾部的結(jié)點(diǎn)
    for(i = 0;i < n;i++)
    {
        p = (Node *)malloc(sizeof(Node));//生成新結(jié)點(diǎn)
        p->data = rand() % 100 + 1;//隨機(jī)生成100以內(nèi)的數(shù)字
        r->next = p;//將表尾終端結(jié)點(diǎn)的指針指向新結(jié)點(diǎn)
        r = p; //就那個(gè)當(dāng)前新結(jié)點(diǎn)定義為表尾終端結(jié)點(diǎn)
    }
    r->next = NULL;//表示當(dāng)前鏈表結(jié)束
}

注意L與r的關(guān)系趁舀，L指整個(gè)單鏈表赖捌，而r指向尾節(jié)點(diǎn)的變量，r會(huì)隨著循環(huán)不斷地變化結(jié)點(diǎn)，而L則是隨著循環(huán)增長(zhǎng)為一個(gè)多結(jié)點(diǎn)的鏈表越庇。

這里需要解釋一下罩锐，r->next = p的意思，其實(shí)就是將剛才的表尾終端結(jié)點(diǎn)r的指針指向新結(jié)點(diǎn)p卤唉。

九涩惑、單鏈表的整表刪除

當(dāng)我們不打算使用這個(gè)單鏈表時(shí)，我們需要把它銷毀桑驱，其實(shí)也就是在內(nèi)存中將它釋放掉竭恬，以便于留出空間給其他程序或軟件使用。

單鏈表整表刪除的算法思路如下：
1. 聲明一結(jié)點(diǎn)p和q熬的；
2. 將第一個(gè)結(jié)點(diǎn)賦值給p痊硕；
3. 循環(huán)
將下一結(jié)點(diǎn)賦值給q;
釋放p;
將q賦值給p。

實(shí)現(xiàn)代碼算法如下:

//初始條件:順序線性表L已經(jīng)存在押框，操作結(jié)果：將L重置為空表
Status ClearList(LinkList *L)
{
    LinkList p,q;
    p = (*L)->next;//p指向第一個(gè)結(jié)點(diǎn)
    while(p)//沒到表尾
    {
        q = p->next;
        free(p);
        p = q;
    }
    (*L)->next = NULL;//頭結(jié)點(diǎn)指針域?yàn)榭?    return OK;
}

十岔绸、單鏈表結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)優(yōu)缺點(diǎn)

簡(jiǎn)單地對(duì)單鏈表結(jié)構(gòu)和順序存儲(chǔ)結(jié)構(gòu)作對(duì)比。
1橡伞、存儲(chǔ)分配方式：
順序存儲(chǔ)結(jié)構(gòu)有一段連續(xù)的存儲(chǔ)單元依然存儲(chǔ)線性表的數(shù)據(jù)元素亭螟。
單鏈表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，用一組任意的存儲(chǔ)單元存放線性表的玩意骑歹。

2预烙、時(shí)間性能：
查找：

• 順序存儲(chǔ)結(jié)構(gòu)O(1)
• 單鏈表O(n)

插入與刪除

• 順序存儲(chǔ)結(jié)構(gòu)需要平均移動(dòng)表長(zhǎng)一半的元素，時(shí)間為O(n)
• 單鏈表在線出某位置的指針后道媚，插入和刪除時(shí)間僅為O(1)

3扁掸、空間性能

• 順序存儲(chǔ)結(jié)構(gòu)需要預(yù)分配存儲(chǔ)空間，分大了最域，浪費(fèi)谴分，分小了易發(fā)生上溢。
• 單鏈表不需要分配存儲(chǔ)空間镀脂，只要有就可以分配牺蹄，元素個(gè)數(shù)也不受限制。

通過上面的對(duì)比薄翅，我們可以得出一些經(jīng)驗(yàn)性的結(jié)論：

①
若線性表需要頻繁查找沙兰，很少進(jìn)入插入和刪除操作時(shí)，宜采用順序存儲(chǔ)結(jié)構(gòu)翘魄。
若需要頻繁插入和刪除時(shí)鼎天，宜采用單鏈表結(jié)構(gòu)。
比如游戲開發(fā)中暑竟，對(duì)于用戶注冊(cè)的個(gè)人信息斋射，除了注冊(cè)時(shí)插入數(shù)據(jù)外，絕大多數(shù)情況下都是讀取，所以應(yīng)該考慮用順序存儲(chǔ)結(jié)構(gòu)罗岖。而游戲中的玩家的武器或者裝備列表涧至，隨著玩家游戲過程中，可能隨時(shí)增加或刪除桑包，此時(shí)應(yīng)該用單鏈表比較合適南蓬。當(dāng)然，這只是簡(jiǎn)單地類比〖穸啵現(xiàn)實(shí)生活中的軟件開發(fā)蓖康，要考慮的問題會(huì)復(fù)雜得多铐炫。

②當(dāng)線性表中的元素個(gè)數(shù)變化較大或者根本不知道有多大時(shí)垒手，最好用單鏈表結(jié)構(gòu)，這樣可以不用考慮存儲(chǔ)空間大小問題倒信。
而如果事先知道線性表的大致長(zhǎng)度科贬，比如一年12個(gè)月，這種用順序存儲(chǔ)結(jié)構(gòu)效率會(huì)高很多鳖悠。

總之榜掌，線性表的順序存儲(chǔ)結(jié)構(gòu)和單鏈表結(jié)構(gòu)各有其優(yōu)點(diǎn)，不是簡(jiǎn)單地說哪個(gè)不好乘综，需要根據(jù)實(shí)際情況憎账，來綜合平衡采用哪種數(shù)據(jù)更能滿足和達(dá)到需求和性能。

十一卡辰、靜態(tài)鏈表

C語言具有指針能力胞皱，使得它可以非常容易地操作內(nèi)存中的地址和數(shù)據(jù)，這比其他高級(jí)語言更加方便靈活九妈。
后來的面向?qū)ο笳Z言反砌，如Java、C#等萌朱，雖不使用指針宴树，但因?yàn)閱⒂昧藢?duì)象引用機(jī)制，從某種角度上也間接實(shí)現(xiàn)了指針的某些作用晶疼。但對(duì)于一些語言酒贬，如Basic、Fortran等早期的編程高級(jí)語言翠霍，由于沒有指針同衣，鏈表結(jié)構(gòu)就沒辦法實(shí)現(xiàn)。

有人想出用數(shù)組來代替指針壶运，來描述鏈表耐齐。

首先我們用數(shù)組的元素都是由兩個(gè)數(shù)據(jù)域組成，data和cur。也就是說埠况，數(shù)組的每個(gè)下表都對(duì)應(yīng)一個(gè)data和一個(gè)cur耸携。數(shù)據(jù)域data，用來存放數(shù)據(jù)元素辕翰，也就是通常我們要處理的數(shù)據(jù)夺衍；而cur相當(dāng)于單鏈表中的next指針，存放該元素后繼在數(shù)組中的下表喜命，我們把cur叫做游標(biāo)沟沙。

我們把這種用數(shù)組描述的鏈表叫靜態(tài)鏈表，這種描述方法還有起名叫做游標(biāo)實(shí)現(xiàn)法壁榕。

為了我們方便插入數(shù)據(jù)矛紫，我們通常會(huì)把數(shù)組建立得大一些，以便有一些空閑空間可以方便插入不至于溢出牌里。

//線性表的靜態(tài)鏈表存儲(chǔ)結(jié)構(gòu)
#define MAXSIZE 1000//假設(shè)鏈表的最大長(zhǎng)度1000
typedef struct
{
    ElemType data;
    int cur;//游標(biāo)(Cursor),為0時(shí)表示無指向
}Component,StaticLinkList[MAXSIZE];

另外我們對(duì)數(shù)組的第一個(gè)和最后一個(gè)元素作為特殊元素處理颊咬，不存數(shù)據(jù)。我們通常把未被使用的數(shù)組元素稱為備用鏈表牡辽。而數(shù)組第一個(gè)元素喳篇，即下標(biāo)為0的元素的cur就存放備用鏈表的第一個(gè)結(jié)點(diǎn)的下表;而數(shù)組的最后一個(gè)元素的cur則存放第一個(gè)有數(shù)值的元素的下表，相當(dāng)于單鏈表中的頭結(jié)點(diǎn)作用态辛，當(dāng)整個(gè)鏈表為空時(shí)麸澜，則為02。

//將一維數(shù)組space中個(gè)分量鏈成一備用鏈表
//space[0].cur為頭指針奏黑，"0"表示空指針
Status InitList(StaticLinkList space)
{
    int I;
    for(i = 0;i < MAXSIZE - 1;i++)
        space[i].cur = i + 1;
    space[MAXSIZE - 1].cur = 0;//目前靜態(tài)鏈表為空
    return OK;
}

1.靜態(tài)鏈表的插入操作

靜態(tài)鏈表中要解決的是：如何用靜態(tài)模擬動(dòng)態(tài)鏈表結(jié)構(gòu)的存儲(chǔ)空間的分配炊邦，需要時(shí)申請(qǐng)，不需要時(shí)釋放攀涵。

我們前面說過铣耘，在動(dòng)態(tài)鏈表中，結(jié)點(diǎn)的申請(qǐng)和釋放分別借用malloc()和free()兩個(gè)函數(shù)來實(shí)現(xiàn)以故。在靜態(tài)鏈表中蜗细，操作的是數(shù)組，不存在像動(dòng)態(tài)鏈表一樣的申請(qǐng)和釋放問題怒详，所以我們需要自己實(shí)現(xiàn)這兩個(gè)函數(shù)炉媒。

為了辨明數(shù)組中哪些分量未被使用，解決的辦法是將所有未被使用過的以及已被刪除的分量用游標(biāo)鏈成一個(gè)備用的鏈表昆烁，每當(dāng)進(jìn)行插入時(shí)吊骤，便可從備用鏈表上取得第一個(gè)結(jié)點(diǎn)作為待插入的新結(jié)點(diǎn)。

//若備用空間鏈表為空静尼，則返回分配的結(jié)點(diǎn)下表白粉，否則返回0
int Malloc_SLL(StaticLinkList space)
{
    int i = space[0].cur;//當(dāng)前數(shù)組的第一個(gè)元素的Cur存的值
    if(space[0].cur)
    {
        space[0].cur = space[i].cur;//由于要拿出一個(gè)分量來使用
                        //所以我們,就得把它的下一個(gè)分量用作備用
    }
    return I;
}

插入元素

//在L中第i個(gè)元素之前插入新的數(shù)據(jù)元素e
Status ListInsert(StaticLinkList L, int i,ElemType e)
{
    int j,k,l;
    k = MAX_SIZE - 1;//注意k首先是最后一個(gè)元素的下表
    if(i < 1 || i > ListLength(L) + 1)
        return ERROR;
    j = Malloc_SSL(L);//獲得空閑分量的下標(biāo)
    if(j)
    {
        L(j).data = e;//將數(shù)據(jù)賦值給此分量的下表
        for(l = 1;l <= i - 1;l++)//相當(dāng)于循環(huán)鏈表传泊，找到第i-1位
        {
            k = L[k].cur;
        }
        L[j].cur = L[k].cur;//新的第i個(gè)元素元素指向原本第i個(gè)元素
        L[k].cur = j;//第i - 1個(gè)元素指向新的第i個(gè)元素
        return OK;
    }
    return ERROR;
}

就這樣，我們實(shí)現(xiàn)了在數(shù)組中鸭巴，實(shí)現(xiàn)不移動(dòng)元素眷细，卻插入了數(shù)據(jù)的操作。

2.靜態(tài)鏈表的刪除操作

和前面一樣鹃祖，刪除元素時(shí)溪椎，原來是需要釋放結(jié)點(diǎn)的函數(shù)free()。我們也要自己實(shí)現(xiàn)它恬口。

//刪除在L中第i個(gè)數(shù)據(jù)元素e
Status ListDelete(StaticLinkList L,int i)
{
    int j , k;
    if(i < 1 || i > ListLength(L))
        return ERROR;
    k = MAX_SIZE - 1;
    for(j = 1;j < = i - 1;j++)//相當(dāng)于遍歷鏈表
    {
        k = L[k].cur;
    }
    j = L[k].cur;//把要?jiǎng)h除的數(shù)組下標(biāo)賦值給j
    Free_SLL(L,j);//調(diào)用刪除函數(shù)
    return OK;
}

//將下表為k的空閑結(jié)點(diǎn)回收到備用鏈表
void Free_SSL(StaticLinkList space,int k)
{
   space[k] = space[0].cur;//把原來第一位指向的下標(biāo)賦給新第一位
   space[0].cur = k;//要?jiǎng)h除的分量賦給第一個(gè)元素cur
}

靜態(tài)鏈表也就是相應(yīng)其他操作的相關(guān)實(shí)現(xiàn)校读。比如ListLength

//初始條件:靜態(tài)鏈表L已存在。操作結(jié)果:返回L中數(shù)據(jù)元素個(gè)數(shù)
int ListLength(StaticLinkList L)
{
    int j = 0;
    int i = L[MAXSIZE - 1].cur;
    while(i)
    {
        i = L[i].cur;
        j++;
    }
    return j;
}

3.靜態(tài)鏈表優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：在插入和刪除操作時(shí)祖能，只要修改游標(biāo)歉秫，不需要移動(dòng)元素，從而改進(jìn)了在順序存儲(chǔ)結(jié)構(gòu)中的插入和刪除操作需要移動(dòng)大量元素的缺點(diǎn)芯杀。

缺點(diǎn)：
①?zèng)]有解決連續(xù)存儲(chǔ)分配帶來表長(zhǎng)難以確定的問題
②失去了順序存儲(chǔ)結(jié)構(gòu)隨機(jī)存儲(chǔ)的特性

十二端考、循環(huán)鏈表

對(duì)于單個(gè)鏈表雅潭，由于每個(gè)結(jié)點(diǎn)只存儲(chǔ)了向后的指針揭厚，到了尾標(biāo)志就停止了向后鏈的操作，這樣當(dāng)中某一結(jié)點(diǎn)就無法找到它的前驅(qū)結(jié)點(diǎn)了扶供。

將單鏈表中終端結(jié)點(diǎn)的指針由空指針改為指向頭結(jié)點(diǎn)筛圆，就使整個(gè)單鏈表形成一個(gè)環(huán)， 這種頭尾相接的單鏈表稱為單循環(huán)鏈表椿浓，簡(jiǎn)稱循環(huán)鏈表太援。

循環(huán)鏈表解決了一個(gè)很麻煩的問題，如何從當(dāng)中一個(gè)結(jié)點(diǎn)出發(fā)扳碍，訪問到鏈表的全部結(jié)點(diǎn)提岔。

循環(huán)鏈表和單鏈表的主要差異就是在于循環(huán)的判斷條件上，原來是判斷p->next是否為空笋敞，現(xiàn)在則是p->next不等于頭結(jié)點(diǎn)碱蒙，則循環(huán)未結(jié)束。

十三夯巷、雙向鏈表

在單鏈表中赛惩，有了next指針，這就使得我們要查找下一結(jié)點(diǎn)的事件復(fù)雜度為O(1)趁餐∨缂妫可是如果我們要查找的是上一節(jié)點(diǎn)的話，那最壞的時(shí)間復(fù)雜度就是O(n)了后雷，因?yàn)槲覀兠看味家獜念^開始遍歷尋找季惯。

為了克服單向性這一缺點(diǎn)吠各，設(shè)計(jì)出了雙向鏈表。雙向鏈表(double linked list)是在單鏈表的每個(gè)結(jié)點(diǎn)中勉抓，再設(shè)置一個(gè)指向其前驅(qū)結(jié)點(diǎn)的指針域走孽。所以在雙向鏈表中的結(jié)點(diǎn)都有兩個(gè)指針域，一個(gè)指向直接后繼琳状，一個(gè)指向直接前驅(qū)磕瓷。

//線性表的雙向鏈表存儲(chǔ)結(jié)構(gòu)
typedef struct DulNode
{
    ElemType data;
    struct DuLNode *prior;//直接前驅(qū)指針
    struct DuLNode *next;//直接后繼指針
}DulNode,*DuLinkList;

既然單鏈表可以有循環(huán)，那么雙向鏈表當(dāng)然可以是循環(huán)表念逞。

由于是雙向鏈表困食，對(duì)于鏈表中某一結(jié)點(diǎn)p，它的后繼的前驅(qū)是它自己翎承。它的前驅(qū)的后繼自然也是它自己硕盹。即：

p->next->prior = p = p->prior->next

插入操作時(shí)，其實(shí)并不復(fù)雜叨咖，但是順序很重要瘩例。
假設(shè)存儲(chǔ)元素e的結(jié)點(diǎn)為s，要實(shí)現(xiàn)將結(jié)點(diǎn)s插入到p和p->next之間需要下面幾部甸各。

s->prior = p;//把p賦給s的前驅(qū)
s->next = p->next;//把p->next賦給s的后繼
p->next->prior = s;//把s賦給p->next的前驅(qū)
p->next = s;//把s賦給p的后繼

如要?jiǎng)h除結(jié)點(diǎn)p垛贤，只要下面兩步驟。

p->prior->next = p->next;//把p->next賦給p->prior的后繼
p->next->prior = p->prior;//把p->proir賦給p->next的前驅(qū)
free(p);//釋放p的空間

雙向鏈表對(duì)于單鏈表來說趣倾，要更復(fù)雜一些聘惦，對(duì)于插入和刪除時(shí)，需要小心儒恋。
另外由于它每個(gè)結(jié)點(diǎn)需要幾輪兩份指針善绎，所以在空間上是要占用略多一些的。不過由于良好的對(duì)稱性诫尽，使得對(duì)某個(gè)結(jié)點(diǎn)的前后結(jié)點(diǎn)的操作禀酱，帶來了方便，可以有效提高算法的時(shí)間性能牧嫉。

說白了剂跟，也就是空間換時(shí)間。