目錄

1.線性表的概念

2.線性表的基本操作

3.存儲(chǔ)線性表的方式

（1）順序表

?順序表的概念

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

靜態(tài)分配：

動(dòng)態(tài)分配：

順序表的插入：

順序表的刪除：

順序表的按位查找：

順序表的按值查找：

順序表的特點(diǎn)：

（2）單鏈表

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

不帶頭結(jié)點(diǎn)的單鏈表：

帶頭結(jié)點(diǎn)的單鏈表：

單鏈表的插入：

?按位序插入（帶頭結(jié)點(diǎn)）

?按位序插入（不帶頭結(jié)點(diǎn)）

?指定結(jié)點(diǎn)的后插操作

?指定結(jié)點(diǎn)的前插操作

單鏈表的刪除：

?按位序刪除（帶頭結(jié)點(diǎn)）

?按位序刪除（不帶頭結(jié)點(diǎn)）

?指定結(jié)點(diǎn)的刪除

單鏈表的查找：

?按位查找

?按值查找

單鏈表的長(zhǎng)度：

單鏈表的兩種建立方法：

?尾插法建立單鏈表

?頭插法建立單鏈表

（3）雙鏈表

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

雙鏈表的初始化：

雙鏈表的插入：

雙鏈表的刪除：

雙鏈表的銷毀：

?雙鏈表的遍歷：

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

? 循環(huán)單鏈表

? 循環(huán)雙鏈表

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

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

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

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

（6）順序表和鏈表的對(duì)比

1.邏輯結(jié)構(gòu)

2.物理結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)）

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

??初始化

??銷毀

??增刪

??查找

??總結(jié)：

1.線性表的概念

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

注：

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

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

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

2.線性表的基本操作

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

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

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

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

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

關(guān)于"&":

對(duì)于下面的代碼：

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

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

對(duì)比下面這段代碼：

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

3.存儲(chǔ)線性表的方式

（1）順序表

?順序表的概念

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

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

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

靜態(tài)分配：

#define MaxSize 10         //定義最大長(zhǎng)度
typedef struct{            
    ElemType data[MaxSize];    //用靜態(tài)的“數(shù)組”存放數(shù)據(jù)元素
    int length;                //順序表的當(dāng)前長(zhǎng)度
}SqList;                   //順序表的類型定義(靜態(tài)分配方式)

/*這里的ElemType指的是元素的類型，可以是int也可以是struct，這取決于順序表存儲(chǔ)的數(shù)據(jù)類型*/

具體地看個(gè)示例：?

#include<stdio.h>
#define MaxSize 10         //定義最大長(zhǎng)度
typedef struct{            
    int data[MaxSize];    //用靜態(tài)的“數(shù)組”存放數(shù)據(jù)元素
    int length;                //順序表的當(dāng)前長(zhǎng)度
}SqList;                   //順序表的類型定義(靜態(tài)分配方式)

//初始化一個(gè)順序表
void InitList(SqList &L){
    for(int i=0;i<MaxSize;i++)
        L.data[i]=0;    //將所有數(shù)據(jù)元素設(shè)置為默認(rèn)初始值
    L.length=0;    //順序表初始長(zhǎng)度為0    
}

int main(){
    SqList L;    //聲明一個(gè)順序表，表示在內(nèi)存中分配存儲(chǔ)順序表L的空間，包括:MaxSize*sizeof(ElemType)和 存儲(chǔ) length 的空間
    InitList(L); //初始化順序表
    return 0;
}

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

#include<stdio.h>
#define MaxSize 10         //定義最大長(zhǎng)度
typedef struct{            
    int data[MaxSize];    //用靜態(tài)的“數(shù)組”存放數(shù)據(jù)元素
    int length;                //順序表的當(dāng)前長(zhǎng)度
}SqList;                   //順序表的類型定義(靜態(tài)分配方式)

//初始化一個(gè)順序表
void InitList(SqList &L){
    L.length=0;    //順序表初始長(zhǎng)度為0    
}

int main(){
    SqList L;    
    InitList(L); //初始化順序表
    //"違規(guī)"打印整個(gè)data數(shù)組
    for(int i=0;i<MaxSize;i++)
        printf("data[%d]=%d\n",i,L.data[i]);
    return 0;
}

打印結(jié)果如下：

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

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

#include<stdio.h>
#define MaxSize 10         //定義最大長(zhǎng)度
typedef struct{            
    int data[MaxSize];    //用靜態(tài)的“數(shù)組”存放數(shù)據(jù)元素
    int length;                //順序表的當(dāng)前長(zhǎng)度
}SqList;                   //順序表的類型定義(靜態(tài)分配方式)

