C++數據結構之單鏈表

Posted on by

簡介：

線性表的順序存儲結構有一個缺點就是插入和刪除時需要移動大量元素，這會耗費許多時間。能不能想辦法解決呢？
幹脆所有的元素都不要考慮相鄰位置瞭，哪有空位就到哪裡，讓每一個元素都知道它下一個元素的位置在哪裡。
線性表鏈式存儲結構： 用一組任意的存儲單元存儲線性表的數據元素(這組存儲單元可以是連續的，也可以是不連續的)。
鏈表是由一個個結點鏈結成的。
結點包括數據域和指針域兩部分，數據域用來存儲數據元素的信息，指針域用來存儲下一個結點的地址。

在這裡插入圖片描述

接下來實現一個無頭單向非循環鏈表。

單鏈表結構的定義

typedef int SLTDataType;

typedef struct SListNode
{
    SLTDataType data;        //數據
    struct SListNode* next;        //指向下一個結點的指針
}SLTNode;

單鏈表打印

void SListPrint(SLTNode* phead)
{
    SLTNode* cur = phead;
    while (cur)
    {
        printf("%d -> ", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}

在這裡插入圖片描述

將指向鏈表的指針plist做參數傳給函數，遍歷一遍鏈表並輸出每個結點數據域的內容。

動態申請一個結點

SLTNode* BuySListNode(SLTDataType x)
{
    SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
    if (node == NULL)
    {
        printf("malloc fail");
        exit(-1);
    }
    node->data = x;
    node->next = NULL;
    return node;
}

用malloc動態開辟一個結點，如果node為NULL說明開辟失敗，退出程序。否則將結點node的數據域賦值為x，指針域賦值為NULL。

單鏈表尾插

如果單鏈表為空，開辟一個新結點用指針指向它即可；如果鏈表不為空，需要開辟一個新結點，然後找到鏈表的最後一個結點，讓最後一個結點的指針域存放新結點的地址。

有一個鏈表，為鏈表尾插一個新結點：

在這裡插入圖片描述

在這裡插入圖片描述

在這裡插入圖片描述

void SListPushBack(SLTNode** pphead, SLTDataType x)
{
    assert(pphead);        //plist地址一定不為NULL，進行斷言
    if (*pphead == NULL)    //鏈表為空
    {
        SLTNode* newnode = BuySListNode(x);
        *pphead = newnode;
    }
    else           //鏈表不為空
    {        
        SLTNode* tail = *pphead;
        while (tail->next)        //找到最後一個結點
            tail = tail->next;
        SLTNode* newnode = BuySListNode(x);
        tail->next = newnode;
    }
}

在這裡插入圖片描述

為指針不好的同學解釋下參數，plist為指向結構體的指針，指向鏈表的頭結點，打印函數的形參phead為plist的一個臨時拷貝，作用和plist是一樣的，這裡的尾插函數pphead為指針plist的地址，是一個二級指針。因為當鏈表為空時，會改變指針的指向，所以參數用二級指針。

在這裡插入圖片描述

單鏈表尾刪

如果鏈表隻有一個結點，把這個結點free掉即可。如果鏈表有多個結點，找到鏈表的尾結點和尾結點的前一個結點，讓尾結點的前一個結點的指針域指向NULL，free掉尾結點。

在這裡插入圖片描述

void SListPopBack(SLTNode** pphead)
{
    assert(pphead);        //斷言pphead
    assert(*pphead);    //當鏈表為空時說明沒有結點，沒法進行刪除操作，所以*pphead不能為NULL
    if ((*pphead)->next == NULL)    //隻有一個結點
    {
        free(*pphead);
        *pphead = NULL;
    }
    else                //多個結點
    {
        SLTNode* tail = *pphead;    //tail表示為節點
        SLTNode* prev = NULL;        //prev表示尾結點的前一個結點
        while (tail->next)        //找到尾結點和尾結點的前一個結點
        {
            prev = tail;
            tail = tail->next;
        }
        prev->next = NULL;
        free(tail);
        tail = NULL;
    }
}

單鏈表頭插

申請一個新結點，讓新結點的指針域存放頭結點的地址，原來指向頭結點的指針plist指向新結點，新結點就變成瞭新的頭結點。

在這裡插入圖片描述

void SListPushFront(SLTNode** pphead, SLTDataType x)
{
    assert(pphead);
    SLTNode* newnode = BuySListNode(x);
    newnode->next = *pphead;
    *pphead = newnode;
}

單鏈表頭刪

用一個指針指向頭結點的下一個結點，把頭結點的空間釋放掉，指向頭結點的指針指向頭結點的下一個結點。頭結點的下一個結點就變成瞭新的頭結點。同時要考慮鏈表為空時不能刪除，進行相應的斷言。

在這裡插入圖片描述

void SListPopFront(SLTNode** pphead)
{
    assert(pphead);
    assert(*pphead);
    SLTNode* next = (*pphead)->next;    //指針next記錄頭結點的下一個結點
    free(*pphead);
    *pphead = next;
}

求單鏈表長度

int SListSize(SLTNode* phead)
{
    int size = 0;
    SLTNode* cur = phead;
    while (cur)
    {
        ++size;
        cur = cur->next;
    }
    return size;
}

單鏈表查找

遍歷一遍單鏈表，如果某一結點數據域內容與要查找內容相同，返回該結點。遍歷完沒有找到，返回NULL。

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

單鏈表在pos位置插入

在pos位置插入，如果pos這個位置是頭結點，和頭插的邏輯是一樣的，可以調用之前寫過的頭插函數。
如果這個位置是除頭結點外的任意一個結點，我們需要申請一個新結點，並且記錄pos結點的前一個結點，讓新結點的指針域存放pos的地址，讓pos前一個結點的指針域存放新結點的地址，把它們鏈結起來。

在這裡插入圖片描述

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
    assert(pphead);        //指向頭結點指針的地址不能為NULL，進行斷言
    assert(pos);        //插入位置pos不能為NULL進行斷言
    if (pos == *pphead)        //要插入的位置pos和頭結點是一個位置
    {
        SListPushFront(pphead, x);
    }
    else                //pos不是頭結點
    {
        SLTNode* prev = *pphead;    //prev用來找到pos位置的前一個結點
        while (prev->next != pos)
            prev = prev->next;
        SLTNode* newnode = BuySListNode(x);        //申請一個新結點
        newnode->next = pos;        //把新結點鏈結
        prev->next = newnode;
    }
}

單鏈表在pos後面位置插入

申請一個新結點，讓新結點的指針域存放pos結點下一個結點的地址，pos結點的指針域存放新結點的地址。

在這裡插入圖片描述

void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
    assert(pos);
    SLTNode* newnode = BuySListNode(x);
    newnode->next = pos->next;
    pos->next = newnode;
}

