[数据结构与算法]数据结构【双向循环链表】

双向循环链表：

数据结构示意图1.1.1如下：

图1.1.1 链表节点结构示意图

让代码来讲话吧：

Structure.h

#ifndef DATA_STRUCTURE_DCNLIST_STRUCTURE_H
#define DATA_STRUCTURE_DCNLIST_STRUCTURE_H
#include <iostream>

using namespace std;
/*-------------------1.链表----------------------*/
#define Mark 0                     //宏定义链表Mark的起始值，更改此处会产生联动效果
#define HeadM pHead->mark = Mark   //设置链表头结点pHead的mark为0
// (1)单向链表：
// (2)单向循环链表：
typedef struct SCNode {
    int date;           //数据
    unsigned int mark;  //第mark个节点
    SCNode *pNext;      //节点尾指针
} SN,                   //单向
SCN;                    //单向循环
//二者数据结构相同
//=============================================//
// (3)双向链表：
// (4)双向循环链表：
typedef struct DCNode {
    int date;           //数据
    unsigned int mark;  //第mark个节点
    DCNode *pPrev;       //节点头指针
    DCNode *pNext;       //节点尾指针
} DN,                   //双向
DCN;                    //双向循环
//二者数据结构相同
/*-------------------1.链表----------------------*/
#endif //DATA_STRUCTURE_DCNLIST_STRUCTURE_H

Structure.cpp

//
// Created by Today me on 2021/7/13.
//

#include "Structure.h"
#include "Operation.h"

/*-------------------1.链表----------------------*/
// (3)双向链表：
//遍历整个链表，返回尾节点
DCN *FindTail(DCN *pHead) {
    DCN *pNTemp = pHead;
    while (pHead->pNext != pNTemp)pHead = pHead->pNext;
    return pHead;
}

//查找任意节点[调用此函数前，需确保List中mark的顺序性]
DCN *FindNode(DCN *pHead, int pos) {
    while (pos-Mark != pHead->mark) {
        pHead = pHead->pNext;
    }
    return pHead;
}

//规律化NODE[mark]
DCN *RegularMark(DCN *pHead) {
    DCN *pNTemp = pHead;
    int count = Mark;
    do {
        pHead->mark = count++;
    }while (pNTemp!= (pHead = pHead->pNext));
    return pNTemp;
}
/*-------------------1.链表----------------------*/

Operation.h

//
// Created by Today me on 2021/7/13.
//

#ifndef DATA_STRUCTURE_DCNLIST_OPERATION_H
#define DATA_STRUCTURE_DCNLIST_OPERATION_H

#include "Structure.h"
/*-------------------1.链表----------------------*/

// (1)单向链表：
//  a.创建链表：
//  b.插入节点：1.头插     2.尾插    3.中间插
//  c.删除节点：1.头删     2.尾删    3.中间删
//  d.打印链表：
// (2)单向循环链表：
//  a.创建链表：
//  b.插入节点：1.头插     2.尾插    3.中间插
//  c.删除节点：1.头删     2.尾删    3.中间删
//  d.打印链表：
//=============================================//
// (3)双向链表：
//  a.创建链表：
//  b.插入节点：1.头插     2.尾插    3.中间插
//  c.删除节点：1.头删     2.尾删    3.中间删
//  d.打印链表：

// (4)双向循环链表：
DCN *FindTail(DCN *pHead);                //遍历整个链表，返回尾节点
DCN *FindNode(DCN *pHead, int pos);       //查找任意节点[调用此函数前，需确保List中mark的顺序性]
DCN *RegularMark(DCN *pHead);             //规律化NODE[mark]
//  a.创建链表：
DCN *CreateHead();

//  b.插入节点：1.头插     2.尾插    3.中间插
DCN *InsertHead(DCN *pHead);              //1.头插
DCN *InsertTail(DCN *pHead);              //2.尾插
DCN *InsertMiddle(DCN *pHead, int pos);    //3.中间插

//  c.删除节点：1.头删     2.尾删    3.中间删
DCN *DeleteHead(DCN *pHead);              //1.头插
DCN *DeleteTail(DCN *pHead);              //2.尾插
DCN *DeleteMiddle(DCN *pHead, int pos);    //3.中间插

//  d.打印链表：先正序输出，后逆序输出链表[以pNext方向为正，pPrev方向为逆向]
unsigned int DisplayList(DCN *pHead);
/*-------------------1.链表----------------------*/
#endif //DATA_STRUCTURE_DCNLIST_OPERATION_H

Operation.cpp

//
// Created by Today me on 2021/7/13.
//

#include "Operation.h"
/*-------------------1.链表----------------------*/
// (1)单向链表：
//  a.创建链表：
//  b.插入节点：1.头插     2.尾插    3.中间插
//  c.删除节点：1.头删     2.尾删    3.中间删
//  d.打印链表：

// (2)单向循环链表：
//  a.创建链表：
//  b.插入节点：1.头插     2.尾插    3.中间插
//  c.删除节点：1.头删     2.尾删    3.中间删
//  d.打印链表：

// (3)双向链表：

/*在此注释中以pNext方向为向后；
 * 以pPrev方向为向前。
 * */

