如何使用C++代碼實(shí)現(xiàn)雙向鏈表

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

雙向鏈表：兩個(gè)指針域，一個(gè)指向前結(jié)點(diǎn)，一個(gè)指向后結(jié)點(diǎn)

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;        //前結(jié)點(diǎn)指針域
    ElemType data;                //數(shù)據(jù)域
    struct DNode *next;            //后結(jié)點(diǎn)指針域
}DNode, *DLinkList;                //結(jié)點(diǎn)和指向結(jié)點(diǎn)的指針

bool InitDLinkList(DLinkList &L);                        //雙鏈表初始化
Status CreatDLinkList(DLinkList &L);                    //尾插法創(chuàng)建鏈表，包含初始化功能
bool InsertNextDNode(DNode *p, DNode *s);                //結(jié)點(diǎn)s插入在結(jié)點(diǎn)p之后
Status DeleteNextDNode(DNode *p, ElemType &e);            //刪除結(jié)點(diǎn)p的后繼節(jié)點(diǎn)                
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);                        //查找鏈表指定位置節(jié)點(diǎn)，返回的是結(jié)點(diǎn)
void DestoryList(DLinkList &L);                            //銷毀雙鏈表,需要釋放頭結(jié)點(diǎn)

oper_func.cpp

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

bool InitDLinkList(DLinkList &L)
{
    //構(gòu)建空的雙鏈表，作為雙鏈表的頭結(jié)點(diǎn)，數(shù)據(jù)域?yàn)榭?
    L = new DNode;
    if (L == NULL)                //內(nèi)存分配失敗
        return FALSE;
    L->prior = NULL;            //頭結(jié)點(diǎn)的前驅(qū)指針始終指向NULL    
    L->next = NULL;                //暫時(shí)指向NULL
    return TRUE;
}

Status CreatDLinkList(DLinkList &L)
{
    //利用InsertNextDNode函數(shù)來創(chuàng)建

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

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

Status DeleteNextDNode(DNode *p, ElemType &e)
{
    if(p == NULL)
        return FALSE;            //非法參數(shù)
    DNode *q = p->next;            //找到p節(jié)點(diǎn)的后繼節(jié)點(diǎn)
    if (q == NULL)                //節(jié)點(diǎn)p沒有后繼節(jié)點(diǎn)
    {
        return ERROR;
    }
    else
    {
        //有后繼節(jié)點(diǎn)，但是p的后繼節(jié)點(diǎn)為空
        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;                    //指向第一個(gè)元素
    if (p == NULL)
    {
        cout << "雙鏈表為空，無法輸出元素！" << endl;
        return;
    }
    while (p)
    {
        cout << "第" << i++ << "個(gè)元素為：" << p->data << endl;
        p = p->next;
    }
}

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

DNode* GetElem(DLinkList L, int i)
{
    DNode *p = L;
    int j = 0;                //表示p指向的當(dāng)前結(jié)點(diǎn)的位置，此時(shí)為頭結(jié)點(diǎn)
    while (p != NULL && j < i)
    {
        p = p->next;        //指向下一個(gè)結(jié)點(diǎn)
        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++ << "個(gè)刪除的元素為：" << temp << endl;
    }
    cout << "雙鏈表全部數(shù)據(jù)銷毀成功！" << endl;
    delete L;
    cout << "頭結(jié)點(diǎn)銷毀，整個(gè)雙鏈表銷毀成功！" << endl;
    L = NULL;                //頭指針指向NULL
}

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

main.cpp

/* 雙向鏈表：帶頭結(jié)點(diǎn)，且頭結(jié)點(diǎn)的prior指針時(shí)鐘指向?yàn)镹ULL

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

*/

#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))        //尾插法創(chuàng)建單鏈表
    {
        cout << "雙鏈表創(chuàng)建成功！" << endl;
    }
    else
        cout << "雙鏈表創(chuàng)建失?。?quot; << 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 << "內(nèi)存分配失敗或者插入位置越界，插入失??！" << endl;
        }
                break;
        case 2: {        //刪除指定位置節(jié)點(diǎn)
            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;
}

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