快捷導航

C++實現(xiàn)一個封裝的雙鏈表的完整代碼

更新時間：2025年07月08日 10:47:17 作者：平凡程序猿~

雙鏈表是鏈表的一種變種,除了每個節(jié)點指向下一個節(jié)點外,還多了一個指向前一個節(jié)點的指針,由于雙鏈表可以從兩端進行遍歷,它的插入和刪除操作更為靈活,本文將詳細介紹如何使用 C++ 語言實現(xiàn)一個封裝的雙鏈表類,需要的朋友可以參考下

一、雙鏈表的基本概念

雙鏈表是一種由一組節(jié)點構(gòu)成的線性數(shù)據(jù)結(jié)構(gòu)，其中每個節(jié)點包含三部分：

數(shù)據(jù)域：存儲節(jié)點的數(shù)據(jù)。
前驅(qū)指針：指向前一個節(jié)點。
后繼指針：指向下一個節(jié)點。

與單鏈表相比，雙鏈表中的每個節(jié)點有兩個指針，可以雙向遍歷，方便插入和刪除操作。

在 C++ 中，我們通過類的封裝特性來實現(xiàn)雙鏈表，利用指針來動態(tài)管理節(jié)點的內(nèi)存空間，保證數(shù)據(jù)的靈活性和高效性。

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

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

1. 雙鏈表類的成員變量

我們定義了一個 DList 類，包含以下成員變量：

phead：指向雙鏈表頭節(jié)點的指針。

2. 構(gòu)造函數(shù)和析構(gòu)函數(shù)

雙鏈表類的構(gòu)造函數(shù)負責初始化成員變量，析構(gòu)函數(shù)負責釋放動態(tài)分配的內(nèi)存。

#include<iostream>
using namespace std;

// 節(jié)點類型聲明
struct Node
{
    int date;
    Node* last;  // 前驅(qū)節(jié)點
    Node* next;  // 后繼節(jié)點
};

class DList
{
private:
    // 成員變量
    Node* phead;

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

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

    // 創(chuàng)建節(jié)點
    Node* CreateNode(int x)
    {
        Node* node = new Node;
        node->date = x;
        node->last = NULL;
        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);
        if (phead == NULL)
        {
            phead = newnode;
        }
        else
        {
            newnode->next = phead;
            phead->last = newnode;
            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;
            newnode->last = tail;
        }
    }

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

    // 尾刪法
    void PopBack()
    {
        if (phead == NULL)
        {
            cout << "鏈表為空，無法進行刪除操作！" << endl;
        }
        else
        {
            if (phead->next == NULL)  // 只有一個節(jié)點
            {
                delete phead;
                phead = NULL;
            }
            else
            {
                Node* tail = phead;
                while (tail->next != NULL)
                {
                    tail = tail->next;
                }
                tail->last->next = NULL;
                delete tail;
                tail = NULL;
            }
        }
    }
     //指定元素后插入
    void InsertAfter(int v, int x)
    {
        Node* node = phead;
        while (node != NULL && node->date != v)
        {
            node = node->next;
        }

        if (node == NULL)
        {
            cout << "未找到值為 " << v << " 的節(jié)點，無法插入!" << endl;
            return;
        }

        Node* newnode = CreateNode(x);
        newnode->last = node;
        newnode->next = node->next;

        if (node->next != NULL)
        {
            node->next->last = newnode;
        }

        node->next = newnode;
    }

    // 根據(jù)值刪除節(jié)點
    void PopValue(int value)
    {
        if (phead == NULL)
        {
            cout << "鏈表為空，無法進行刪除操作！" << endl;
            return;
        }
        Node* cur = phead;
        while (cur != NULL)
        {
            if (cur->date == value)
            {
                // 刪除節(jié)點
                if (cur->last != NULL)
                {
                    cur->last->next = cur->next;
                }
                else
                {
                    // 刪除的是頭節(jié)點
                    phead = cur->next;
                }

                if (cur->next != NULL)
                {
                    cur->next->last = cur->last;
                }
                delete cur;
                cur = NULL;
                cout << "刪除節(jié)點 " << value << " 成功！" << endl;
                return;
            }
            cur = cur->next;
        }
        cout << "未找到值為 " << value << " 的節(jié)點！" << endl;
    }
};

int main()
{
    DList 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();

    ls1.InsertAfter(9,7);
    ls1.PrintList();

    ls1.PopValue(4);
    ls1.PrintList();
    return 0;
}

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

PushFront：在鏈表的頭部插入新元素。
PushBack：在鏈表的尾部插入新元素。
PopFront：刪除鏈表的頭元素。
PopBack：刪除鏈表的尾元素。
InsertAfter：在指定節(jié)點之后插入新節(jié)點。
PopValue：根據(jù)節(jié)點值刪除該節(jié)點。

四、總結(jié)

通過面向?qū)ο蟮姆绞綄崿F(xiàn)雙鏈表，我們能夠更加方便和安全地進行雙鏈表操作。封裝了內(nèi)存管理、節(jié)點操作等的類，使得雙鏈表的使用更加直觀并且易于維護。雙鏈表的優(yōu)勢在于其靈活的插入和刪除操作，特別適合需要頻繁變更數(shù)據(jù)結(jié)構(gòu)的場景。

以上就是C++實現(xiàn)一個封裝的雙鏈表的完整代碼的詳細內(nèi)容，更多關(guān)于C++封裝的雙鏈表的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: