如何使用C++代碼實現雙向鏈表

這篇文章主要介紹“如何使用C++代碼實現雙向鏈表”的相關知識，小編通過實際案例向大家展示操作過程，操作方法簡單快捷，實用性強，希望這篇“如何使用C++代碼實現雙向鏈表”文章能幫助大家解決問題。

雙向鏈表：兩個指針域，一個指向前結點，一個指向后結點

list.h

#pragma once
#define OK         1
#define ERROR     0
#define TRUE     1
#define FALSE     0

typedef int Status;
typedef int ElemType;

typedef struct DNode
{
    struct DNode *prior;        //前結點指針域
    ElemType data;                //數據域
    struct DNode *next;            //后結點指針域
}DNode, *DLinkList;                //結點和指向結點的指針

bool InitDLinkList(DLinkList &L);                        //雙鏈表初始化
Status CreatDLinkList(DLinkList &L);                    //尾插法創建鏈表，包含初始化功能
bool InsertNextDNode(DNode *p, DNode *s);                //結點s插入在結點p之后
Status DeleteNextDNode(DNode *p, ElemType &e);            //刪除結點p的后繼節點                
void ListTraverse(const DLinkList L);                    //雙鏈表的遍歷
Status ListInsert(DLinkList &L, int i, ElemType e);        //指定位置插入元素
Status ListDelete(DLinkList &L, int i, ElemType &e);    //指定位置刪除元素
DNode* GetElem(DLinkList L, int i);                        //查找鏈表指定位置節點，返回的是結點
void DestoryList(DLinkList &L);                            //銷毀雙鏈表,需要釋放頭結點

oper_func.cpp

#include <iostream>
#include"list.h"

bool InitDLinkList(DLinkList &L)
{
    //構建空的雙鏈表，作為雙鏈表的頭結點，數據域為空
    L = new DNode;
    if (L == NULL)                //內存分配失敗
        return FALSE;
    L->prior = NULL;            //頭結點的前驅指針始終指向NULL    
    L->next = NULL;                //暫時指向NULL
    return TRUE;
}

Status CreatDLinkList(DLinkList &L)
{
    //利用InsertNextDNode函數來創建

    using std::cin;
    using std::cout;
    using std::endl;
    if (InitDLinkList(L))
    {
        DNode *s,*r = L;                //s為新建的新結點，用來存儲數據，而r為尾指針，始終指向尾部節點
        int num;
        cout << "輸入你需要創建的雙鏈表的個數：";
        cin >> num;
        for (int i = 1; i <= num; i++)
        {
            s = new DNode;                //創建的新結點
            cout << "輸入第" << i << "個元素：";
            cin >> s->data;                //輸入數據
            s->next = NULL;
            InsertNextDNode(r,s);        //結點s插在尾部節點之后
            r = s;                        //尾指針指向新的尾結點
        }
        return OK;
    }
    else
    {
        cout << "內存不夠，單鏈表創建失敗！" << endl;
        return ERROR;
    }
}

//結點s插入在結點p之后
bool InsertNextDNode(DNode *p, DNode *s)
{
    if (p == NULL || s == NULL)
        return FALSE;            //非法參數
    s->next = p->next;
    if (p->next != NULL)        //如果p不是最后一個結點
    {
        p->next->prior = s;
    }
    s->prior = p;
    p->next = s;
    return TRUE;
}

Status DeleteNextDNode(DNode *p, ElemType &e)
{
    if(p == NULL)
        return FALSE;            //非法參數
    DNode *q = p->next;            //找到p節點的后繼節點
    if (q == NULL)                //節點p沒有后繼節點
    {
        return ERROR;
    }
    else
    {
        //有后繼節點，但是p的后繼節點為空
        p->next = q->next;
        e = q->data;
        if (q->next != NULL)
        {
            q->next->prior = p;
        }
        delete q;
        return OK;
    }
}

void ListTraverse(const DLinkList L)
{
    using std::cout;
    using std::endl;
    int i = 1;
    DNode *p = L->next;                    //指向第一個元素
    if (p == NULL)
    {
        cout << "雙鏈表為空，無法輸出元素！" << endl;
        return;
    }
    while (p)
    {
        cout << "第" << i++ << "個元素為：" << p->data << endl;
        p = p->next;
    }
}

Status ListDelete(DLinkList &L, int i, ElemType &e)
{
    if (i < 1)                 //位置不合理
        return ERROR;
    //尋找第i-1個結點
    DNode *p = GetElem(L, i - 1);
    //刪除i-1結點的后面結點
    return DeleteNextDNode(p,e);
}

DNode* GetElem(DLinkList L, int i)
{
    DNode *p = L;
    int j = 0;                //表示p指向的當前結點的位置，此時為頭結點
    while (p != NULL && j < i)
    {
        p = p->next;        //指向下一個結點
        j++;
    }
    return p;
}

void DestoryList(DLinkList &L)
{
    using std::cout;
    using std::endl;
    ElemType temp;
    int i = 1;
    while (L->next != NULL)
    {
        DeleteNextDNode(L,temp);
        cout << "第" << i++ << "個刪除的元素為：" << temp << endl;
    }
    cout << "雙鏈表全部數據銷毀成功！" << endl;
    delete L;
    cout << "頭結點銷毀，整個雙鏈表銷毀成功！" << endl;
    L = NULL;                //頭指針指向NULL
}

Status ListInsert(DLinkList &L, int i, ElemType e)
{
    if (i < 1)
        return FALSE;
    //尋找第i-1個結點
    DNode *p = GetElem(L, i - 1);
    //直接在i-1結點的后面插入元素即可
    DNode *s = new DNode;        //新建節點
    s->data = e;
    s->next = NULL;
    s->prior = NULL;
    return InsertNextDNode(p,s);
}

main.cpp

/* 雙向鏈表：帶頭結點，且頭結點的prior指針時鐘指向為NULL

1、雙鏈表的初始化
2、雙鏈表的創建
3、雙鏈表的結點插入（相當于后插操作）：（結點s插入結點p之后）需要考慮p結點是不是最后一個結點
    如果想前插操作，則找到該節點的i-1節點，然后實行后插操作也是一樣
4、雙鏈表的結點刪除（相當于后刪操作）：（刪除p節點的后序節點q）需要考慮p結點是不是最后一個結點
    也要考慮q節點是不是最后一個結點
5、雙鏈表的刪除：
6、雙鏈表的遍歷：
7、雙鏈表的銷毀：需要回收頭結點

*/

#include <iostream>
#include"list.h"

void showMenu()
{
    using std::cout;
    using std::cin;
    using std::endl;
    cout << "*********************************************************" << endl;
    cout << "*** 1.指定位置插入元素            2.刪除指定位置元素 ***" << endl;
    cout << "*** 3.遍歷單鏈表            0.銷毀雙鏈表并退出 ***" << endl;
    cout << "*********************************************************" << endl;
}

int main()
{
    using std::cout;
    using std::cin;
    using std::endl;
    int select = 0, flag = -1;            //輸入的選擇

    DLinkList L;                //L表示頭指針，始終指向表頭

    if (CreatDLinkList(L))        //尾插法創建單鏈表
    {
        cout << "雙鏈表創建成功！" << endl;
    }
    else
        cout << "雙鏈表創建失敗！" << endl;

    while (true)
    {
        showMenu();
        cout << "輸入你的選擇：";
        cin >> select;
        switch (select)
        {
        case 1: {        //指定位置插入元素
            int position = 0, elem = 0;
            cout << "輸入插入的位置和元素:";
            cin >> position >> elem;
            if (ListInsert(L, position, elem))
                cout << "指定位置插入元素成功！" << endl;
            else
                cout << "內存分配失敗或者插入位置越界，插入失敗！" << endl;
        }
                break;
        case 2: {        //刪除指定位置節點
            int position = 0, elem = 0;
            cout << "輸入指定位置:";
            cin >> position;
            if (ListDelete(L, position, elem))
            {
                cout << "刪除指定位置元素成功！元素為：" << elem << endl;
            }
            else
            {
                cout << "單鏈表為空或者刪除位置不合理！" << endl;
            }
        }
                break;
        case 3: {
            ListTraverse(L);
        }
                break;
        case 0: {
            DestoryList(L);
            system("pause");
            return 0;
        }
        break;
        }
    }
    return 0;
}

關于“如何使用C++代碼實現雙向鏈表”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識，可以關注億速云行業資訊頻道，小編每天都會為大家更新不同的知識點。