1，線性表的定義

首先，數(shù)據(jù)結(jié)構(gòu)中的順序表和鏈表都屬于線性表。何為線性表？線性表可以描述為：具有相同數(shù)據(jù)類型的n個數(shù)據(jù)元素的有限序列。

形象理解線性表的要素：

• 幼兒園小朋友放學(xué)，需要在校內(nèi)站成一隊，等待家長來接。這是一個有限的序列。

• 總共有幾個小朋友，稱之為線性表的長度。特別地，當(dāng)隊伍長度為0時，線性表為空表；

• 孩子在第幾位，稱之為位序。

• 除了隊伍最前面的小朋友，其他每個小朋友前面都有一位同學(xué)，稱之為直接前驅(qū)元素；除了隊伍最后面的小朋友，其他每個小朋友后面都有一位同學(xué)，稱之為直接后繼元素。

• 瑪卡巴卡同學(xué)去上廁所，拿自己的書包占了一個位置，此時該隊伍就不再是線性表，因為書包和小朋友不是相同的數(shù)據(jù)類型。

• 每個小朋友都帶著自己的書包、玩具、水杯…這些內(nèi)容可稱之為數(shù)據(jù)項，較復(fù)雜的線性表中，一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項構(gòu)成。

2，說明

2.1，參數(shù)的引用符號—“&”

線性表的主要基本操作：

• InitList(&L)：初始化表。構(gòu)造一個空的線性表L，分配內(nèi)存空間。
• DestoryList(&L)：銷毀線性表，并釋放線性表L所占用的內(nèi)存空間。
• ListInsert(&L,i,e)：在表L中的第i個位置上插入指定元素e。
• ListDelete(&L,i,&e)：刪除表L中第i個位置的元素，并用e返回刪除元素的值。
• LocateElem(L,e)：按值查找。在表L中查找元素e。
• GetElem(L,i)：按位查找。獲取表L中第i個位置的元素的值。
• …

上述部分基本操作需要傳入參數(shù)的引用“&”，對參數(shù)的修改結(jié)果需要“帶回來”的時候需要傳入。

代碼理解：

#include<stdio.h>
void test(int x){
	x=1024;
	printf("test函數(shù)內(nèi)部 x=%d\n",x);
}
int main(){
	int x=1;
	printf("調(diào)用test函數(shù)前 x=%d\n",x);
	test(x);
	printf("調(diào)用test函數(shù)后 x=%d\n",x);
}

運行結(jié)果：

注意：上述程序，沒有在test(x)內(nèi)部沒有使用參數(shù)引用符“&”，因此test函數(shù)內(nèi)部的x和main函數(shù)內(nèi)部聲明的x不同，二者各占一份內(nèi)存空間。

加上引用“&”后，查看運行效果：

#include<stdio.h>
void test(int &x){
	x=1024;
	printf("test函數(shù)內(nèi)部 x=%d\n",x);
}
int main(){
	int x=1;
	printf("調(diào)用test函數(shù)前 x=%d\n",x);
	test(x);
	printf("調(diào)用test函數(shù)后 x=%d\n",x);
}

此時加上了參數(shù)的引用符“&”，test函數(shù)內(nèi)操作的x就是main()中的x，對x的修改就帶了回來。

2.2，malloc()函數(shù)和free()函數(shù)

• malloc()：用于申請內(nèi)存空間，返回一個指向分配好的一整片存儲空間起始地址的指針；*

• 注意malloc()返回的指針類型需要強制轉(zhuǎn)換為你定義的數(shù)據(jù)元素指針類型，這個后續(xù)會提到。

• free()：釋放內(nèi)存空間。

malloc()和free()都包含在stdlib.h頭文件內(nèi)，因此使用到malloc()或free()的程序需要加上#include <stdlib.h>

2.3，typedef關(guān)鍵字

C語言中使用typedef關(guān)鍵字進行數(shù)據(jù)類型的重命名。
typedef <數(shù)據(jù)類型> <別名>

typedef int ElemType; —將int類型起別名為ElemType。

如此一來，int i = 0 就等價于ElemType i = 0；

3，順序表

順序表，即使用順序存儲方式實現(xiàn)的線性表。把邏輯上相鄰的元素存儲在物理上也相鄰的存儲單元中，其中重要的三個屬性包括：

• 存儲空間的起始位置。
• 最大容量
• 當(dāng)前長度

順序表使用數(shù)組存儲元素。順序表的實現(xiàn)方式有靜態(tài)分配和動態(tài)分配。，靜態(tài)分配在定義時就確定了數(shù)組的大小，而動態(tài)分配可以在程序運行時根據(jù)需要動態(tài)地分配內(nèi)存空間。下面一一展開。

3.1，靜態(tài)分配和動態(tài)分配

靜態(tài)分配中，數(shù)組的大小和空間都是事先固定好的。

順序表靜態(tài)分配代碼描述：

#include <stdio.h>
#define MAXSIZE 20    //定義線性表的最大長度
typedef int ElemType;
typedef struct{
	ElemType data[MAXSIZE];
	int length;     //順序表的當(dāng)前長度
}SqList;

void InitList(SqList &L){
	L.length=0;   //順序表初始長度為0
}

int main(){
	SqList L;
	InitList(L);  //初始化順序表
	return 0;
}

靜態(tài)分配中數(shù)組的大小和空間都是事先固定，因此空間占滿時插入元素會導(dǎo)致溢出，進而導(dǎo)致程序崩潰，存在弊端。而動態(tài)分配可以完美解決這一問題。下面詳細(xì)學(xué)習(xí)動態(tài)分配。

動態(tài)分配：程序運行時根據(jù)需要動態(tài)地分配內(nèi)存空間

順序表動態(tài)分配代碼描述：

#include <stdio.h>
#include <stdlib.h>
#define InitSize 10  //默認(rèn)的最大長度
typedef struct {
	int *data;       //指示動態(tài)分配數(shù)組的指針
	int maxsize;     //順序表的最大容量
	int length;      //順序表當(dāng)前長度
}SeqList;

