《數據結構》2.5線性表的其他表示形式，《數據結構》2.5
![]()
1 //單循環鏈表（對兩個單循環鏈表L1、L2進行連接操作，即將L2的第一個數據元素節點連接到L1的尾節點之後，時間復雜度O(n)優化為O(1)）
2 q = r1->next; //保存L1的頭節點指針
3 r1->next = r2->next->next; //L1與L2尾頭連接
4 free(r2_>next); //釋放L2表的頭節點
5 r2->next = q; //組成循環鏈表
6
7 //雙向鏈表
8 //定義雙向鏈表節點
9 typedef struct dunode
10 {
11 datatype data;
12 struct dunode *prior, *next;
13 }DulNode, *DulLinkList;
14 //插入操作（設q指向雙向鏈表中某節點，s指向待插入的值為e的新節點，將*s插入*q的前面）
15 s->prior = q->prior; //(1)
16 q->prior = s; //(2) (1)(2)的順序不能改變，否則*q的直接前驅節點指針就會丟掉
17 q->prior->next = s;
18 s->nsxt = q;
19 //刪除操作（設q指向雙向鏈表中某節點，刪除*q）
20 q->next->prior = q->prior; //(1)
21 q->prior->next = q->next; //(2) (1)(2)順序可以改變
22 free(q);
23
24 //靜態鏈表
25 //定義數組S
26 #define MAXSIZE 1000
27 typedef struct
28 {
29 datatype data;
30 int next;
31 }SNode; //節點類型
32 SNode S[MAXSIZE];
33 int SL, SX; //兩個頭指針變量，SL頭指針代表用戶的線性表，SX頭指針指向空閒節點組成的鏈表
34 //申請節點空間（向SX空閒鏈表申請，不能調用系統函數malloc()）
35 if(SX != -1) //當SX為非空時
36 {
37 t = SX; //分配的節點地址（下標）存入t中
38 SX = S[SX].next; //取下一個節點給用戶後，SX指針移到下一個節點位置
39 }
40 //回收節點空間（通過該節點的相地址t回收給SX，不能調用系統函數free()）
41 s[t].next = SX;
42 SX = t;
View Code
說明：
1.單循環鏈表
將單鏈表最後一個節點的指針域不再為空指針而改成指向頭節點，使鏈表頭、尾節點相連，就構成了單循環鏈表；
若對單鏈表常做的操作是在表尾、表頭進行的，則可以改變鏈表的標識方法，即不用頭指針h而用一個指向尾節點的
指針r來標識循環鏈表，使操作效率提高。
2.雙向鏈表
每個節點再增加一個指向直接前驅的指針域，這種節點組成的鏈表稱為雙向鏈表。
3.靜態鏈表
用一維數組來描述線性鏈表，數組屬於靜態存儲結構，則這種方式下描述的鏈表稱為靜態鏈表。
指針域記錄的是邏輯上相鄰的下一個數據元素的相對地址（此結構中即為數組的下標），稱為靜態指針；由於C語言
定義的數組沒有下標為-1的單元，則空指針用-1表示。
