C++程式碼實現雙向連結串列

#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);                            //銷燬雙連結串列,需要釋放頭結點

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

/* 雙向連結串列：帶頭結點，且頭結點的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;
}