void InitList(SeqList &L){
	//使用malloc函數(shù)申請一片連續(xù)的存儲空間
	L.data=(int *)malloc(InitSize*sizeof(int));
	L.length=0;
	L.maxsize=InitSize;
}
 
void IncreaseSize(SeqList &L, int len){   //len表示需要增加的長度
	int *p=L.data;  //p指針指向原先未擴容數(shù)組的起始地址
	L.data=(int *)malloc((L.maxsize+len)*sizeof(int));  //分配新空間
	for(int i=0; i<L.length; i++){
		L.data[i]=p[i];  //將原始數(shù)據(jù)復(fù)制到新區(qū)域
	}
	L.maxsize=L.maxsize+len;  //順序表最大長度增加len
	free(p);  //釋放掉原來的內(nèi)存空間
}

int main(){
	SeqList L;
	InitList(L);
	/*
	省略操作...：往順序表中插入一些元素
	*/
	printf("順序表當(dāng)前最大容量為%d\n",L.maxsize);  //運行，輸出為10
	IncreaseSize(L,5);  //擴容
	printf("順序表當(dāng)前最大容量為%d\n",L.maxsize);  //運行，輸出為15，擴容成功
	return 0;
}

3.2，順序表的插入

ListInsert(&L,i,e)：插入操作。在表L的第i個位置上插入指定元素e。

根據(jù)順序表的性質(zhì)，元素e插入之后第i個位置元素和第i個位置元素后面的元素都需要依次后移。這就好比食堂里一群人排隊買飯，如果前面隊伍里有人插隊，后面的排隊的每一個人就相當(dāng)于向后移了一個位置。

因此順序表插入算法的思想可以概括為以下幾點：

• 插入位置不合理時，需要有報錯信息；
• 如果順序表長度大于等于數(shù)組的最大長度，需要用報錯信息；
• 從最后一個元素開始向前遍歷到第i個位置，分別將它們向后移動一個位置（第i個位置之后的元素和第i個元素元素都要向后移動）；
• 將要插入的元素填入位置i處；
• 表長加1。

順序表插入的代碼實現(xiàn)如下（此處使用靜態(tài)分配方式實現(xiàn)，動態(tài)分配方式雷同）：

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

void InitList(SqList &L){
	L.length=0;   //順序表初始長度為0
}

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--){         //將第i個元素及第i個元素后面的元素向后移動
		L.data[j]=L.data[j-1];
	}
	L.data[i-1]=e;  //在順序表的第i個位置（即下表為i-1的位置）上放入元素e
	L.length++; //插入一個元素，順序表長度增加1
	return true;
}

int main(){
	SqList L;
	InitList(L);
	ListInsert(L,1,1);
	ListInsert(L,2,2);
	ListInsert(L,3,3);
	ListInsert(L,4,4);
	ListInsert(L,5,5);
	ListInsert(L,3,520);
	for(int i=0;i<L.length;i++){
		printf("data[%d]=%d\n",i,L.data[i]);  //將順序表打印輸出
	}
	return 0;
}

運行結(jié)果為：

對順序表插入的時間復(fù)雜度進行分析，第i個位置元素及其后面的元素都要移動位置（表內(nèi)n個元素，第i個位置插入新元素，則需要移動元素n-i+1次）。很顯然，問題規(guī)模和表長有關(guān)，時間主要花費在元素的移動上面。因此順序表插入元素操作的時間復(fù)雜度為O(n)。

3.3，順序表的刪除

ListDelete(&L,i,&e)：刪除操作。刪除表L的第i個位置上的元素，并用e返回刪除元素的值。

根據(jù)順序表的性質(zhì)，刪除表L的第i個位置上的元素之后，第i個位置元素后面的元素都需要依次前移。如插隊的人受不了后面排隊人群的譴責(zé)，從隊伍中離開，后面排隊的人群向前移動一個位置。

因此順序表刪除算法的思想可以概括為以下幾點：

• 如果刪除的位置不合理，需要有報錯信息；
• 取出刪除元素；
• 從刪除元素位置開始遍歷到最后一個元素位置，分別將它們向前移動一個位置；
• 表長減1；

順序表刪除操作核心代碼：

bool ListDelete(SqList &L,int i,int &e){
	if(i<1||i>L.length+1){
		return false;
	}
	e=L.data[i-1];
	for(int j=i;j<L.length;j++){
		L.data[j-1]=L.data[j];
	}
	L.length--;
	return true;
}

同樣地，對順序表插入的時間復(fù)雜度進行分析，第i個位置后面的元素都要移動位置（表中有n個元素，刪除第i個位置的元素之后，需要移動n-i個元素）。很顯然，問題規(guī)模也和表長有關(guān)，時間主要花費在元素的移動上面。因此順序表刪除元素操作的時間復(fù)雜度為O(n)。

3.4，順序表的查找

順序表的查找分為按位查找和按值查找。

3.4.1，按位查找

GetElem(L,i)：按位查找操作。獲取表L中第i個位置元素的值。

順序表按位查找代碼實現(xiàn)（直接返回第i個位置元素的值）：

ElemType GetElem(SqList L,int i){
	return L.data[i-1];    //第i個位置元素的數(shù)組下表為（i-1）
}

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

3.4.2，按值查找

LocateElem(L,e)：按值查找操作。獲取表L中值為e的元素。

順序表按值查找代碼實現(xiàn)：

//在順序表L中查找第一個元素值為e的元素，并返回其位序
int LocateElem(SqList L,ElemType e){
	for(int i=0;i<L.length-1;i++){
		if(L.data[i]==e){
			return i+1;  //返回其位序
		}
	}
	return 0;  //退出循環(huán)，說明查找失敗
}

顯然，順序表按值查找的時間復(fù)雜度為O(n)，主要時間花費在了元素的遍歷上。