//初始化一個(gè)順序表
void InitList(SqList &L){
    L.length=0;    //順序表初始長(zhǎng)度為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)存空間是固定的，若設(shè)置的內(nèi)存空間過(guò)小，那么數(shù)組很容易被存滿，如果過(guò)大，則浪費(fèi)內(nèi)存空間。所以可以采用動(dòng)態(tài)分配。

動(dòng)態(tài)分配：

//malloc和free函數(shù)的頭文件
#include<stdlib.h>
#define InitSize 10
typedef struct{
    int *data;    //指示動(dòng)態(tài)分配數(shù)組的指針，這里是整型指針
    int MaxSize;
    int length;
}SeqList;

//使用malloc和free動(dòng)態(tài)申請(qǐng)和釋放內(nèi)存空間
void InitList(seqList &L){
    L.data=(int *)malloc(InitSize*sizeof(int));
//malloc函數(shù)的參數(shù)指明要分配多大的連續(xù)內(nèi)存空間
//malloc函數(shù)返回一個(gè)指針，需要強(qiáng)制轉(zhuǎn)型定義的數(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指針指向同一個(gè)內(nèi)存空間

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

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

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

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

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

順序表的插入：

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

#include <stdio.h>

#define MaxSize 10

typedef 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;  // 當(dāng)前存儲(chǔ)空間已滿，不能插入
    for (int j = L.length; j >= i; j--)
        L.data[j] = L.data[j - 1];  // 將第i個(gè)元素及之后的元素后移
    L.data[i - 1] = e;              // 在位置i上放入e
    L.length++;                     // L長(zhǎng)度加1
    return true;
}

int main() {
    SqList L;
    InitList(L);
	for (int i = 0; i < 5; i++) {
    	ListInsert(L, i + 1, i + 1); // 插入元素，自動(dòng)更新長(zhǎng)度
	}
	
    printf("插入前的順序表為:\n");
    for (int i = 0; i < L.length; i++) {
        printf("%d ", L.data[i]);
    }
    printf("\n");

    ListInsert(L, 3, 99);  // 在第3位插入元素99

    printf("插入后的順序表為:\n");
    for (int i = 0; i < L.length; i++) {
        printf("%d ", L.data[i]);
    }
    printf("\n");

    return 0;
}

實(shí)現(xiàn)結(jié)果：

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

注：?jiǎn)栴}規(guī)模n就是線性表的表長(zhǎng)L.length

最好情況：新元素插入到表尾，不需要移動(dòng)元素

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

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

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

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

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

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

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

順序表的刪除：

刪除表與插入表的操作相反，就是將要?jiǎng)h除的元素的后面的元素往前移動(dòng)一位，并且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++)   //將被刪除的元素賦給e
        L.data[j-1]=L.data[j];    //將第i個(gè)位置后的位置前移
    L.length--;    //線性表長(zhǎng)度減1
    return 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;    //聲明一個(gè)變量e，初始值設(shè)為-1
    if(ListDelete(L,3,e))
        printf("\n已刪除第3個(gè)元素，刪除元素值=%d\n",e); 
    else
        printf("位序i不合法，刪除失敗\n");
    printf("刪除元素后的順序表為:\n"); 
    for(int i=0;i<L.length;i++){
		printf("%d ",L.data[i]);
	}
    return 0;   
}

實(shí)現(xiàn)結(jié)果：

注意：

（1）

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

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

接著調(diào)用ListDelete()時(shí)，會(huì)把要?jiǎng)h除的變量的值復(fù)制到e變量所對(duì)應(yīng)的內(nèi)存區(qū)域中，即

e=L.data[i-1];

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

（2）

刪除操作中，i位置后的元素往前移，是先從前面的元素往前移動(dòng)的，而插入操作中，是先從后面的元素往后移動(dòng)的。這個(gè)應(yīng)該很好理解。

刪除操作的時(shí)間復(fù)雜度是多少呢？

最好情況：刪除表尾元素，不需要移動(dòng)其他元素

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

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

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

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

平均時(shí)間復(fù)雜度=O(n)

?寫代碼要注意：

1.題目中的i是位序i（從1開始），還是數(shù)組下標(biāo)i（從0開始），例如，第3個(gè)元素其實(shí)數(shù)組下標(biāo)為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];
}


//動(dòng)態(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];
}

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

如圖所示，計(jì)算機(jī)會(huì)根據(jù)指針?biāo)赶驍?shù)據(jù)類型的空間大小，計(jì)算每個(gè)數(shù)組下標(biāo)對(duì)應(yīng)哪些字節(jié)的數(shù)據(jù)。

例如int型變量：

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

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

順序表的按值查找：

#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ù)組下標(biāo)為i的元素值等于e,返回其位序i+1
    return 0;    //退出循環(huán)，說(shuō)明查找失敗

}

注意：“==”不能比較兩個(gè)結(jié)構(gòu)體類型：

需要依次對(duì)比各個(gè)分量比較兩個(gè)結(jié)構(gòu)體是否相等：?

按值查找的時(shí)間復(fù)雜度：

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

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

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

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

平均時(shí)間復(fù)雜度為：O(n)

順序表的特點(diǎn)：

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

②存儲(chǔ)密度高，每個(gè)節(jié)點(diǎn)只存儲(chǔ)數(shù)據(jù)元素。

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

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

（2）單鏈表

邏輯結(jié)構(gòu)為線性表的數(shù)據(jù)，物理上也能采用鏈?zhǔn)酱鎯?chǔ)的方式。

順序表：

優(yōu)點(diǎn):可隨機(jī)存取，存儲(chǔ)密度高

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

單鏈表：

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

缺點(diǎn):不可隨機(jī)存取，要耗費(fèi)一定空間存放指針

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

struct LNode{    //定義單鏈表結(jié)點(diǎn)類型
ElemType data;   //每個(gè)節(jié)點(diǎn)存放一個(gè)數(shù)據(jù)元素
struct LNode *next;    //指針指向下一個(gè)節(jié)點(diǎn)
};

//增加一個(gè)新的結(jié)點(diǎn):在內(nèi)存中申請(qǐng)一個(gè)結(jié)點(diǎn)所需空間，并用指針p指向這個(gè)結(jié)點(diǎn)
struct LNode *p=(struct LNode *)malloc(sizeof(struct LNode));

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

這樣：

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

可以寫為：

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

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

struct LNode{
    ElemType data;
    struct LNode *next;
 };
typedef struct LNode LNode;
typedef struct LNode *LinkList;

//更簡(jiǎn)潔地：
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

要表示一個(gè)單鏈表時(shí)，只需聲明一個(gè)頭指針L，指向單鏈表的第一個(gè)結(jié)點(diǎn)

