知識回顧
? ? ? ? 在前面的學習中，我們已經了解到了鏈表（線性表的鏈式存儲）的一些基本特點，并且深入的研究探討了單鏈表的一些特性，我們知道，單鏈表在實現插入刪除上，是要比順序表方便的，但是，單鏈表中每個結點僅存在一個指針指向其后續(xù)結點，那么如果我們想要找到其前面的節(jié)點，則需要從頭部開始遍歷，這是十分不方便的；那么，是不是對其添加一些元素或特性，使其的操作更加簡單呢？那么我們就來看下這節(jié)將要學習的一些鏈表。?
雙鏈表
? ? ? ? 我們知道，單鏈表中每個結點只有一個指向其后續(xù)的指針，這邊可以使得單鏈表可以從前往后的遍歷整個鏈表，但如果我們想要去訪問某個結點的前驅節(jié)點時，則需要從頭開始遍歷，這樣就會消耗較多的時間；那么為了解決這一問題我們引入雙鏈表。
?????????我們不難觀察到，雙鏈表則是在單鏈表的基礎上，在結點中又添加了一個指針，用于指向該結點的前驅結點，那么這樣的話，我們也就可以通過一個結點很好的去查詢其前驅和后繼結點了，雖然我們增加了存儲密度，但在對鏈表的操作上就更加的靈活。
結點初始化：
typedef struct DNode{
int data ;
struct DNode *prior, *next ;
}DNode, *DLinkList;雙鏈表的插入
? ? ? ? 實際上，雙鏈表的插入是類似于單鏈表的插入的，只不過，由于雙鏈表存在指向后續(xù)結點以及前驅結點的指針，所以在進行插入操作時，我們需要對這兩個指針分別進行類似的操作即可。
? ? ? ? 如圖所示，我們若要在雙鏈表中插入x，那么我們首先需要讓x結點的后續(xù)指針指向插入位置后結點，之后再將插入位置后結點（c）的前驅指針指向x；之后再讓x結點的前驅指針指向插入位置的前驅結點（a），之后再將插入位置的前驅結點（a）的后繼指針指向x；這樣我們就成功的將x插入到鏈表之中了。
????????需要思考的是，當我們的插入位置為鏈表的末尾時，我們應該怎么去操作呢？這當然也不難操作，通過對雙鏈表的觀察，我們知道，在其末尾結點的后續(xù)結點會指向NULL;那么這時就不會存在一個后面的結點指向末尾結點了，也就是說，在之前我們的結點是存在兩個指向結點的箭頭和兩個指出的箭頭；但到了末尾就缺少一個指向的箭頭。
? ? ? ? 知道了這層差異，那么我們就要對其進行相應的處理，首先我們需要判斷我們插入位置前的結點是否指向NULL，當其指向NULL時，則證明我們插入的為末尾結點，這里我們對前續(xù)的操作不變，只不過在對其后續(xù)操作時，我們只需要讓其指向NULL（也就前末結點指向的位置）即可，不需要進行指向插入結點的操作。
? ? ? ? 當然，插入首位的方法也同上所示，只不過從特殊處理后續(xù)操作轉變?yōu)樘厥馓幚砬膀尣僮骷纯伞?/p>
//插入
bool InsertNextDNode(DNode *p, DNode *s) {
if(p == NULL || s == NULL) return false;
s->next = p->next;
if(p->next != NULL) {
p->next->prior = s;
}
p->next = s;
s->prior = p;
return true;
}雙鏈表的刪除
? ? ? ? 對于刪除操作，其原理也與單鏈表的操作類似，只不過其具有兩個指針，所以我們需要更改兩個指針的指向即可。
? ? ? ? 對于雙倆表的刪除操作，例如我們需要刪除b結點，那么我們只需要讓a的后續(xù)指針指向c（b后續(xù)指針指向位置），讓c的前驅指針指向a（b前驅指針指向位置），這樣我們就可以刪除b結點了。
? ? ? ? 例如：刪除p指針后的結點b。
p->next=q->next;
q->next->prior=p;
free(q);
? ? ? ? 當然，刪除前驅結點的方法也與之類似，我們更改其相應的指針指向即可。
? ? ? ? 那我們如果刪除的結點位于雙鏈表的頭部或者尾部呢？這樣對于我們的操作是否存在什么影響？下面我們來看一下：（在這里我們以末結點為例，實際上頭結點刪除方法與其類似）
?
? ? ? ? 當我們遇到尾結點時，由于我們末尾元素后指向NULL，所以其不存在一個指向前的指針，也就是說，如果我們想要刪除末尾元素的話，我們就只需要讓其前面的元素結點向后指向NULL即可，之后再釋放我們想要刪除的末尾結點，就可以解決這種問題了。
//刪除(p后的節(jié)點）
bool DeleteNextDNode(DNode *p) {
if(p == NULL) return false;
DNode *q = p->next;
if(q == NULL) return false;
p->next = q->next;
if(q->next != NULL) q->next->prior = p;
free(q);
return true;
}
雙鏈表的遍歷?
? ? ? ? 至于遍歷雙鏈表這里由于我們前面的學習，這部分的內容就十分的簡單了。我們就像單鏈表遍歷一樣，通過頭指針或頭結點開始從頭部或者我們所指定的某一點，以此遍歷其next指針，直到其指向NULL為止，那么這樣我們是不是就可以成功的從頭部遍歷一遍鏈表了呢！
? ? ? ? 乍一聽，這與單鏈表是沒什么不同的，但由于我們雙鏈表是一個結點存在兩個指針的（也就是指向前的prior以及指向后續(xù)的next）指針，所以我們在進行遍歷的時候，也就可以去嘗試更多的遍歷方法了，我們可以嘗試從后向前遍歷。
? ? ? ? 這與前面的從前向后遍歷并沒有什么不同，只是我們需要從尾部向頭部遍歷的時候需要不停的訪問改結點的prior指針，直到其指向NULL為止。
//遍歷
//從前向后遍歷
void PriorFindList(DLinkList L) {
DNode *p = L->next;
while(p != NULL) {
cout << p->data << " " ;
p = p->next;
}
cout << endl;
}
//從后向前遍歷
void AfterFindList(DLinkList L) {
DNode *p = L;
while(p->next != NULL) {
p = p->next;
}
while(p!=L) {
cout << p->data << " " ;
p = p->prior;
}
cout << endl;
}循環(huán)鏈表
? ? ? ? 循環(huán)鏈表又可以分為循環(huán)單鏈表和循環(huán)雙鏈表。其原理是十分相同的。
循環(huán)單鏈表
? ? ? ? 通過圖我們不難看出，上面的鏈表是我們已經討論過多次的單鏈表，其尾結點指針指向NULL，那么我們怎么使其變成循環(huán)鏈表呢？
? ? ? ? 循環(huán)、循環(huán)，顧名思義，就是當我們訪問某一序列最后一個元素時，緊接著我們就可以以相同的操作去訪問該序列第一個元素；在這里對于鏈表也是相同的：也就是當我們訪問的某鏈表的尾結點時，我們依舊可以通過常規(guī)的訪問該結點的next指針的方法去訪問到該鏈表的頭結點。
? ? ? ? 那么這樣我們的思路就十分清晰了，我們就只需要在創(chuàng)立鏈表時，使其的末結點的next指針指向該鏈表的頭結點，這樣我們就可以很輕松的實現循環(huán)單鏈表了。
? ? ? ? 那么我們?yōu)槭裁匆獙W習單鏈表呢？?
? ? ? ? 如果我們只是使用單鏈表，當我們有某一結點的位置時，我們可以通過單鏈表的特性去合理的訪問到其后面的各個結點；但其前面的結點對于我們來說就是未知的了。
? ? ? ? 為了解決這個問題，我們就可以引入循環(huán)單鏈表，這樣我們在得到某一結點位置后，我們依次訪問最終就可以成功的訪問到該鏈表頭結點，那么我們指定結點前的區(qū)域就不再是未知的了。
?
? ? ? ? ?在引入循環(huán)鏈表時，我們就可以設立一個尾指針，甚至說尾指針在這里要比頭指針更加的方便！我們不難知道，對于頭指針來說訪問鏈表頭部需要O(1)的時間復雜度、訪問尾部時需要O(n)的時間復雜度。但對于循環(huán)單鏈表的話，我們就可以使用O(1)的時間復雜度訪問其頭結點和尾結點，對于尾結點沒什么好說的，因為其就指向尾結點我們直接訪問即可；但對于頭結點我們在訪問時僅僅需要訪問尾結點的next指針，由于其是循環(huán)的，所以我們就可以僅用O(1)的時間復雜度就訪問到了頭結點，這無疑來說節(jié)省了很多時間。那么同理，我們在遇到某些操作中包含需要查找尾結點的操作時，這樣都可以節(jié)省其時間。
循環(huán)雙鏈表?
? ? ? ? 如上圖中上方的鏈表一樣，該鏈表是剛才我們已經了解過的雙鏈表；那么其循環(huán)雙鏈表的建立實際上是類似于循環(huán)單鏈表的；只不過需要注意的是，由于我們的雙鏈表的每個結點是有兩個指針的，所以我們在使其尾部指向頭部時，也要去更改頭部的prior指針，使其指向鏈表的尾，這樣我們就可以實現循環(huán)雙鏈表了。
? ? ? ? ?這里，由于循環(huán)鏈表于前面的單雙鏈表相似，所以這里就不給出其完整代碼實現了，實際上我們只需對一些地方的代碼進行特定的修改就可以得到該循環(huán)鏈表的代碼了。
靜態(tài)鏈表
? ? ? 通過前面的學習，我們知道，單鏈表各個結點的存儲，在我們計算機的內存中是完全隨機雜亂的，我們需要通過指針去link（連接）這些結點；那么我們可不可以在內存中申請一塊連續(xù)的存儲空間，去進行存儲這個鏈表呢？
? ? ? ? 當然這乍一聽與數組十分的相似，只不過我們需要通過這一連續(xù)的存儲空間去實現鏈表的功能，也就是需要通過next"指針"去指向后續(xù)節(jié)點。
? ? ? ? 那么這里我們就可以參考數組，我們將結點劃分為存數據的data和存下一位置的數組下標next；這樣我們在存入一個元素時首先判斷該數組位置是否已存入數據，若沒有存入數據的話，我們將其存入，并將上一尾結點的next更新為該結點的數組下標。
? ? ? ? 這里我們通過next去串聯(lián)數組的下標，進而實現鏈表功能。
? ? ? ? ? 例如上圖所示，我們可以將結點的data默認初始化為 -2 (也就是說，當我們在某結點進行存入數據時，可以判斷下其next是否為-2，若不是-2則說明該結點已經存在元素)，那么我們觀察圖中鏈表，可以看出這里我們:頭->數組[2]->數組[1]->數組[6]->數組[3]->-1;-1則表明到達了尾部。
優(yōu)點：增、刪 操作不需要大量移動元素 缺點：不能隨機存取，只能從頭結點開始依次往后查 找；容量固定不可變
適用場景：①不支持指針的低級語言；②數據元素數 量固定不變的場景（如操作系統(tǒng)的文件分配表FAT）
代碼
雙鏈表代碼
// 2.4 雙鏈表 #include <bits/stdc++.h> using namespace std ; typedef struct DNode{ int data ; struct DNode *prior, *next ; }DNode, *DLinkList; //初始化 bool InitDLinkList(DLinkList &L) { L = (DNode *)malloc(sizeof(DNode)) ; if(L == NULL) return false ; //分配失敗 L->next = NULL; L->prior = NULL; return true; } //尾插法建立 DLinkList DList_TailInsert(DLinkList &L) { int x; cin >> x; DNode *s, *r = L; while(x!=9999) { s = (DNode *)malloc(sizeof(DNode)) ; s->data = x; r->next = s; s->prior = r; r = s; cin >> x; } r->next = NULL; return L; } //插入 bool InsertNextDNode(DNode *p, DNode *s) { if(p == NULL || s == NULL) return false; s->next = p->next; if(p->next != NULL) { p->next->prior = s; } p->next = s; s->prior = p; return true; } //刪除(p后的節(jié)點） bool DeleteNextDNode(DNode *p) { if(p == NULL) return false; DNode *q = p->next; if(q == NULL) return false; p->next = q->next; if(q->next != NULL) q->next->prior = p; free(q); return true; } //銷毀 void DestoryList(DLinkList &L) { while(L->next != NULL){ DeleteNextDNode(L); } free(L); L=NULL; } //遍歷 //從前向后遍歷 void PriorFindList(DLinkList L) { DNode *p = L->next; while(p != NULL) { cout << p->data << " " ; p = p->next; } cout << endl; } //從后向前遍歷 void AfterFindList(DLinkList L) { DNode *p = L; while(p->next != NULL) { p = p->next; } while(p!=L) { cout << p->data << " " ; p = p->prior; } cout << endl; } int main() { DLinkList L; InitDLinkList(L); DList_TailInsert(L); PriorFindList(L); AfterFindList(L); DNode *p, *s; p = L; s = L; for(int i=0; i<=3; i++) p = p->next; //刪去第五個值 DeleteNextDNode(p); PriorFindList(L); AfterFindList(L); return 0; }?
?
尾：
????????由于博主才疏學淺，總結的相關知識僅限于自我學習認知，若出現錯誤。望各位大神指點。在這里感謝各位。文章來源：http://www.zghlxwxcb.cn/news/detail-847001.html
? ? ? ? （由于學習的倉促，有些代碼未能完全實現以及部分磨塊的講解不充分；若后期實現該代碼，將會進行下一步的補充）文章來源地址http://www.zghlxwxcb.cn/news/detail-847001.html
到了這里，關于【玩轉408數據結構】線性表——雙鏈表、循環(huán)鏈表和靜態(tài)鏈表（線性表的鏈式表示 下）的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