單鏈表刪除pos位置

如果pos位置是頭結點，刪除邏輯和頭刪相同，調用頭刪函數即可。
如果是除頭結點外的其它結點，找到pos的前一個結點，讓這個結點的指針域指向pos的下一個結點。把pos結點空間釋放。

在這裡插入圖片描述

void SListErase(SLTNode** pphead, SLTNode* pos)
{
    assert(pphead && *pphead);    //pphead不能為空，鏈表不能為空進行斷言
    assert(pos);            //pos不能為空
    if (pos == *pphead)        //要刪除的位置pos是頭結點
    {
        SListPopFront(pphead);
    }
    else                    //不是頭結點
    {
        SLTNode* prev = *pphead;    //prev指針用來找到pos結點的前一個結點
        while (prev->next != pos)
            prev = prev->next;
        prev->next = pos->next;
        free(pos);
        pos = NULL;
    }
}

單鏈表刪除pos的下一個結點

記錄下pos的下一個結點，pos結點指針域指向pos下一個結點指針域指向的結點，釋放掉pos的下一個結點。

在這裡插入圖片描述

void SListEraseAfter(SLTNode* pos)
{
    //pos不能為空，不能為尾結點，因為尾結點的下一個是NULL，什麼也刪除不瞭
    assert(pos && pos->next);    
    SLTNode* next = pos->next;        //next指針指向pos下一個結點
    pos->next = next->next;
    free(next);
    next = NULL;
}

判斷單鏈表是否為空

bool SListEmpty(SLTNode* phead)
{
    return phead == NULL;
}

頭文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int SLTDataType;

typedef struct SListNode
{
    SLTDataType data;        //數據
    struct SListNode* next;        //指向下一個結點的指針
}SLTNode;

//打印
void SListPrint(SLTNode* phead);
//新節點
SLTNode* BuySListNode(SLTDataType x);
//尾插
void SListPushBack(SLTNode** pphead, SLTDataType x);
//尾刪
void SListPopBack(SLTNode** pphead);
//頭插
void SListPushFront(SLTNode** pphead, SLTDataType x);
//頭刪
void SListPopFront(SLTNode** pphead);
//長度
int SListSize(SLTNode* phead);
//查找
SLTNode* SListFind(SLTNode* phead, SLTDataType x);
//在pos位置插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//pos位置後面插入
void SListInsertAfter(SLTNode* pos, SLTDataType x);
//刪除pos位置
void SListErase(SLTNode** pphead, SLTNode* pos);
//刪除pos後面位置
void SListEraseAfter(SLTNode* pos);
//判空
bool SListEmpty(SLTNode* phead);

