C語言深入講解鏈表的使用
更新時間：2022年05月26日 10:40:20 作者：披星戴月的賈維斯
當(dāng)我們在寫一段代碼時，如果要頻繁的在一塊區(qū)域進行插入或者刪除操作時，會發(fā)現(xiàn)用數(shù)組實現(xiàn)會比較復(fù)雜，這時候我們就要用另一種數(shù)據(jù)結(jié)構(gòu)，鏈表來實現(xiàn)
現(xiàn)實生活中的火車就像一個完整的鏈表，現(xiàn)在我們來深入理解一下鏈表這個數(shù)據(jù)結(jié)構(gòu)。
一、鏈表的概念
概念：鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈 接次序?qū)崿F(xiàn)的 。
注：
1、從上圖中可看出，鏈?zhǔn)浇Y(jié)構(gòu)在邏輯上是連續(xù)的，但是在物理上不一定連續(xù)。
2、從現(xiàn)實中的結(jié)點一般是通過malloc函數(shù)申請的，所以其內(nèi)存分配是在堆區(qū)。
3、從堆上申請的空間，是按照一定的策略來分配的，則一個節(jié)點的大小為8個字節(jié)。
二、鏈表的分類
實際中鏈表的結(jié)構(gòu)非常多樣，以下情況組合起來就有8種鏈表結(jié)構(gòu)：
1. 單向或者雙向鏈表
2. 帶頭或者不帶頭(是否有自帶哨兵位頭結(jié)點)
第二個鏈表的d1指向了我們的哨兵位頭結(jié)點。
3. 循環(huán)或者非循環(huán)鏈表
4. 無頭單向非循環(huán)鏈表和帶頭雙向循環(huán)鏈表
1. 無頭單向非循環(huán)鏈表：結(jié)構(gòu)簡單，一般不會單獨用來存數(shù)據(jù)。實際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié) 構(gòu)，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。
2. 帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，一般用在單獨存儲數(shù)據(jù)。實際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向 循環(huán)鏈表。另外這個結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使用代碼實現(xiàn)以后會發(fā)現(xiàn)結(jié)構(gòu)會帶來很多優(yōu)勢，實現(xiàn)反而 簡單了。
3、鏈表的實現(xiàn)(代碼和注釋)
無頭+單向+非循環(huán)鏈表增刪查改實現(xiàn)
頭文件：
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//要求存儲的數(shù)據(jù)從0開始，依次存儲
//靜態(tài)的順序表
//問題：開小了，不夠用，開大了，存在浪費。
//struct SeqList
//{
// int a[N];
// int size;//記錄存儲了多少個數(shù)據(jù)。
//};
typedef int SLDateType;//宏定義我們的 SLDateType是int類型的
//動態(tài)的順序表
typedef struct SeqList
{
SLDateType* a;
int size; //存儲數(shù)據(jù)個數(shù)
int capacity;//存儲空間大小
}SL, SeqList;
void SeqListPrint(SeqList* psl);//鏈表的打印
void SeqListInit(SeqList* psl);//鏈表的初始化
void SeqListDestroy(SeqList* psl);//鏈表的銷毀
void SeqListCheckCapacity(SeqList* psl);//檢查內(nèi)存空間是否足夠
//時間復(fù)雜度是o(1)
void SeqListPushBack(SeqList* psl, SLDateType x);//鏈表的尾插
void SeqListPopBack(SeqList* psl);//鏈表的尾刪
//時間復(fù)雜度是o(n)
void SeqListPushFront(SeqList* psl, SLDateType x);//鏈表的頭插
void SeqListPopFront(SeqList* psl);//鏈表的頭刪
void SeqListInsert(SeqList* psl, size_t pos, SLDateType x);
// 刪除pos位置的數(shù)據(jù)
void SeqListErase(SeqList* psl, size_t pos);
// 順序表查找
int SeqListFind(SeqList* psl, SLDateType x);鏈表的函數(shù)實現(xiàn)部分的代碼：
#include"SeqList.h"
#include<assert.h>
void SeqListPrint(SeqList* psl)//結(jié)構(gòu)體指針傳參
{
for (int i = 0; i < psl->size; ++i)
{
printf("%d ", psl->a[i]);
}
printf("\n");
}
void SeqListInit(SeqList* psl)
{
assert(psl);//斷言psl不為空
psl->a = NULL;//a就相當(dāng)于是鏈表的頭
psl->size = 0;
psl->capacity = 0;
}
void SeqListDestroy(SeqList* psl)//鏈表的刪除
{
assert(psl);
free(psl->a);//free掉鏈表中a這個節(jié)點的位置
psl->a = NULL;//將a指向空
psl->capacity = psl->size = 0;//將鏈表的內(nèi)存大小置為0
}
void SeqListCheckCapacity(SeqList* psl)//檢查鏈表的內(nèi)存，如果不夠就增容。
{
assert(psl);
if (psl->size == psl->capacity)
{
//capacity == 0,所以要先特判一下capacity 的值
size_t newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;//初始節(jié)點數(shù)為4，如果內(nèi)存現(xiàn)在為0就擴大一倍
SLDateType* tmp = realloc(psl->a, sizeof(SLDateType) * newCapacity);//申請空間
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
else
{
psl->a = tmp;
psl->capacity = newCapacity;//原來的空間變?yōu)樾驴臻g
}
}
}
void SeqListPushBack(SeqList* psl, SLDateType x)
{
//如果滿了，要擴容
if (psl->size == psl->capacity)
{
//capacity == 0,所以要先特判一下capacity 的值
size_t newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
SLDateType* tmp = realloc(psl->a, sizeof(SLDateType) * newCapacity);
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
else
{
psl->a = tmp;
psl->capacity = newCapacity;
}
}
psl->a[psl->size] = x;
psl->size++;
}
void SeqListPopBack(SeqList* psl)
{
assert(psl);
if (psl->size > 0)
{
psl->size--;//尾刪就size--就好了
}
}
void SeqListPushFront(SeqList* psl, SLDateType x)
{
assert(psl);
SeqListCheckCapacity(psl);
int end = psl->size - 1;
while (end >= 0)//所有的數(shù)據(jù)往后挪1位
{
psl->a[end + 1] = psl->a[end];
--end;
}
psl->a[0] = x;//兩種操作是等價的
psl->size++;
//SeqListInsert(psl, 0, x);在頭部插入。
}
void SeqListPopFront(SeqList* psl)
{
assert(psl);
if (psl->size > 0)
{
int begin = 1;
while (psl->size > begin)
{
psl->a[begin - 1] = psl->a[begin];
++begin;
}
--psl->size;
}
}
void SeqListInsert(SeqList* psl, size_t pos, SLDateType x)
{
// 暴力檢查
assert(psl);
// 溫和檢查
if (pos > psl->size)
{
printf("pos 越界：%d\n", pos);
return;
//exit(-1);
}
// 暴力檢查
//assert(pos <= psl->size);
SeqListCheckCapacity(psl);
//int end = psl->size - 1;
//while (end >= (int)pos)
//{
// psl->a[end + 1] = psl->a[end];
// --end;
//}
size_t end = psl->size;
while (end > pos)
{
psl->a[end] = psl->a[end - 1];
--end;
}
psl->a[pos] = x;
psl->size++;
}4、鏈表oj題(小試牛刀)
包含三種情況
畫個圖分析：
思路：情況一和情況二都可以用prev和cur指針遍歷數(shù)組的兩個元素， if cur指針不等于6，prev指針和cur指針都往前走，如果cur = 6，prev跳到cur的下一個位置
如果是第三種情況，則需先找到head != val的位置，再重復(fù)進行如上操作。
代碼示例：
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode* prev = NULL;
struct ListNode* cur = head;
while(cur)
{
if(cur->val != val)//當(dāng)cur這個位置的值不等于val時往下走
{
prev = cur;//prev跳到cur位置
cur = cur->next;//cur指針繼續(xù)往下走
}
else
{
struct ListNode* next = cur->next;//定義一個新的指針
if(prev == NULL)//頭刪，head為空的狀態(tài)
{
free(cur);
head = next;//繼續(xù)往后面走
cur = next;
}
else
{
free(cur);//free掉cur這個節(jié)點
prev->next = next;//跳過了cur這個點
cur = next;//cur繼續(xù)往后走
}
}
}
return head;
}
思路1：反轉(zhuǎn)指針方向
思路二：用三個指針， n1, n2, n3 分別存放NULL, head, head->next;
代碼示例：
struct ListNode* reverseList(struct ListNode* head)
{
if(head == NULL) return NULL;
struct ListNode* n1, *n2, *n3;
n1 = NULL;
n2 = head;
n3 = n2->next;//n3的地址是n2的下一位
while(n2)
{
n2->next = n1;//n2 的下一位指向 n1;起到掉頭的作用
n1 = n2;
n2 = n3;
if(n3)
n3 = n3->next;
}
return n1;
}方法2：頭插法
殊途同歸。newhead 相當(dāng)于之前的n1, cur = n2, next = n3;
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* NewHead = NULL;
struct ListNode* cur = head;
while(cur)
{
struct ListNode* next = cur->next;
//頭插
cur->next = NewHead;//代表鏈表的指向方向。
NewHead = cur;//接著把地址傳過來(更新)
cur = next;//（更新）
}
return NewHead;
}思路：快慢指針法
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode* slow, * fast;
slow = fast = head;//剛開始slow和fast指針都指向頭
while(fast && fast->next) //想的是結(jié)束的條件，寫的是繼續(xù)的條件
{
slow = slow->next;
fast = fast->next->next;//fast 每次走兩步
}
return slow;
}總結(jié)
這里我?guī)Т蠹覐逆湵淼母拍睿湵淼姆诸?，鏈表的簡單實現(xiàn)以及3題oj題四個方面帶大家認(rèn)識鏈表
到此這篇關(guān)于C語言深入講解鏈表的使用的文章就介紹到這了,更多相關(guān)C語言鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C++實現(xiàn)LeetCode(179.最大組合數(shù))
這篇文章主要介紹了C++實現(xiàn)LeetCode(179.最大組合數(shù)),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-08-08
這篇文章主要介紹了怎樣用cmd運行C程序？今天就來和大家分享一下用cmd運行C程序的實現(xiàn)方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-10-10
采用類的機制后實現(xiàn)了數(shù)據(jù)的隱藏與封裝，類的數(shù)據(jù)成員一般定義為私有成員，成員函數(shù)一般定義為公有的，依此提供類與外界間的通信接口。但是，有時需要定義一些函數(shù)，這些函數(shù)不是類的一部分，但又需要頻繁地訪問類的數(shù)據(jù)成員，這時可以將這些函數(shù)定義為該類的友元函數(shù)2022-06-06
這篇文章主要介紹了C語言實現(xiàn)打印數(shù)字金字塔方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-11-11
本篇文章是c語言基礎(chǔ)篇，主要為大家介紹了C語言的函數(shù)與數(shù)組，每個函數(shù)本質(zhì)上都實現(xiàn)一個最小的功能，而main函數(shù)只負責(zé)調(diào)用函數(shù)，實現(xiàn)代碼的核心邏輯，提高代碼的可維護性2021-08-08
VisualStudio2022配置opencv的實現(xiàn)
本文主要介紹了VisualStudio2022配置opencv的實現(xiàn),文中通過圖文介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2024-06-06
這篇文章主要為大家介紹了詳解C語言算法fscanf讀取文件示例教程，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步2022-02-02
C語言實現(xiàn)學(xué)生成績管理系統(tǒng)
這篇文章主要為大家詳細介紹了C語言實現(xiàn)學(xué)生成績管理系統(tǒng)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-01-01
這篇文章主要介紹了C++中function包裝器的相關(guān)資料,std::function是C++11引入的一個模板類,用于封裝任何可調(diào)用對象,使得函數(shù)能夠像對象一樣傳遞、存儲和調(diào)用,文中通過代碼介紹的非常詳細,需要的朋友可以參考下2024-12-12
這篇文章主要給大家介紹了C++中進行txt文件讀入和寫入的相關(guān)資料，文中通過示例代碼介紹的非常詳細，對大家學(xué)習(xí)或者使用C++具有一定的參考學(xué)習(xí)價值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧2019-09-09