C語言數(shù)據(jù)結(jié)構(gòu)之雙鏈表&循環(huán)鏈表&靜態(tài)鏈表詳解

更新時間：2022年09月27日 10:09:36 作者：程序喵正在路上

這篇文章主要為大家詳細介紹了C語言數(shù)據(jù)結(jié)構(gòu)中雙鏈表&循環(huán)鏈表&靜態(tài)鏈表的原理與使用，文中的示例代碼講解詳細，感興趣的可以了解一下

單鏈表 VS 雙鏈表

我們都知道，單鏈表只有一個指向下一個結(jié)點的指針，當(dāng)我們想要找到前一個結(jié)點時就比較麻煩，而雙鏈表擁有兩個指針

總的來說：

單鏈表 —— 無法逆向檢索，有時候不太方便
雙鏈表 —— 可進可退，存儲密度更低一丟丟

定義雙鏈表結(jié)點類型

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

雙鏈表

雙鏈表的初始化（帶頭結(jié)點）

定義一個 InitLinklist 函數(shù)，參數(shù)為雙鏈表的引用，加引用是因為要改變這個雙鏈表

注意：頭結(jié)點的前驅(qū)指針永遠指向 NULL

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;

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

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

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

void testDLinklist() {
	//初始化雙鏈表
	DLinklist L;
	InitLinklist(L);
}

雙鏈表的插入

后插法

//在p結(jié)點之后插入s結(jié)點
bool InsertNextDNode(DNode *p, DNode *s) {
	if (p == NULL || s == NULL) return false;	//非法參數(shù)

	s->next = p->next;
	if (p->next != NULL)		//如果p結(jié)點有后繼結(jié)點
		p->next->prior = s;
	s->prior = p;
	p->next = s; 
	return true;
}

學(xué)會了后插操作，我們也就學(xué)會了按位序插入和前插法，大概思路為找到目標(biāo)結(jié)點的前驅(qū)結(jié)點，然后對其進行后插操作

雙鏈表的刪除

//刪除p結(jié)點的后繼結(jié)點
bool DeleteNextDNode(DNode *p) {
	if (p == NULL) return false;

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

//銷毀雙鏈表
void DestoryList(DLinklist &L) {
	//循環(huán)釋放各個數(shù)據(jù)結(jié)點
	while (L->next != NULL) {
		DeleteNextDNode(L);
	}
	free(L);	//釋放頭結(jié)點
	L = NULL;	//頭指針指向NULL
}

雙鏈表的遍歷

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

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

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

//前向遍歷（跳過頭結(jié)點）
while (p->prior != NULL) {
	//對結(jié)點p做相應(yīng)處理
	p = p->prior;
}

循環(huán)單鏈表

我們都知道，單鏈表的表尾結(jié)點的 next 指針是指向 NULL，顧名思義，循環(huán)單鏈表的表尾結(jié)點的 next 指針就是指向頭結(jié)點的

循環(huán)單鏈表的優(yōu)點：從一個結(jié)點出發(fā)可以找到其他任何一個結(jié)點

typedef int ElemType;

typedef struct LNode{
	ElemType data;			//每個節(jié)點存放一個數(shù)據(jù)元素
	struct LNode *next;		//指針指向下一個節(jié)點
}LNode, *LinkList;

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

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

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

循環(huán)雙鏈表

雙鏈表：

表頭結(jié)點的 prior 指向 NULL
表尾結(jié)點的 next 指向 NULL

循環(huán)雙鏈表

表頭結(jié)點的 prior 指向表尾結(jié)點
表尾結(jié)點的 next 指向頭結(jié)點

循環(huán)雙鏈表的初始化

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;

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)雙鏈表是否為空
bool Empty(DLinklist L) {
	if (L->next == L)
		return true;
	else
		return false;
}

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

void testDLinklist() {
	//初始化雙鏈表
	DLinklist L;
	InitDLinklist(L);
}

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

