日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網(wǎng)站首頁 編程語言 正文

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

作者：程序喵正在路上 ? 更新時間： 2022-11-16 編程語言

單鏈表 VS 雙鏈表

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

總的來說：

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

定義雙鏈表結點類型

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

雙鏈表

雙鏈表的初始化（帶頭結點）

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

注意：頭結點的前驅指針永遠指向 NULL

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

typedef int ElemType;

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

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

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

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

雙鏈表的插入

后插法

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

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

學會了后插操作，我們也就學會了按位序插入和前插法，大概思路為找到目標結點的前驅結點，然后對其進行后插操作

雙鏈表的刪除

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

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

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

雙鏈表的遍歷

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

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

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

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

循環(huán)單鏈表

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

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

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));		//分配一個頭結點
	if (L == NULL) return false;			//內存不足，分配失敗
	L->next = L;			//頭結點next指針指向頭結點
	return true;
}

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

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

循環(huán)雙鏈表

雙鏈表：

  • 表頭結點的 prior 指向 NULL
  • 表尾結點的 next 指向 NULL

循環(huán)雙鏈表

  • 表頭結點的 prior 指向表尾結點
  • 表尾結點的 next 指向頭結點

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

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

typedef int ElemType;

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

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

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

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

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

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

//在p結點之后插入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的后繼結點q
p->next = q->next;
q->next->prior = p;
free(q);

靜態(tài)鏈表

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

單鏈表：各個結點在內存中星羅棋布、散落天涯

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

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

定義靜態(tài)鏈表

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

或者

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

SLinkList a 相當于 struct Node a[MaxSize]

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

初始化

把 a[0] 的 next 設置為 -1

把空的結點的 next 設置為 -2

查找

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

插入位序為 i 的結點

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

刪除某個結點

  • 從頭結點出發(fā)找到前驅結點
  • 修改前驅結點的游標
  • 被刪除結點的 next 設置為 -2

順序表和鏈表的比較

從邏輯結構來說，順序表和鏈表都屬于線性表，都是線性結構

從存儲結構來說，順序表采用順序存儲，而鏈表采用鏈式存儲

順序表

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

缺點：大片連續(xù)空間分配不方便，改變容量不方便

鏈表：

優(yōu)點：離散的小空間分配方便，改變容量方便

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

從基本操作來看

創(chuàng)

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

銷

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

增刪

  • 對順序表來說，插入或刪除都要講后續(xù)元素全部后移或前移，時間復雜度為 O(n)，時間開銷主要來自移動元素
  • 對鏈表來說，插入或刪除元素只需要修改指針即可，時間復雜度為 O(n)，時間開銷主要來自查找目標元素
  • 雖然時間復雜度一樣，但是結合實際因素，鏈表增刪的效率要比順序表高得多

查

  • 對順序表來說，按位查找的時間復雜度為 O(1)；按值查找的時間復雜度為 O(n)，如果表內元素有序，可采用折半查找等方法在 O(log2n) 時間內找到
  • 對鏈表來說，按位查找的時間復雜度為 O(n)；按值查找的時間復雜度也為 O(n)

綜上所述

  • 表長難以預估、經(jīng)常要增加或刪除元素 —— 鏈表
  • 表長可預估、查詢操作較多 —— 順序表

原文鏈接：https://blog.csdn.net/weixin_62511863/article/details/127020407

欄目分類
最近更新