??本篇文章我們學習線性表的鏈式表示，也就是鏈表，我們知道，順序表可以隨機存取，查找方便，但是插入和洗掉需要移動大量元素，鏈式存盤線性表的時候，不需要使用地址連續的存盤單元，而是通過"鏈"建立起資料元素之間的邏輯關系，不要求物理位置連續，插入和洗掉只需要修改指標，很方便，但是這樣的話由于不要求物理位置連續，就會失去隨機存取的優點，下面就來介紹各種鏈表的，
??由于鏈表在網上的介紹很多，所以具體結構就不用圖片展示了，直接介紹如何用代碼實作，
一：單鏈表定義
??線性表最簡單的鏈式儲存是單鏈表，是通過一組任意的存盤單元存盤線性表中的資料元素，和順序表不同的是，任意代表存盤單元位置不相鄰，而單鏈表的結點也和順序表不同，
??單鏈表除存放元素自身的資訊之外，還需要存放一個指向其后繼結點的指標，也就是結點包括資料域和指標域，指標存放繼結點的地址，因為附加了一個指標域，所以存在浪費空間，空間利用率不高的情況，因為不是隨機存盤的，所以就造成了它的缺點是如果需要查找某個特定的結點時，需要從表頭開始遍歷，依次查找，
??單鏈表的結點型別描述如下：
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
??通常用頭指標來標識一個單鏈表，頭指標為NULL表示一個空表，有時候為了操作上的方便，在單鏈表頭指標和第一個結點之間附加一個結點，稱為頭結點，頭結點的資料域可以不包含任何資訊，也可以記錄表長等資訊，頭結點的指標域指向線性表的第一個元素結點，
??引入頭結點優點：
??在鏈表的第一個位置上的操作和在表的其他位置上的操作一致，無須進行特殊處理，
??無論鏈表是否為空，頭指標都是指向頭結點的非空指標(空表中頭結點的指標域為空)，空表和非空表的處理得到了統一，
二：單鏈表的操作
1.頭插法建立單鏈表
??該方法將新結點插入到鏈表的表頭，即頭結點之后，
??該演算法相當于改變了頭結點和其后繼結點之間的對應關系，代碼如下：
LinkList List_HeadInsert(LinkList &L){
LNode *s,int x;
L = (LinkList)malloc(sizeof(LNode)); //創建頭結點
L->next = NULL; //初始為空鏈表
scanf("%d", &x);
while(x!=99999){
//創建新結點，區別頭結點用 LNode*指向
s = (LNode*)malloc(sizeof(LNode));
s->data = https://www.cnblogs.com/ITXiaoAng/p/x;
s->next = L->next;
L->next = s;
scanf("%d", &x);
}
return L;
}
??由于頭插法是在表頭插，只改變頭結點的指向，則插入后的時間復雜度為O(1)，則對于一個表長為n的單鏈表，頭插法建立完單鏈表的總的時間復雜度為O(n)，
2.尾插法建立單鏈表
??還有一種演算法是在鏈表的表尾插入，因此必須增加一個尾指標r，使其指向當前鏈表的尾結點，然后把尾結點的指標指向要插入的元素，代碼如下：
LinkList List_TailInsert(LinkList &L){
int x;
L = (LinkList)malloc(sizeof(LNode)); //創建頭結點
LNode *s,*r = L; //r為尾指標
scanf("%d", &x);
while(x!=99999){
s = (LNode*)malloc(sizeof(LNode));
s->data = https://www.cnblogs.com/ITXiaoAng/p/x;
r->next = s;
r=s; //r指向新的尾結點
scanf("%d", &x);
}
s->next = NULL; //尾指標置為空
return L;
}
??因為附設了一個指向尾結點的指標，所以時間復雜度和頭插法相同，
3.按序號查找結點值
??這個就是最簡單查找結點的方法，從第一個結點出發，直到找到第i個結點為止，否則回傳最后一個節點的指標域NULL，代碼如下：
LNode *GetElem(LinkList L,int i){
int j = 1; //計數，初始值為1
LNode *p = L->next; //頭結點賦值給p
if(i == 0)
return L; //若i等于0，則回傳頭結點
if(i < 1)
return NULL; //若i無效，則回傳NULL
//從第1個結點開始找，知道找到第i個結點
while(p && j < i){
p = p->next;
j++;
}
//回傳第i個結點的指標，若i大于表長則回傳NULL
return p;
}
4.按值查找結點值
??這個也是最簡單查找結點的方法，從第一個結點出發，直到找到第1個結點等于e的值為止，否則回傳最后一個節點的指標域NULL，代碼如下：
LNode *LocateElem(LinkList L,int e){
LNode *p = L->next;
//從第一個結點查找data域為e的結點
while(p != NULL && p->data != e)
p = p->next;
//找到后回傳該結點指標，否則回傳NULL
return p;
}
??因為最快情況要遍歷整個鏈表，所以按值查找和按位查找元素的平均時間復雜度都是O(n)，
5.隨機插入結點操作
??該操作把值為x的新結點插入到單鏈表的第i個位置上，首先呼叫查找演算法GetElem(L,i-1)，查找到第i-1個結點，然后改變指標即可，演算法的位置不能顛倒，否則會造成等號兩邊不相等的錯誤，代碼如下：
p = GetElem(L,i-1)
s->next = p->next;
p->next = s;
??本演算法的時間主要花在查找第i-1個元素，時間復雜度是O(n)，如果給定結點插入新結點，時間復雜度僅為O(1)，該演算法是前插操作，
??也可以對線性表進行前插操作，但是也可以轉化為后插操作，重要的是找到前插位置元素的前驅結點，時間復雜度為O(n)，也可以用如下的演算法轉化為后插操作實作，代碼如下：
//和之前的后插操作一樣
s->next = p->next;
p->next = s;
temp = s->data;
s->data = https://www.cnblogs.com/ITXiaoAng/p/p->data;
p->data = temp;
//交換資料域
6.洗掉結點操作
??洗掉結點操作將單鏈表的第i個結點洗掉先找到要洗掉元素的前驅結點，然后修改指標，就可以將其洗掉，代碼如下：
p = GetElem(L,i-1)
q = p->next;
p->next = q->next;
free(q);
??由于洗掉操作也是先要找到其前驅結點，因此演算法的主要時間也耗費在查找操作上，時間復雜度為O(n)，
??也可以用其他方法洗掉結點，
7.求表長操作
??求表長的操作就是計算單鏈表中資料結點的個數，需要設定一個計數器變數，最后求得表長，演算法的時間復雜度為O(n)，
8.注意事項
??由于單鏈表的長度是不包括頭結點的，因此不帶頭結點和帶頭結點的單鏈表在求表長操作上會有不同，
三：雙鏈表
??單鏈表只有一個指標，因此單鏈表只能依次從后往前遍歷，訪問后繼結點的時間復雜度是O(1)，訪問前驅結點的時間復雜度是o(n)，
??為了克服這種缺點，引入了雙鏈表，有兩個指標prior和next，結構代碼如下：
typedef struct DNode{ //定義雙鏈表結點型別
ElemType data; //資料域
struct DNode *prior,*next; //前驅和后繼指標
}DNode,*DLinkList;
??雙鏈表增加了一個指向前驅的prior指標，因此按值查找和安危查找的操作與單鏈表相同，但雙鏈表在插入和洗掉操作的實作上，與單鏈表有著較大的不同，是由于也要對prior指標修改，保證在修改程序中不斷鏈，雙鏈表很方便地找到其前驅結點，因此，插入和洗掉操作的時間復雜度僅為O(n)，
1.雙鏈表的插入操作
s->next = p->next;
p->next->prior = s;
s->prior = p;
p->next = s;
2.雙鏈表的洗掉操作
p->next = q->next;
q->next->prior = p;
free(q);
四.其他鏈表
??還有其他鏈表，這里進行介紹.
1.回圈單鏈表
??回圈單鏈表相當于把最后一個結點的指標從NULL改為指向頭結點，從而使整個鏈表形成一個環，因此回圈單鏈表的判空條件是指標是否等于頭指標，
??回圈單鏈表插入，洗掉演算法和單鏈表一樣，不用的是如果操作在表尾進行，讓單鏈表保持回圈的性質，正是因為回圈單鏈表是一個環，所以在任何位置上的插入和洗掉操作都是等價的，無需判斷是否是表尾，
??回圈單鏈表可以從表中的任意一個結點開始遍歷單鏈表，有時操作在表頭和表尾進行，僅設尾指標，使操作效率更高，是由于r->next即為頭指標，對于表頭和表尾的操作都只需要O(1)的時間復雜度，
2.回圈雙鏈表
??回圈雙鏈表就是回圈單鏈表然后加上頭結點的prior指標還要指向表尾結點，在回圈雙鏈表中，某結點為尾結點時，它的指標域是頭指標；當回圈雙鏈表為空表時，頭結點的prior和next域都等于頭指標，
3.靜態鏈表
??靜態鏈表借助陣串列示，也有資料域和指標域，但這里的指標是結點的相對地址，也就是陣列下標，又稱游標，需要預先分配一塊連續的記憶體空間，可以理解為順序表資料元素加一個指標域，
??靜態鏈表以next==-1作為結束的標志，靜態鏈表的插入，洗掉操作與動態鏈表相同，但沒有單鏈表使用方便，是為了不支持指標的高級語言設計的，比如python,Basic，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/143955.html
標籤：其他