LNODE * L;    //聲明一個(gè)指向單鏈表第一個(gè)結(jié)點(diǎn)的指針
或者
LinkList L;


typedef struct LNode{    //定義單鏈表節(jié)點(diǎn)類型
    ElemType data;       //每個(gè)節(jié)點(diǎn)存放一個(gè)數(shù)據(jù)元素
    struct LNode *next;  //指針指向下一個(gè)節(jié)點(diǎn)    
}LNode,*LinkList;

//這里用LNode* 和 LinkList 表示都可以，只是前面用LNode*強(qiáng)調(diào)返回的是一個(gè)結(jié)點(diǎn)，后面用LinkList強(qiáng)調(diào)返回的是一個(gè)單鏈表
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;
}

不帶頭結(jié)點(diǎn)的單鏈表：

typedef struct LNode{
    ElemType data;
    struct Lnode *next;
}LNode,*LinkList;

//初始化一個(gè)空的單鏈表
bool InitList(LinkList &L){
    L = NULL;    //空表，暫時(shí)還沒有任何結(jié)點(diǎn),設(shè)為NULL的目的是防止遺留的臟數(shù)據(jù)
    return true;
}

void test(){
    LinkList L;    //聲明一個(gè)單鏈表指針
    InitList(L);
}

//判斷單鏈表是否為空
bool Empty(LinkList L){
    if(L == NULL)
        return true;
    else
        return false;
}
//或者，直接寫為
bool Empty(LinkList L){
    return(L=NULL);
}

帶頭結(jié)點(diǎn)的單鏈表：

typedef struct LNode{
    ElemType data;
    struct Lnode *next;
}LNode,*LinkList;

//初始化一個(gè)空的單鏈表
bool InitList(LinkList &L){
    L=(LNode *)malloc(sizeof(LNode));    
    if(L==NULL)
        return false;
    L->next=NULL;    //頭結(jié)點(diǎn)之后暫時(shí)還沒有節(jié)點(diǎn)
    return true;
}

void test(){
    LinkList L;    //聲明一個(gè)單鏈表指針
    InitList(L);
}

//判斷單鏈表是否為空
bool Empty(LinkList L){
    if(L->next == NULL)
        return true;
    else
        return false;
}
//或者，直接寫為
bool Empty(LinkList L){
    return(L->next == NULL);
}

?注：頭結(jié)點(diǎn)是不存儲(chǔ)數(shù)據(jù)的，設(shè)置頭結(jié)點(diǎn)只是為了后續(xù)處理更加方便。因?yàn)椴粠ь^結(jié)點(diǎn)的話，對(duì)第一個(gè)數(shù)據(jù)結(jié)點(diǎn)和后續(xù)數(shù)據(jù)結(jié)點(diǎn)的處理需要用不同的代碼邏輯。對(duì)空表和非空表的處理也需要用不同的代碼邏輯。

單鏈表的插入：

?按位序插入（帶頭結(jié)點(diǎn)）

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

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

//在第i個(gè)位置插入元素e(帶頭結(jié)點(diǎn))
bool ListInsert(LinkList &L,int i,ElemType e){
    if(i<1)
        return false;
    LNode *p;    //指針p指向當(dāng)前掃描到的結(jié)點(diǎn)
    int j=0;     //當(dāng)前p指向的是第幾個(gè)結(jié)點(diǎn)
    p = L;       //L指向頭結(jié)點(diǎn)，頭結(jié)點(diǎn)是第0個(gè)結(jié)點(diǎn)(不存數(shù)據(jù))
    while(p!=NULL && j<i-1){     //循環(huán)找到第 i-1 個(gè)結(jié)點(diǎn)
//因?yàn)橐诘趇個(gè)位置插入，所以要找到第i-1個(gè)結(jié)點(diǎn)，在i-1個(gè)結(jié)點(diǎn)后插入
        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;      //將結(jié)點(diǎn)s連到p之后
    return true;    //插入成功
}

如果i=1，即插在表頭

因?yàn)閕=1，不滿足j<i-1，不會(huì)跳到while(p!=NULL && j<i-1)

LNode *s=(LNode*)malloc(sizeof(LNOde));//申請(qǐng)一個(gè)結(jié)點(diǎn)空間

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

s->next=p->next;//s指向結(jié)點(diǎn)的next指針等于p結(jié)點(diǎn)next指針指向的位置

p->next=s;//p結(jié)點(diǎn)的next指針指向新結(jié)點(diǎn)

這種情況，因?yàn)閕=1，while循環(huán)直接被跳過(guò)，所以時(shí)間復(fù)雜度為O(1)，這也是最好時(shí)間復(fù)雜度。

如果i=5，那么就是在第四個(gè)結(jié)點(diǎn)后插入：

s->next=p->next; //s的next指針指向p的next指針，由于p結(jié)點(diǎn)的next指針指向的是NULL，所以s的next指針也指向NULL

p->next=s;//最后，p的next指針指向新的結(jié)點(diǎn)

將新結(jié)點(diǎn)插到表尾，即最壞時(shí)間復(fù)雜度，為O(n)

平均時(shí)間復(fù)雜度也為O(n)

如果i=6，那么在while循環(huán)中j=5時(shí)，p==NULL，就會(huì)進(jìn)入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指針，就會(huì)出現(xiàn)如下情況：

?按位序插入（不帶頭結(jié)點(diǎn)）

不帶頭結(jié)點(diǎn)的插入中不存在“第0個(gè)”結(jié)點(diǎn)，所以i=1時(shí)需要特殊處理：

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