4，鏈表

由于順序表中的插入、刪除元素操作，需要移動大量元素。因此對于需要頻繁插入刪除的應(yīng)用場景，運行效率會很低。因此引入鏈?zhǔn)酱鎯Α?/p>

鏈表，使用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素。這些存儲單元可以連續(xù)，也可以不連續(xù)。也就是說，鏈表不要求邏輯上相鄰的元素在物理上也相鄰。

形象理解

上世紀(jì)的銀行，辦理業(yè)務(wù)時需要客戶排成一隊，依次辦理。隨著前面客戶辦理結(jié)束，隊伍也會向前移動。同樣的有人插隊時，插入位置之后的隊伍相當(dāng)于向后移動，這就是順序表。顯然這不太合理，大家都站在一起，耗時耗精力。這種排隊方式可以理解為順序表。

于是后來慢慢優(yōu)化成了如今的樣子：客戶來銀行辦理業(yè)務(wù)時，先去取號，取完之后不必排隊等候，可以隨便找個位置坐下休息，等到廣播叫到自己的號時前去辦理業(yè)務(wù)，實際上這就是鏈表的思想。

4.1，單鏈表的定義

單鏈表中，其每個結(jié)點除了要存儲數(shù)據(jù)元素，還需要存儲指向下一個結(jié)點的指針（相當(dāng)于例子中銀行客戶取到的號）。

單鏈表的定義：

typedef struct LNode{     //定義單鏈表結(jié)點類型
	ElemType data;        //數(shù)據(jù)域。結(jié)點存放數(shù)據(jù)元素
	struct LNode *next;   //指針域。存放指向下一個結(jié)點的指針
}LNode,*LinkList;

//要表示一個單鏈表，只需要一個頭指針，指向單鏈表的第一個結(jié)點
LNode *L;   //聲明一個指向單鏈表第一個結(jié)點的指針（強調(diào)結(jié)點）
LinkList L; //聲明一個指向單鏈表第一個結(jié)點的指針（強調(diào)單鏈表）

4.2，單鏈表的初始化

首先要理解何為頭結(jié)點，何為頭指針？

• 頭結(jié)點是放在鏈表第一個元素結(jié)點之前的結(jié)點，其數(shù)據(jù)域一般無意義（也可以用來存放鏈表的長度）。
• 頭結(jié)點是鏈表的非必需要素，但引入頭結(jié)點后，寫代碼更方便。有頭結(jié)點時，第一個元素結(jié)點前插入節(jié)點和刪除第一結(jié)點操作就和其他結(jié)點統(tǒng)一起來了（后續(xù)提到），就可以實現(xiàn)一套邏輯搞定所有結(jié)點。
• 頭指針是鏈表的必需要素，是指向第一個結(jié)點的指針。若單鏈表有頭結(jié)點，則是指向頭結(jié)點的指針。
• 頭指針具有標(biāo)志作用，所有常用頭指針冠以鏈表的名字。

單鏈表初始化分兩種情況：帶頭結(jié)點的單鏈表和不帶頭結(jié)點的單鏈表。下面分別進行實現(xiàn)：

①初始化不帶頭結(jié)點的單鏈表：

typedef int ElemType;    
typedef struct LNode{     //定義單鏈表結(jié)點類型
	ElemType data;        //數(shù)據(jù)域。結(jié)點存放數(shù)據(jù)元素
	struct LNode *next;   //指針域。存放指向下一個結(jié)點的指針
}LNode,*LinkList;

//初始化不帶頭結(jié)點的單鏈表
bool InitList(LinkList &L){
	L=NULL;       //空表，暫時還沒有任何結(jié)點（防止臟數(shù)據(jù)）
	return true;
}

//不帶頭結(jié)點的單鏈表的判空操作
bool Empty(LinkList L){
	if(L==NULL){
		return true;
	}else{
		return false;
	}
}

②初始化帶頭結(jié)點的單鏈表：

//初始化帶頭結(jié)點單鏈表
bool InitList(LinkList &L){
	L=(LNode *)malloc(sizeof(LNode));  //給頭結(jié)點分配空間
	if(L==NULL){
		return false;   //內(nèi)存不足，分配失敗
	}
	L->next=NULL;   //頭結(jié)點之后暫時無其他結(jié)點
	return true;
}
//帶頭結(jié)點的單鏈表的判空操作
bool Empty(LinkList L){
	if(L->next==NULL){
		return true;
	}else{
		return false;
	}
}

不難看出，判空時，不帶頭結(jié)點的單鏈表直接根據(jù)頭指針是否指向空，判斷表是否為空。而帶頭結(jié)點的單鏈表則是通過判斷頭結(jié)點下一個位置是否為空。

4.3，單鏈表的插入

單鏈表的插入操作分為按位序插入、指定節(jié)點的后插、指定節(jié)點的前插。接下來對三種插入操作一一進行實現(xiàn)。

4.3.1，按位序插入

ListInsert(&L,i,e)：按位序插入操作，在鏈表L中的第i個結(jié)點位置插入元素e。（頭結(jié)點可以看作是第0個結(jié)點）

單鏈表按位序插入具體實現(xiàn)思路如下：

• 聲明一指針p指向鏈表的頭結(jié)點，初始化 j（計數(shù)器變量，表示當(dāng)前p指向第幾個結(jié)點）從0開始；
• 當(dāng) j<i-1 時，讓p指針向后移動，不斷指向下一個結(jié)點，j累加1；
• 若到鏈表末尾p為空，則說明第i個結(jié)點不存在；
• 否則查找成功，在系統(tǒng)中生成一個空結(jié)點s；
• 將數(shù)據(jù)元素e賦值給 s->data;
• 單鏈表插入的標(biāo)準(zhǔn)語句：s->next=p->next; p->next=s;（先后順序不可顛倒。要先過河才能拆橋，如果先拆橋就沒辦法過河）；
• 返回成功；

