C++双向链表

鸦领主

“双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。”
CList.h文件

#pragma once
typedef int Data;
struct SNode
{
    Data data;
    SNode* pPrev,* pNext;//前驱，后继
};
typedef void* POSITION;
class CList
{
    SNode* m_pHead, * m_pTail;//头节点，尾节点
    int m_count; //计数
public:
    CList()
    {
        m_pHead = m_pTail=0;//头节点，尾节点
        m_count=0; //计数
    }
    ~CList()
    {
        RemoveAll();
    }
    //单行函数可放如类里面，会直接转换成内联
    POSITION GetHeadPosition()//void* GetHeadPosition()
    {//获取头节点
        return m_pHead;
    }
    POSITION GetTailPosition()//void* GetHeadPosition()
    {//获取尾节点
        return m_pHead;
    }
    Data GetCount()//intGetCount()
    {//获取有多少节点
        return m_count;
    }
    Data GetAt(POSITION p)//int GetAt(POSITION p)
    {//或者当前节点的内容（注:POSITION是void*类型的,接收任何类型）
        return ((SNode*)p)->data;//但是使用要转换一下
    }

    void RemoveAll();

    Data GetNext(POSITION& p);
    Data GetPrev(POSITION& p);
    void AddHead(Data data);
    void AddTail(Data data);
    void RemoveAt(POSITION p);
    void SetAt(POSITION p, Data data);
};

CList.cpp文件

#include "CList.h"

void CList::RemoveAll()
{//删除所有节点，释放堆空间
    SNode* p = m_pHead,*p1;
    while (p)
    {
        p1 = p;
        p = p->pNext;
        delete p1;
    }
}


Data CList::GetNext(POSITION& p)//int CList::GetNext(void*& p)
{
    Data d = ((SNode*)p)->data;//获取当前节点的内容
    SNode* p1 = ((SNode*)p)->pNext;//获取当前节点的下一个节点
    p = p1;//将当前节点等于下一个节点
    return d;
}


Data CList::GetPrev(POSITION& p)//int CList::GetpPrev(void*& p)
{
    Data d = ((SNode*)p)->data;//获取当前节点的内容
    SNode* p1 = ((SNode*)p)->pPrev;//获取当前节点的上一个节点
    return d;//将当前节点等于上一个节点
}


void CList::AddHead(Data data)//从头插入
{
    SNode* p = new SNode;
    p->data = data;
    if (m_pHead)//头节点不是空
        m_pHead->pPrev = p;//将头节点的上一个节点等于现在的节点
    else
        m_pTail = p;//是空的话就将尾巴节点连接到现在的节点
    p->pNext = m_pHead;//现在的节点的下一个节点是头节点
    p->pPrev = 0;//上一个节点是0
    m_pHead = p;//将p赋值给头节点
}


void CList::AddTail(Data data)//从尾插入
{
    SNode* p = new SNode;
    p->data = data;
    if (m_pTail)
        m_pTail->pNext = p;
    else
        m_pHead = p;
    p->pNext = 0;
    p->pPrev = m_pTail;
    m_pTail = p;
}


void CList::RemoveAt(POSITION p)
{
    SNode* p1 = (SNode*)p;//①如果p是头节点       ②如果p是节点    ③如果p是中间的节点    
    if (p == m_pHead)//②不执行   ③不执行
        m_pHead = p1->pNext;//①将头节点指向p1的下一个节点
    else
        p1->pPrev->pNext = p1->pNext;//②p1上一个节点的下一节点(p1自己)赋值为p1的下一个节点(下一个节点是空)    ③执行
     if (p == m_pTail)//①不执行   ③不执行
        m_pTail = p1->pPrev;//②将尾节点指向p1的上一个节点
    else
        p1->pNext->pPrev = p1->pPrev;//①p1下一个节点的上一节点(p1自己)赋值为p1的上一个节点(上一个节点是空）   ③执行  
    delete p1;
    --m_count;//计数
}


void CList::SetAt(POSITION p, Data data)//void CList::SetAt(void* p, int data)
{
    ((SNode*)p)->data = data;//将输入进来的替换掉
}

//这几个函数的实现方法

CList：： AddHead                 将一个元素(或另一个列表中的所有元素) 添加到列表的开头(会成为新的 head) 。
CList：： AddTail                 将一个元素(或另一个列表中的所有元素) 添加到列表的尾部(会生成新的尾部) 。
CList：： GetAt                        获取给定位置处的元素。
CList：： GetCount                  返回此列表中的元素数。
CList：： GetHeadPosition         返回列表头元素的位置。
CList：： GetTailPosition         返回列表的尾元素的位置。
CList：： SetAt                     修改指定数据的内容
CList：： GetNext                 获取用于循环访问的下一个元素。
CList：： GetPrev                 获取用于循环访问的上一个元素
CList：： RemoveAt                 从此列表中移除按位置指定的元素。
CList：： RemoveAll                 从此列表中移除所有元素。

成员函数后面加上const的意思

    Data GetAt(POSITION p) const //后面加上const表示这个是只读的，不能修改成员变量
    {
        return ((SNode*)p)->data;
    }

void CList::AddTail(Data data)//这里加上const就是错误的了
{
    SNode* p = new SNode;
    p->data = data;
    if (m_pTail)
        m_pTail->pNext = p;
    else
        m_pHead = p;// m_pHead成员变量被修改了
    p->pNext = 0;
    p->pPrev = m_pTail;
    m_pTail = p;// m_pTail成员变量被修改了
}