目錄

1.線性表的概念

2.線性表的基本操作

3.存儲線性表的方式

（1）順序表

?順序表的概念

?順序表的實現(xiàn)

靜態(tài)分配：

動態(tài)分配：

順序表的插入：

順序表的刪除：

順序表的按位查找：

順序表的按值查找：

順序表的特點：

（2）單鏈表

?單鏈表的實現(xiàn)

不帶頭結點的單鏈表：

帶頭結點的單鏈表：

單鏈表的插入：

?按位序插入（帶頭結點）

?按位序插入（不帶頭結點）

?指定結點的后插操作

?指定結點的前插操作

單鏈表的刪除：

?按位序刪除（帶頭結點）

?按位序刪除（不帶頭結點）

?指定結點的刪除

單鏈表的查找：

?按位查找

?按值查找

單鏈表的長度：

單鏈表的兩種建立方法：

?尾插法建立單鏈表

?頭插法建立單鏈表

（3）雙鏈表

??雙鏈表的實現(xiàn)

雙鏈表的初始化：

雙鏈表的插入：

雙鏈表的刪除：

雙鏈表的銷毀：

?雙鏈表的遍歷：

（4）循環(huán)鏈表

? 循環(huán)單鏈表

? 循環(huán)雙鏈表

（5）靜態(tài)鏈表

??靜態(tài)鏈表的相關概念

??靜態(tài)鏈表的定義

??靜態(tài)鏈表的相關基本操作

（6）順序表和鏈表的對比

1.邏輯結構

2.物理結構（存儲結構）

3.數(shù)據(jù)運算/基本操作

??初始化

??銷毀

??增刪

??查找

??總結：

---

1.線性表的概念

線性表是具有相同數(shù)據(jù)類型的n(n0)個數(shù)據(jù)元素的有限序列，其中n為表長，當n=0時線性表是一個空表。若用L命名線性表，則其一般表示為 L=(a1,a2,…,ai,ai+1,…,an)

注：

1.這里的“相同”是指每個數(shù)據(jù)元素所占空間一樣大，同時強調(diào)有限序列，例如，所有整數(shù)按遞增次序排列，雖然有次序，但是對象是所有整數(shù)，所以不是線性表。

2.ai是線性表中的“第i個”元素線性表中的位序（位序從1開始，數(shù)組下標從0開始）。

3.a1是表頭元素；an是表尾元素。
4.除第一個元素外，每個元素有且僅有一個直接前驅(qū)；除最后一個元素外，每個元素有且僅有一個直接后繼。

2.線性表的基本操作

初始化，銷毀，增刪改查：

?InitList(&L)：初始化表。構造一個空的線性表L，分配內(nèi)存空間。

?DestroyList(&L)：銷毀操作。銷毀線性表，并釋放線性表L所占用的內(nèi)存空間。
?Listlnsert(&L,i,e)：插入操作。在表L中的第i個位置上插入指定元素e。
?ListDelete(&Li,&e)：刪除操作。刪除表L中第i個位置的元素，并用e返回刪除元素的值。
?LocateElem(L,e)：按值查找操作。在表L中查找具有給定關鍵字值的元素。
?GetElem(L,i)：按位查找操作。獲取表L中第i個位置的元素的值。
其他常用操作:
?Length(L)：求表長。返回線性表L的長度，即L中數(shù)據(jù)元素的個數(shù)。

?PrintList(L)：輸出操作。按前后順序輸出線性表L的所有元素值。

?Empty(L)：判空操作。若L為空表，則返回true，否則返回false。

關于"&":

對于下面的代碼：

在main函數(shù)中定義了一個變量x=1，接著調(diào)用test()，test(int x)中的“x”其實是main函數(shù)中“x”的復制品，兩個"x"是不同的數(shù)據(jù)（占用不同的內(nèi)存空間），所以test()中定義的"x"的值，其實修改的是復制品"x"的值，并沒有修改main()中變量"x"的值。

所以輸出的結果中，"調(diào)用test后x=1"。

對比下面這段代碼：

test(int &x)，參數(shù)x為引用類型，所以test()中操作的參數(shù)“x”與main()中的“x”是同一份數(shù)據(jù)（占用同一個空間），所以在test()中對"x"的修改會影響到main()中"x"的值，即對參數(shù)的修改帶回到了main()中。

3.存儲線性表的方式

（1）順序表

?順序表的概念

用順序存儲的方式實現(xiàn)線性表順序存儲。把邏輯上相鄰的元素存儲在物理位置上也相鄰的存儲單元中，元素之間的關系由存儲單元的鄰接關系來體現(xiàn)。

設線性表第一個元素的存放位置是 LOC(L)，由于每個數(shù)據(jù)元素在物理上連續(xù)存放，并且每個數(shù)據(jù)元素所占空間大小相同。所以有：

?順序表的實現(xiàn)

靜態(tài)分配：

#define MaxSize 10         //定義最大長度
typedef struct{            ElemType data[MaxSize];    //用靜態(tài)的“數(shù)組”存放數(shù)據(jù)元素int length;                //順序表的當前長度
}SqList;                   //順序表的類型定義(靜態(tài)分配方式)/*這里的ElemType指的是元素的類型，可以是int也可以是struct，這取決于順序表存儲的數(shù)據(jù)類型*/

具體地看個示例：?

#include<stdio.h>
#define MaxSize 10         //定義最大長度
typedef struct{            int data[MaxSize];    //用靜態(tài)的“數(shù)組”存放數(shù)據(jù)元素int length;                //順序表的當前長度
}SqList;                   //順序表的類型定義(靜態(tài)分配方式)//初始化一個順序表
void InitList(SqList &L){for(int i=0;i<MaxSize;i++)L.data[i]=0;    //將所有數(shù)據(jù)元素設置為默認初始值L.length=0;    //順序表初始長度為0    
}int main(){SqList L;    //聲明一個順序表，表示在內(nèi)存中分配存儲順序表L的空間，包括:MaxSize*sizeof(ElemType)和 存儲 length 的空間InitList(L); //初始化順序表return 0;
}

若沒有設置默認數(shù)據(jù)元素的默認值：

#include<stdio.h>
#define MaxSize 10         //定義最大長度
typedef struct{            int data[MaxSize];    //用靜態(tài)的“數(shù)組”存放數(shù)據(jù)元素int length;                //順序表的當前長度
}SqList;                   //順序表的類型定義(靜態(tài)分配方式)//初始化一個順序表
void InitList(SqList &L){L.length=0;    //順序表初始長度為0    
}int main(){SqList L;    InitList(L); //初始化順序表//"違規(guī)"打印整個data數(shù)組for(int i=0;i<MaxSize;i++)printf("data[%d]=%d\n",i,L.data[i]);return 0;
}

打印結果如下：

不同的計算機中運行此代碼結果都會不同，這是因為內(nèi)存中會遺留“臟數(shù)據(jù)”。雖然聲明順序表之后，系統(tǒng)會分配一塊內(nèi)存空間，但是這片內(nèi)存空間之前存放的是什么我們是不知道的，所以如果不設置默認值的話，之前的臟數(shù)據(jù)就會遺留下來。

其實不設置默認初始值是可以的，只要將i<MaxSize改為i<L.length，就是不從第一個元素訪問到最后一個元素，而是從第一個元素訪問到實際存儲的最后一個元素。例如當前沒有存儲任何數(shù)據(jù)，那么系統(tǒng)就不會打印任何值。

#include<stdio.h>
#define MaxSize 10         //定義最大長度
typedef struct{            int data[MaxSize];    //用靜態(tài)的“數(shù)組”存放數(shù)據(jù)元素int length;                //順序表的當前長度
}SqList;                   //順序表的類型定義(靜態(tài)分配方式)//初始化一個順序表
void InitList(SqList &L){L.length=0;    //順序表初始長度為0    
}int main(){SqList L;    InitList(L); //初始化順序表for(int i=0;i<L.length;i++)printf("data[%d]=%d\n",i,L.data[i]);return 0;
}

靜態(tài)分配中順序表的內(nèi)存空間是固定的，若設置的內(nèi)存空間過小，那么數(shù)組很容易被存滿，如果過大，則浪費內(nèi)存空間。所以可以采用動態(tài)分配。

動態(tài)分配：

//malloc和free函數(shù)的頭文件
#include<stdlib.h>
#define InitSize 10
typedef struct{int *data;    //指示動態(tài)分配數(shù)組的指針，這里是整型指針int MaxSize;int length;
}SeqList;//使用malloc和free動態(tài)申請和釋放內(nèi)存空間
void InitList(seqList &L){L.data=(int *)malloc(InitSize*sizeof(int));
//malloc函數(shù)的參數(shù)指明要分配多大的連續(xù)內(nèi)存空間
//malloc函數(shù)返回一個指針，需要強制轉型定義的數(shù)據(jù)類型指針，在這里就是(int *)L.length=0;L.MaxSize=InitSize;
}void IncreaseSize(SeqList &L,int len){int *p=L.data;L.data=(int *)malloc(L.MaxSize+len)*sizeof(int);for(int i=0;i<L.length;i++){L.data[i]=p[i];}L.MaxSize=L.MaxSize+len;free(p);   
}int main(){SeqList L;InitList(L);IncreaseSize(L,5);return 0;}

在IncreaseSize中

int *p=L.data，表示p指針與data指針指向同一個內(nèi)存空間

L.data=(int *)malloc(L.MaxSize+len)*sizeof(int)，表示新分配一個內(nèi)存空間，此空間包括原來順序表的最大長度，以及新增加的長度len。同時將data指針指向這個內(nèi)存空間。

?for(int i=0;i<L.length;i++){
? ? ? ? L.data[i]=p[i];
? ? }
? ? L.MaxSize=L.MaxSize+len;

表示將原來的數(shù)據(jù)復制到新的區(qū)域中，并且改變最大長度為新增內(nèi)存空間的長度

free(p)，表示釋放原來的內(nèi)存空間，歸還給系統(tǒng)。由于p變量是局部變量，所以執(zhí)行完free(p)之后，存儲p變量的內(nèi)存空間也會被回收。

至此就實現(xiàn)了動態(tài)增加數(shù)組長度的操作。由于需要將舊數(shù)據(jù)復制到新的內(nèi)存空間，所以會增加時間開銷。

順序表的插入：

之前講過，在第i個位置上插入元素，需要將i及以后的元素都往后移動一位。這里是基于“靜態(tài)分配"的代碼。

#include <stdio.h>#define MaxSize 10typedef struct {int data[MaxSize];int length;
} SqList;void InitList(SqList &L) {L.length = 0;
}// 在L的位序i中插入元素e
bool ListInsert(SqList &L, int i, int e) {if (i < 1 || i > L.length + 1)  // 判斷i的范圍是否有效return false;if (L.length >= MaxSize)return false;  // 當前存儲空間已滿，不能插入for (int j = L.length; j >= i; j--)L.data[j] = L.data[j - 1];  // 將第i個元素及之后的元素后移L.data[i - 1] = e;              // 在位置i上放入eL.length++;                     // L長度加1return true;
}int main() {SqList L;InitList(L);for (int i = 0; i < 5; i++) {ListInsert(L, i + 1, i + 1); // 插入元素，自動更新長度}printf("插入前的順序表為:\n");for (int i = 0; i < L.length; i++) {printf("%d ", L.data[i]);}printf("\n");ListInsert(L, 3, 99);  // 在第3位插入元素99printf("插入后的順序表為:\n");for (int i = 0; i < L.length; i++) {printf("%d ", L.data[i]);}printf("\n");return 0;
}

實現(xiàn)結果：

插入操作的時間復雜度（最深層循環(huán)語句的執(zhí)行次數(shù)與問題規(guī)模 n的關系）是多少呢？

注：問題規(guī)模n就是線性表的表長L.length

最好情況：新元素插入到表尾，不需要移動元素

i=n+1，循環(huán)0次；最好時間復雜度=O(1)；

最壞情況：新元素插入到表頭，需要將原有的n個元素全都向后移動

i=1，循環(huán)n次；最壞時間復雜度=O(n)；

平均情況：假設新元素插入到任何一個位置的概率相同，即i=1,2,3,…,length+1的概率都是p=
1/n+1

i=1，循環(huán)n次；i=2時，循環(huán)n-1次；i=3，循環(huán)n-2次…i=n+1時，循環(huán)0次

循環(huán)n次的概率是p，循環(huán)n-1的概率也是p，依此類推，將p提出來就是

p*[n+(n-1)+(n-2)+·····+0]====O(n)

順序表的刪除：

刪除表與插入表的操作相反，就是將要刪除的元素的后面的元素往前移動一位，并且length值減1

#include<stdio.h>
#define MaxSize 10
typedef struct{int data[MaxSize];int length;
} SqList;void InitList(SqList &L){L.length = 0;
}bool ListDelete(SqList &L,int i,int &e){if(i<1 || i>L.length)return false;e=L.data[i-1];for(int j=i;j<L.length;j++)   //將被刪除的元素賦給eL.data[j-1]=L.data[j];    //將第i個位置后的位置前移L.length--;    //線性表長度減1return true;
}int main()
{SqList L;InitList(L);printf("順序表為:\n"); for (int i = 0; i < 5; i++) {L.data[i] = i + 1;printf("%d ", L.data[i]);L.length++;}int e=-1;    //聲明一個變量e，初始值設為-1if(ListDelete(L,3,e))printf("\n已刪除第3個元素，刪除元素值=%d\n",e); elseprintf("位序i不合法，刪除失敗\n");printf("刪除元素后的順序表為:\n"); for(int i=0;i<L.length;i++){printf("%d ",L.data[i]);}return 0;   
}

實現(xiàn)結果：

注意：

（1）

bool ListDelete(SqList &L,int i,int &e)，這里的參數(shù)e一定要是引用類型的，即刪除e，再把e的值返回。

首先在main()中聲明一個變量e，初始值為-1

接著調(diào)用ListDelete()時，會把要刪除的變量的值復制到e變量所對應的內(nèi)存區(qū)域中，即

e=L.data[i-1];

最后for循環(huán)，將刪除元素之后的元素依次往前移動，并且length值減1

（2）

刪除操作中，i位置后的元素往前移，是先從前面的元素往前移動的，而插入操作中，是先從后面的元素往后移動的。這個應該很好理解。

刪除操作的時間復雜度是多少呢？

最好情況：刪除表尾元素，不需要移動其他元素

i=n，循環(huán)0次；最好時間復雜度=O(1)

最壞情況：刪除表頭元素，需要將后續(xù)的n-1個元素全都向前移動i=1，循環(huán) n-1次；最壞時間復雜度=0(n)；

平均情況：假設刪除任何一個元素的概率相同，即i=1,2,3,…,length的概率都是p=1/n，

i=1，循環(huán) n-1次；i=2 時，循環(huán) n-2 次；i=3，循環(huán) n-3 次…i=n時，循環(huán)0次

平均時間復雜度=O(n)

?寫代碼要注意：

1.題目中的i是位序i（從1開始），還是數(shù)組下標i（從0開始），例如，第3個元素其實數(shù)組下標為2。

2.算法要有健壯性，注意判斷i的合法性。

順序表的按位查找：

//靜態(tài)分配方式
#define MaxSize 10
typedef struct{int data[MaxSize];int length;
} SqList;ElemType GetElem(SqList L,int i){return L.data[i-1];
}//動態(tài)分配
#define InitSize 10
typedef struct{ElemType *data;int MaxSize;int length;
} SeqList;ElemType GetElem(SeqList L,int i){return L.data[i-1];
}

對于ElemType *data，如果一個ElemType 占6B,即 sizeof(ElemType)==6，指針 data 指向的地址為 2000。

如圖所示，計算機會根據(jù)指針所指向數(shù)據(jù)類型的空間大小，計算每個數(shù)組下標對應哪些字節(jié)的數(shù)據(jù)。

例如int型變量：

這就可以解釋：L.data=(int *)malloc(InitSize*sizeof(int))，使用malloc分配內(nèi)存空間時需要強制轉換數(shù)據(jù)類型，雖然指針指向的是同一個地址，但是指針指向的數(shù)據(jù)類型定義錯誤，訪問元素的時候也會出現(xiàn)錯誤。

按位查找的時間復雜度：O(1)，由于順序表的各個數(shù)據(jù)元素在內(nèi)存中連續(xù)存放，因此可以根據(jù)起始地址和數(shù)據(jù)元素大小立即找到第i個元素，這也體現(xiàn)了順序表隨機存取的特性。

順序表的按值查找：

#define InitSize 10
typedef struct{ElemType *data;int MaxSize;int length;
} SeqList;ElemType LocateElem(SeqList L,ElemType e){for(int i=0;i<L.length;i++)if(L.data[i]==e)return i+1;    //數(shù)組下標為i的元素值等于e,返回其位序i+1return 0;    //退出循環(huán)，說明查找失敗}

注意：“==”不能比較兩個結構體類型：

需要依次對比各個分量比較兩個結構體是否相等：?

按值查找的時間復雜度：

最好情況：目標元素在表頭
循環(huán)1次；最好時間復雜度=O(1)

最壞情況：目標元素在表尾
循環(huán)n次；最壞時間復雜度=O(n)

平均情況：假設目標元素出現(xiàn)在任何一個位置的概率相同，都是1/n

目標元素在第1位，循環(huán)1次；在第2位，循環(huán)2次；…在第n位，循環(huán)n次

平均時間復雜度為：O(n)

順序表的特點：

①隨機訪問，即可以在 O(1)時間內(nèi)找到第i個元素。

②存儲密度高，每個節(jié)點只存儲數(shù)據(jù)元素。

③拓展容量不方便(即便采用動態(tài)分配的方式實現(xiàn)，拓展長度的時間復雜度也比較高)。

④插入、刪除操作不方便，需要移動大量元素。

（2）單鏈表

邏輯結構為線性表的數(shù)據(jù)，物理上也能采用鏈式存儲的方式。

順序表：

優(yōu)點:可隨機存取，存儲密度高

缺點:要求大片連續(xù)空間，改變?nèi)萘坎环奖?/p>

單鏈表：

優(yōu)點:不要求大片連續(xù)空間，改變?nèi)萘糠奖?/p>

缺點:不可隨機存取，要耗費一定空間存放指針

?單鏈表的實現(xiàn)

struct LNode{    //定義單鏈表結點類型
ElemType data;   //每個節(jié)點存放一個數(shù)據(jù)元素
struct LNode *next;    //指針指向下一個節(jié)點
};//增加一個新的結點:在內(nèi)存中申請一個結點所需空間，并用指針p指向這個結點
struct LNode *p=(struct LNode *)malloc(sizeof(struct LNode));

每次寫代碼時都要寫struct LNode比較麻煩，可以使用typedef關鍵字對數(shù)據(jù)類型重命名：
typedef struct LNode LNode；

這樣：

struct LNode *p=(struct LNode *)malloc(sizeof(struct LNode));

可以寫為：

LNode *p=(LNode *)malloc(sizeof(LNode));

以下兩個代碼都表示，定義了一個struct LNode的數(shù)據(jù)類型，接著將struct LNode重命名為LNode，并且用LinkList表示指向struct LNode的指針。

struct LNode{ElemType data;struct LNode *next;};
typedef struct LNode LNode;
typedef struct LNode *LinkList;//更簡潔地：
typedef struct LNode{ElemType data;struct LNode *next;
}LNode,*LinkList;

要表示一個單鏈表時，只需聲明一個頭指針L，指向單鏈表的第一個結點

LNODE * L;    //聲明一個指向單鏈表第一個結點的指針
或者
LinkList L;typedef struct LNode{    //定義單鏈表節(jié)點類型ElemType data;       //每個節(jié)點存放一個數(shù)據(jù)元素struct LNode *next;  //指針指向下一個節(jié)點    
}LNode,*LinkList;//這里用LNode* 和 LinkList 表示都可以，只是前面用LNode*強調(diào)返回的是一個結點，后面用LinkList強調(diào)返回的是一個單鏈表
LNode * GetElem(LinkList L,int i){int i;LNode *p=L->next;if(i=0)return L;if(i<1)return NULL;while(p!=NULL && j<i){p=p->next;j++;}return p;
}

不帶頭結點的單鏈表：

typedef struct LNode{ElemType data;struct Lnode *next;
}LNode,*LinkList;//初始化一個空的單鏈表
bool InitList(LinkList &L){L = NULL;    //空表，暫時還沒有任何結點,設為NULL的目的是防止遺留的臟數(shù)據(jù)return true;
}void test(){LinkList L;    //聲明一個單鏈表指針I(yè)nitList(L);
}//判斷單鏈表是否為空
bool Empty(LinkList L){if(L == NULL)return true;elsereturn false;
}
//或者，直接寫為
bool Empty(LinkList L){return(L=NULL);
}

帶頭結點的單鏈表：

typedef struct LNode{ElemType data;struct Lnode *next;
}LNode,*LinkList;//初始化一個空的單鏈表
bool InitList(LinkList &L){L=(LNode *)malloc(sizeof(LNode));    if(L==NULL)return false;L->next=NULL;    //頭結點之后暫時還沒有節(jié)點return true;
}void test(){LinkList L;    //聲明一個單鏈表指針I(yè)nitList(L);
}//判斷單鏈表是否為空
bool Empty(LinkList L){if(L->next == NULL)return true;elsereturn false;
}
//或者，直接寫為
bool Empty(LinkList L){return(L->next == NULL);
}

?注：頭結點是不存儲數(shù)據(jù)的，設置頭結點只是為了后續(xù)處理更加方便。因為不帶頭結點的話，對第一個數(shù)據(jù)結點和后續(xù)數(shù)據(jù)結點的處理需要用不同的代碼邏輯。對空表和非空表的處理也需要用不同的代碼邏輯。

單鏈表的插入：

?按位序插入（帶頭結點）

帶頭結點插入時，若想在i=1時，插入一個新的結點，那么就可以將頭結點看作“第0個”結點，使用和后續(xù)結點一樣的處理邏輯，不帶頭結點則不行。

