快捷導(dǎo)航

使用C++實現(xiàn)單鏈表的操作與實踐

更新時間：2025年02月10日 09:28:55 作者：平凡程序猿~

在程序設(shè)計中,鏈表是一種常見的數(shù)據(jù)結(jié)構(gòu),特別是在動態(tài)數(shù)據(jù)管理、頻繁插入和刪除元素的場景中,鏈表相比于數(shù)組,具有更高的靈活性和高效性,尤其是在需要頻繁修改數(shù)據(jù)結(jié)構(gòu)的應(yīng)用中,本文將詳細(xì)介紹如何用C++語言實現(xiàn)一個面向?qū)ο蟮膯捂湵?并展示完整的代碼示例

一、單鏈表的基本概念

單鏈表是一種由節(jié)點組成的線性數(shù)據(jù)結(jié)構(gòu)，其中每個節(jié)點包含數(shù)據(jù)部分和指向下一個節(jié)點的指針。與數(shù)組不同，鏈表的節(jié)點在內(nèi)存中不要求連續(xù)存儲，而是通過指針連接。因此，鏈表的插入和刪除操作較為靈活，不需要大量的數(shù)據(jù)移動。

在C++中，我們通過類的封裝特性來實現(xiàn)面向?qū)ο蟮逆湵?，這不僅能有效管理鏈表的內(nèi)存，還能通過封裝實現(xiàn)更易用、更安全的操作。

二、單鏈表類的設(shè)計

我們將通過一個簡單的C++類來實現(xiàn)單鏈表，該類包含基本的鏈表操作，如插入、刪除、打印鏈表等。

1. 節(jié)點的定義

首先，我們定義了一個 Node 結(jié)構(gòu)體來表示鏈表中的每個節(jié)點。每個節(jié)點包含一個數(shù)據(jù)部分 data 和一個指向下一個節(jié)點的指針 next。

struct Node {
    int data;      // 數(shù)據(jù)域
    Node* next;    // 指針域，指向下一個節(jié)點
};

2. 鏈表的類定義

接下來，我們定義 List 類，它包含一個指向鏈表頭部的指針 phead，以及若干成員函數(shù)來實現(xiàn)鏈表的常見操作。

class List {
private:
    Node* phead; // 鏈表頭指針

public:
    // 構(gòu)造函數(shù)
    List() : phead(nullptr) {}

    // 析構(gòu)函數(shù)
    ~List() {
        while (phead != nullptr) {
            PopFront();
        }
    }

    // 創(chuàng)建節(jié)點
    Node* CreateNode(int x) {
        Node* node = new Node;
        node->data = x;
        node->next = nullptr;
        return node;
    }

    // 打印鏈表
    void PrintList() {
        Node* cur = phead;
        while (cur) {
            cout << cur->data << "-->";
            cur = cur->next;
        }
        cout << "NULL" << endl;
    }

    // 頭插法
    void PushFront(int x) {
        Node* newNode = CreateNode(x);
        newNode->next = phead;
        phead = newNode;
    }

    // 尾插法
    void PushBack(int x) {
        Node* newNode = CreateNode(x);
        if (phead == nullptr)
            phead = newNode;
        else {
            Node* tail = phead;
            while (tail->next != nullptr) {
                tail = tail->next;
            }
            tail->next = newNode;
        }
    }

    // 頭刪
    void PopFront() {
        if (phead == nullptr)
            cout << "鏈表為空，無法進(jìn)行刪除操作！" << endl;
        else {
            Node* del = phead;
            phead = del->next;
            delete del;
            del = nullptr;
        }
    }

    // 尾刪
    void PopBack() {
        if (phead == nullptr)
            cout << "鏈表為空，無法進(jìn)行刪除操作！" << endl;
        else {
            if (phead->next == nullptr) {
                delete phead;
                phead = nullptr;
            } else {
                Node* tail = phead;
                while (tail->next->next != nullptr) {
                    tail = tail->next;
                }
                delete tail->next;
                tail->next = nullptr;
            }
        }
    }
};

三、單鏈表的操作實現(xiàn)

PushFront: 在鏈表的頭部插入新節(jié)點。
PushBack: 在鏈表的尾部插入新節(jié)點。
PopFront: 刪除鏈表的頭節(jié)點。
PopBack: 刪除鏈表的尾節(jié)點。
PrintList: 打印鏈表中的所有節(jié)點。