//在第i個(gè)位置插入元素e(不帶頭結(jié)點(diǎn))
bool ListInsert(LinkList &L,int i,ElemType e){
    if(i<1)
        return false;

    if(i==1){//插入第一個(gè)結(jié)點(diǎn)的操作與其他結(jié)點(diǎn)操作不同
        LNode *s=(LNode *)malloc(sizeof(LNode));
        s->data=e;
        s->next=L;
        L=s;    //頭指針指向新結(jié)點(diǎn)
        return true;
}

    LNode *p;    
    int j=1;     //這里j=1
    p = 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;      //將結(jié)點(diǎn)s連到p之后
    return true;    //插入成功
}

如果i=1?：

首先申請(qǐng)一個(gè)新的結(jié)點(diǎn)，放入?yún)?shù)e

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

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

? ? ? ? s->next=L;

最后修改頭指針L，使L指向新的結(jié)點(diǎn)

? ? ? ? L=s;

所以，如果不帶頭結(jié)點(diǎn)，則插入、刪除第1個(gè)元素時(shí)，需要更改頭指針L（L=s），如果帶頭結(jié)點(diǎn)的話，頭指針永遠(yuǎn)都是指向頭結(jié)點(diǎn)的。

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

而帶頭結(jié)點(diǎn)，剛開始指向的是第“0”個(gè)結(jié)點(diǎn)：

?指定結(jié)點(diǎn)的后插操作

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

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

//后插操作:在p結(jié)點(diǎn)之后插入元素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;    //用結(jié)點(diǎn)s保存數(shù)據(jù)元素e
    s->next=p->next;
    p->next=s;    //將結(jié)點(diǎn)s連到p之后
    return true;
}

時(shí)間復(fù)雜度為O(1)

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

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;

//后插操作:在p結(jié)點(diǎn)之后插入元素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;    //用結(jié)點(diǎn)s保存數(shù)據(jù)元素e
    s->next=p->next;
    p->next=s;    //將結(jié)點(diǎn)s連到p之后
    return true;
}

//在第i個(gè)位置插入元素e(帶頭結(jié)點(diǎn))
bool ListInsert(LinkList &L,int i,ElemType e){
    if(i<1)
        return false;
    LNode *p;    //指針p指向當(dāng)前掃描到的結(jié)點(diǎn)
    int j=0;     //當(dāng)前p指向的是第幾個(gè)結(jié)點(diǎn)
    p = L;       //L指向頭結(jié)點(diǎn)，頭結(jié)點(diǎn)是第0個(gè)結(jié)點(diǎn)(不存數(shù)據(jù))
    while(p!=NULL && j<i-1){     //循環(huán)找到第 i-1 個(gè)結(jié)點(diǎn)
//因?yàn)橐诘趇個(gè)位置插入，所以要找到第i-1個(gè)結(jié)點(diǎn)，在i-1個(gè)結(jié)點(diǎn)后插入
        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;      //將結(jié)點(diǎn)s連到p之后
    return true;    //插入成功
*/
}

?指定結(jié)點(diǎn)的前插操作

之前說(shuō)過(guò)單鏈表只知道p結(jié)點(diǎn)后的元素，那么如何找到p的前驅(qū)結(jié)點(diǎn)呢？

可以傳入頭指針

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

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

時(shí)間復(fù)雜度為O(n)

如果沒有傳入頭結(jié)點(diǎn)，可以這樣實(shí)現(xiàn)：

//前插操作:在p結(jié)點(diǎn)之前插入元素 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;    //新結(jié)點(diǎn) s連到 p 之后
    s->data=p->data;
    p->data=e;    //將p中元素復(fù)制到s中
    return true;    //p 中元素覆蓋為 e

?首先申請(qǐng)一個(gè)新的結(jié)點(diǎn)，并把這一結(jié)點(diǎn)作為p結(jié)點(diǎn)的后繼節(jié)點(diǎn)：

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

最后將要新插入的元素e覆蓋原來(lái)p結(jié)點(diǎn)存放的元素x：

這樣，即使沒有傳入頭結(jié)點(diǎn)，也可以完成前插操作。

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

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

//前插操作:在p結(jié)點(diǎn)之前插入結(jié)點(diǎn) 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;
}

單鏈表的刪除：

注：對(duì)于刪除結(jié)點(diǎn)的操作只探討帶頭結(jié)點(diǎn)的情況

?按位序刪除（帶頭結(jié)點(diǎn)）

具體地將頭結(jié)點(diǎn)看作"第0個(gè)"結(jié)點(diǎn)，找到第 i-1?個(gè)結(jié)點(diǎn)，將其指針指向第 i+1 個(gè)結(jié)點(diǎn)，并釋放第i個(gè)結(jié)點(diǎn)。

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指向當(dāng)前掃描到的結(jié)點(diǎn)
    int j=0;     //當(dāng)前p指向的是第幾個(gè)結(jié)點(diǎn)
    p = L;       //L指向頭結(jié)點(diǎn)，頭結(jié)點(diǎn)是第0個(gè)結(jié)點(diǎn)(不存數(shù)據(jù))
    while(p!=NULL && j<i-1){     //循環(huán)找到第 i-1 個(gè)結(jié)點(diǎn)
        p=p->next;    
        j++;
    }

    if(p==NULL)    //i值不合法
        return false;
    if(p->next == NULL)   //第i-1個(gè)結(jié)點(diǎn)之后已無(wú)其他結(jié)點(diǎn)
        return false;
    LNode *q=p->next;    //令q指向被刪除結(jié)點(diǎn)
    e = q->data;         //用e返回元素的值
    p->next=q->next;     //將*q結(jié)點(diǎn)從鏈中“斷開”
    free(q);             //釋放結(jié)點(diǎn)的存儲(chǔ)空間
    return true;         //刪除成功
}

如果i=4，經(jīng)過(guò)while循環(huán)后，p會(huì)指向第3個(gè)結(jié)點(diǎn)（i-1個(gè)結(jié)點(diǎn)）：

將q指針指向p結(jié)點(diǎn)的next元素，即第i個(gè)結(jié)點(diǎn)：LNode *q=p->next

接下來(lái)會(huì)把q指針指向的結(jié)點(diǎn)中的元素復(fù)制給變量e：e=q->data

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

p->next=q->next;

free(q);

?按位序刪除（不帶頭結(jié)點(diǎn)）

不帶頭結(jié)點(diǎn)的刪除，若刪除第一個(gè)元素，那么需要更改頭指針，和不帶頭結(jié)點(diǎn)的操作類似：

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;    // 將頭指針指向第一個(gè)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)
        free(q);        // 釋放第一個(gè)結(jié)點(diǎn)的內(nèi)存空間
        return true;
    }

    LNode *p;    
    int j=1;
    p = L;  
    while(p!=NULL && j<i-1){     //循環(huán)找到第 i-1 個(gè)結(jié)點(diǎn)
        p=p->next;    
        j++;
    }

    if(p==NULL)    //i值不合法
        return false;
    if(p->next == NULL)   //第i-1個(gè)結(jié)點(diǎn)之后已無(wú)其他結(jié)點(diǎn)
        return false;
    LNode *q=p->next;    //令q指向被刪除結(jié)點(diǎn)
    e = q->data;         //用e返回元素的值
    p->next=q->next;     //將*q結(jié)點(diǎn)從鏈中“斷開”
    free(q);             //釋放結(jié)點(diǎn)的存儲(chǔ)空間
    return true;         //刪除成功
}

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

最好時(shí)間復(fù)雜度：O(1)

?指定結(jié)點(diǎn)的刪除

如果要?jiǎng)h除結(jié)點(diǎn)p，需要修改前驅(qū)結(jié)點(diǎn)的next指針：

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

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

聲明結(jié)點(diǎn)q，指向p的后繼結(jié)點(diǎn)：LNode *q=p->next;

?

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

將p結(jié)點(diǎn)的next指針，指向q結(jié)點(diǎn)之后的位置：p->next=q->next;

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

時(shí)間復(fù)雜度：O(1)

若刪除的結(jié)點(diǎn)時(shí)最后一個(gè)結(jié)點(diǎn)，那么代碼執(zhí)行到：p->data = p->next->data 就會(huì)出錯(cuò)，因?yàn)檎也坏絧結(jié)點(diǎn)的后繼結(jié)點(diǎn)，這樣的話，只能從表頭開始依次尋找p的前驅(qū)，時(shí)間復(fù)雜度:O(n)。

單鏈表的查找：

?按位查找

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

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

②如果i的值大于鏈表的實(shí)際長(zhǎng)度，例如i=8，最后返回NULL

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

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

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

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

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

//后插操作:在p結(jié)點(diǎn)之后插入元素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;    //用結(jié)點(diǎn)s保存數(shù)據(jù)元素e
    s->next=p->next;
    p->next=s;    //將結(jié)點(diǎn)s連到p之后
    return true;
}

//在第i個(gè)位置插入元素e(帶頭結(jié)點(diǎn))
bool ListInsert(LinkList &L,int i,ElemType e){
    if(i<1)
        return false;
    LNode *p=GetElem(L,i-1); //找到第i-1個(gè)結(jié)點(diǎn)
    return InsertNextNode(p,e);    //p后插入新元素e
}

//刪除第i個(gè)位置的元素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個(gè)結(jié)點(diǎn)之后已無(wú)其他結(jié)點(diǎn)
        return false;
    LNode *q=p->next;    //令q指向被刪除結(jié)點(diǎn)
    e = q->data;         //用e返回元素的值
    p->next=q->next;     //將*q結(jié)點(diǎn)從鏈中“斷開”
    free(q);             //釋放結(jié)點(diǎn)的存儲(chǔ)空間
    return true;         //刪除成功
}

?按值查找

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

按值查找的時(shí)間復(fù)雜度為O(n)

單鏈表的長(zhǎng)度：

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

//不帶頭結(jié)點(diǎn)
int Length(LinkList L) {
    int len = 0; // 統(tǒng)計(jì)鏈表長(zhǎng)度
    LNode* p = L;
   
    if (p == NULL) {
        return len;
    }

    while (p != NULL) {
        len++;
        p = p->next;
    }
    
    return len;
}

求表的長(zhǎng)度，時(shí)間復(fù)雜度O(n)?

單鏈表的兩種建立方法：

?尾插法建立單鏈表

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

typedef struct LNode{
    int data;
    struct LNode *next;
}LNode,*LinkList;

//初始化一個(gè)單鏈表(帶頭結(jié)點(diǎn))
bool InitList(LinkList &L){
    L=(LNode *)malloc(sizeof(LNode));    //分配一個(gè)頭結(jié)點(diǎn)
    if(L==NULL)//內(nèi)存不足，分配失敗
        return false;
    L->next = NULL;//頭結(jié)點(diǎn)之后暫時(shí)還沒有節(jié)點(diǎn)
    return true;


// 尾部插入節(jié)點(diǎn)（帶頭結(jié)點(diǎn)）
LinkList TailInsert(LinkList &L) {
    L = (LinkList)malloc(sizeof(LNode)); // 建立頭結(jié)點(diǎn)
    L->next = NULL; // 頭結(jié)點(diǎn)的next指針初始化為NULL
    int x;
    LNode *s, *r = L; // r為表尾指針
    printf("請(qǐng)輸入節(jié)點(diǎn)的值，輸入9999表示結(jié)束：\n");
    scanf("%d", &x); // 輸入結(jié)點(diǎn)的值
    while (x != 9999) { // 輸入9999表示結(jié)束
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next = s; // 將新節(jié)點(diǎn)鏈接到鏈表尾部
        r = s; // 更新表尾指針
        scanf("%d", &x);
    }
    r->next = NULL; // 將表尾節(jié)點(diǎn)的next指針設(shè)置為NULL
    return L;
}


// 尾部插入節(jié)點(diǎn)（不帶頭結(jié)點(diǎn)）
LinkList TailInsert(LinkList &L) {
    L = NULL; // 初始化鏈表為空
    int x;
    LNode *s, *r = NULL; // r為表尾指針
    printf("請(qǐng)輸入節(jié)點(diǎn)的值，輸入9999表示結(jié)束：\n");
    scanf("%d", &x); // 輸入結(jié)點(diǎn)的值
    while (x != 9999) { // 輸入9999表示結(jié)束
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        s->next = NULL;

        if (L == NULL) {
            L = s; // 第一個(gè)節(jié)點(diǎn)直接作為鏈表頭
        } else {
            r->next = s; // 將新節(jié)點(diǎn)鏈接到鏈表尾部
        }

        r = s; // 更新表尾指針
        scanf("%d", &x);
    }
    return L;
}

這里假設(shè)輸入的值為10，也就是x=10，首先申請(qǐng)一個(gè)新的結(jié)點(diǎn)，并用s指針指向這一新結(jié)點(diǎn)

接著讓這一新結(jié)點(diǎn)的值為x：s->data=x; 并且讓r指向的結(jié)點(diǎn)的next指針指向向s：r->next=s;

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

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

尾插法時(shí)間復(fù)雜度為O(n)

?頭插法建立單鏈表

頭插法每插入一個(gè)元素就是對(duì)頭結(jié)點(diǎn)的后插操作：

typedef struct LNode{
    int data;
    struct LNode *next;
}LNode,*LinkList;

//初始化一個(gè)單鏈表(帶頭結(jié)點(diǎn))
bool InitList(LinkList &L){
    L=(LNode *)malloc(sizeof(LNode));    //分配一個(gè)頭結(jié)點(diǎn)
    if(L==NULL)//內(nèi)存不足，分配失敗
        return false;
    L->next = NULL;//頭結(jié)點(diǎn)之后暫時(shí)還沒有節(jié)點(diǎn)
    return true;

//頭插法（帶頭結(jié)點(diǎn)）
LinkList HeadInsert(LinkList &L){ //逆向建立單鏈表
    LNode *s;
    int x;
    L=(LinkList)malloc(sizeof(LNode));    //創(chuàng)建頭結(jié)點(diǎn)
    L->next=NULL;    //初始為空鏈表
    scanf("%d",&x);
    while(x!=9999){
//和后插操作一樣的邏輯，只是每次都是對(duì)頭結(jié)點(diǎn)進(jìn)行后插操作
        s=(LNode*)malloc(sizeof(LNode));//創(chuàng)建新結(jié)點(diǎn)
        s->data=x;
        s->next=L->next;
        L->next=s;    //將新結(jié)點(diǎn)插入表中，L為頭指針
        scanf("%d",&x);
    }
    return L;
}

//頭插法（不帶頭結(jié)點(diǎn)）
LinkList HeadInsert(LinkList &L) {
    L = NULL; // 初始化鏈表為空
    LNode *s;
    int x;
    scanf("%d", &x);
    while (x != 9999) {
        s = (LNode *)malloc(sizeof(LNode)); // 創(chuàng)建新結(jié)點(diǎn)
        s->data = x;
        s->next = L; // 將新結(jié)點(diǎn)插入鏈表頭部

        L = s; // 更新鏈表頭指針為新結(jié)點(diǎn)

        scanf("%d", &x);
    }
    return L;
}

注意：對(duì)于L->next=NULL

在尾插法中不寫這一句不會(huì)有影響，因?yàn)樵厥遣逶阪湵淼奈膊?，但是使用頭插法就一定不能缺這句代碼：

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

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

最后頭結(jié)點(diǎn)指向新的結(jié)點(diǎn)：

其他新結(jié)點(diǎn)插入的情況類似，最后的結(jié)點(diǎn)的next指針會(huì)指向未知的結(jié)點(diǎn)：

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

L->next=NULL;

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

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

（3）雙鏈表

單鏈表無(wú)法逆向檢索，所以找前驅(qū)結(jié)點(diǎn)會(huì)比較麻煩，雙鏈表可以雙向檢索，就不會(huì)存在這個(gè)問(wèn)題：

雙鏈表在單鏈表的基礎(chǔ)上加入了一個(gè)指針prior,指向前驅(qū)結(jié)點(diǎn)：?

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

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

雙鏈表的初始化：

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

//初始化雙鏈表
bool InitDLinkList(DLinklist &L){
    L=(DNode *)malloc(sizeof(DNode));     //分配一個(gè)頭結(jié)點(diǎn)
    if(L==NULL)    //內(nèi)存不足，分配失敗
        return false;
    L->prior = NULL;    //頭結(jié)點(diǎn)的 prior 永遠(yuǎn)指向 NULL
    L->next = NULL;    //頭結(jié)點(diǎn)之后暫時(shí)還沒有節(jié)點(diǎn)
    return true;
}

void testDLinkList(){
//初始化雙鏈表
    DLinklist L;
    InitDLinkList(L);
}

//判斷雙鏈表是否為空(帶頭結(jié)點(diǎn))
bool Empty(DLinklist L){
    if(L->next == NULL)    
        return true;
    else
        return false;
}

雙鏈表的插入：

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

① 首先將s的next指針指向p的next指針指向的結(jié)點(diǎn)：s->next=p->next;

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

③ 接下來(lái)將s的前項(xiàng)指針指向p結(jié)點(diǎn)：s->prior=p;

④ 最后將p的后項(xiàng)指針指向s結(jié)點(diǎn)：p->next=s;

修改指針時(shí)要注意順序，例如：

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

首先p的next指針指向s結(jié)點(diǎn)：

再讓s的next指針指向p的next指針指向的結(jié)點(diǎn)：

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

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

雙鏈表的刪除：

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

聲明q指針，指向p的后繼結(jié)點(diǎn)。如果p沒有后繼，即q==NULL，返回false，否則：

① p結(jié)點(diǎn)的next指針會(huì)指向q結(jié)點(diǎn)的next指針指向的位置，也就是指向q的后繼結(jié)點(diǎn)：

p->next=q->next;

如果q不是最后一個(gè)結(jié)點(diǎn)，修改q的后繼結(jié)點(diǎn)的前項(xiàng)指針，執(zhí)行②；如果q是最后一個(gè)結(jié)點(diǎn)，就會(huì)直接執(zhí)行③

② q節(jié)點(diǎn)的后繼結(jié)點(diǎn)的前項(xiàng)指針指向p結(jié)點(diǎn)：

q->next->prior=p;

③ 釋放q結(jié)點(diǎn)：free(q)

q是最后一個(gè)結(jié)點(diǎn)，直接執(zhí)行③的結(jié)果：

雙鏈表的銷毀：

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

?雙鏈表的遍歷：

//后向遍歷
while (p!=NULL){    //對(duì)結(jié)點(diǎn)p做相應(yīng)處理，如打印
    p= p->next;
}

//前向遍歷
while (p!=NULL){    //對(duì)結(jié)點(diǎn)p做相應(yīng)處理
    p= p->prior;
}

//若只想處理數(shù)據(jù)結(jié)點(diǎn)，不想處理頭結(jié)點(diǎn)
while (p->prior!=NULL){    //如果p結(jié)點(diǎn)的前項(xiàng)指針指的是NULL的話，表明p指針此時(shí)指向的是頭結(jié)點(diǎn)
    p= p->prior;
}

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

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

? 循環(huán)單鏈表

之前學(xué)習(xí)的單鏈表最后一個(gè)結(jié)點(diǎn)的next指針指向的是NULL，而循環(huán)單鏈表最后一個(gè)結(jié)點(diǎn)的next指針指向的是頭結(jié)點(diǎn)。

所以初始化單鏈表時(shí)，要將頭結(jié)點(diǎn)的指針指向自己：

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;

//初始化一個(gè)循環(huán)單鏈表
bool InitList(LinkList &L){
    L=(LNode *)malloc(sizeof(LNode));    //分配一個(gè)頭結(jié)點(diǎn)
    if (L==NULL)    //內(nèi)存不足，分配失敗
        return false;
    L->next = L;    //頭結(jié)點(diǎn)next指向頭結(jié)點(diǎn)
    return true;
}

//判斷循環(huán)單鏈表是否為空
bool Empty(LinkList L){
    if(L->next == L)
        return true;
    else
        return false;
}

//判斷結(jié)點(diǎn)p是否為循環(huán)單鏈表的表尾結(jié)點(diǎn)
bool isTail(LinkList L,LNode *p){
    if (p->next==L)
        return true;
    else
        return false;
}

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

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

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

? 循環(huán)雙鏈表

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

所以初始化雙鏈表時(shí)，需要讓頭結(jié)點(diǎn)的前項(xiàng)指針和后項(xiàng)指針都指向頭結(jié)點(diǎn)自己，也就是頭結(jié)點(diǎn)既是第一個(gè)結(jié)點(diǎn)，也是最后一個(gè)結(jié)點(diǎn)。

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

//初始化空的循環(huán)雙鏈表
bool InitDLinkList(DLinklist &L){
    L=(DNode *)malloc(sizeof(DNode));    //分配一個(gè)頭結(jié)點(diǎn)
    if(L==NULL)    //內(nèi)存不足，分配失敗
        return false;
    L->prior =L;    //頭結(jié)點(diǎn)的 prior 指向頭結(jié)點(diǎn)
    L->next = L;    //頭結(jié)點(diǎn)的 next 指向頭結(jié)點(diǎn)
    return true;
}

//判斷循環(huán)雙鏈表是否為空
bool Empty(DLinklist L){
    if(L->next == L)
        return true;
    else
        return false;
}

//判斷結(jié)點(diǎn)p是否為循環(huán)雙鏈表的表尾結(jié)點(diǎn)
bool isTail(DLinklist L,DNode *p){
    if(p->next == L)
        return true;
    else
        return false;
}

void testDLinkList(){
    //初始化循環(huán)雙鏈表
    DLinklist L;
    InitDLinkList(L);
}

?雙鏈表的插入：

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

對(duì)于普通的雙鏈表會(huì)出現(xiàn)錯(cuò)誤：

當(dāng)p結(jié)點(diǎn)剛好是表尾結(jié)點(diǎn)時(shí)，p->next->prior=s;這句代碼會(huì)出現(xiàn)錯(cuò)誤，因?yàn)閜結(jié)點(diǎn)沒有后繼結(jié)點(diǎn)了。

但如果使用的是循環(huán)雙鏈表，這個(gè)邏輯就是對(duì)的，因?yàn)榧幢鉷結(jié)點(diǎn)是表尾結(jié)點(diǎn)，他的next指針指向的結(jié)點(diǎn)是非空的，將p的后繼結(jié)點(diǎn)的前項(xiàng)指針指向s是沒問(wèn)題的。

雙鏈表的刪除：

雙鏈表的刪除同理：

∥刪除p的后繼結(jié)點(diǎn)q
p->next=q->next;
q->next->pior=p;
free(q);

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

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

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

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

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

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

區(qū)別是，指針指明的是下一個(gè)結(jié)點(diǎn)的地址，而游標(biāo)指明的是下一個(gè)結(jié)點(diǎn)的數(shù)據(jù)下標(biāo)。

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

因?yàn)殪o態(tài)鏈表中各個(gè)結(jié)點(diǎn)是連續(xù)存放的，如果每個(gè)數(shù)據(jù)元素4B，每個(gè)游標(biāo)4B(每個(gè)結(jié)點(diǎn)共8B)。設(shè)起始地址為 addr。那么數(shù)組下標(biāo)為2的結(jié)點(diǎn)的存放地址就是addr+8*2。

這樣就能把靜態(tài)鏈表中的數(shù)組下標(biāo)，映射為某個(gè)數(shù)組下標(biāo)對(duì)應(yīng)結(jié)點(diǎn)的實(shí)際存放位置。

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

#define Maxsize 10    //靜態(tài)鏈表的最大長(zhǎng)度
struct Node{          //靜態(tài)鏈表結(jié)構(gòu)類型的定義
    ElemType data;     //存儲(chǔ)數(shù)據(jù)元素
    int next;         //下一個(gè)元素的數(shù)組下標(biāo)
};

void testSLinkList(){
    struct Node a[Maxsize];    //數(shù)組a作為靜態(tài)鏈表
}

??

王道書上是這樣寫的：

#define Maxsize 10
typedef struct {
    ElemType data;
    int next;
}SLinkList[Maxsize];
//等價(jià)于
#define Maxsize 10
struct Node{
    ElemType data;
    int next;
};
typedef struct Node SLinkList[Maxsize];
//可用 sLinkList 定義“一個(gè)長(zhǎng)度為 MaxSize 的Node 型數(shù)組”


//當(dāng)我們聲明一個(gè)SLinkList a時(shí),其實(shí)是聲明了一個(gè)數(shù)組
//這個(gè)數(shù)組的元素個(gè)數(shù)為MaxSize，每個(gè)數(shù)組元素就是一個(gè)Struct Node結(jié)構(gòu)體
void testSLinkList(){
    SLinkList a;
}
//等價(jià)于
void testSLinkList(){
    struct Node a[MaxSize];
}
//使用“SLinkList a”的寫法強(qiáng)調(diào)的是a是靜態(tài)鏈表

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

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

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

（3）插入：

① 找到一個(gè)空的結(jié)點(diǎn)，存入數(shù)據(jù)元素。

② 從頭結(jié)點(diǎn)出發(fā)找到位序?yàn)閕-1的結(jié)點(diǎn)。

③ 修改新結(jié)點(diǎn)的next。

④ 修改i-1號(hào)結(jié)點(diǎn)的next。

（4）刪除：

① 從頭結(jié)點(diǎn)出發(fā)找到前驅(qū)結(jié)點(diǎn)。

② 修改前驅(qū)結(jié)點(diǎn)的游標(biāo)。

③ 被刪除結(jié)點(diǎn) next 設(shè)為 -2。

總結(jié)：

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

優(yōu)點(diǎn)：增、刪操作不需要大量移動(dòng)元素，只要修改相關(guān)數(shù)據(jù)元素的游標(biāo)即可。

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

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

（6）順序表和鏈表的對(duì)比

1.邏輯結(jié)構(gòu)

順序表和鏈表在邏輯上都是線性結(jié)構(gòu)的，都屬于線性表。

2.物理結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)）

順序表：

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

并且順序表中的各個(gè)結(jié)點(diǎn)，只需要存儲(chǔ)各個(gè)元素本身，不需要存儲(chǔ)其他的冗余信息。因此順序表存儲(chǔ)密度高。

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

鏈表：

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

但是鏈?zhǔn)酱鎯?chǔ)中要查找第i個(gè)結(jié)點(diǎn)時(shí)，只能從表頭開始遍歷尋找，所以不可隨機(jī)存取。并且由于各個(gè)結(jié)點(diǎn)除了存儲(chǔ)數(shù)據(jù)元素外，還需要花費(fèi)一定空間存儲(chǔ)指針，所以存儲(chǔ)密度較低。

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

??初始化

順序表：

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

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

鏈表：

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

采用鏈表，存儲(chǔ)空間更加靈活。

??銷毀

順序表：

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

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

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

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

鏈表：

通過(guò)free函數(shù)，利用循環(huán)依次刪除各個(gè)結(jié)點(diǎn)。

注：malloc和free必須成對(duì)存在。

??增刪

順序表：

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

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

鏈表：

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

2.鏈表的時(shí)間復(fù)雜度也為 O(n)，時(shí)間開銷主要來(lái)自查找目標(biāo)元素。查找元素的時(shí)間代價(jià)相比于移動(dòng)大量元素的時(shí)間代價(jià)更低。

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

??查找

順序表：

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

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

鏈表：

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

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

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

??總結(jié)：

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

2.如果線性表表長(zhǎng)可預(yù)估，查詢(搜索)操作比較多。那么就采用順序表。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-853552.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)（二）----線性表（順序表，鏈表）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！