typedef struct LNode{ElemType data;struct LNode *next;
}LNode,*LinkList;//在第i個位置插入元素e(帶頭結點)
bool ListInsert(LinkList &L,int i,ElemType e){if(i<1)return false;LNode *p;    //指針p指向當前掃描到的結點int j=0;     //當前p指向的是第幾個結點p = L;       //L指向頭結點，頭結點是第0個結點(不存數(shù)據(jù))while(p!=NULL && j<i-1){     //循環(huán)找到第 i-1 個結點
//因為要在第i個位置插入，所以要找到第i-1個結點，在i-1個結點后插入p=p->next;j++;}if(p==NULL)    //i值不合法return false;LNode *s=(LNode*)malloc(sizeof(LNOde));s->data=e;s->next=p->next;p->next=s;      //將結點s連到p之后return true;    //插入成功
}

如果i=1，即插在表頭

因為i=1，不滿足j<i-1，不會跳到while(p!=NULL && j<i-1)

LNode *s=(LNode*)malloc(sizeof(LNOde));//申請一個結點空間

s->data=e;//將參數(shù)e放到這一結點空間中

s->next=p->next;//s指向結點的next指針等于p結點next指針指向的位置

p->next=s;//p結點的next指針指向新結點

這種情況，因為i=1，while循環(huán)直接被跳過，所以時間復雜度為O(1)，這也是最好時間復雜度。

如果i=5，那么就是在第四個結點后插入：

s->next=p->next; //s的next指針指向p的next指針，由于p結點的next指針指向的是NULL，所以s的next指針也指向NULL

p->next=s;//最后，p的next指針指向新的結點

將新結點插到表尾，即最壞時間復雜度，為O(n)

平均時間復雜度也為O(n)

如果i=6，那么在while循環(huán)中j=5時，p==NULL，就會進入if循環(huán)，跳出循環(huán)：

if(p==NULL) ? ?//i值不合法
? ? ? ? return false;

注：

s->next=p->next;? ? ? ? ①

p->next=s;? ? ? ? ? ②

兩句不能顛倒，如果先讓p的next指針指向s，即執(zhí)行②，再讓s的next指針指向p的next指針，就會出現(xiàn)如下情況：

?按位序插入（不帶頭結點）

不帶頭結點的插入中不存在“第0個”結點，所以i=1時需要特殊處理：

typedef struct LNode{ElemType data;struct LNode *next;
}LNode,*LinkList;//在第i個位置插入元素e(不帶頭結點)
bool ListInsert(LinkList &L,int i,ElemType e){if(i<1)return false;if(i==1){//插入第一個結點的操作與其他結點操作不同LNode *s=(LNode *)malloc(sizeof(LNode));s->data=e;s->next=L;L=s;    //頭指針指向新結點return true;
}LNode *p;    int j=1;     //這里j=1p = L;       while(p!=NULL && j<i-1){    p=p->next;j++;}if(p==NULL)    //i值不合法return false;LNode *s=(LNode*)malloc(sizeof(LNOde));s->data=e;s->next=p->next;p->next=s;      //將結點s連到p之后return true;    //插入成功
}

如果i=1?：

首先申請一個新的結點，放入?yún)?shù)e

? ? ? ? LNode *s=(LNode *)malloc(sizeof(LNode));
? ? ? ? s->data=e;

接著將新節(jié)點的next指針指向L所指向的結點

? ? ? ? s->next=L;

最后修改頭指針L，使L指向新的結點

? ? ? ? L=s;

所以，如果不帶頭結點，則插入、刪除第1個元素時，需要更改頭指針L（L=s），如果帶頭結點的話，頭指針永遠都是指向頭結點的。

后續(xù)i>1的情況，與帶頭結點的處理是相同的，只是需要注意，int j=1，即p指針剛開始指向的是第一個結點：

而帶頭結點，剛開始指向的是第“0”個結點：

?指定結點的后插操作

由于單鏈表只能往后尋找，所以單鏈表p結點后的元素都是可知的，利用循環(huán)的方式可以知道后續(xù)元素的值。而p結點前的值是不知道的。

typedef struct LNode{ElemType data;struct LNode *next;
}LNode,*LinkList;//后插操作:在p結點之后插入元素e
bool InsertNextNode(LNode *p,ElemType e){if (p==NULL)return false;LNode *s =(LNode *)malloc(sizeof(LNode));if(s==NULL)    //內(nèi)存分配失敗(如內(nèi)存不足)return false;s->data =e;    //用結點s保存數(shù)據(jù)元素es->next=p->next;p->next=s;    //將結點s連到p之后return true;
}

時間復雜度為O(1)

實現(xiàn)后插操作后,可以直接寫為：

typedef struct LNode{ElemType data;struct LNode *next;
}LNode,*LinkList;//后插操作:在p結點之后插入元素e
bool InsertNextNode(LNode *p,ElemType e){if (p==NULL)return false;LNode *s =(LNode *)malloc(sizeof(LNode));if(s==NULL)    //內(nèi)存分配失敗(如內(nèi)存不足)return false;s->data =e;    //用結點s保存數(shù)據(jù)元素es->next=p->next;p->next=s;    //將結點s連到p之后return true;
}//在第i個位置插入元素e(帶頭結點)
bool ListInsert(LinkList &L,int i,ElemType e){if(i<1)return false;LNode *p;    //指針p指向當前掃描到的結點int j=0;     //當前p指向的是第幾個結點p = L;       //L指向頭結點，頭結點是第0個結點(不存數(shù)據(jù))while(p!=NULL && j<i-1){     //循環(huán)找到第 i-1 個結點
//因為要在第i個位置插入，所以要找到第i-1個結點，在i-1個結點后插入p=p->next;j++;}return InsertNextNode(p,e);
/*if(p==NULL)    //i值不合法return false;LNode *s=(LNode*)malloc(sizeof(LNOde));s->data=e;s->next=p->next;p->next=s;      //將結點s連到p之后return true;    //插入成功
*/
}

?指定結點的前插操作

之前說過單鏈表只知道p結點后的元素，那么如何找到p的前驅(qū)結點呢？

可以傳入頭指針

bool InsertPriorNode(LinkList L,LNode *p,ElemType e)

傳入頭指針后，整個鏈表的信息就都能知道了。具體操作是遍歷整個單鏈表，找到結點p的前驅(qū)節(jié)點，在前驅(qū)結點后插入元素e

時間復雜度為O(n)

如果沒有傳入頭結點，可以這樣實現(xiàn)：

//前插操作:在p結點之前插入元素 e
bool InsertPriorNode(LNode *p,ElemType e){if (p==NULL)return false;LNode *s=(LNode *)malloc(sizeof(LNode));if(s==NULL)//內(nèi)存分配失敗return false,s->next=p->next;p->next=s;    //新結點 s連到 p 之后s->data=p->data;p->data=e;    //將p中元素復制到s中return true;    //p 中元素覆蓋為 e

?首先申請一個新的結點，并把這一結點作為p結點的后繼節(jié)點：

接著，將p結點(p指針指向的結點)存放的元素x，復制到新的結點中：s->data=p->data;

最后將要新插入的元素e覆蓋原來p結點存放的元素x：

這樣，即使沒有傳入頭結點，也可以完成前插操作。

并且這一實現(xiàn)方式的實現(xiàn)方式是O(1)，而上一種實現(xiàn)方式是O(n)。

王道書中的寫法是這樣的，但是思路是一致的。

//前插操作:在p結點之前插入結點 s
bool InsertPriorNode(LNode *p,LNode *s){if(p==NULL s==NULL)return false;s->next=p->next;p->next=s;    //s連到p之后ElemType temp=p->data;    //交換數(shù)據(jù)域部分p->data=s->data;s->data=temp;return true;
}

單鏈表的刪除：

注：對于刪除結點的操作只探討帶頭結點的情況

?按位序刪除（帶頭結點）

具體地將頭結點看作"第0個"結點，找到第 i-1?個結點，將其指針指向第 i+1 個結點，并釋放第i個結點。

typedef struct LNode{ElemType data;struct LNode *next;
}LNode,*LinkList;bool ListDelete(LinkList &L,int i,ElemType &e){if(i<1)return false;LNode *p;    //指針p指向當前掃描到的結點int j=0;     //當前p指向的是第幾個結點p = L;       //L指向頭結點，頭結點是第0個結點(不存數(shù)據(jù))while(p!=NULL && j<i-1){     //循環(huán)找到第 i-1 個結點p=p->next;    j++;}if(p==NULL)    //i值不合法return false;if(p->next == NULL)   //第i-1個結點之后已無其他結點return false;LNode *q=p->next;    //令q指向被刪除結點e = q->data;         //用e返回元素的值p->next=q->next;     //將*q結點從鏈中“斷開”free(q);             //釋放結點的存儲空間return true;         //刪除成功
}

如果i=4，經(jīng)過while循環(huán)后，p會指向第3個結點（i-1個結點）：

將q指針指向p結點的next元素，即第i個結點：LNode *q=p->next

接下來會把q指針指向的結點中的元素復制給變量e：e=q->data

最后將p的next指針指向q的next指針，并且釋放q：

p->next=q->next;

free(q);

?按位序刪除（不帶頭結點）

不帶頭結點的刪除，若刪除第一個元素，那么需要更改頭指針，和不帶頭結點的操作類似：

typedef struct LNode{ElemType data;struct LNode *next;
}LNode,*LinkList;bool ListDelete(LinkList &L,int i,ElemType &e){if(i<1)return false;if (i == 1) {if (L == NULL)  // 判斷鏈表是否為空return false;LNode *q = L;e = q->data;L = L->next;    // 將頭指針指向第一個結點的下一個結點free(q);        // 釋放第一個結點的內(nèi)存空間return true;}LNode *p;    int j=1;p = L;  while(p!=NULL && j<i-1){     //循環(huán)找到第 i-1 個結點p=p->next;    j++;}if(p==NULL)    //i值不合法return false;if(p->next == NULL)   //第i-1個結點之后已無其他結點return false;LNode *q=p->next;    //令q指向被刪除結點e = q->data;         //用e返回元素的值p->next=q->next;     //將*q結點從鏈中“斷開”free(q);             //釋放結點的存儲空間return true;         //刪除成功
}

刪除操作的最壞，平均時間復雜度：O(n)

最好時間復雜度：O(1)

?指定結點的刪除

如果要刪除結點p，需要修改前驅(qū)結點的next指針：

可以傳入頭指針，循環(huán)尋找p的前驅(qū)，也可以進行類似于前插的操作：

//刪除指定結點 p
bool DeleteNode (LNode *p){if (p==NULL)return false;LNode *q=p->next;    //令q指向*p的后繼結點p->data=p->next->data;    //和后繼結點交換數(shù)據(jù)域p->next=q->next;    //將*q結點從鏈中“斷開”free(q);    //釋放后繼結點的存儲空間return true;
}

聲明結點q，指向p的后繼結點：LNode *q=p->next;

?

把p結點后繼結點的數(shù)據(jù)復制到p結點中：p->data=p->next->data;

將p結點的next指針，指向q結點之后的位置：p->next=q->next;

將q結點釋放，將內(nèi)存歸還給系統(tǒng)：free(q);

時間復雜度：O(1)

若刪除的結點時最后一個結點，那么代碼執(zhí)行到：p->data = p->next->data 就會出錯，因為找不到p結點的后繼結點，這樣的話，只能從表頭開始依次尋找p的前驅(qū)，時間復雜度:O(n)。

單鏈表的查找：

?按位查找

//按位查找，返回第 1個元素(帶頭結點)
LNode * GetElem(LinkList L,int i){if(i<0)return NULL;LNode *p;     //指針p指向當前掃描到的結點int j=0;      //當前p指向的是第幾個結點p = L;        //L指向頭結點，頭結點是第0個結點(不存數(shù)據(jù))while(p!=NULL && j<i){ //循環(huán)找到第 1 個結點p=p->next;    j++;}return p;
}

①如果p的值=0，那么會跳過while循環(huán)

②如果i的值大于鏈表的實際長度，例如i=8，最后返回NULL

按位查找平均時間復雜度：O(n)

王道書是這樣寫的，實現(xiàn)效果是一樣的：

LNode * GetElem(LinkList L,int i){int j=1;LNode *p=L->next;if(i==0)    //當i的值為0時，返回頭節(jié)點return L;if(i<1)return NULL;while(p!=NULL && j<i){p=p->next;j++;}    return p;
}

只是p結點剛開始是指向第1個節(jié)點，而不是第0個節(jié)點：

有了查找的功能，按位插入和按位刪除中的查找操作，就可以直接調(diào)用這個函數(shù)實現(xiàn)：

//后插操作:在p結點之后插入元素e
bool InsertNextNode(LNode *p,ElemType e){if (p==NULL)return false;LNode *s =(LNode *)malloc(sizeof(LNode));if(S==NULL)    //內(nèi)存分配失敗(如內(nèi)存不足)return false;s->data =e;    //用結點s保存數(shù)據(jù)元素es->next=p->next;p->next=s;    //將結點s連到p之后return true;
}//在第i個位置插入元素e(帶頭結點)
bool ListInsert(LinkList &L,int i,ElemType e){if(i<1)return false;LNode *p=GetElem(L,i-1); //找到第i-1個結點return InsertNextNode(p,e);    //p后插入新元素e
}//刪除第i個位置的元素e
bool ListDelete(LinkList &L,int i,ElemType &e){if(i<1)return false;LNode *p=GetElem(L,i-1);if(p==NULL)    //i值不合法return false;if(p->next == NULL)   //第i-1個結點之后已無其他結點return false;LNode *q=p->next;    //令q指向被刪除結點e = q->data;         //用e返回元素的值p->next=q->next;     //將*q結點從鏈中“斷開”free(q);             //釋放結點的存儲空間return true;         //刪除成功
}

?按值查找

//按值查找，找到數(shù)據(jù)域==e 的結點
LNode *LocateElem(LinkList L,ElemType e){LNode *p =L->next;    //從第1個結點開始查找數(shù)據(jù)域為e的結點while(p != NULL && p->data != e)p = p->next;return p;    //找到后返回該結點指針，否則返回NULL，如果返回NULL表示不存在要查找的值
}

按值查找的時間復雜度為O(n)

單鏈表的長度：

//求表的長度
//帶頭結點
int Length(LinkList L){int len =0;//統(tǒng)計表長LNode *p =L;
// 遍歷鏈表，統(tǒng)計節(jié)點個數(shù)while(p->next != NULL){p = p->next;len++;}return len;
}//不帶頭結點
int Length(LinkList L) {int len = 0; // 統(tǒng)計鏈表長度LNode* p = L;if (p == NULL) {return len;}while (p != NULL) {len++;p = p->next;}return len;
}

求表的長度，時間復雜度O(n)?

單鏈表的兩種建立方法：

?尾插法建立單鏈表

就是每次取一個數(shù)據(jù)元素，插入到表尾：

typedef struct LNode{int data;struct LNode *next;
}LNode,*LinkList;//初始化一個單鏈表(帶頭結點)
bool InitList(LinkList &L){L=(LNode *)malloc(sizeof(LNode));    //分配一個頭結點if(L==NULL)//內(nèi)存不足，分配失敗return false;L->next = NULL;//頭結點之后暫時還沒有節(jié)點return true;// 尾部插入節(jié)點（帶頭結點）
LinkList TailInsert(LinkList &L) {L = (LinkList)malloc(sizeof(LNode)); // 建立頭結點L->next = NULL; // 頭結點的next指針初始化為NULLint x;LNode *s, *r = L; // r為表尾指針printf("請輸入節(jié)點的值，輸入9999表示結束：\n");scanf("%d", &x); // 輸入結點的值while (x != 9999) { // 輸入9999表示結束s = (LNode *)malloc(sizeof(LNode));s->data = x;r->next = s; // 將新節(jié)點鏈接到鏈表尾部r = s; // 更新表尾指針scanf("%d", &x);}r->next = NULL; // 將表尾節(jié)點的next指針設置為NULLreturn L;
}// 尾部插入節(jié)點（不帶頭結點）
LinkList TailInsert(LinkList &L) {L = NULL; // 初始化鏈表為空int x;LNode *s, *r = NULL; // r為表尾指針printf("請輸入節(jié)點的值，輸入9999表示結束：\n");scanf("%d", &x); // 輸入結點的值while (x != 9999) { // 輸入9999表示結束s = (LNode *)malloc(sizeof(LNode));s->data = x;s->next = NULL;if (L == NULL) {L = s; // 第一個節(jié)點直接作為鏈表頭} else {r->next = s; // 將新節(jié)點鏈接到鏈表尾部}r = s; // 更新表尾指針scanf("%d", &x);}return L;
}

這里假設輸入的值為10，也就是x=10，首先申請一個新的結點，并用s指針指向這一新結點

接著讓這一新結點的值為x：s->data=x; 并且讓r指向的結點的next指針指向向s：r->next=s;

最后讓r指針指向s：r=s;表示現(xiàn)在的表尾為s指向的結點，即r指針永遠指向鏈表最后一個結點

依次類推，若最后用戶輸入9999，那么r->next=NULL,最后返回這一鏈表

尾插法時間復雜度為O(n)

?頭插法建立單鏈表

頭插法每插入一個元素就是對頭結點的后插操作：

typedef struct LNode{int data;struct LNode *next;
}LNode,*LinkList;//初始化一個單鏈表(帶頭結點)
bool InitList(LinkList &L){L=(LNode *)malloc(sizeof(LNode));    //分配一個頭結點if(L==NULL)//內(nèi)存不足，分配失敗return false;L->next = NULL;//頭結點之后暫時還沒有節(jié)點return true;//頭插法（帶頭結點）
LinkList HeadInsert(LinkList &L){ //逆向建立單鏈表LNode *s;int x;L=(LinkList)malloc(sizeof(LNode));    //創(chuàng)建頭結點L->next=NULL;    //初始為空鏈表scanf("%d",&x);while(x!=9999){
//和后插操作一樣的邏輯，只是每次都是對頭結點進行后插操作s=(LNode*)malloc(sizeof(LNode));//創(chuàng)建新結點s->data=x;s->next=L->next;L->next=s;    //將新結點插入表中，L為頭指針scanf("%d",&x);}return L;
}//頭插法（不帶頭結點）
LinkList HeadInsert(LinkList &L) {L = NULL; // 初始化鏈表為空LNode *s;int x;scanf("%d", &x);while (x != 9999) {s = (LNode *)malloc(sizeof(LNode)); // 創(chuàng)建新結點s->data = x;s->next = L; // 將新結點插入鏈表頭部L = s; // 更新鏈表頭指針為新結點scanf("%d", &x);}return L;
}

注意：對于L->next=NULL

在尾插法中不寫這一句不會有影響，因為元素是插在鏈表的尾部，但是使用頭插法就一定不能缺這句代碼：

若沒有寫這句話，頭結點的next指針可能指向未知的區(qū)域：

接下來執(zhí)行s->next=L->next;

最后頭結點指向新的結點：

其他新結點插入的情況類似，最后的結點的next指針會指向未知的結點：

所以無論再寫尾插法還是頭插法，都建議初始化單鏈表，將頭指針指向NULL，即

L->next=NULL;

使用頭插法產(chǎn)生的結果是輸入元素的逆序：

如果需要單鏈表逆置，就可以用頭插法。

（3）雙鏈表

單鏈表無法逆向檢索，所以找前驅(qū)結點會比較麻煩，雙鏈表可以雙向檢索，就不會存在這個問題：

雙鏈表在單鏈表的基礎上加入了一個指針prior,指向前驅(qū)結點：?

typedef struct DNode{    //定義雙鏈表結點類型ElemType data;    //數(shù)據(jù)域struct DNode *prior,*next;    //前驅(qū)和后繼指針
}DNode,*DLinklist;

??雙鏈表的實現(xiàn)

雙鏈表的初始化：

typedef struct DNode{    //定義雙鏈表結點類型ElemType data;    //數(shù)據(jù)域struct DNode *prior,*next;    //前驅(qū)和后繼指針
}DNode,*DLinklist;//初始化雙鏈表
bool InitDLinkList(DLinklist &L){L=(DNode *)malloc(sizeof(DNode));     //分配一個頭結點if(L==NULL)    //內(nèi)存不足，分配失敗return false;L->prior = NULL;    //頭結點的 prior 永遠指向 NULLL->next = NULL;    //頭結點之后暫時還沒有節(jié)點return true;
}void testDLinkList(){
//初始化雙鏈表DLinklist L;InitDLinkList(L);
}//判斷雙鏈表是否為空(帶頭結點)
bool Empty(DLinklist L){if(L->next == NULL)    return true;elsereturn false;
}

雙鏈表的插入：

//在p結點之后插入s結點
bool InsertNextDNode(DNode *p,DNode *s){if(p==NULL || S==NULL)    //非法參數(shù)return false;s->next=p->next;if(p->next != NULL)    //如果p結點有后繼結點p->next->prior=s;s->prior=p;p->next=s;    return true;
}

① 首先將s的next指針指向p的next指針指向的結點：s->next=p->next;

② 如果p沒有后繼結點，直接跳到接下來步驟③。如果有后繼節(jié)點，就將p結點的后繼結點的前項指針指向s：p->next->prior=s;

③ 接下來將s的前項指針指向p結點：s->prior=p;

④ 最后將p的后項指針指向s結點：p->next=s;

修改指針時要注意順序，例如：

如果按④ ①執(zhí)行：

首先p的next指針指向s結點：

再讓s的next指針指向p的next指針指向的結點：

當我們進行按位插入時，只需要從頭結點開始，找到某個位序的前驅(qū)結點，然后對前驅(qū)結點進行后插操作接口。但我們想在某點前做前插操作，由于雙鏈表的特性，我們可以很方便地找到某一點地前驅(qū)結點，接著對前驅(qū)結點執(zhí)行后插操作即可。

所以其他的插入操作都可以轉換為用后插實現(xiàn)。

雙鏈表的刪除：

//刪除p結點的后繼結點
bool DeleteNextDNode(DNode *p){if(p==NULL)return false;DNode *q= p->next;    //找到p的后繼結點qif(q==NULL)    //p沒有后繼return false;p->next=q->next;if (q->next!=NULL)    //q結點不是最后一個結點q->next->prior=p;free(q);    //釋放結點空間return true;
}

聲明q指針，指向p的后繼結點。如果p沒有后繼，即q==NULL，返回false，否則：

① p結點的next指針會指向q結點的next指針指向的位置，也就是指向q的后繼結點：

p->next=q->next;

如果q不是最后一個結點，修改q的后繼結點的前項指針，執(zhí)行②；如果q是最后一個結點，就會直接執(zhí)行③

② q節(jié)點的后繼結點的前項指針指向p結點：

q->next->prior=p;

③ 釋放q結點：free(q)

q是最后一個結點，直接執(zhí)行③的結果：

雙鏈表的銷毀：

void DestoryList(DLinklist &L){    //循環(huán)釋放各個數(shù)據(jù)結點while(L->next != NULL)DeleteNextDNode(L);    //刪除頭結點的后繼結點free(L);    //最后釋放頭結點L=NULL;    //頭指針指向NULL
}

?雙鏈表的遍歷：

//后向遍歷
while (p!=NULL){    //對結點p做相應處理，如打印p= p->next;
}//前向遍歷
while (p!=NULL){    //對結點p做相應處理p= p->prior;
}//若只想處理數(shù)據(jù)結點，不想處理頭結點
while (p->prior!=NULL){    //如果p結點的前項指針指的是NULL的話，表明p指針此時指向的是頭結點p= p->prior;
}

?雙鏈表不可隨機存取，按位查找、按值查找操作都只能用遍歷的方式實現(xiàn)。時間復雜度O(n)

（4）循環(huán)鏈表

? 循環(huán)單鏈表

之前學習的單鏈表最后一個結點的next指針指向的是NULL，而循環(huán)單鏈表最后一個結點的next指針指向的是頭結點。

所以初始化單鏈表時，要將頭結點的指針指向自己：

typedef struct LNode{ElemType data;struct LNode *next;
}LNode, *LinkList;//初始化一個循環(huán)單鏈表
bool InitList(LinkList &L){L=(LNode *)malloc(sizeof(LNode));    //分配一個頭結點if (L==NULL)    //內(nèi)存不足，分配失敗return false;L->next = L;    //頭結點next指向頭結點return true;
}//判斷循環(huán)單鏈表是否為空
bool Empty(LinkList L){if(L->next == L)return true;elsereturn false;
}//判斷結點p是否為循環(huán)單鏈表的表尾結點
bool isTail(LinkList L,LNode *p){if (p->next==L)return true;elsereturn false;
}

對于單鏈表而言，從一個結點出發(fā)只能找到后續(xù)的各個結點。對于循環(huán)單鏈表而言，從一個結點出發(fā)可以找到其他任何一個結點。

對于單鏈表而言，從頭結點找到尾部，時間復雜度為O(n)，對于循環(huán)單鏈表而言，如果指針L不指向頭結點，而是指向尾部結點，那么從尾結點出發(fā)找到頭部結點只需要O(1)的時間復雜度。并且，如果需要對鏈表尾部進行操作，也可以在O(1)的時間復雜度找到操作的位置。?

如果應用場景中需要經(jīng)常對表頭或表尾進行操作，使用循環(huán)單鏈表時，可以讓L指向表尾元素。這樣的話，如果想在表尾進行插入，刪除時，就需要修改L。

? 循環(huán)雙鏈表

雙鏈表：表頭結點的 prior指向 NULL；表尾結點的next指向NULL。
循環(huán)雙鏈表：表頭結點的prior指向表尾結點；表尾結點的next指向頭結點。

所以初始化雙鏈表時，需要讓頭結點的前項指針和后項指針都指向頭結點自己，也就是頭結點既是第一個結點，也是最后一個結點。

typedef struct DNode{
ElemType data;
struct DNode *prior,*next;
}DNode, *DLinklist;//初始化空的循環(huán)雙鏈表
bool InitDLinkList(DLinklist &L){L=(DNode *)malloc(sizeof(DNode));    //分配一個頭結點if(L==NULL)    //內(nèi)存不足，分配失敗return false;L->prior =L;    //頭結點的 prior 指向頭結點L->next = L;    //頭結點的 next 指向頭結點return true;
}//判斷循環(huán)雙鏈表是否為空
bool Empty(DLinklist L){if(L->next == L)return true;elsereturn false;
}//判斷結點p是否為循環(huán)雙鏈表的表尾結點
bool isTail(DLinklist L,DNode *p){if(p->next == L)return true;elsereturn false;
}void testDLinkList(){//初始化循環(huán)雙鏈表DLinklist L;InitDLinkList(L);
}

?雙鏈表的插入：

//在p結點之后插入s結點
bool InsertNextDNode(DNode *p,DNode *s){s->next=p->next;    //將結點*s插入到結點*p之后p->next->prior=s;s->prior=p;p->next=s;
}

對于普通的雙鏈表會出現(xiàn)錯誤：

當p結點剛好是表尾結點時，p->next->prior=s;這句代碼會出現(xiàn)錯誤，因為p結點沒有后繼結點了。

但如果使用的是循環(huán)雙鏈表，這個邏輯就是對的，因為即便p結點是表尾結點，他的next指針指向的結點是非空的，將p的后繼結點的前項指針指向s是沒問題的。

雙鏈表的刪除：

雙鏈表的刪除同理：

∥刪除p的后繼結點q
p->next=q->next;
q->next->pior=p;
free(q);

?普通的雙鏈表中，執(zhí)行q->next->prior=p;會出現(xiàn)錯誤。而使用循環(huán)雙鏈表則沒有問題

（5）靜態(tài)鏈表

??靜態(tài)鏈表的相關概念

單鏈表中的各個結點是離散分布在內(nèi)存中的各個角落，每個結點會存放一個數(shù)據(jù)元素，以及指向下一個結點的指針（地址）。

靜態(tài)鏈表則分配一整片連續(xù)的內(nèi)存空間，各個結點集中安置。每個結點會存放一個數(shù)據(jù)元素，以及下一個結點的數(shù)組下標（游標）。

在靜態(tài)鏈表中，0號結點充當“頭結點”，頭結點中不存放數(shù)據(jù)元素，而頭結點的下一個結點被存放在了數(shù)據(jù)下標為2的位置。再往后的結點就是數(shù)組下標為1的結點，以此類推。所以靜態(tài)鏈表中的數(shù)組下標（游標），和單鏈表中的指針作用是相同的。

區(qū)別是，指針指明的是下一個結點的地址，而游標指明的是下一個結點的數(shù)據(jù)下標。

在單鏈表中，表尾結點的指針是指向NULL的，而在靜態(tài)鏈表中，表尾結點指向-1，表示靜態(tài)鏈表后沒有其他結點了。

因為靜態(tài)鏈表中各個結點是連續(xù)存放的，如果每個數(shù)據(jù)元素4B，每個游標4B(每個結點共8B)。設起始地址為 addr。那么數(shù)組下標為2的結點的存放地址就是addr+8*2。

這樣就能把靜態(tài)鏈表中的數(shù)組下標，映射為某個數(shù)組下標對應結點的實際存放位置。

??靜態(tài)鏈表的定義

#define Maxsize 10    //靜態(tài)鏈表的最大長度
struct Node{          //靜態(tài)鏈表結構類型的定義ElemType data;     //存儲數(shù)據(jù)元素int next;         //下一個元素的數(shù)組下標
};void testSLinkList(){struct Node a[Maxsize];    //數(shù)組a作為靜態(tài)鏈表
}

??

王道書上是這樣寫的：

#define Maxsize 10
typedef struct {ElemType data;int next;
}SLinkList[Maxsize];
//等價于
#define Maxsize 10
struct Node{ElemType data;int next;
};
typedef struct Node SLinkList[Maxsize];
//可用 sLinkList 定義“一個長度為 MaxSize 的Node 型數(shù)組”//當我們聲明一個SLinkList a時,其實是聲明了一個數(shù)組
//這個數(shù)組的元素個數(shù)為MaxSize，每個數(shù)組元素就是一個Struct Node結構體
void testSLinkList(){SLinkList a;
}
//等價于
void testSLinkList(){struct Node a[MaxSize];
}
//使用“SLinkList a”的寫法強調(diào)的是a是靜態(tài)鏈表

??靜態(tài)鏈表的相關基本操作

（1）初始化靜態(tài)鏈表：將a[0]的next設為-1。在內(nèi)存中沒有存放數(shù)據(jù)的地方，其實都存放著臟數(shù)據(jù)，可以在初始化時讓其它結點的next為某個特殊值用來表示結點空閑。例如-2，若某個結點的游標是-2，則表明這一結點時空閑的，可以用這個結點存放新的數(shù)據(jù)元素。

（2）查找：從頭結點出發(fā)挨個往后遍歷結點。所以查找某個位序的結點的平均時間復雜度為O(n)

（3）插入：

① 找到一個空的結點，存入數(shù)據(jù)元素。

② 從頭結點出發(fā)找到位序為i-1的結點。

③ 修改新結點的next。

④ 修改i-1號結點的next。

（4）刪除：

① 從頭結點出發(fā)找到前驅(qū)結點。

② 修改前驅(qū)結點的游標。

③ 被刪除結點 next 設為 -2。

總結：

雖然靜態(tài)鏈表的存儲空間是一整片的，連續(xù)的存儲空間，但是這片空間內(nèi)，邏輯上相鄰的數(shù)據(jù)元素，在物理上可以不相鄰，各個數(shù)據(jù)元素之間邏輯關系是由游標來指明的。

優(yōu)點：增、刪操作不需要大量移動元素，只要修改相關數(shù)據(jù)元素的游標即可。

缺點：不能隨機存取，只能從頭結點開始依次往后查找；容量固定不可變，只要聲明了一個靜態(tài)鏈表，他所能存放的最大容量就被固定了。

適用場景:①不支持指針的低級語言②數(shù)據(jù)元素數(shù)量固定不變的場景(如操作系統(tǒng)的文件分配表FAT)

（6）順序表和鏈表的對比

1.邏輯結構

順序表和鏈表在邏輯上都是線性結構的，都屬于線性表。

2.物理結構（存儲結構）

順序表：

順序表采用了順序存儲的方式，并且各個數(shù)據(jù)元素的大小相等，由于這兩個條件，只需要知道順序表的起始地址，就可以找到第i個元素存放的位置。也就是順序表具有隨機存取的特性。

并且順序表中的各個結點，只需要存儲各個元素本身，不需要存儲其他的冗余信息。因此順序表存儲密度高。

順序存儲的結構要求系統(tǒng)分配大片連續(xù)的存儲空間，所以分配空間時不方便。改變?nèi)萘恳膊环奖恪?/p>

鏈表：

若采用鏈式存儲的方式實現(xiàn)線性結構，由于各個結點可以離散地存放在內(nèi)存空間中，所以要添加一個元素時，只需要用malloc函數(shù)動態(tài)申請一小片空間即可，這樣分配空間就比較方便。由于各個結點的存儲空間不要求連續(xù)，因此改變?nèi)萘恳草^為方便。

但是鏈式存儲中要查找第i個結點時，只能從表頭開始遍歷尋找，所以不可隨機存取。并且由于各個結點除了存儲數(shù)據(jù)元素外，還需要花費一定空間存儲指針，所以存儲密度較低。

3.數(shù)據(jù)運算/基本操作

??初始化

順序表：

1.由于順序表初始化需要一整片的內(nèi)存空間，所以需要預分配大片連續(xù)空間，若分配空間過小，則之后不方便拓展容量;若分配空間過大，則浪費內(nèi)存資源。

2.若順序表采用靜態(tài)分配，那么靜態(tài)數(shù)組的容量是固定的。即便采用動態(tài)分配的方式，更改動態(tài)數(shù)組的容量也需要移動大量的元素，時間代價高。

鏈表：

1.初始化鏈表時，只需分配一個頭結點(也可以不要頭結點，只聲明一個頭指針)，之后方便拓展。

采用鏈表，存儲空間更加靈活。

??銷毀

順序表：

1.首先將length=0，這步操作只是在邏輯上把順序表置空。但是順序表占用的存儲空間還沒有回收。

2.若采用靜態(tài)分配，就意味著順序表占用的存儲空間是通過聲明靜態(tài)數(shù)組的方式請求系統(tǒng)分配的。這種情況下，系統(tǒng)會自動回收空間。

3.若采用動態(tài)分配的方式，也就是使用malloc函數(shù)申請的一片內(nèi)存空間，那么就需要用free函數(shù)手動釋放空間。因為malloc函數(shù)申請的空間屬于內(nèi)存的堆區(qū)，堆區(qū)的內(nèi)存空間系統(tǒng)不會自動回收。

L.data =(ElemType *)malloc(sizeof(ElemType)*InitSize)
free(L.data);

鏈表：

通過free函數(shù)，利用循環(huán)依次刪除各個結點。

注：malloc和free必須成對存在。

??增刪

順序表：

1.由于順序表中的各個元素在內(nèi)存中是相鄰并且有序的，所以在插入/刪除元素要將后續(xù)元素都后移/前移。

2.順序表的插入時間復雜度和刪除時間復雜度都是O(n)，時間開銷主要來自移動元素。若數(shù)據(jù)元素很大，則移動的時間代價很高。

鏈表：

1.插入/刪除元素只需修改指針即可。

2.鏈表的時間復雜度也為 O(n)，時間開銷主要來自查找目標元素。查找元素的時間代價相比于移動大量元素的時間代價更低。

所以雖然順序表和鏈表的插入，刪除操作時間復雜度都為O(n)，但是實際上，鏈表的效率比順序表高得多。

??查找

順序表：

1.順序表具有隨機存取的特性，采用按位查找的時間復雜度為O(1)。

2.采用按值查找，時間復雜度為O(n)，若表內(nèi)元素有序，采用安值查找，那么可在O(log2n)時間內(nèi)找到（采用折半查找等方式）。

鏈表：

1.鏈表只能從第一個數(shù)據(jù)元素開始依次遍歷查找，按位查找時間復雜度為O(n)。

2.按值查找，也只能從第一個數(shù)據(jù)元素依次往后遍歷，時間復雜度為O(n)。

所以查找操作中順序表效率高很多。

??總結：

1.如果線性表表長難以估計，并且經(jīng)常需要增加/刪除元素，那么就使用鏈表。

2.如果線性表表長可預估，查詢(搜索)操作比較多。那么就采用順序表。