四、測試與演示

下面的 main 函數(shù)展示了如何使用上述鏈表類實現(xiàn)基本操作：

int main() {
    List ls1;  // 創(chuàng)建一個鏈表對象

    // 進(jìn)行一些操作
    ls1.PushBack(1);
    ls1.PushBack(2);
    ls1.PushBack(3);
    ls1.PushBack(4);
    ls1.PushBack(5);

    // 打印鏈表
    ls1.PrintList();

    // 頭刪除和尾刪除
    ls1.PopFront();
    ls1.PopBack();

    // 頭插操作
    ls1.PushFront(9);

    // 打印鏈表
    ls1.PrintList();

    return 0;
}

五、鏈表操作的復(fù)雜度

PushFront 和 PopFront：這兩個操作的時間復(fù)雜度為 O(1)，因為它們僅僅操作鏈表的頭節(jié)點。
PushBack 和 PopBack：這兩個操作的時間復(fù)雜度為 O(n)，需要遍歷整個鏈表，直到找到尾節(jié)點。
PrintList：打印鏈表的時間復(fù)雜度為 O(n)，需要遍歷所有節(jié)點。

六、完整代碼

#include<iostream>
using namespace std;
//節(jié)點類型聲明
struct Node
{
    int date;
    Node* next;
};
class List
{
private:
    //成員變量
    Node* phead;
public:
    //成員函數(shù)
    List() : phead(nullptr) {}//構(gòu)造函數(shù)
    ~List()//析構(gòu)函數(shù)
    {
        while(phead!=NULL)
        {
            PopFront();
        }
    }
    Node* CreateNode(int x)//創(chuàng)建節(jié)點
    {
        Node* node=new Node;
        node->date=x;
        node->next=NULL;
        return node;
    }
    void PrintList()//打印鏈表
    {
        Node *cur=phead;
        while(cur)
        {
            cout<<cur->date<<"-->";
            cur=cur->next;
        }
        cout<<"NULL"<<endl;
    }
    void PushFront(int x)//頭插
    {
        Node*newnode=CreateNode(x);
        newnode->next=phead;
        phead=newnode;
    }
    void PushBack(int x)//尾插
    {
        Node*newnode=CreateNode(x);
        if(phead==NULL)
            phead=newnode;
        else
        {
            Node* tail = phead;
            while (tail->next != NULL)
            {
                tail = tail->next;
            }
            tail->next = newnode;
        }

    }
    void PopFront() //頭刪
    {
        if (phead==NULL)
            cout<<"鏈表為空，無法進(jìn)行刪除操作！"<<endl;
        else
        {
            Node* del=phead;
            phead=del->next;
            delete del;
            del=NULL;
        }
    }

    void PopBack()  //尾刪
    {
        if (phead== NULL)
            cout<<"鏈表為空，無法進(jìn)行刪除操作！"<<endl;
       else
        {
           if(phead->next==NULL)
           {
               delete phead;
               phead=NULL;
           }
           else
           {
               Node* tail = phead;
               while (tail->next->next != NULL)
               {
                   tail = tail->next;
               }
               delete tail->next;
               tail->next=NULL;
           }
        }
    }

};
int main()
{
    List ls1;
    ls1.PushBack(1);
    ls1.PushBack(2);
    ls1.PushBack(3);
    ls1.PushBack(4);
    ls1.PushBack(5);
    ls1.PrintList();
    ls1.PopFront();
    ls1.PopBack();
    ls1.PushFront(9);
    ls1.PrintList();
    return 0;
}

七、總結(jié)

通過面向?qū)ο蟮姆绞綄崿F(xiàn)單鏈表，我們可以更加方便和安全地進(jìn)行鏈表操作。封裝了節(jié)點管理、內(nèi)存管理以及鏈表操作函數(shù)的類，讓鏈表操作更加直觀并且容易維護(hù)。在實際開發(fā)中，鏈表結(jié)構(gòu)廣泛應(yīng)用于各種算法和數(shù)據(jù)管理系統(tǒng)，掌握鏈表的使用可以幫助我們高效地解決許多動態(tài)數(shù)據(jù)管理的問題。

以上就是使用C++實現(xiàn)單鏈表的操作與實踐的詳細(xì)內(nèi)容，更多關(guān)于C++實現(xiàn)單鏈表的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: