C++学习笔记_13 双向链表和链表模板 2021-05-06

// C++学习笔记_13 双向链表和链表模板
#include<cstdio> 
#include<iostream>
using namespace std;
class AAA
{
private:
    int x;
    int y;
public:
    AAA() :x(0), y(0) {}
    AAA(int a, int b) :x(a), y(b){}
    friend ostream&  operator << (ostream &os, const AAA &A)
    {
        os << "(" << A.x << ", " << A.y << ")";
        return os;
    }
};
template <typename T>
class CDbList
{
private:
    class Node
    {
    public:
        T data;
        Node *pNext;
        Node *pPrev;
        Node(T t_data) :data(t_data), pNext(NULL), pPrev(NULL){}
    };
    //头结点和尾节点都不放数据
    Node *pHead; //链表的头结点
    Node *pTail; //链表的尾节点
    size_t  iSize; //链表中节点个数 
public:
    CDbList() :iSize(0), pHead(new Node(T())), pTail(new Node(T()))
    {
        //连接头尾节点，构成一个中间无数据节点的双向链表
        pHead->pNext = pTail;
        pTail->pPrev = pHead;
    }
    ~CDbList()
    {
        clear();
        delete pHead;
        delete pTail;
    }
    size_t size(){return iSize;}
    //增删查
    int insert(size_t pos, T data);
    int erase(size_t pos);
    T& getValue(size_t pos);
    //清除所有节点数据，释放资源 (保留头尾节点)
    void clear();
    void reverse();
    void Print()
    {
        Node *pNode = pHead->pNext;
        while (pNode != pTail)
        {
            cout << pNode->data << " ";
            pNode = pNode->pNext;
        }
        cout << endl;
    }
    void rPrint()
    {
        Node *pNode = pTail->pPrev;
        while (pNode != pHead)
        {
            cout << pNode->data << " ";
            pNode = pNode->pPrev;
        }
        cout << endl;
        return;
    }
};
template <typename T>
int CDbList<T>::insert(size_t pos, T data)
{
    //pos 从 0 还是编号
    if (pos > iSize){return -1; }//越界
    Node *pNewNode = new Node(data);
    //寻找待插入位置的前一个节点
    int i = 0;
    Node *pNode = pHead;
    while (i < pos){
        pNode = pNode->pNext;i++;
    }
    //考虑一个问题，如果 iSize = 100000，十万个节点了
    //我们想在 99000 个节点位置增加一个节点， 这个查找方式能不能更快一点？
    //---> 从 pTail 位置往前找 
    //  -->if(pos < iSize/2) {从前往后找} else {从后往前找}
    //pNewNode 插入到 pNode 之后
    //顺序从 pNode --- pTmpNode 变为  pNode --- pNewNode --- pTmpNode
    //1：把 pNode 后面那个节点 pTmpNode ，(pPrev)连接到 pNewNode (防止断链)
    (pNode->pNext)->pPrev = pNewNode; //给下一个节点的pPrev赋值
    //2：把 pNewNode 的 pNext 赋值为 pTmpNode
    pNewNode->pNext = pNode->pNext;
    //3：把 pNewNode 的 pPrev 赋值为 pNode
    pNewNode->pPrev = pNode;
    //4：把 pNode 的 pNext 指向 pNewNode
    pNode->pNext = pNewNode;
    iSize++;
    return 0;
}
template <typename T>
int CDbList<T>::erase(size_t pos)
{
    //pos 从 0 还是编号
    if (pos > iSize-1){return -1; }//越界
    //寻找待删除节点的前一个节点
    int i = 0;
    Node *pNode = pHead;
    while (i < pos){
        pNode = pNode->pNext;i++;
    }
    //pNode 是待删除节点的上一个节点
    //第一步，保存待删除节点   ---》 释放内存
    Node *pDelNode = pNode->pNext;
    //第二步，连接待删除节点的前后节点(连接 pDelNode->pNext 这个节点和 pNode 节点)
    (pDelNode->pNext)->pPrev = pNode;
    pNode->pNext = (pDelNode->pNext);
    //第三步，释放内存
    delete pDelNode;
    iSize--;
    return 0;
}
template <typename T>
T& CDbList<T>::getValue(size_t pos)
{
    if (pos > iSize - 1){
        //越界，不处理：已经提供了 size 函数给使用者判断是否越界
        //      这里由用户来保存程序不越界
    }
    //寻找节点位置
    int i = 0;
    Node *pNode = pHead->pNext; // 从第 0 个节点开始往后找
    while (i < pos){
        pNode = pNode->pNext;
        i++;
    }
    return pNode->data;
}
template <typename T>
void CDbList<T>::clear()
{
    if (iSize == 0){return; }
    Node *pDelNode = pHead->pNext; //删除所有节点，保留 pHead 和 pTail
    while (pDelNode != pTail){
        //删除节点前，需要保存这个节点的下一个节点
        pHead->pNext = pDelNode->pNext;
        delete pDelNode;
        pDelNode = pHead->pNext;//取出下一个要删除的节点
    }
    pTail->pPrev = pHead; //最后，链表的 pTail->pPrev 要指向 pHead
    iSize = 0;
    return;
}
template <typename T>
void CDbList<T>::reverse()
{
    if (iSize < 2){return;}
    Node *pNode = pTail; 
    Node *pNextNode = pHead->pNext; //第0个节点
    while (pNextNode != pTail) {
       pHead->pNext = pNextNode->pNext;//保存下一个节点
        //依次连接 尾节点和第0个节点，第0个和第一个节点，第一个和第二个......
        pNextNode->pNext=pNode;//最后连接 最后一个节点和pHead 
        pNode->pPrev = pNextNode;
        //替换，进入下一轮节点的连接 
        pNode=pNextNode;
        pNextNode=pHead->pNext;//这个在上面暂存了一下待连接的节点 
    }
    //pNextNode到了pTail位置后，把pNode节点和pHead连接起来 
    pNode->pPrev=pHead;
    pHead->pNext=pNode;
    return;
}
void Test_Dblist()
{
    CDbList<int>  iList;
    CDbList<AAA>  aList;
    int iArr[] = { 1, 3, 5, 7, 9, 11 };
    AAA aArr[] = { AAA(), AAA(1, 0), AAA(1, 1), AAA(2, 1), AAA(2, 2) };
    for (int i = 0; i < sizeof(iArr) / sizeof(iArr[0]); i++)
        iList.insert(i, iArr[i]);
    for (int i = 0; i < sizeof(aArr) / sizeof(aArr[0]); i++)
        aList.insert(i, aArr[i]);
    iList.insert(2, 99);
    aList.insert(2, AAA(3, 3));
    iList.erase(3);
    aList.erase(3);
    cout << "iList:";
    iList.Print();
    cout << "aList:";
    aList.Print();
    cout << endl;
    cout << "Reverse Print:" << endl;
    cout << "iList:";
    iList.rPrint();
    cout << "aList:";
    aList.rPrint();
    cout << endl;
    cout << iList.getValue(0) << endl; //获取某个元素的值
    iList.getValue(0) = 88; //修改某个元素的值
    iList.Print();
    iList.reverse();
    iList.Print();
    cout << "逆向输出:";
    iList.rPrint();
}
int main()
{
    Test_Dblist();
  return 0;
}