如何使用C++代码实现双向链表

这篇文章主要介绍“如何使用C++代码实现双向链表”的相关知识，小编通过实际案例向大家展示操作过程，操作方法简单快捷，实用性强，希望这篇“如何使用C++代码实现双向链表”文章能帮助大家解决问题。

双向链表：两个指针域，一个指向前结点，一个指向后结点

list.h

#pragma once#define OK         1#define ERROR     0#define TRUE     1#define FALSE     0typedef 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

#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++代码实现双向链表”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识，可以关注编程网行业资讯频道，小编每天都会为大家更新不同的知识点。