單鏈表按位序插入代碼實現(xiàn)（帶頭結(jié)點）：

//初始化帶頭結(jié)點單鏈表
bool InitList(LinkList &L){
	L=(LNode *)malloc(sizeof(LNode));
	if(L==NULL){
		return false;   //內(nèi)存不足，分配失敗
	}
	L->next=NULL;   //頭結(jié)點之后暫時無其他結(jié)點
	return true;
}

//單鏈表按位序插入
bool ListInsert(LinkList &L, int i, ElemType e){
	if(i<1){
		return false;
	}
	LNode *p;  //指針，用來指向當(dāng)前掃描到的結(jié)點
	int j=0;   //計數(shù)器，用來表示當(dāng)前p指向第幾個結(jié)點，頭結(jié)點是第0個結(jié)點
	p=L;        //指針指向頭結(jié)點
	while(p!=NULL && j<i-1){    //循環(huán)找到第（i-1）個結(jié)點
		p=p->next;
		j++;
	}
	if(p=NULL){
		return false;    //說明第（i-1）個結(jié)點不存在
	}
	LNode *s=(LNode *)malloc(sizeof(LNode));

	//將結(jié)點s連接在p之后
	s->data=e;
	s->next=p->next;
	p->next=s;
	return true;  //走到這里，表示插入成功
}

以上是帶頭結(jié)點的單鏈表的按位序插入操作。思考不帶頭結(jié)還能使用如上代碼進行按位序插入嗎？

答案是不能。

帶頭結(jié)點的單鏈表，進行按位序插入時，是先找到第（i-1）個結(jié)點，然后將新結(jié)點插入其后，如果要在第一個結(jié)點位置進行插入元素，就會先找到第0個結(jié)點（頭結(jié)點）。但不帶頭結(jié)點的單鏈表沒有第0個結(jié)點。走如上代碼邏輯是行不通的，因此需要額外針對插入位置為1的情況進行特殊處理。

單鏈表按位序插入代碼實現(xiàn)（不帶頭結(jié)點）：

//單鏈表按位序插入（不帶頭結(jié)點）
bool ListInsert(LinkList &L, int i, ElemType e){
	if(i<1){
		return false;
	}
	if(i==1){      //不帶頭結(jié)點的單鏈表需要針對第一個位置進行特殊處理
		LNode *s=(LNode *)malloc(sizeof(LNode));   //新結(jié)點
		s->data=e;
		s->next=L;
		L=s;   //頭指針指向新結(jié)點
		return true;
	}

	//處理其余結(jié)點
	LNode *p;  //指針，用來指向當(dāng)前掃描到的結(jié)點
	int j=1;   //指向第一個結(jié)點?。?！
	p=L;        //指針指向第一個結(jié)點
	while(p!=NULL && j<i-1){    //循環(huán)找到第（i-1）個結(jié)點
		p=p->next;
		j++;
	}
	if(p=NULL){
		return false;    //i值不合法
	}
	LNode *s=(LNode *)malloc(sizeof(LNode));

	//將結(jié)點s連接在p之后
	s->data=e;
	s->next=p->next;
	p->next=s;
	return true;  //走到這里，表示插入成功
}

4.3.2，指定結(jié)點后插

InsertNextNode(LNode *p, ElemType e)：指定結(jié)點的后插操作。將元素e插入到p結(jié)點之后

單鏈表指定結(jié)點的后插操作實現(xiàn)如下：

//單鏈表指定結(jié)點的后插操作
bool InsertNextNode(LNode *p, ElemType e){
	if(p==NULL){
		return false;
	}
	LNode *s=(LNode *)malloc(sizeof(LNode));   //新結(jié)點
	if(s==NULL){
		return false;    //內(nèi)存分配失敗的情況。比如內(nèi)存空間不足
	}
	s->data=e;
	s->next=p->next;      //將結(jié)點s連接到p之后
	p->next=s;
	return true;
}

我們可以發(fā)現(xiàn)按位序插入操作內(nèi)，也包含了指定節(jié)點的后插操作的邏輯（對第i-1個結(jié)點進行后插）。因此可以使用封裝好的代碼對按位序插入操作的代碼進行簡化，如下為簡化后的代碼：

//單鏈表按位序插入（帶頭結(jié)點）
bool ListInsert(LinkList &L, int i, ElemType e){
	if(i<1){
		return false;
	}
	LNode *p;  //指針，用來指向當(dāng)前掃描到的結(jié)點
	int j=0;   //計數(shù)器，用來表示當(dāng)前p指向第幾個結(jié)點，頭結(jié)點是第0個結(jié)點
	p=L;        //指針指向頭結(jié)點
	while(p!=NULL && j<i-1){    //循環(huán)找到第（i-1）個結(jié)點
		p=p->next;
		j++;
	}
	return InsertNextNode(p,e);
}

4.3.3，指定結(jié)點前插

InsertPriorNode(LNode *p, ElemType e)：指定結(jié)點的前插操作。在p結(jié)點之前插入元素e。

對于單鏈表，但每個結(jié)點都是向后指，前一個元素是不可知的，除非從鏈表頭部開始遍歷。那如何對指定的結(jié)點進行前插，難不成要從頭指針開始遍歷整個鏈表，找到指定結(jié)點的前驅(qū)元素嗎？

對指定p結(jié)點要想把元素e插入到他的前面，我們可以通過節(jié)點不動，讓數(shù)據(jù)跑路的騷操作巧妙完成。具體思路如下：

• 先對p結(jié)點進行后插操作，將新結(jié)點s插入到p結(jié)點后；
• 將結(jié)點p中的元素值復(fù)制到s中；
• 再將p中的元素值使用e覆蓋。

單鏈表指定結(jié)點單獨前插操作代碼實現(xiàn)如下：

//單鏈表前插操作
bool InsertPriorNode(LNode *p, LNode *s){
	if(p==NULL || s==NULL){
		return false;
	}
	s->next=p->next;
	p->next=s;           //將s連接到p結(jié)點之后

	ElemType temp=p->data;    //交換數(shù)據(jù)域部分
	p->data=s->data;
	s->data=temp;
	return true;
}

4.4，單鏈表的刪除

單鏈表的刪除操作分為按位序刪除和指定結(jié)點刪除。接下來一一進行實現(xiàn)。

4.4.1，按位序刪除

ListDelete(&L,i,&e)：刪除表L中第i個位置元素，并使用e返回刪除元素的值。

實現(xiàn)時可以先找到第（i-1）個結(jié)點，將其next指針指向第（i+1）個結(jié)點，并釋放第i個結(jié)點。

單鏈表按位序刪除操作（帶頭結(jié)點）具體實現(xiàn)思路如下：

• 聲明一指針p指向鏈表頭結(jié)點，初始化j從０開始；
• 當(dāng) j<i-1 時，遍歷鏈表，讓ｐ指針向后移動，不斷指向下一個結(jié)點，ｊ進行累加；
• 若到鏈表末尾ｐ為空，則說明第（i-1）個結(jié)點不存在；
• 若第(ｉ-1)個節(jié)點存在，聲明一結(jié)點q指向被刪除結(jié)點（q=p->next）；
• 將q結(jié)點從單鏈表中斷開：p->next=q->next；
• 將q結(jié)點中的數(shù)據(jù)賦值給e，作為返回；
• 釋放結(jié)點q；
• 返回成功。

單鏈表按位序刪除操作（帶頭結(jié)點）具體代碼實現(xiàn)如下：

//單鏈表按位序刪除（帶頭結(jié)點）
bool ListDelete(LinkList &L, int i, ElemType &e){
	if(i<1){
		return false;
	}
	LNode *p;  //指針指向當(dāng)前掃描到的結(jié)點
	int j=0;   //計數(shù)器
	p=L;    //指向頭結(jié)點

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

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

	LNode *q;
	q=p->next;
	p->next=q->next;
	free(q);   
	return true;
}

4.4.2，指定結(jié)點的刪除

DeleteNode(LNode *p)：刪除指定結(jié)點p。

由于p結(jié)點之前的結(jié)點不好找，可以通過指定結(jié)點前插操作中的節(jié)點不動，讓數(shù)據(jù)跑路的思想：把結(jié)點p->next的數(shù)據(jù)域部分賦值給p，然后將p->next刪除。

• 聲明一結(jié)點q指向p的下一個結(jié)點（即p->next）;
• q結(jié)點的數(shù)據(jù)域部分賦值給p結(jié)點的數(shù)據(jù)域部分；
• 將q結(jié)點從單鏈表中斷開；
• 釋放q結(jié)點。

單鏈表指定結(jié)點刪除操作（帶頭結(jié)點）具體代碼實現(xiàn)如下：

//指定結(jié)點的刪除操作（帶頭結(jié)點）
bool DeleteNode(LNode *p){
	if(p==NULL){
		return false;
	}

	LNode *q=p->next;     //令q指向p的后繼結(jié)點
	p->data=p->next->data;       //更新p結(jié)點數(shù)據(jù)域為后繼結(jié)點數(shù)據(jù)域
	p->next=q->next;       //將后繼結(jié)點從鏈表內(nèi)斷開
	free(q);        //釋放后繼結(jié)點的存儲空間
	return true;
}

但上述代碼存在一個問題：如果要刪掉的結(jié)點p是最后一個結(jié)點，p->next就是NULL，如此一來p->next->data就會出現(xiàn)空指針錯誤。那就只能針對表尾元素進行特殊處理：通過從表頭開始遍歷的方法，找到p結(jié)點的前驅(qū)元素，然后進行刪除。代碼完善之后如下：

//指定結(jié)點的刪除操作
bool DeleteNode(LinkList &L, LNode *p){
	if(p==NULL){
		return false;
	}

	if(p->next==NULL){       //p結(jié)點為單鏈表最后一個結(jié)點時
		LNode *s=L;     //s指向表頭
		while(s->next!=p){   //從表頭開始循環(huán)找到p結(jié)點的前驅(qū)結(jié)點
			s=s->next;
		}
		s->next=NULL;  //p結(jié)點的前驅(qū)結(jié)點指向NULL
		free(p);
		return true;
	}else{        //p結(jié)點不是最后單鏈表一個結(jié)點時
		LNode *q=p->next;     //令q指向p的后繼結(jié)點
		p->data=p->next->data;       //更新p結(jié)點數(shù)據(jù)域為后繼結(jié)點數(shù)據(jù)域
		p->next=q->next;       //將后繼結(jié)點從鏈表內(nèi)斷開
		free(q);        //釋放后繼結(jié)點的存儲空間
		return true;
	}
}

上述代碼。如果刪除的結(jié)點不是最后一個結(jié)點，時間復(fù)雜度為O(1)；如果刪除的結(jié)點是最后一個結(jié)點，時間復(fù)雜度為O(n)，時間主要花費在從表頭開始遍歷尋找p結(jié)點前驅(qū)上。

4.5，單鏈表的查找

和順序表一樣，單鏈表的查找同樣分為按位查找和按值查找。

4.5.1，單鏈表按位查找

GetElem(L,i)：按位查找操作。獲取表L中第i個位元素的值；

實際上前面的單鏈表按位序插入和按位序刪除操作中已經(jīng)包含了單鏈表的按位查找。按位序插入和按位序刪除都需要先找到第（i-1）個結(jié)點。此即為按位查找第（i-1）個元素的操作。

單鏈表按位查找具體實現(xiàn)代碼實現(xiàn)如下：

