查看: 162|回复: 0

[原创图文] C++双向链表

[复制链接]

34

主题

43

帖子

3

精华

解密专家

Rank: 16

学币
357
荣耀
0
rank
0
违规
0
发表于 2021-1-23 14:34:54 | 显示全部楼层 |阅读模式
本帖最后由 鸦领主 于 2021-1-24 15:58 编辑

“双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。”
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成员变量被修改了
}




温馨提示:
1.如果您喜欢这篇帖子,请给作者点赞评分,点赞会增加帖子的热度,评分会给作者加学币。(评分不会扣掉您的积分,系统每天都会重置您的评分额度)。
2.回复帖子不仅是对作者的最好奖励,还可以获得学币奖励,请尊重作者的劳动成果,拒绝做伸手党!
3.发广告、灌水回复等违规行为一经发现直接禁言,如果本帖内容涉嫌违规,请点击论坛底部的举报反馈按钮,也可以在【投诉建议】板块发帖举报。
学逆向论坛-免费的逆向学习论坛
微信扫一扫即可使用手机论坛
快速回复 返回顶部 返回列表