源文件

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"

void SListPrint(SLTNode* phead)
{
    SLTNode* cur = phead;
    while (cur)
    {
        printf("%d -> ", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}

SLTNode* BuySListNode(SLTDataType x)
{
    SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
    if (node == NULL)
    {
        printf("malloc fail");
        exit(-1);
    }
    node->data = x;
    node->next = NULL;
    return node;
}

void SListPushBack(SLTNode** pphead, SLTDataType x)
{
    assert(pphead);        //plist地址一定不為NULL，進行斷言
    if (*pphead == NULL)    //鏈表為空
    {
        SLTNode* newnode = BuySListNode(x);
        *pphead = newnode;
    }
    else           //鏈表不為空
    {        
        SLTNode* tail = *pphead;
        while (tail->next)
            tail = tail->next;
        SLTNode* newnode = BuySListNode(x);
        tail->next = newnode;
    }
}

void SListPopBack(SLTNode** pphead)
{
    assert(pphead);        //斷言pphead
    assert(*pphead);    //當鏈表為空時說明沒有結點，沒法進行刪除操作，所以*pphead不能為NULL
    if ((*pphead)->next == NULL)    //隻有一個結點
    {
        free(*pphead);
        *pphead = NULL;
    }
    else                //多個結點
    {
        SLTNode* tail = *pphead;    //tail表示為節點
        SLTNode* prev = NULL;        //prev表示尾結點的前一個結點
        while (tail->next)        //找到尾結點和尾結點的前一個結點
        {
            prev = tail;
            tail = tail->next;
        }
        prev->next = NULL;
        free(tail);
        tail = NULL;
    }
}

void SListPushFront(SLTNode** pphead, SLTDataType x)
{
    assert(pphead);
    SLTNode* newnode = BuySListNode(x);
    newnode->next = *pphead;
    *pphead = newnode;
}

void SListPopFront(SLTNode** pphead)
{
    assert(pphead);
    assert(*pphead);
    SLTNode* next = (*pphead)->next;
    free(*pphead);
    *pphead = next;
}

int SListSize(SLTNode* phead)
{
    int size = 0;
    SLTNode* cur = phead;
    while (cur)
    {
        ++size;
        cur = cur->next;
    }
    return size;
}

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

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
    assert(pphead);        //指向頭結點指針的地址不能為NULL，進行斷言
    assert(pos);        //插入位置pos不能為NULL進行斷言
    if (pos == *pphead)        //要插入的位置pos和頭結點是一個位置
    {
        SListPushFront(pphead, x);
    }
    else                //pos不是頭結點
    {
        SLTNode* prev = *pphead;    //prev用來找到pos位置的前一個結點
        while (prev->next != pos)
            prev = prev->next;
        SLTNode* newnode = BuySListNode(x);        //申請一個新結點
        newnode->next = pos;        //把新結點鏈結
        prev->next = newnode;
    }
}

void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
    assert(pos);
    SLTNode* newnode = BuySListNode(x);
    newnode->next = pos->next;
    pos->next = newnode;
}

void SListErase(SLTNode** pphead, SLTNode* pos)
{
    assert(pphead && *pphead);    //pphead不能為空，鏈表不能為空進行斷言
    assert(pos);            //pos不能為空
    if (pos == *pphead)        //要刪除的位置pos是頭結點
    {
        SListPopFront(pphead);
    }
    else                    //不是頭結點
    {
        SLTNode* prev = *pphead;    //prev指針用來找到pos結點的前一個結點
        while (prev->next != pos)
            prev = prev->next;
        prev->next = pos->next;
        free(pos);
        pos = NULL;
    }
}

void SListEraseAfter(SLTNode* pos)
{
    //pos不能為空，不能為尾結點，因為尾結點的下一個是NULL，什麼也刪除不瞭
    assert(pos && pos->next);    
    SLTNode* next = pos->next;        //next指針指向pos下一個結點
    pos->next = next->next;
    free(next);
    next = NULL;
}

bool SListEmpty(SLTNode* phead)
{
    return phead == NULL;
}

到此這篇關於C++數據結構之單鏈表的文章就介紹到這瞭,更多相關C++ 單鏈表內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：