//單鏈表按位查找，返回第i個元素（帶頭結(jié)點）
LNode *GetElem(LinkList L,int i){
	if(i<0){    //i值不合法
		return NULL;
	}
	LNode *p;   //指針p指向當(dāng)前掃描到的結(jié)點
	int j=0;    //計數(shù)器
	p=L;        //指向頭結(jié)點
	while(p!=NULL && j<i){   //循環(huán)找到第i個結(jié)點
		p=p->next;
		j++;
	}
	return p;
}

單鏈表按位序插入操作平均時間復(fù)雜度為O(n)，主要花費在循環(huán)找第i個結(jié)點上面。

4.5.1，單鏈表按值查找

LocateElem(L,e)：按值查找操作。獲取表L中值為e的元素。

單鏈表按值查找。從表頭開始依次查找數(shù)據(jù)域為e的結(jié)點，代碼實現(xiàn)如下：

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

4.6，單鏈表的建立

拿到很多個數(shù)據(jù)元素，如何把它們存到一個單鏈表里呢？

創(chuàng)建單鏈表的過程是一個動態(tài)生成鏈表的過程，先初始化一個單鏈表，然后每次取一個數(shù)據(jù)元素，插入到表頭或者表尾。因此單鏈表的建立有兩種分別是頭插法和尾插法。

4.6.1，尾插法建立單鏈表

尾插法建立單鏈表思路：

• 聲明一個指針r 始終指向表尾元素；
• 對表尾元素進行后插操作；
• 插入完成后讓指針r繼續(xù)指向新的表尾結(jié)點；

尾插法建立單鏈表代碼實現(xiàn)如下：

//尾插法建立單鏈表（帶頭結(jié)點）
LinkList List_TailInsert(LinkList &L){
	LNode *r;
	L=(LinkList)malloc(sizeof(LNode));    //初始化空的單鏈表（帶頭結(jié)點）
	LNode *r=L;
	int x;      //用來接收鍵盤輸入的值
	scanf("%d",&x);
	while(x!=9999){       //輸入9999表示結(jié)束
		//在r結(jié)點之后插入結(jié)點x（指定結(jié)點的后插操作）
		LNode *s=(LNode *)malloc(sizeof(LNode));  
		s->data=x;
		r->next=s;
		r=s;  //r指針繼續(xù)指向新的表尾結(jié)點
		scanf("%d",&x);      //繼續(xù)輸入下一個值
	}
	r->next=NULL;
	return L;
}

如上代碼實現(xiàn)： 手動輸入值，插入相應(yīng)結(jié)點元素到單鏈表表尾，插入完成后輸入下一個值，如果輸入的值為9999，則程序運行結(jié)束。

4.6.2，頭插法建立單鏈表

尾插法建立單鏈表是通過對表尾結(jié)點進行后插操作，不難想到頭插法建立單鏈表就是對頭結(jié)點進行后插操作。

頭插法建立單鏈表代碼實現(xiàn)如下：

//頭插法建立單鏈表（帶頭結(jié)點）
LinkList List_HeadInsert(LinkList &L){
	//①初始化一個空的單鏈表
	L=(LinkList)malloc(sizeof(LNode));
	L->next=NULL;
	//②輸入結(jié)點的值
	int x;
	scanf("%d",x);
	while(x!=9999){
		//③對頭結(jié)點進行后插
		LNode *s=(LNode *)malloc(sizeof(LNode));
		s->data=x;
		s->next=L->next;
		L->next=s;
		scanf("%d",&x);    //繼續(xù)輸入下一個待插入值
	}
	return L;
}

比較頭插法和尾插法可以發(fā)現(xiàn)，如果插入數(shù)據(jù)域為1，2，3的三個結(jié)點，頭插法插入后元素是逆序的，因此頭插法建立單鏈表的一個重要的應(yīng)用就是鏈表的逆置。

4.7，雙向鏈表

通過前面的學(xué)習(xí)可以知道，對于單鏈表，只有一個指針域，指向后繼結(jié)點。因此想要找到某結(jié)點的后繼結(jié)點可以直接通過指針找到，但找前驅(qū)結(jié)點則比較麻煩，需要從表頭遍歷。雙向鏈表則可以完美解決這一問題。

雙向鏈表相當(dāng)于在單鏈表的每個結(jié)點中，在設(shè)置一個指向前驅(qū)結(jié)點的指針域。因此雙向鏈表中的結(jié)點都有兩個指針域，一個指向直接后繼，一個指向直接前驅(qū)。結(jié)構(gòu)如下圖所示：

雙向鏈表結(jié)點的代碼定義為：

typedef struct DNode{
	ElemType data;       //數(shù)據(jù)域
	struct DNode *prior,*next;    //前驅(qū)和后繼指針
}DNode,*DLinkList;

4.7.1，雙向鏈表的初始化

雙向鏈表初始化操作思想：

• 給頭結(jié)點分配空間；
• 頭結(jié)點的prior指針（前驅(qū)指針）永遠(yuǎn)指向NULL；
• 頭結(jié)點的next指針（后繼指針）在雙鏈表沒有元素時指向NULL；

雙向鏈表初始化操作代碼實現(xiàn)如下：

//雙向鏈表的初始化操作（帶頭結(jié)點）
bool InitDlinkList(DLinkList &L){
	L=(DNode *)malloc(sizeof(DNode));
	if(L==NULL){
		return false;  //內(nèi)存不足，分配失敗
	}
	L->prior=NULL; //頭結(jié)點的prior指針指向NULL
	L->next=NULL;   //頭結(jié)點的next指針指向NULL
	return true;
}

4.7.2，雙向鏈表的插入

想要實現(xiàn)指定結(jié)點的后插操作，如在雙向鏈表的p結(jié)點之后插入s結(jié)點，核心在于修改指針。

• s->next=p->next; —新結(jié)點的后繼指針指向p結(jié)點的后繼結(jié)點
• p->next->prior=s; —p結(jié)點的后繼結(jié)點的前驅(qū)指針指向新結(jié)點
• s->prior=p; —新結(jié)點的前驅(qū)指針指向p結(jié)點
• p->next=s; —p結(jié)點的后繼指針指向新結(jié)點
• 如果p是最后一個結(jié)點需進行特殊處理，否則執(zhí)行p->next->prior=s時會報空指針錯誤（因為此時p->next為NULL）；

