Hello,米娜桑們，這里是君兮_，我們接著之前講過(guò)的順序表來(lái)繼續(xù)介紹初階數(shù)據(jù)結(jié)構(gòu)的內(nèi)容，今天給大家?guī)?lái)的是有關(guān)鏈表的基本知識(shí)和各種接口功能的實(shí)現(xiàn)
好了，廢話不多說(shuō)，開(kāi)始今天的學(xué)習(xí)吧！—

一.鏈表的基礎(chǔ)知識(shí)

1.鏈表的概念與基本結(jié)構(gòu)

• 概念：鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的 。
• 鏈表鏈表，表如其名，鏈表的結(jié)構(gòu)就如同被連接起來(lái)了，只不過(guò)在中間連接鏈表的“繩索”是指針。
  
• 從基本結(jié)構(gòu)圖中我們可以看出：
  1.鏈?zhǔn)浇Y(jié)構(gòu)在邏輯上是連續(xù)的，但與順序表不同，在物理上鏈表是不一定連續(xù)的
  2.現(xiàn)實(shí)中，鏈表的節(jié)點(diǎn)一般都是從堆上申請(qǐng)出來(lái)的。
  3.從堆上申請(qǐng)的空間，是按照一定的策略來(lái)分配的，兩次申請(qǐng)的空間可能連續(xù)，也可能不連續(xù)。

2.鏈表的分類

• 在實(shí)際中鏈表的結(jié)構(gòu)非常多樣，下面就簡(jiǎn)單的介紹幾種
  
  
  

• 雖然鏈表有多種結(jié)構(gòu)，但是最常用的還是這兩種
  
• 1. 無(wú)頭單向非循環(huán)鏈表：結(jié)構(gòu)簡(jiǎn)單，一般不會(huì)單獨(dú)用來(lái)存數(shù)據(jù)。實(shí)際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。
• 2. 帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，一般用在單獨(dú)存儲(chǔ)數(shù)據(jù)。實(shí)際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表。另外這個(gè)結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使用代碼實(shí)現(xiàn)以后會(huì)發(fā)現(xiàn)結(jié)構(gòu)會(huì)帶來(lái)很多優(yōu)勢(shì)，實(shí)現(xiàn)反而簡(jiǎn)單了，后面我也會(huì)帶大家逐一實(shí)現(xiàn)代碼。

二.無(wú)頭單鏈表的實(shí)現(xiàn)

• 由于我們是初階數(shù)據(jù)結(jié)構(gòu)，且這是有關(guān)鏈表的第一篇博客，我們就先從最簡(jiǎn)單的無(wú)頭單鏈表開(kāi)始實(shí)現(xiàn)。
• 首先我們先把需要的幾個(gè)功能的接口列出來(lái)然后咱們來(lái)一個(gè)一個(gè)介紹。

說(shuō)明：以下包括后面的所有代碼的函數(shù)名稱等都是我根據(jù)該函數(shù)的功能編的，也就是說(shuō)這些函數(shù)名等不唯一，你也可以起別的名字，不影響鏈表的使用，但就像給孩子取名一樣，我們都不希望我們的孩子的名字叫狗蛋，二狗子什么的，實(shí)際上，在函數(shù)的命名中你瞎起名字就和這些差不多，因此我建議無(wú)論是現(xiàn)在還是以后的函數(shù)的命名最好都按照功能來(lái)命名，這樣既增加了代碼的可讀性，也讓人一看便知各個(gè)函數(shù)的功能。

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
    SLTDataType Data;
    struct SListNode * next;

}SLTNode;
//打印鏈表
void SLTPrint(SLTNode* phead);
//初始化鏈表
SLTNode* BuySListNode(SLTDataType x);
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);

void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
// 找某個(gè)數(shù)
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);

// 在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);

// 在pos以后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);

// 刪除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos);

// 刪除pos的后一個(gè)位置
void SLTEraseAfter(SLTNode* pos);
//修改pos位置的值
void SLTModify(SLTNode**pphead, SLTNode* pos, SLTDataType x);
// 單鏈表的銷毀
void SListDestroy(SLTNode** pphead);

• 注意：對(duì)接口的聲明都包含在頭文件中
• 先講一下這里面需要注意的幾個(gè)地方：
• 1.第一處的 typedef 實(shí)際是為了方便我們的使用，因?yàn)槲覀円膊恢牢覀兊逆湵硎怯脕?lái)存儲(chǔ)什么類型的數(shù)據(jù)的，因此我們這里就定義一個(gè)SLDataType，下面的代碼中統(tǒng)一把數(shù)據(jù)類型用它來(lái)代替，這樣一來(lái)，我們以后想要改變存儲(chǔ)的數(shù)據(jù)類型，只需要改動(dòng)這里即可，比如我們現(xiàn)在想要存儲(chǔ)double類型的數(shù)據(jù)

typedef double SLDataType;

• 2.關(guān)于我們的鏈表的結(jié)構(gòu)體

typedef struct SListNode
{
    SLTDataType Data;
    struct SListNode * next;

}SLTNode;

• 我們說(shuō)了，我們的鏈表的連接是通過(guò)指針來(lái)實(shí)現(xiàn)的，因此我們的結(jié)構(gòu)體中第一個(gè)成員是該節(jié)點(diǎn)存儲(chǔ)的值，第二個(gè)成員則是一個(gè)該結(jié)構(gòu)體的指針，指向的是下一個(gè)節(jié)點(diǎn)的地址。