//在p結(jié)點之后插入s節(jié)點
bool InsertNextDNode(DNode *p, DNode *s) {
    s->next = p->next;
    p->next->prior = s;
    s->prior = p;
    p->next = s;
    return true;
}

循環(huán)雙鏈表的刪除

//刪除p的后繼結(jié)點q
p->next = q->next;
q->next->prior = p;
free(q);

靜態(tài)鏈表

什么是靜態(tài)鏈表

單鏈表：各個結(jié)點在內(nèi)存中星羅棋布、散落天涯

靜態(tài)鏈表：分配一整片連續(xù)的內(nèi)存空間，各個結(jié)點集中安置，0 號結(jié)點充當(dāng) “頭結(jié)點”，下一個結(jié)點的數(shù)組下標(biāo)（也稱為游標(biāo)）充當(dāng) “指針”，游標(biāo)為 -1 時表示已經(jīng)到達表尾

靜態(tài)鏈表是用數(shù)組的方式來實現(xiàn)的鏈表，其優(yōu)點為 —— 增、刪操作不需要大量移動元素；缺點為 —— 不能隨機存取，只能從頭結(jié)點開始依次往后查找；容量固定不可變

定義靜態(tài)鏈表

#define MaxSize 10            //靜態(tài)鏈表的最大長度
struct Node{
    ElemType data;            //存儲數(shù)據(jù)元素
    int next;                //下一個元素的數(shù)組下標(biāo)
};

或者

#define MaxSize 10            //靜態(tài)鏈表的最大長度
typedef struct {
    ElemType data;            //存儲數(shù)據(jù)元素
    int next;                //下一個元素的數(shù)組下標(biāo)
} SLinkList[MaxSize];

SLinkList a 相當(dāng)于 struct Node a[MaxSize]

基本操作的實現(xiàn)

初始化

把 a[0] 的 next 設(shè)置為 -1

把空的結(jié)點的 next 設(shè)置為 -2

查找

從頭結(jié)點出發(fā)依次往后遍歷結(jié)點

插入位序為 i 的結(jié)點

找到一個空的結(jié)點，存入數(shù)據(jù)元素
從頭結(jié)點出發(fā)找到位序為 i-1 的結(jié)點
修改新結(jié)點的 next
修改 i-1 號結(jié)點的 next

刪除某個結(jié)點

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

順序表和鏈表的比較

從邏輯結(jié)構(gòu)來說，順序表和鏈表都屬于線性表，都是線性結(jié)構(gòu)

從存儲結(jié)構(gòu)來說，順序表采用順序存儲，而鏈表采用鏈?zhǔn)酱鎯?/p>

順序表

優(yōu)點：支持隨機存取，存取密度高

缺點：大片連續(xù)空間分配不方便，改變?nèi)萘坎环奖?/p>

鏈表：

優(yōu)點：離散的小空間分配方便，改變?nèi)萘糠奖?/p>

缺點：不可隨機存取，存儲密度低

從基本操作來看

創(chuàng)

順序表需要預(yù)分配大片連續(xù)空間，若分配空間過小，則之后不方便擴展容量；若分配空間過大，則浪費內(nèi)存資源。如果采取靜態(tài)分配的方式，則容量不可改變；如果采取動態(tài)分配的方式，則容量可改變，但需要移動大量元素，時間代價高
鏈表只需分配一個頭結(jié)點（也可以不要頭結(jié)點，只聲明一個頭指針），之后方便拓展

銷

對鏈表來說，你只需掃描整個鏈表，依次刪除（free）各個結(jié)點即可
對順序表來說，首先你需要修改 length = 0，如果是采用靜態(tài)分配的方式，當(dāng)靜態(tài)數(shù)組的生命周期結(jié)束時，系統(tǒng)會自動回收空間；如果是采用動態(tài)分配的方式，用 malloc 申請的空間是屬于內(nèi)存中的堆區(qū)，在堆區(qū)的內(nèi)存空間不會由系統(tǒng)自動回收，需要我們手動 free

增刪