雙向鏈表的插入操作（指定結(jié)點后插）代碼實現(xiàn)如下：

//雙鏈表指定結(jié)點的后插操作（帶頭結(jié)點）
bool InsertNextNode(DNode *p,DNode *s){
	if(p==NULL || s==NULL){  //非法參數(shù)
		return false;    
	}
	
	//雙鏈表元素插入
	s->next=p->next;
	if(p->next!=NULL){      
		p->next->prior=s;     //p結(jié)點不是雙向鏈表內(nèi)最后一個結(jié)點時執(zhí)行
	}
	s->prior=p;
	p->next=s;
	return true;
}

4.7.3，雙向鏈表的元素刪除和整表銷毀

①雙向鏈表的元素刪除操作，一般是刪除指定結(jié)點的后繼結(jié)點。并核心也是修改指針，實現(xiàn)思路如下：

• 假設(shè)要刪除的結(jié)點為p，p的后繼結(jié)點為q；
• 修改指針p->next=q->next；
• q->next如果不為空則說明p不是最后一個元素，此時執(zhí)行操作q->next->prior=p；q->next如果不為空則不執(zhí)行；
• 釋放結(jié)點q的空間。

雙向鏈表元素刪除操作代碼實現(xiàn)如下：

//雙向鏈表刪除p結(jié)點的后繼結(jié)點
bool DeleteNextNode(DNode *p){
	if(p==NULL){
		return false;  //參數(shù)不合法
	}
	DNode *q=p->next;  //找到p的后繼結(jié)點q
	if(q==NULL){       //p結(jié)點沒有后繼結(jié)點
		return false;   
	}

	//刪除結(jié)點
	p->next=q->next;  
	if(q->next!=NULL){  //q結(jié)點不是最后一個結(jié)點時
		q->next->prior=p;
	}
	return true;
}

②雙向鏈表的整表銷毀操作可以循環(huán)執(zhí)行元素刪除操作實現(xiàn)，具體實現(xiàn)思路如下：

• 循環(huán)刪除頭結(jié)點后的各結(jié)點；
• 刪除各結(jié)點之后釋放頭結(jié)點空間；
• 使頭指針指向NULL；

雙向鏈表整表銷毀操作代碼實現(xiàn)如下：

//雙向鏈表整表銷毀
void DestoryList(DLinkList &L){
	//循環(huán)釋放各個數(shù)據(jù)結(jié)點
	while(L->next!=NULL){
		//雙鏈表刪除指定結(jié)點的后繼結(jié)點操作（前面已定義）
		DeleteNextNode(L);
	}
	free(L); //刪除完成，釋放頭結(jié)點
	L=NULL;  //頭指針指向NULL
}

4.7.4，雙向鏈表的遍歷

雙向鏈表的遍歷方式分為前向遍歷和后向遍歷。其中前向遍歷又分為帶頭結(jié)點和不帶頭結(jié)點兩種實現(xiàn)方式。具體代碼邏輯如下

//不帶頭結(jié)點的雙向鏈表的前向遍歷
while(p!=NULL){
	/*對結(jié)點p做相應(yīng)的操作，此處省略*/
	p=p->prior;  //p指針指向前驅(qū)結(jié)點
}

//帶頭結(jié)點的雙向鏈表的前向遍歷
while(p->prior!=NULL){
	/*對結(jié)點p做相應(yīng)的操作，此處省略*/
	p=p->prior;  //p指針指向前驅(qū)結(jié)點
}

//雙向鏈表后向遍歷
while(p->next!=NULL){
	/*對結(jié)點p做相應(yīng)的操作，此處省略*/
	p=p->next;  //p指針指向后繼結(jié)點
}

此外，由于雙向鏈表不可隨機存取，按位查找，按值查找操作都只能通過遍歷的方式實現(xiàn)。因此時間復(fù)雜度均為O(n)。

4.8，循環(huán)鏈表

循環(huán)鏈表有循環(huán)單鏈表和循環(huán)雙鏈表。

4.8.1，循環(huán)單鏈表

前面學(xué)習(xí)到的普通單鏈表的表尾結(jié)點的next指針是指向NULL的，而循環(huán)單鏈表的表尾結(jié)點的next指針是指向頭結(jié)點的。圖示如下：

那么循環(huán)單鏈表來說，它的初始化狀態(tài)（空表狀態(tài)）如下圖所示：

因此循環(huán)單鏈表的結(jié)點定義和初始化操作代碼實現(xiàn)如下：

//循環(huán)單鏈表的結(jié)點定義（同單鏈表）
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;  //循環(huán)單鏈表初始化時頭結(jié)點的next指針指向頭結(jié)點?。?！
	return true;
}

已知空表的狀態(tài)，則循環(huán)單鏈表的判空操作即看頭指針是否指向頭結(jié)點； 代碼實現(xiàn)如下：

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

同理，若要判斷結(jié)點p是否為循環(huán)單鏈表的表尾結(jié)點，則只需要判斷p->next是否為L。

對于單鏈表，給定一個結(jié)點，只能找到該結(jié)點的后續(xù)的各結(jié)點；
而對于循環(huán)單鏈表而言，給定一個結(jié)點，可以找到表中其他任何一個結(jié)點。

拓展思考：
在很多情況下，我們對鏈表的操作都是在鏈表的頭部或尾部。那么對于一個循環(huán)單鏈表，若頭指針指向頭結(jié)點，那么查找表頭的時間復(fù)雜度為O(1)，而查找表尾的時間復(fù)雜度為O(n)。這種情況能不能進行優(yōu)化呢？

實際上，只需要讓頭指針指向表尾元素即可，這樣的話可以通過指針直接訪問表尾元素，若要訪問循環(huán)單鏈表的表頭元素，可以直接訪問表尾元素的下一個結(jié)點即可，對表頭和表尾元素查找的時間復(fù)雜度均為O(1)；

4.8.2，循環(huán)雙鏈表

前面學(xué)習(xí)到的普通雙鏈表的表尾結(jié)點的next指針和表頭結(jié)點的prior指針都是指向NULL的，而循環(huán)雙鏈表的表尾結(jié)點的next指針是指向頭結(jié)點的，表頭結(jié)點的prior指針是指向表尾結(jié)點的。圖示如下：

那么循環(huán)雙鏈表來說，它的初始化狀態(tài)（空表狀態(tài)）如下圖所示：

因此循環(huán)雙鏈表的結(jié)點定義和初始化操作代碼實現(xiàn)如下：

//循環(huán)雙鏈表的結(jié)點定義（同雙鏈表）
typedef struct DNode{
	ElemType data;       //數(shù)據(jù)域
	struct DNode *prior,*next;    //前驅(qū)和后繼指針
}DNode,*DLinkList;

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

同理，循環(huán)雙鏈表的判空操作和判斷指定結(jié)點是否為表尾結(jié)點的代碼如下：

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

//判斷指定結(jié)點是否為循環(huán)雙鏈表表尾結(jié)點
bool isTail(DLinkList L,DNode *p){
	if(p->next==L){      //看該結(jié)點的下一個結(jié)點是否為表頭結(jié)點
		return true;
	}else{
		return false; 
	}
}

循環(huán)雙鏈表的插入操作

回顧普通雙鏈表，p結(jié)點的后插操作中，需要判斷p結(jié)點是否為表尾結(jié)點，若為非表尾結(jié)點則需要修改其后繼結(jié)點p->next的指針。因為在普通雙鏈表內(nèi)，表尾結(jié)點next指針指向NULL，需要特殊處理。而循環(huán)雙鏈表內(nèi)，表尾元素的next指針指向頭結(jié)點，無需特殊處理，無需判斷p結(jié)點是否為最后一個結(jié)點。邏輯較普通雙鏈表更簡單。

循環(huán)雙鏈表指定結(jié)點后插操作的代碼實現(xiàn)如下：

//在p結(jié)點之后插入s結(jié)點
bool InsertNextNode(DNode *p, DNode *s){
	s->next=p->next;
	p->next->prior=s;   //循環(huán)雙鏈表表尾結(jié)點next指針指向表頭，不會出現(xiàn)空指針錯誤
	s->prior=p;
	p->next=s;
	return true;
}

同理，循環(huán)雙鏈表的刪除（指定結(jié)點后刪操作），也無需判斷是否為表尾結(jié)點，核心代碼邏輯如下：

//刪除p的后繼結(jié)點q
bool deleteNode(DNode *p){
	DNode *q=p->next;   
	p->next=q->next;
	q->next->prior=p;  //循環(huán)雙鏈表此處不會出現(xiàn)空指針錯誤
}

4.9，靜態(tài)鏈表

• 靜態(tài)鏈表是用數(shù)組方式實現(xiàn)的鏈表；
• 某個結(jié)點存放的游標(biāo)如果為-1，則說明該結(jié)點為表尾結(jié)點；
• 為了方便，也可以將空閑結(jié)點位置的游標(biāo)設(shè)置為-2，這樣就可以覆蓋臟數(shù)據(jù)，并且可以通過判斷游標(biāo)是否為-2來判斷該結(jié)點是否為空；
• 靜態(tài)鏈表的優(yōu)點是增刪操作無需移動大量元素；
• 靜態(tài)鏈表的缺點是不能隨機存取，只能頭結(jié)點開始依次向后查找；且容量固定不變；
• 適用于不支持指針的語言以及數(shù)據(jù)元素固定不變的場景；

靜態(tài)鏈表的兩種初始化方式：

#define MaxSize 10
typedef int ElemType;

//初始化方式一
typedef struct{
	ElemType data;  //數(shù)據(jù)域
	int next;  //游標(biāo)
}SLinkLisk[MaxSize];

//初始化方式二
struct Node{
	ElemType data;
	int next;
};
typedef struct Node SLinkList[MaxSize];  //這樣就可以使用SLinkList定義一個長度為MaxSize的Node型數(shù)組（SLinkList List;）

靜態(tài)鏈表的插入（位序i的位置上插入結(jié)點）：

• 先在靜態(tài)鏈表內(nèi)找到一個空的結(jié)點，存入數(shù)據(jù)元素；
• 從頭結(jié)點循環(huán)找到位序為（i-1）的結(jié)點；
• 修改新結(jié)點的游標(biāo)；
• 修改（i-1）號結(jié)點的游標(biāo)；

靜態(tài)鏈表刪除某個結(jié)點：

• 從頭結(jié)點出發(fā)找到該結(jié)點的前驅(qū)結(jié)點；
• 修改前驅(qū)結(jié)點的游標(biāo)；
• 被刪除結(jié)點的游標(biāo)可以設(shè)置為-2；

4.10，順序表和鏈表的總結(jié)

4.10.1，邏輯結(jié)構(gòu)

從邏輯結(jié)構(gòu)來看，順序表和鏈表都是線性結(jié)構(gòu)，元素之間為一對一關(guān)系。

4.10.2，存儲結(jié)構(gòu)

從存儲結(jié)構(gòu)來看二者各有優(yōu)缺點。

因此當(dāng)表長難以預(yù)估，并且需要頻繁插入刪除元素的場景下，使用鏈表更合適。比如實現(xiàn)奶茶店的排隊取號功能；
當(dāng)表長可預(yù)估，且查詢操作比較多的場景下，使用順序表更合適。比如實現(xiàn)課堂上的學(xué)生點名功能。

文章來源地址http://www.zghlxwxcb.cn/news/detail-460522.html

到了這里，關(guān)于順序表和鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！