//  a.创建链表：
//  b.插入节点：1.头插     2.尾插    3.中间插
//  c.删除节点：1.头删     2.尾删    3.中间删
//  d.打印链表：

// (4)双向循环链表：

/*在此注释中以pNext方向为向后；
 * 以pPrev方向为向前。
 * */

//  a.创建链表：
DCN *CreateHead() {
    DCN *pHead = new DCNode();
    pHead->pNext = pHead;     //节点尾指向自己pHead[循环]
    pHead->pPrev = pHead;     //节点头指向自己pHead[循环]
    HeadM;                      //设置HeadMark
    cout << "Enter a value of the ListHead[" << pHead->mark << "]:" << endl;
    cin >> pHead->date;         //键入头结点存储数据
    return pHead;
}

//  b.插入节点：1.头插     2.尾插    3.中间插
DCN *InsertHead(DCN *pHead) {
    DCN *LTail = FindTail(pHead);
    int TpMark = pHead->mark;
    char ch = 'y';
    while ('y' == ch || 'Y' == ch) {
        DCN *newNode = new DCNode();
        //if (nullptr == newNode){perror("内存申请失败");exit(-1);}
        cout << "Enter a value of the node[" << ++TpMark << "]:" << endl;
        newNode->mark = TpMark;      //设置newNode的mark
        cin >> newNode->date;        //键入存储的值

        pHead->pPrev = newNode;      //[内部]使原链表头的pPrev指针指向newNode[将NewNode插入pHead前，链接好向前的结构]
        newNode->pNext = pHead;      //[内部]使NewNode的尾指针pNext指向pHead[将NewNode插入pHead前，链接好向后的结构]

        newNode->pPrev = LTail;      //[外部]使NewNode的pPrev指针指向链表尾节点LTail[LTail与NewNode通过pPrev链接，构成向前环结构]
        LTail->pNext = newNode;      //[外部]使链表尾节点LTail的尾指针pNext指向NewNode[LTail与NewNode通过pNext链接，构成向后环结构]
        pHead = newNode;             //将NewNode赋值给pHead[前移指针pHead,保证pHead始终指向链表头]

        cout << "Enter choice inserter(y/n):" << endl;
        cin >> ch;
    }
    //RegularMark(pHead);
    return pHead;
}

DCN *InsertTail(DCN *pHead) {
    DCN *LTail = pHead;
    char ch = 'Y';
    LTail = FindTail(LTail);       //调用FindTail找到尾节点指针，赋给LTail
    int TpMark = LTail->mark;      //记录尾节点Mark
    while (ch == 'y' || ch == 'Y') {
        DCN *newNode = new DCNode();
        //if (nullptr == newNode){perror("内存申请失败");exit(-1);}
        cout << "Enter a value of the node[" << ++TpMark << "]:" << endl;
        newNode->mark = TpMark;     //写入TpMark到newNode Mark中
        cin >> newNode->date;

        LTail->pNext = newNode;     //[内部]将尾节点LTail的pNext指针指向NewNode[链接NewNode到List尾部,链接好向后的结构]
        newNode->pPrev = LTail;     //[内部]将新节点newNode的pPrev指针指向LTail[链接NewNode到List尾部,链接好向前的结构]

        newNode->pNext = pHead;     //[外部]使NewNode的尾指针pNext指针指向链表头节点pHead[pHead与NewNode通过pHead的pPrev链接，构成向后环结构]
        pHead->pPrev = newNode;     //[外部]使链表头节点pHead的头指针pPrev指向NewNode[pHead与NewNode通过NewNode的pNext链接，构成向前环结构]
        LTail = newNode;            //将NewNode赋给LTail[使LTail始终指向尾节点]

        cout << "Enter choice inserter(y/n):" << endl;
        cin >> ch;
    }
    //RegularMark(pHead);
    return pHead;
}

DCN *InsertMiddle(DCN *pHead, int pos) {
    DCN *pNTemp01 = pHead, *pNTemp02 = nullptr;
    pos--;
    char ch = 'y';
    //int count = 0;
    RegularMark(pHead);
    pNTemp01 = FindNode(pNTemp01, pos);    // 找到插入节点的前一个节点pNTemp01
    pNTemp02 = pNTemp01->pNext;         // 找到应该插入的位置节点pNTemp02
    while (ch == 'y' || ch == 'Y') {
        DCN *newNode = new DCNode();
        //if (nullptr == newNode){perror("内存申请失败");exit(-1);}
        newNode->mark = pNTemp01->mark;
        newNode->mark++;
        cout << "Enter a value of the inserted node:" << endl;
        cin >> newNode->date;
        pNTemp01->pNext = newNode;      // 将前节点pNTemp01的pNext指针指向新节点newNode[链接NewNode到pNTemp01后,链接好向后的结构]
        newNode->pPrev = pNTemp01;      // 将新节点newNode的pPrev指针指向前节点pNTemp01[链接NewNode到pNTemp01后,链接好向前的结构]
        newNode->pNext = pNTemp02;      // 将pNTemp02赋给newNode->pNext[将pNTemp02链接在newNode后]
        pNTemp02->pPrev = newNode;      // 将newNode赋给pNTemp02->pPrev[将newNode链接在pNTemp02前]
        pNTemp01 = pNTemp01->pNext;     // 将pNTemp01后移一位指向newNode
        //while (nullptr != (pNTemp01 = pNTemp01->pNext))++pNTemp01->mark;
        cout << "Enter choice of inserter(y/n):" << endl;
        cin >> ch;
        //count++;
    }
    //while (nullptr != (pNTemp01 = pNTemp01->pNext))pNTemp01->mark += count;
    RegularMark(pHead);
    return pHead;
}

//  c.删除节点：1.头删     2.尾删    3.中间删
DCN *DeleteHead(DCN *pHead) {
    char ch = 'y';
    DCN *pNTemp = pHead, *LTail = pHead->pPrev;
    while ('y' == ch || 'Y' == ch) {
        pNTemp = pHead;         //暂存pHead
        pHead = pHead->pNext;   //将pHead指向下一个节点
        pHead->pPrev = LTail;   //链接头尾
        LTail->pNext = pHead;   //链接尾头
        cout << "Enter choice of deleting head node (y/n):" << endl;
        cin >> ch;
        if (pHead != LTail) {      //确保DisplayList函数正常调用
            DisplayList(pHead);
            delete pNTemp;         //释放内存
        } else {
            cout << "Can't remove the last node!" << endl;
            return pHead;
        }
    }
    //RegularMark(pHead);
    return pHead;
}

DCN *DeleteTail(DCN *pHead) {     //（1）不断循环寻找最后节点删除
    //（1）
    char ch = 'y';
    DCN *pNTemp = nullptr, *LTail = pHead->pPrev, *pNTemp01 = nullptr;
    RegularMark(pHead);
    while ('y' == ch || 'Y' == ch) {
        pNTemp01 = LTail->pPrev;            // 找到尾节点的前一个节点
        pNTemp = LTail;                     // 暂存尾节点
        pNTemp01->pNext = pHead;            // 使得原尾节点前一个节点变为尾节点[尾首相连]
        pHead->pPrev = pNTemp01;            // 使得原尾节点前一个节点变为尾节点[首尾相连]
        //delete pNTemp;                      // 释放原尾节点内存
        cout << "Enter choice of deleting tail node (y/n):" << endl;
        cin >> ch;
        if (pHead != LTail) {       //确保DisplayList函数正常调用
            DisplayList(pHead);
            LTail = LTail->pPrev;   //偏移LTail，始终指向最新的尾节点
            delete pNTemp;          //释放内存
        } else {
            cout << "Can't remove the last node!" << endl;
            return pHead;
        }
    }
    //RegularMark(pHead);
    return pHead;
}

DCN *DeleteMiddle(DCN *pHead, int pos) {
    DCN *pNTemp01 = pHead, *pNTemp02 = nullptr, *pNTemp03 = nullptr;
    pNTemp01 = FindNode(pNTemp01, pos - 2);     // 前节点指针
    pNTemp02 = pNTemp01->pNext;                      // 中结点指针
    pNTemp03 = pNTemp02->pNext;                      // 尾结点指针
    pNTemp01->pNext = pNTemp03;         // 前后链接
    pNTemp03->pPrev = pNTemp01;         // 后前连接
    delete pNTemp02;                    // 删除中间节点
    pNTemp02 = nullptr;                 // 避免pNTemp02野指针
    //RegularMark(pHead);
    return pHead;
}

//  d.打印链表：
unsigned int DisplayList(DCN *pHead) {
    DCN *LTail = FindTail(pHead), *pNTemp = pHead;
    unsigned int count = 0;
    cout << "Forward display list:" << endl;
    do {
        cout << "NODE[" << pHead->mark << "] = " << pHead->date << endl;\
        pHead = pHead->pNext;
        count++;
    } while (pHead != LTail->pNext);
    cout << "\nInverted display list:" << endl;
    do {
        cout << "NODE[" << LTail->mark << "] = " << LTail->date << endl;
        LTail = LTail->pPrev;
    } while (LTail != pNTemp->pPrev);
    return count;
}

main.cpp

#include "Structure.h"
#include "Operation.h"

int main() {
    DCN *pHead = nullptr;               //创建单向链表类型的头指针pHead,初始化为空指针nullptr
    pHead = CreateHead();               //创建头结点，pHead存储头结点的位置（存储头结点的位置）
//    pHead = InsertHead(pHead);        //调用头插
    pHead = InsertTail(pHead);        //调用尾插
//    pHead = InsertMiddle(pHead,2);    //调用中间插入
//    pHead = DeleteHead(pHead);        //调用头删
//    pHead = DeleteTail(pHead);        //调用尾删
    pHead = DeleteMiddle(pHead,2);    //调用中间删除[至少三个节点]

    unsigned int count = DisplayList(pHead);
    cout << "\nCount of list = " << count << "\nThe tail date of list = " << FindTail(pHead)->date << endl;
    if (pHead!= nullptr)delete pHead;       //释放pHead
    return 0;
}

测试结果如下图1.1.2：

图1.1.2 测试结果