鏈表的實作

首先我們要先有一個結構體

?
typedef int SLTDateType;//這樣是為了方便修改資料型別

typedef struct SListNode
{
    SLTDataType data;      //存盤資料
    struct SListNode* next;//儲存下一個節點的指標，鏈表就是通過此互相鏈接起來的
}SLTNode;                  //將該結構體進行重命名

struct SListNode
{
    //...
    //...
}SLTNode;
//這里還需要區分的是，如果前面沒有typedef，那么這里的SLTNode就相當于一個結構體變數

?

有了結構體之后我們應該創建一個鏈表，只需要一個結構體指標就夠了

STNode* plist = NULL;

新節點的創建

思路：

1. 開辟一塊新空間

2. 把值放進這塊新空間里面去

3. 回傳

那么我們實作出來會是這樣子的

SLTNode* BuyListNode(SLTDateType x)
{
    SLTNode* newnode = ((SLTNode*)malloc(sizeof(SLTNode)));
    
    newnode->data = x;
    
    return newnode;
}

當然除了主體框架之外還有一些小細節需要留意，如

1. 是否開辟成功

2. 新節點還存放了一個指標，該指標需要先初始化

SLTNode* SListBuyList(SLTDateType x)
{
    SLTNode* newnode = ((SLTNode*)malloc(sizeof(SLTNode)));
    if(newnode == NULL)
    {
        printf("malloc fail\n");
        exit(-1);//開辟失敗就結束程式
    }
    newnode->data = x;
    newnode->next = NULL;
    
    return newnode;
}

列印

1. 遍歷鏈表

2. 將每個節點的存放的值列印出來

tip：這里我們就需要看到函式傳參的問題了，到底要傳一級指標還是二級指標呢？

A：

如果我們不需要改變指標的值，就傳一級指標（如列印，查找）

如果我們需要改變指標的值，就傳二級指標（如洗掉，插入，銷毀）

void Print(SLTNode* phead)
{
    //遍歷鏈表，這是一個非常重要的操作
    SLTNode* cur = phead;
    while(cur)
    {
        cur = cur->next;
        printf("%d->", cur->data);
        //在這里還需要注意一點，訪問結構體的元素應該寫成cur->data,不能單純寫data
    }
    printf("NULL\n");
    //末尾加了NULL能告訴我們鏈表最后的指標指向空
}

尾插

1. 開辟新節點

2. 找到鏈表尾部

3. 將新節點插入到鏈表尾部

void SListPushBack(SLTNode** pphead)
{
    //開辟新節點，用newnode接收
    SListNode* newnode = BuyListNode(x);
    
    //找到鏈表尾部，也就是我們前面寫的遍歷鏈表
    STListNode* tail = *pphead;
    while(tail->next)//當tail->next == NULL時，那么tail就是最后一個節點了
    {
        tail = tail->next;
    }
    
    //將新節點插入到鏈表尾部
    tail->next = newnode;
    
    //從這里開始我們將會學習怎么將節點鏈接起來
    //思路是這樣的，就是把每個節點的尾都賦上我們想要的值
    //tail->next = newnode的意思就是tail的下個節點指向newnode
    //那么newnode的下一個節點呢？
    //在SListBuyList中我們已將其置空
}

當然這樣函式還遺漏了一些小問題

比如

函式傳參如果傳來了一個空指標？

鏈表本身就為空？

針對上述問題我們只需要做出兩步修改

1. 斷言避免空指標

2. 判斷鏈表是否為空

void SListPushBack(SLTNode** pphead, SLTDataType x)
{
    assert(pphead);
    
    SLTNode* newnode = BuyListNode(x);
    if((*pphead) == NULL)
    {
        return newnode;
    }
    else
    {
        SLTNode* tail = *pphead;
        while(tail->next)
        {
            tail = tail->next;
        }
        tail->next = newnode;
    }
}

尾刪

1. 找到尾部

2. 將尾部的節點銷毀，并將指向尾部節點的指標置空

void SListPopBakc(SLTNode** pphead)
{
    //找到尾部，這個操作我們已經講過兩遍了哦
    SLTNode* tail = *pphead;
    while(tail->next)
    {
        tail = tail->next;
    }
    
    //銷毀，置空
    free(tail);
    tail = NULL;
}

不過尾刪并沒有我們上面寫的那么簡單，上面的程式至少存在以上問題：

1. 傳參的時候可能會接收到空指標（尾插的時候已有提及）

2. 如果鏈表為空呢？

3. 我們將尾節點洗掉之后，指向尾節點的指標不是存放在上一個節點中嘛？這不就造成野指標了嘛？

解決方法：

根據第3點我們可以知道，尾節點銷毀之后還需要將指向它的指標置空，不然就會造成野指標，而這個指標存放在上一個節點中，所以我們需要記錄好上一個節點，然后在銷毀之后，將尾節點置空之外，還要將指向它的指標也置空

這里還需要注意，前面的討論是建立在至少有兩個節點的情況下的，那如果只有一個節點呢？如果一個節點都沒有呢？

我們可以知道，如果只有一個節點，那只需要將它本身置空就好，并沒有上一個節點存放它的地址（這里尚且不討論帶哨兵位頭節點的情況）

如果一個節點都沒有，那我們直接加斷言避免程式進行尾刪操作就好了

void SListPopBack(SLTNode** pphead)
{
    assert(pphead);//但凡接收指標最好都要加上斷言，易于我們查找錯誤，接下來函式實作將不再贅述
    assert(*pphead != NULL);
    
    if((*pphead)->next == NULL) //只有一個節點
    {
        free(*pphead);
        *pphead = NULL;
    }
    else	//有一個以上節點
    {
        //找尾并記錄前一個節點
        SLTNode* prev = NULL;
        SLTNode* tail = *pphead;
        while(tail->next)
        {
            prev = tail;
            //prev->next = tail;這里不能認為既然tail是prev的前一個就可以這么寫，因為prev是空指標，這樣會造成非法訪問
            //tail將會變成它的下一個節點，那么只需要在這之前讓prev = tail就好了，也就相當于記錄下了tail的前一個節點
            tail = tail->next;
        }
        free(tail);
        tail = NULL;
        
        prev->next = NULL;
        
        
        //這里還有第二種解法
        SLTNode* tail = *pphead;
        while(tail->next->next)
        {
            tail = tail->next;
        }
        free(tail->next);
        tail->next = NULL;
    }
}

這里是第二種方法的圖示

其實啊，置空之后節點的指標置空的問題很簡單

你只要讓每個節點存放的指標都有所指向就行了

就像第一種方法，你讓tail置空了

但是它上一個節點存放的指標卻沒有了指向，那么就也需要置空

所以說第一種方法的tail = NULL可要可不要，只要前一個節點存放的指標置空就好了，建議各位讀者還是要畫圖才能理解得更深

第二種方法需要有所指向的也只有 tail->next

頭插

1. 斷言避免空指標（這個我相信大家已經很清楚了，斷言是一種很好的習慣喔）

2. 創建一個新節點

3. 將新節點插入到頭節點前面

void SListPushFront(SLTNode** pphead, SLTDataType x)
{
    assert(pphead);
    SLTNode* newnode = BuyListNode(x); 
    //前面的我們已經基本都會了，這里我們來看看如何插入
    //前面講過，其實插入就是讓各個節點存放的指標都有所指向就好了
    newnode->next = *pphead;//讓原頭節點鏈接到新節點的后面
    *pphead = newnode;//因為newnode是插在頭部的嘛，所以它自然會變成新的頭節點
}

頭刪

1. 斷言避免空指標

2. 判斷鏈表是否為空（這一步跟尾插是一樣的）

3. 將頭節點銷毀并置空

void SListPopFront(SLTNode** pphead)
{
    assert(pphead);
    assert(*pphead != NULL);
    free(*pphead);
    *pphead = NULL;
}

不過這里寫完我們會發現一個問題：就是沒有新的頭節點了

那么我們需要把下一個節點先記錄起來，然后最后再讓它做新的頭節點

void SListPopFront(SLTNode** pphead)
{
    assert(pphead);
    assert(*pphead != NULL);
    SLTNode* Next = (*pphead)->next;
    free(*pphead);
    *pphead = NULL;
    *pphead = Next;//當然這兩步也可以直接合并起來
}

因此，尾刪的時候需要記錄上一個節點，頭刪的時候需要記錄下一個節點，這是由單向非回圈鏈表的特性所決定的，我們如果銷毀了該節點，就很難找到該節點的上一個或下一個節點，因此將其記錄下來是一個很好的方式

我們再回顧一下記錄上一個節點的方法，不斷重復才能深刻掌握

SLTNode* Prev = NULL;
while(tail->next)
{    
    Prev = tail;    
    tail = tail->next;
}

讀者也可在閱讀時上機親自實作這些函式，實踐才能出真知，并且體驗到編程的魅力

在節點pos后進行插入

1. 斷言避免空指標

2. 創建一個新節點

3. 將新節點鏈接到pos的后面（還記得鏈接的關鍵是什么嗎？讓每個節點都有所指向）

void SListInsertAfter(SLTNode** pphead, SLTNode* pos, SLDataType x)
{
    assert(pos && pphead);
    SLTNode* newnode = BuyListNode(x);
	newnode->next = pos->next;
    pos->next = newnode;
}

我們在這里仔細觀察一下，可以總結出一個結論

其實鏈接就是：讓每個節點存放的指標有所指向

這里的pos->next和newnode->next不就是每個節點存放的指標嘛

其實更具體地說，應該是改動的那些節點存放的指標有所指向

所以只要抓住這個點，鏈接這方面就會變得非常簡單

所以再回頭看看前面鏈接的步驟，會不會有不一樣的識訓呢？

在節點pos前進行插入

1. 斷言避免空指標

2. 創建新節點

3. 找到pos的前一個節點

4. 鏈接

void SListInsert(SLTNode** pphead, SLTDataType x)
{
    assert(pphead);
    SLTNode* newnode = BuyListNode(x);
    SLTNode* posPrev = *pphead;
    while(posPrev->next != pos)
    {
        posPrev = posPrev->next;
    }
    //找到之后就會跳出回圈，我們就可以進行鏈接
    //哪些節點存放的指標需要有所指向呢？分別是newnode->next和posPrev->next
    newnode->next = pos;
    posPrev->next = newnode;
}

細心的朋友可能會發現，我們這里考慮的情況仍然不全面

在前面其他函式的實作中，我們可以看到大抵可以分為三種情況：

1. 鏈表為空

2. 鏈表只有一個節點

3. 鏈表有一個以上節點

這里因為已經有一個pos節點，故我們不需要考慮第一種情況

而只有一個節點的話，那么這一個節點就是pos

void SListInsert(SLTNode** pphead, SLTDataType x)
{
    assert(pphead);
    SLTNode* newnode = BuyListNode(x);
    if((*pphead) == pos)
    {
        newnode->next = pos;
        *pphead = newnode;//讓newnode做新的頭節點
        //如果頭節點需要改變，就需要這一步，像尾插尾刪等都是不需要的
    }
    else
    {
        SLTNode* posPrev = *pphead;
        while(posPrev->next = pos)
        {
            posPrev = posPrev->next;
        }
        posPrev->next = newnode;
        newnode->next = pos;
    }
}

所以說，我們以后在實作完自己的程式之后，一定要想想是否已經考慮到所有情況，有無遺漏

這是程式設計的一個關鍵點

并且在上述函式的實作中，我們可以看到有很多類似的地方，比如

1. 接收指標時記得斷言

2. 鏈接就是讓每個節點存放的指標都有所指向

3. 頭插頭刪的時候還要記得改變頭節點

4. 如果在節點洗掉后，需要操作節點前或后的位置，可以將其記錄下來

5. 要盡量考慮到鏈表如果為空，鏈表只有一個節點這種情況

并且，在學習資料結構的程序中，畫圖給我們更加直觀的感受

查找并回傳節點

1. 斷言避免空指標

2. 遍歷鏈表

3. 判斷，如果里面的元素是我們需要的就回傳

4. 不是就繼續遍歷

void SListFind(SLTNode* phead, SLTDataType x)
{
    assert(phead);
    SLTNode* cur = phead;
    if(cur->data == x)
    {
        return cur;
    }
    else
    {
        cur = cur->next;
    }
    return NULL;
}

這里不需要改變指標的值，就不需要傳二級指標哦

洗掉pos節點

1. 斷言避免空空指標

2. 鏈接

3. 若鏈表只有一個節點則直接洗掉

4. 若鏈表有一個以上節點則需要記錄前一個節點

void SListErase(SLTNode** pphead, SLTNode* pos)
{
    assert(pphead && pos);
    if((*pphead) == pos)//只有一個節點，那也就是頭節點，那我們就還需要改變一下頭節點的值
    {
        *pphead = NULL;
        free(pos);
        pos = NULL;
    }
    else
    {
        SLTNode* posPrev = *pphead;
        while(posPrev->next != pos)
        {
			posPrev = posPrev->next;
        }
        posPrev->next = pos->next;
        free(pos);
        pos = NULL;
    }
}

所以我們需要加個if判斷一下

但是可能還會有一種情況，就如果我們洗掉的就是頭節點，那么頭節點就需要改變了

所以我們需要加個if判斷一下

else
{
    if((*pphead) == pos)//誒這里我們會發現這一句跟前面鏈表只有一個值是一樣的啊
    {
        *pphead = pos->next;//而且如果當鏈表里只有一個節點，那么pos->next不就是NULL嘛，那么我們就可以直接將其合并起來
        free(pos);
        pos = NULL;
    }
}

通過以上，我們可以得到最終的函式

void SListErase(SLTNode** pphead, SLTNode* pos)
{
    if((*pphead) == pos)//當洗掉的是首尾的元素的時候，只有一個節點或有一個以上節點的情況相同
    {
        *pphead = pos->next;
        free(pos);
        pos = NULL:
    }
    else//洗掉的不是頭節點
    {
        SLTNode* posPrev = *pphead;
        while(posPrev->next != pos)
        {
            posPrev = posPrev->next;
        }
        posPrev->next = pos->next;
        free(pos);
        pos = NULL;
    }
}

洗掉pos的后一個節點

1. 斷言避免空指標

2. 找到pos的后一個節點

3. 鏈接

4. 洗掉

void SListEraseAfter(SLTNode** pphead, SLTNode* pos)
{
    assert(pphead && pos);
    //找到pos的后一個節點
    SLTNode* Next = pos->next;
    //鏈接
    pos->next = Next->next;
    //洗掉
    free(Next);
    Next = NULL;
}

銷毀鏈表

1. 斷言避免空指標

2. 遍歷鏈表，逐個銷毀并置空

void SListDestory(SLTNode** pphead)
{
    assert(pphead);
    SLTNode* cur = *pphead;
    while(cur)
    {
        free(cur);
        cur = NULL;
        cur = cur->next;
    }
    *pphead = NULL;
}

注意，上面這種寫法是錯的，因為你已經將節點釋放掉了，還給作業系統了

這塊空間就不屬于用戶了，再去進行訪問 cur->next就會出阿信非法訪問的問題

前面我們在總結的第四點也有所提及

所以我們只需要提前將其記錄下來

while(cur)
{
    SLTNode* Next = cur->next;
    free(cur);
    cur = NULL;
    cur = Next;
}

到這里，單向不帶哨兵位鏈表的基本操作我們就都能實作

讀者也可以試著利用洗掉pos節點去實作頭刪和尾刪

還有利用插入pos節點前后的函式去實作頭插和尾插

在學習資料結構的程序中，我們要特別注意畫圖

畫圖能帶給我們更加直觀的感受

目錄

新節點的創建

列印

尾插

尾刪

頭插

頭刪

在節點pos前進行插入

查找并回傳節點

洗掉pos節點

洗掉pos的后一個節點

銷毀鏈表