C語言數(shù)據(jù)結構之雙鏈表&循環(huán)鏈表&靜態(tài)鏈表詳解
更新時間：2022年09月27日 10:09:36 作者：程序喵正在路上
這篇文章主要為大家詳細介紹了C語言數(shù)據(jù)結構中雙鏈表&循環(huán)鏈表&靜態(tài)鏈表的原理與使用，文中的示例代碼講解詳細，感興趣的可以了解一下
單鏈表 VS 雙鏈表
我們都知道，單鏈表只有一個指向下一個結點的指針，當我們想要找到前一個結點時就比較麻煩，而雙鏈表擁有兩個指針
總的來說：
- 單鏈表 —— 無法逆向檢索，有時候不太方便
- 雙鏈表 —— 可進可退，存儲密度更低一丟丟
定義雙鏈表結點類型
typedef struct DNode{
ElemType data; //數(shù)據(jù)域
struct DNode *prior, *next; //前驅(qū)和后繼指針
}DNode, *DLinklist;
雙鏈表
雙鏈表的初始化（帶頭結點）
定義一個 InitLinklist 函數(shù)，參數(shù)為雙鏈表的引用，加引用是因為要改變這個雙鏈表
注意：頭結點的前驅(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)); //分配一個頭結點
if (L == NULL) return false; //內(nèi)存不足，分配失敗
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;
}
學會了后插操作，我們也就學會了按位序插入和前插法，大概思路為找到目標結點的前驅(qū)結點，然后對其進行后插操作
雙鏈表的刪除
//刪除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; //內(nèi)存不足，分配失敗
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; //前驅(qū)和后繼指針
}DNode, *DLinklist;
//初始化空的循環(huán)雙鏈表
bool InitDLinklist(DLinklist &L) {
L = (DNode *)malloc(sizeof(DNode)); //分配一個頭結點
if (L == NULL) return false; //內(nèi)存不足，分配失敗
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)鏈表
單鏈表：各個結點在內(nèi)存中星羅棋布、散落天涯
靜態(tài)鏈表：分配一整片連續(xù)的內(nèi)存空間，各個結點集中安置，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ā)找到前驅(qū)結點
- 修改前驅(qū)結點的游標
- 被刪除結點的 next 設置為 -2
順序表和鏈表的比較
從邏輯結構來說，順序表和鏈表都屬于線性表，都是線性結構
從存儲結構來說，順序表采用順序存儲，而鏈表采用鏈式存儲
順序表
優(yōu)點：支持隨機存取，存取密度高
缺點：大片連續(xù)空間分配不方便，改變?nèi)萘坎环奖?/p>
鏈表：
優(yōu)點：離散的小空間分配方便，改變?nèi)萘糠奖?/p>
缺點：不可隨機存取，存儲密度低
從基本操作來看
創(chuàng)
- 順序表需要預分配大片連續(xù)空間，若分配空間過小，則之后不方便擴展容量；若分配空間過大，則浪費內(nèi)存資源。如果采取靜態(tài)分配的方式，則容量不可改變；如果采取動態(tài)分配的方式，則容量可改變，但需要移動大量元素，時間代價高
- 鏈表只需分配一個頭結點（也可以不要頭結點，只聲明一個頭指針），之后方便拓展
銷
- 對鏈表來說，你只需掃描整個鏈表，依次刪除（free）各個結點即可
- 對順序表來說，首先你需要修改 length = 0，如果是采用靜態(tài)分配的方式，當靜態(tài)數(shù)組的生命周期結束時，系統(tǒng)會自動回收空間；如果是采用動態(tài)分配的方式，用 malloc 申請的空間是屬于內(nèi)存中的堆區(qū)，在堆區(qū)的內(nèi)存空間不會由系統(tǒng)自動回收，需要我們手動 free
增刪
- 對順序表來說，插入或刪除都要講后續(xù)元素全部后移或前移，時間復雜度為 O(n)，時間開銷主要來自移動元素
- 對鏈表來說，插入或刪除元素只需要修改指針即可，時間復雜度為 O(n)，時間開銷主要來自查找目標元素
- 雖然時間復雜度一樣，但是結合實際因素，鏈表增刪的效率要比順序表高得多
查
- 對順序表來說，按位查找的時間復雜度為 O(1)；按值查找的時間復雜度為 O(n)，如果表內(nèi)元素有序，可采用折半查找等方法在 O(log2n) 時間內(nèi)找到
- 對鏈表來說，按位查找的時間復雜度為 O(n)；按值查找的時間復雜度也為 O(n)
綜上所述
- 表長難以預估、經(jīng)常要增加或刪除元素 —— 鏈表
- 表長可預估、查詢操作較多 —— 順序表
以上就是C語言數(shù)據(jù)結構之雙鏈表&循環(huán)鏈表&靜態(tài)鏈表詳解的詳細內(nèi)容，更多關于C語言鏈表的資料請關注腳本之家其它相關文章！
相關文章
當我們編寫C++代碼時，經(jīng)常需要使用頭文件來引入一些常用的函數(shù)、類或者變量，如果一個頭文件被重復包含，就會導致編譯錯誤或者運行時錯，為了避免發(fā)生，我們需要使用預處理指令來防止頭文件被重復包含，常用的預處理指令有#pragma once和#ifndef,需要的朋友可以參考下2023-05-05
這篇文章主要為大家詳細介紹了如何利用得到的RGB信息重新對RGB圖片進行編碼，以及對其他圖片如BMP所得到的RGB信息進行編碼從而得到*.jpg文件，感興趣的可以了解一下2023-05-05
這篇文章主要為大家詳細介紹了C語言實現(xiàn)BMP圖像細化處理，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-10-10
本文主要介紹了Qt實現(xiàn)網(wǎng)絡聊天室，實現(xiàn)一個在線聊天室, 使用tcp對客戶端和服務器端進行通訊。具有一定的參考價值，具有一定的參考價值，2021-06-06
本篇文章是對C語言中段錯誤的問題進行了詳細的分析介紹，需要的朋友參考下2013-05-05
本篇文章主要介紹了C++的字符串分割函數(shù)，主要用strtok、STL、Boost進行字符串分割，有需要的可以了解一下。2016-11-11
這篇文章主要為大家詳細介紹了C語言線性表之雙鏈表，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-02-02
本篇文章是對鏈表的各類操作進行了詳細的分析介紹，需要的朋友參考下2013-05-05
C++中CString string char* char 之間的字符轉(zhuǎn)換（多種方法）
在寫程序的時候，我們經(jīng)常遇到各種各樣的類型轉(zhuǎn)換，比如 char* CString string 之間的互相轉(zhuǎn)換，這里簡單為大家介紹一下,需要的朋友可以參考下2017-09-09
這篇文章主要介紹了C語言實現(xiàn)的PNPoly算法代碼例子,PNPoly算法j是判斷一個坐標點是否在不規(guī)則多邊形內(nèi)部的算法,需要的朋友可以參考下2014-07-07