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;
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。