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

简介: 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;
}
相关文章
|
10天前
|
存储 C++ 容器
C++STL(标准模板库)处理学习应用案例
【4月更文挑战第8天】使用C++ STL,通过`std:vector`存储整数数组 `{5, 3, 1, 4, 2}`,然后利用`std::sort`进行排序,输出排序后序列:`std:vector<int> numbers; numbers = {5, 3, 1, 4, 2}; std:sort(numbers.begin(), numbers.end()); for (int number : numbers) { std::cout << number << " "; }`
17 2
|
21天前
|
编译器 C++
C++入门指南:10分钟带你快速了解模板究竟是什么(建议收藏!!)
C++入门指南:10分钟带你快速了解模板究竟是什么(建议收藏!!)
27 0
|
21天前
|
C++
【链表】还不会用C++实现链表?一文教会你各种链表的实现
【链表】还不会用C++实现链表?一文教会你各种链表的实现
|
24天前
|
安全 算法 编译器
【C++ 泛型编程 进阶篇】深入探究C++模板参数推导:从基础到高级
【C++ 泛型编程 进阶篇】深入探究C++模板参数推导:从基础到高级
240 3
|
20天前
|
存储 算法 C语言
线性表,双向链表,静态链表,循环链表(约瑟夫环)(上)
线性表,双向链表,静态链表,循环链表(约瑟夫环)
39 5
|
24天前
|
设计模式 程序员 C++
【C++ 泛型编程 高级篇】C++模板元编程:使用模板特化 灵活提取嵌套类型与多容器兼容性
【C++ 泛型编程 高级篇】C++模板元编程:使用模板特化 灵活提取嵌套类型与多容器兼容性
241 2
|
10天前
|
程序员 C++
C++语言模板学习应用案例
C++模板实现通用代码,以适应多种数据类型。示例展示了一个计算两数之和的模板函数`add&lt;T&gt;`,可处理整数和浮点数。在`main`函数中,展示了对`add`模板的调用,分别计算整数和浮点数的和,输出结果。
10 2
|
23天前
|
存储 程序员 编译器
【C++ 模板类与虚函数】解析C++中的多态与泛型
【C++ 模板类与虚函数】解析C++中的多态与泛型
46 0
|
23天前
|
存储 算法 C语言
【C/C++ 链表结构】探索链表迭代器:C++实现的深入分析与优化策略
【C/C++ 链表结构】探索链表迭代器:C++实现的深入分析与优化策略
36 0
|
23天前
|
算法 编译器 C++
【C++ 模板编程 基础知识】C++ 模板类部分特例化的参数顺序
【C++ 模板编程 基础知识】C++ 模板类部分特例化的参数顺序
21 0

热门文章

最新文章