1.初始化鏈表 BuySListNode

• 當(dāng)我們想使用我們的鏈表時(shí)，首先就像變量一樣需要先把它初始化一下

//初始化鏈表
SLTNode* BuySListNode(SLTDataType x)
{
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    if (newnode == NULL)
    {
        perror("malloc failed:");
        exit(-1);
    }
    newnode->Data = x;
    newnode->next = NULL;
    return newnode;

}

• 我們首先通過(guò)malloc為我們鏈表的一個(gè)節(jié)點(diǎn)開(kāi)辟了空間，然后通過(guò)perror判斷了我們的malloc是否成功，如果成功，我們就把該鏈表的值置為我們輸入的x，由于此時(shí)只有它一個(gè)節(jié)點(diǎn)，因此next置空，這樣我們的一個(gè)節(jié)點(diǎn)就初始化好了。

2.打印鏈表 SLTPrint

• 當(dāng)我們初始化成功后，我們就想把我們的鏈表打印一下，看看我們的鏈表是否成功初始化了，因此我們繼續(xù)來(lái)寫打印鏈表的函數(shù)

//打印鏈表
void SLTPrint(SLTNode* phead)
{
    SLTNode* cur = phead;
    while (cur)
    {
        printf("%d->", cur->Data);
        cur = cur->next;
    }
    printf("NULL\n");
}

• 我們定義了一個(gè)結(jié)構(gòu)體指針cur指向傳入的鏈表的表頭，當(dāng)cur不為空時(shí)，我們就打印一下此時(shí)該節(jié)點(diǎn)中的Data，并通過(guò)next找到下一個(gè)節(jié)點(diǎn)
• 由于我們鏈表的最后一個(gè)元素是NULL，因此我們最后把鏈表中所有節(jié)點(diǎn)都打印完后，在最后再補(bǔ)上一個(gè)NULL。

• 效果如上圖

3.頭插 SLTPushFront與頭刪 SLTPopFront

• 頭插與頭刪顧名思義，就是在鏈表表頭插入節(jié)點(diǎn)或者刪除鏈表表頭的節(jié)點(diǎn)

頭插

//頭插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
    SLTNode* newnode = BuySListNode(x);
    newnode->next = *pphead;
    *pphead = newnode;
}

• 頭插的邏輯圖是這樣的
  
  

頭刪

//頭刪
void SLTPopFront(SLTNode** pphead)
{
    //空
    assert(*pphead);
    //非空；
    SLTNode* newhead = (*pphead)->next;//保存一下下一個(gè)節(jié)點(diǎn)的地址
    free(*pphead);
    *pphead = newhead;
}

• 頭刪的邏輯圖
• 首先先判斷*pphead是否為空，如果為空，說(shuō)明這個(gè)鏈表壓根不存在
  
  

4.尾插SLTPushBack和尾刪 SLTPopBack

• 與前面同理，尾插和尾刪是作用于鏈表的最后的

尾插

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
    SLTNode* newnode = BuySListNode(x);
    SLTNode* tail = *pphead;
    //鏈表中沒(méi)有節(jié)點(diǎn)時(shí)
    if (*pphead == NULL)
    {
        *pphead = newnode;
    }
    else
    {
        //不為空時(shí)
        while (tail->next)
        {
            tail = tail->next;
        }
        tail->next = newnode;

    }
}

• 我們知道鏈表的最后一個(gè)節(jié)點(diǎn)的next存放的地址為空，我們來(lái)通過(guò)邏輯圖分析一下
• 首先還是特殊情況，當(dāng)我們的鏈表中沒(méi)有節(jié)點(diǎn)時(shí)，那我們就把頭指針直接指向需要插入的節(jié)點(diǎn)就行。
  
  

尾刪

//尾刪
void SLTPopBack(SLTNode** pphead)
{
    //為空
    assert(*pphead);
    //只有一個(gè)節(jié)點(diǎn)
    if ((*pphead)->next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
    }
    //不為空且有多個(gè)節(jié)點(diǎn)
    else
    {
        SLTNode* tail = *pphead;
        while (tail->next->next)
        {
            tail = tail->next;
        }
        free(tail->next);
        tail->next = NULL;


    }
}

• 還是先來(lái)分析特殊情況，先通過(guò)assert斷言來(lái)判斷一下該鏈表是否為空，其次，如果這個(gè)鏈表只有一個(gè)節(jié)點(diǎn)時(shí)，我們指向把該節(jié)點(diǎn)free釋放掉再置空即可，不需要其他操作。
• 一般情況的邏輯圖
  
  

總結(jié)

• 由于篇幅有限，今天的內(nèi)容到這里就結(jié)束了，之后我們會(huì)把剩下沒(méi)講的接口講完然后再帶大家做幾道oj題讓大家更加熟悉鏈表的使用。相信如果你能一直跟著堅(jiān)持下去那么你鏈表這一塊的初階知識(shí)就一定沒(méi)什么問(wèn)題啦！切記要自己上手敲敲代碼哦！

• 好了，如果你有任何疑問(wèn)歡迎在評(píng)論區(qū)或者私信我提出，大家下次再見(jiàn)啦！

新人博主創(chuàng)作不易，如果感覺(jué)文章內(nèi)容對(duì)你有所幫助的話不妨三連一下這個(gè)新人博主再走唄。你們的支持就是我更新的動(dòng)力?。。?/font>