考研數(shù)據(jù)結(jié)構(gòu)筆記——2.線性表的鏈?zhǔn)奖硎荆◤?fù)雜鏈表）

雙鏈表

單鏈表存在的不足是，由于其結(jié)點(diǎn)中只有一個(gè)指向其后繼結(jié)點(diǎn)的指針，導(dǎo)致單鏈表只能從頭結(jié)點(diǎn)依次向后遍歷；如果要訪問某個(gè)結(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)，則必須從頭開始遍歷；訪問后繼結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(1)，訪問前驅(qū)結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(n)

為了克服單鏈表訪問前驅(qū)節(jié)點(diǎn)的時(shí)間復(fù)雜度缺陷，引入了雙鏈表；雙鏈表結(jié)點(diǎn)中有兩個(gè)指針prior和next，分別指向其前驅(qū)節(jié)點(diǎn)和后繼結(jié)點(diǎn)

雙鏈表中的結(jié)點(diǎn)類型描述如下

typedef struct DNode{
    Elemtype data;
    struct DNode *prior,*next;
}DNode,DLinklist;

雙鏈表插入、刪除操作的時(shí)間復(fù)雜度均為O(1)

雙鏈表的插入操作

在雙鏈表中p所指的結(jié)點(diǎn)之后插入結(jié)點(diǎn)*s，代碼片段如下

1 s->next = p->next;
2 p->next->prior = s;
3 s->prior = p;
4 p->next = s;

p->next必須在1、2兩句之后更改，4句p->next的內(nèi)容已經(jīng)發(fā)生變化，因此1、2兩句必須在4句之前

雙鏈表的刪除操作

刪除雙鏈表中結(jié)點(diǎn) *p的后繼結(jié)點(diǎn) *q，步驟類似于單鏈表

p->next = q->next;
q->next-prior = p;
free(q);

循環(huán)鏈表

循環(huán)單鏈表和單鏈表的區(qū)別在于，循環(huán)鏈表最后一個(gè)結(jié)點(diǎn)的指針域不是向單鏈表一樣為NULL，而是指向鏈表的頭結(jié)點(diǎn)，從而使整個(gè)鏈表形成一個(gè)環(huán)

循環(huán)單鏈表的表尾結(jié)點(diǎn)指向頭結(jié)點(diǎn)，因此它的判空條件不是頭結(jié)點(diǎn)的指針是否為空，而是頭結(jié)點(diǎn)的指針域是否等于頭指針；循環(huán)鏈表是一個(gè)“環(huán)”，因此循環(huán)鏈表在任何一個(gè)位置上的插入、刪除操作都是等價(jià)的，無需判斷是否表尾，也可以從任意一個(gè)結(jié)點(diǎn)來遍歷鏈表

有時(shí)對(duì)單鏈表的操作經(jīng)常是在表頭和表尾進(jìn)行的，因此對(duì)循環(huán)單鏈表不設(shè)頭指針只設(shè)尾指針；原因在于，如果設(shè)頭指針，則對(duì)表尾進(jìn)行操作需要O(n)的復(fù)雜度；而如果設(shè)尾指針為r，則r->next即為頭指針，對(duì)于表頭和表尾操作均只需O(1)的復(fù)雜度

在循環(huán)雙鏈表中，尾結(jié)點(diǎn)的next要指向頭結(jié)點(diǎn)，而頭結(jié)點(diǎn)的prior要指向表尾結(jié)點(diǎn)；當(dāng)循環(huán)雙鏈表為空表時(shí)，其頭結(jié)點(diǎn)的prior和next域都等于它本身

靜態(tài)鏈表

靜態(tài)鏈表借助數(shù)組來描述線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)；結(jié)點(diǎn)也有數(shù)據(jù)域data和指針域next，但這里的指針指的是結(jié)點(diǎn)的相對(duì)地址，即數(shù)組下標(biāo)（游標(biāo)）

和順序表一樣，靜態(tài)鏈表也要預(yù)先分配一塊連續(xù)的內(nèi)存空間；靜態(tài)鏈表結(jié)構(gòu)類型的描述如下

#define MaxSize 50  //靜態(tài)鏈表的最大長(zhǎng)度
typedef struct{
    ElemType data;
    int next;
}SLinkList MaxSize;

靜態(tài)鏈表以next = -1作為其結(jié)束的標(biāo)志；靜態(tài)鏈表的插入、刪除操作與動(dòng)態(tài)鏈表相同

順序表與鏈表的比較

1. 存取方式。順序表可以順序存取，也可以隨機(jī)存??；單鏈表只能從表頭順序存取元素
2. 邏輯結(jié)構(gòu)與物理結(jié)構(gòu)。采用順序存儲(chǔ)時(shí)，邏輯上相鄰的元素，物理上也相鄰；而采用鏈?zhǔn)酱鎯?chǔ)時(shí)，邏輯上相鄰的元素物理上不一定相鄰，通過鏈表來連接其邏輯關(guān)系
3. 查找、插入與刪除操作。對(duì)于按值查找，在順序表（數(shù)據(jù)）無序時(shí)，順序表和鏈表的時(shí)間復(fù)雜度均為O(n)，順序表有序時(shí)，采用二分查找，時(shí)間復(fù)雜度為O(log(2)n);對(duì)于按序號(hào)查找，順序表由于支持隨機(jī)訪問，時(shí)間復(fù)雜度為O(1)，鏈表的平均時(shí)間復(fù)雜度為O(n);順序表的插入、刪除操作，平均要移動(dòng)半個(gè)表長(zhǎng)的元素，鏈表的插入、刪除操作，只需修改相關(guān)結(jié)點(diǎn)的指針域；鏈表的每個(gè)結(jié)點(diǎn)都帶有指針域，因此存儲(chǔ)空間上付出的代價(jià)較大，而存儲(chǔ)密度不夠大
4. 空間分配。順序存儲(chǔ)在靜態(tài)分配情景下，一旦分配就不能再擴(kuò)充，而預(yù)先分配過大又會(huì)導(dǎo)致大量空間閑置，動(dòng)態(tài)分配雖然可以擴(kuò)充，但是需要分配大量元素、分配效率低，并且內(nèi)存中如果沒有大塊的內(nèi)存空間，還會(huì)導(dǎo)致分配失?。绘?zhǔn)酱鎯?chǔ)的結(jié)點(diǎn)空間只在申請(qǐng)時(shí)分配，只要內(nèi)存有空間就可以分配，操作靈活、高效