41_链表

作用

    1. 元素不是连续存放的
    2. 解决方式:知道前后位置存放的位置
    3. 链式存储:插入和删除快,也叫链表

List

单向链表(早期内存不够的情况下)

    1. 前面放数据,后面放后继,用结构体取名为节点,没有前驱
    2. 头节点,存放链表的起始位置,如果不存放头指针,每次插入删除需要判断头节点与尾节点。效率更高
    3. 带头尾单链表 Head data1 next data2 next data3 next data4 next tail
    4. 不带头尾单链表 data1 next data2 next data3 next null(标记结束)

静态链表

    1. 有头尾节点,有前驱后继,使用动态数组存储

循环链表

    1. 有头尾节点,有前驱后继,尾节点存放头节点位置
    2. 好处:任何链表节点位置都可以遍历

双向链表(最常用)

    1. 有头尾节点,有前驱后继,数据放中间
    2. 好处,很容易知道上下节点

双向循环链表

    1. 有头尾节点,有前驱后继,数据放中间,尾节点存放头节点位置

应用

记事本

作业

1.实现循环链表类

 //Integer.h
#pragma once
class Integer
{
public:
    Integer(int n = 0);
    ~Integer();
    const int getValue() const;
private:
    int *m_pInt;
};
 //Integer.cpp
#include "Integer.h"


Integer::Integer(int n)
{
    m_pInt = new int(n);
}

Integer::~Integer()
{
    delete m_pInt;
}

const int Integer::getValue() const
{
    return *m_pInt;
}
 //LinkList.h
#pragma once
#include "Integer.h"
#include 
#include 

class LinkNode //双向链表结点
{
public:
    LinkNode(int element, LinkNode *previousNode = nullptr, LinkNode *nextNode = nullptr);
    ~LinkNode();
public:
    Integer *m_pElement;
    LinkNode *m_pPreviousNode;
    LinkNode *m_pNextNode;
};

class CLinkList //双向链表类
{
public:
    CLinkList();
    CLinkList(int element);
    CLinkList(const CLinkList& obj);
    ~CLinkList();
    void test();                                                //显示测试
    const unsigned getSize() const;                             //获取链表大写
    LinkNode* push_back(const int& element);                    //尾结点增加元素
    LinkNode* push_front(const int& element);                   //头节点增加元素
    LinkNode* insert(LinkNode* pos, const int& element);        //指定结点前增加元素
    const bool empty() const;                                   //是否空链表
    void clear();                                               //清空表
    void erese(LinkNode* pos);                                  //删除指定位置的元素
    void pop_back();                                            //删除最后一个元素
    void pop_front();                                           //删除第一个元素
    Integer& back();                                            //获得最后一个元素
    Integer& front();                                           //获得最第一个元素
    CLinkList& operator= (const CLinkList& list);               //拷贝链表
    void operator+= (const CLinkList& list);

private:
    void setSize(const unsigned size);                                     //设置大小
private:
    unsigned m_uSize;       //链表大小
    LinkNode *m_pHeadNode;  //头结点
    LinkNode *m_pTailNode;  //尾结点
};

LinkNode::LinkNode(int element, LinkNode *previousNode, LinkNode *nextNode)
{
    m_pElement = new Integer(element);
    m_pPreviousNode = previousNode;
    m_pNextNode = nextNode;
}

CLinkList::CLinkList()
{
    //创建结点
    m_pHeadNode = new LinkNode(0);    //头结点
    m_pTailNode = new LinkNode(0);    //尾结点
    //设置头结点
    m_pHeadNode->m_pNextNode = m_pTailNode;
    //设置尾结点
    m_pTailNode->m_pPreviousNode = m_pHeadNode;
    //大小为一
    setSize(0U);
}

CLinkList::CLinkList(int element)
{
    //创建结点
    LinkNode *pNewNode = new LinkNode(element); //创建的新结点
    m_pHeadNode = new LinkNode(0);    //头结点
    m_pTailNode = new LinkNode(0);    //尾结点
    //设置头结点
    m_pHeadNode->m_pNextNode = pNewNode;
    //设置新结点
    pNewNode->m_pPreviousNode = m_pHeadNode;
    pNewNode->m_pNextNode = m_pTailNode;
    //设置尾结点
    m_pTailNode->m_pPreviousNode = pNewNode;
    //大小为一
    setSize(1U);
}

CLinkList::CLinkList(const CLinkList& obj)
{
    m_pHeadNode = new LinkNode(0);    //头结点
    m_pTailNode = new LinkNode(0);    //尾结点
    m_pHeadNode->m_pNextNode = m_pTailNode; //设置头结点
    m_pTailNode->m_pPreviousNode = m_pHeadNode; //设置尾结点
    //拷贝的链表非空链表
    if (!obj.empty())
    {
        LinkNode *pNode = obj.m_pHeadNode->m_pNextNode;
        while (pNode->m_pNextNode != nullptr)
        {
            push_back((pNode->m_pElement->getValue()));
            pNode = pNode->m_pNextNode;
        }
    }
    setSize(obj.getSize()); //设置大小
}

LinkNode::~LinkNode()
{
    //printf("%p\r\n", this);
    if (m_pElement != nullptr)
    {
        delete m_pElement;
    }
}

CLinkList::~CLinkList()
{
    LinkNode *pNowNode = m_pHeadNode;
    LinkNode *pNextNode = nullptr;

    while (pNowNode->m_pNextNode != nullptr)
    {
        pNextNode = pNowNode->m_pNextNode;
        delete pNowNode;
        pNowNode = pNextNode;
    }

    delete pNowNode;
}

void CLinkList::test()
{
    printf("list size: %d\r\n", getSize());
    printf("HeadDate:%d, HeadAddress:%p, previousNode address:%p, nextNode address: %p\r\n",
        m_pHeadNode->m_pElement->getValue(),
        m_pHeadNode,
        m_pHeadNode->m_pPreviousNode,
        m_pHeadNode->m_pNextNode
    );
    LinkNode *pNode = m_pHeadNode->m_pNextNode;
    while (pNode->m_pNextNode != nullptr)
    {
        printf("NodeDate:%d, NodeAddress:%p, previousNode address:%p, nextNode address: %p\r\n",
            pNode->m_pElement->getValue(),
            pNode,
            pNode->m_pPreviousNode,
            pNode->m_pNextNode
        );

        pNode = pNode->m_pNextNode;
    }

    printf("TailDate:%d, TailAddress:%p, previousNode address:%p, nextNode address: %p\r\n",
        m_pTailNode->m_pElement->getValue(),
        m_pTailNode,
        m_pTailNode->m_pPreviousNode,
        m_pTailNode->m_pNextNode
    );
}

LinkNode* CLinkList::push_back(const int& element)
{
    LinkNode *pNode = new LinkNode(element);
    //设置当前结点的前驱与后继
    pNode->m_pPreviousNode = m_pTailNode->m_pPreviousNode;
    pNode->m_pNextNode = m_pTailNode;
    //设置尾结点的前驱结点的后继为当前结点
     m_pTailNode->m_pPreviousNode->m_pNextNode = pNode;
    //设置尾节点的前驱
    m_pTailNode->m_pPreviousNode = pNode;
    setSize(getSize() + 1U);
    return pNode;
}

LinkNode* CLinkList::push_front(const int& element)
{
    LinkNode *pNode = new LinkNode(element);
    //设置当前结点的前驱与后继
    pNode->m_pPreviousNode = m_pHeadNode;
    pNode->m_pNextNode = m_pHeadNode->m_pNextNode;
    //设置头结点的后继结点的前继为当前结点
    m_pHeadNode->m_pNextNode->m_pPreviousNode = pNode;
    //设置头节点的后继
    m_pHeadNode->m_pNextNode = pNode;
    setSize(getSize() + 1U);
    return pNode;
}

const unsigned CLinkList::getSize() const
{
    return m_uSize;
}

void CLinkList::setSize(const unsigned size)
{
    m_uSize = size;
}

LinkNode* CLinkList::insert(LinkNode* pos, const int& element)
{
    LinkNode *pNode = new LinkNode(element);

    //设置新结点
    pNode->m_pPreviousNode = pos->m_pPreviousNode;
    pNode->m_pNextNode = pos;
    //设置旧结点的前继结点
    pos->m_pPreviousNode->m_pNextNode = pNode;
    //设置旧结点
    pos->m_pPreviousNode = pNode;
    setSize(getSize() + 1U);
    return pNode;
}

const bool CLinkList::empty() const
{
    if (getSize() != 0)
    {
        return false;
    }
    else
    {
        return true;
    }
}

void CLinkList::clear()
{
    if (!empty())
    {
        LinkNode *pNowNode = m_pHeadNode->m_pNextNode;
        LinkNode *pNextNode = nullptr;

        while (pNowNode->m_pNextNode != nullptr)
        {
            pNextNode = pNowNode->m_pNextNode;
            delete pNowNode;
            pNowNode = pNextNode;
        }

        m_pHeadNode->m_pNextNode = m_pTailNode;
        m_pTailNode->m_pPreviousNode = m_pHeadNode;
        setSize(0U);
    }
}

void CLinkList::erese(LinkNode* pos)
{
    if (!empty())
    {
        pos->m_pPreviousNode->m_pNextNode = pos->m_pNextNode;
        pos->m_pNextNode->m_pPreviousNode = pos->m_pPreviousNode;
        setSize(getSize() - 1U);
        delete pos;
    }
}

void CLinkList::pop_back()
{
    if (!empty())
    {
        LinkNode *pNode = m_pTailNode->m_pPreviousNode;
        pNode->m_pPreviousNode->m_pNextNode = pNode->m_pNextNode;
        pNode->m_pNextNode->m_pPreviousNode = pNode->m_pPreviousNode;
        setSize(getSize() - 1U);
        delete pNode;
    }
}

void CLinkList::pop_front()
{
    if (!empty())
    {
        LinkNode *pNode = m_pHeadNode->m_pNextNode;
        pNode->m_pPreviousNode->m_pNextNode = pNode->m_pNextNode;
        pNode->m_pNextNode->m_pPreviousNode = pNode->m_pPreviousNode;
        setSize(getSize() - 1U);
        delete pNode;
    }
}

Integer& CLinkList::back()
{
    if (!empty())
    {
        LinkNode *pNode = m_pTailNode->m_pPreviousNode;
        return *pNode->m_pElement;
    }
}

Integer& CLinkList::front()
{
    if (!empty())
    {
        LinkNode *pNode = m_pHeadNode->m_pNextNode;
        return *pNode->m_pElement;
    }
}

CLinkList& CLinkList::operator= (const CLinkList& list)
{
    CLinkList *pLink = new CLinkList;
    CLinkList *pOldLink = this;

    if (!list.empty())
    {
        this->~CLinkList();
        LinkNode *pNode = list.m_pHeadNode->m_pNextNode;
        while (pNode->m_pNextNode != nullptr)
        {
            pLink->push_back((pNode->m_pElement->getValue()));
            pNode = pNode->m_pNextNode;
        }
    }
    pLink->setSize(list.getSize());

    pOldLink->m_pHeadNode = pLink->m_pHeadNode;
    pOldLink->m_pTailNode = pLink->m_pTailNode;

    return *pLink;
}

void CLinkList::operator+= (const CLinkList& list)
{
    if (!list.empty())
    {
        LinkNode *pNode = list.m_pHeadNode->m_pNextNode;
        while (pNode->m_pNextNode != nullptr)
        {
            push_back((pNode->m_pElement->getValue()));
            pNode = pNode->m_pNextNode;
        }
    }
    else
    {
        return;
    }
}
 //test1.cpp
#include "LinkList.h"

int main()
{
    {
        CLinkList list(1);
        //CLinkList list2;
        //list2.test();
        /*
        for (int i = 2; i < 6; i++)
        {
            list.push_back(i);
        }
        
        for (int i = 2; i < 6; i++)
        {
            list.push_front(i);
        }
        

        LinkNode *pNode  = list.push_back(4);

        list.insert(pNode, 2);
        
        list.test();
        list.clear();
        list.test();
        list.push_front(3);
        list.test();
        */
        
        LinkNode *pNode = list.push_back(3);
        //list.test();
        //list.erese(pNode);
        //list.pop_back();
        list.pop_front();
        //list.test();
        list.push_back(4);
        //list.test();
        CLinkList list3 = list;
        //list3.test();
        CLinkList list4(1);
        list4 = list3;
        //list4.test();
        list4.push_front(1);
        list4.push_front(2);
        list4.test();
        list3.test();

        list4 += list3;
        list4.test();
    }
    system("pause");
    return 0;
}

2.实现循环链表基础上实现模板循环链表

 //LinkList.h
#pragma once
#include 
using namespace std;

template 
class LinkNode //双向链表结点
{
public:
    LinkNode(T element = (T)0, LinkNode *previousNode = nullptr, LinkNode *nextNode = nullptr);
    ~LinkNode();
public:
    T *m_pElement;
    LinkNode *m_pPreviousNode;
    LinkNode *m_pNextNode;
};

template 
class CLinkList //双向链表类
{
public:
    CLinkList();
    CLinkList(T element);
    CLinkList(const CLinkList& obj);
    ~CLinkList();
    void test();                                                            //显示测试
    const unsigned getSize() const;                                         //获取链表大写
    void push_back(const T& element);                               //尾结点增加元素
    void push_front(const T& element);                              //头节点增加元素
    LinkNode* insert(LinkNode* pos, const T& element);                //指定结点前增加元素
    const bool empty() const;                                               //是否空链表
    void clear();                                                           //清空表
    void erese(LinkNode* pos);                                           //删除指定位置的元素
    void pop_back();                                                        //删除最后一个元素
    void pop_front();                                                       //删除第一个元素
    LinkNode& back();                                                   //获得最后一个元素
    LinkNode& front();                                                  //获得最第一个元素
    CLinkList& operator= (const CLinkList& list);                        //拷贝链表
    void operator+= (const CLinkList& list);                             //合并另一个链表到当前链表
    //CLinkList& operator= (const T& element);                              //修改
private:
    void setSize(const unsigned size);                                      //设置大小

private:
    unsigned m_uSize;       //链表大小
    LinkNode *m_pHeadNode;  //头结点
    LinkNode *m_pTailNode;  //尾结点
};

template
LinkNode::LinkNode(T element, LinkNode * previousNode, LinkNode * nextNode)
{
    m_pElement = new T(element);
    m_pPreviousNode = previousNode;
    m_pNextNode = nextNode;
}

template
LinkNode::~LinkNode()
{
    if (m_pElement != nullptr)
    {
        delete m_pElement;
    }
}

template
CLinkList::CLinkList()
{
    m_pHeadNode = new LinkNode();                    //头结点
    m_pTailNode = new LinkNode();                    //尾结点
    m_pHeadNode->m_pNextNode = m_pTailNode;             //设置头结点
    m_pTailNode->m_pPreviousNode = m_pHeadNode;         //设置尾结点
    setSize(0U);                                        //大小为一
}

template
CLinkList::CLinkList(T element)
{
    LinkNode *pNewNode = new LinkNode(element); //创建的新结点
    m_pHeadNode = new LinkNode(T(0));    //头结点
    m_pTailNode = new LinkNode(T(0));    //尾结点                                         
    m_pHeadNode->m_pNextNode = pNewNode;    //设置头结点    
    pNewNode->m_pPreviousNode = m_pHeadNode;    //设置新结点
    pNewNode->m_pNextNode = m_pTailNode;
    m_pTailNode->m_pPreviousNode = pNewNode; //设置尾结点
    setSize(1U);    //大小为一
}

template
CLinkList::CLinkList(const CLinkList& obj)
{
    m_pHeadNode = new LinkNode();    //头结点
    m_pTailNode = new LinkNode();    //尾结点
    m_pHeadNode->m_pNextNode = m_pTailNode; //设置头结点
    m_pTailNode->m_pPreviousNode = m_pHeadNode; //设置尾结点
                                                //拷贝的链表非空链表
    if (!obj.empty())
    {
        LinkNode *pNode = obj.m_pHeadNode->m_pNextNode;
        while (pNode->m_pNextNode != nullptr)
        {
            push_back(*(pNode->m_pElement));
            pNode = pNode->m_pNextNode;
        }
    }
    setSize(obj.getSize()); //设置大小
}

template
CLinkList::~CLinkList()
{
    LinkNode *pNowNode = m_pHeadNode;
    LinkNode *pNextNode = nullptr;

    while (pNowNode->m_pNextNode != nullptr)
    {
        pNextNode = pNowNode->m_pNextNode;
        delete pNowNode;
        pNowNode = pNextNode;
    }

    delete pNowNode;
}


template
void CLinkList::test()
{
    cout << "list size:" << getSize() << endl;
    cout << "HeadDate:" << *m_pHeadNode->m_pElement;
    cout << ", HeadAddress:" << m_pHeadNode;
    cout << ", previousNode:" << m_pHeadNode->m_pPreviousNode;
    cout << ", nextNode address:" << m_pHeadNode->m_pNextNode << endl;

    LinkNode *pNode = m_pHeadNode->m_pNextNode;
    while (pNode->m_pNextNode != nullptr)
    {
        cout << "NodeDate:" << *pNode->m_pElement;
        cout << ", NodeAddress:" << pNode;
        cout << ", previousNode:" << pNode->m_pPreviousNode;
        cout << ", nextNode address:" << pNode->m_pNextNode << endl;

        pNode = pNode->m_pNextNode;
    }

    cout << "TailDate:" << *m_pTailNode->m_pElement;
    cout << ", TailAddress:" << m_pTailNode;
    cout << ", previousNode:" << m_pTailNode->m_pPreviousNode;
    cout << ", nextNode address:" << m_pTailNode->m_pNextNode << endl;
}


template
void CLinkList::push_back(const T& element)
{
    LinkNode *pNode = new LinkNode(element);
    //设置当前结点的前驱与后继
    pNode->m_pPreviousNode = m_pTailNode->m_pPreviousNode;
    pNode->m_pNextNode = m_pTailNode;
    //设置尾结点的前驱结点的后继为当前结点
    m_pTailNode->m_pPreviousNode->m_pNextNode = pNode;
    //设置尾节点的前驱
    m_pTailNode->m_pPreviousNode = pNode;
    setSize(getSize() + 1U);
}

template
void CLinkList::push_front(const T& element)
{
    LinkNode *pNode = new LinkNode(element);
    //设置当前结点的前驱与后继
    pNode->m_pPreviousNode = m_pHeadNode;
    pNode->m_pNextNode = m_pHeadNode->m_pNextNode;
    //设置头结点的后继结点的前继为当前结点
    m_pHeadNode->m_pNextNode->m_pPreviousNode = pNode;
    //设置头节点的后继
    m_pHeadNode->m_pNextNode = pNode;
    setSize(getSize() + 1U);
}

template
const unsigned CLinkList::getSize() const
{
    return m_uSize;
}

template
void CLinkList::setSize(const unsigned size)
{
    m_uSize = size;
}

template
LinkNode* CLinkList::insert(LinkNode* pos, const T& element)
{
    LinkNode *pNode = new LinkNode(element);

    //设置新结点
    pNode->m_pPreviousNode = pos->m_pPreviousNode;
    pNode->m_pNextNode = pos;
    //设置旧结点的前继结点
    pos->m_pPreviousNode->m_pNextNode = pNode;
    //设置旧结点
    pos->m_pPreviousNode = pNode;
    setSize(getSize() + 1U);
    return pNode;
}

template
const bool CLinkList::empty() const
{
    if (getSize() != 0U)
    {
        return false;
    }
    else
    {
        return true;
    }
}

template
void CLinkList::clear()
{
    if (!empty())
    {
        LinkNode *pNowNode = m_pHeadNode->m_pNextNode;
        LinkNode *pNextNode = nullptr;

        while (pNowNode->m_pNextNode != nullptr)
        {
            pNextNode = pNowNode->m_pNextNode;
            delete pNowNode;
            pNowNode = pNextNode;
        }

        m_pHeadNode->m_pNextNode = m_pTailNode;
        m_pTailNode->m_pPreviousNode = m_pHeadNode;
        setSize(0U);
    }
}

template
void CLinkList::erese(LinkNode* pos)
{
    if (!empty())
    {
        pos->m_pPreviousNode->m_pNextNode = pos->m_pNextNode;
        pos->m_pNextNode->m_pPreviousNode = pos->m_pPreviousNode;
        setSize(getSize() - 1U);
        delete pos;
    }
}

template
void CLinkList::pop_back()
{
    if (!empty())
    {
        LinkNode *pNode = m_pTailNode->m_pPreviousNode;
        pNode->m_pPreviousNode->m_pNextNode = pNode->m_pNextNode;
        pNode->m_pNextNode->m_pPreviousNode = pNode->m_pPreviousNode;
        setSize(getSize() - 1U);
        delete pNode;
    }
}

template
void CLinkList::pop_front()
{
    if (!empty())
    {
        LinkNode *pNode = m_pHeadNode->m_pNextNode;
        pNode->m_pPreviousNode->m_pNextNode = pNode->m_pNextNode;
        pNode->m_pNextNode->m_pPreviousNode = pNode->m_pPreviousNode;
        setSize(getSize() - 1U);
        delete pNode;
    }
}

template
LinkNode& CLinkList::back()
{
    if (!empty())
    {
        LinkNode *pNode = m_pTailNode->m_pPreviousNode;
        return pNode;
    }
    else
    {
        return nullptr;
    }

}

template
LinkNode& CLinkList::front()
{
    if (!empty())
    {
        LinkNode *pNode = m_pHeadNode->m_pNextNode;
        return pNode;
    }
    else
    {
        return nullptr;
    }
}

template
CLinkList& CLinkList::operator= (const CLinkList& list)
{
    CLinkList *pLink = new CLinkList;
    CLinkList *pOldLink = this;

    if (!list.empty())
    {
        this->~CLinkList();
        LinkNode *pNode = list.m_pHeadNode->m_pNextNode;
        while (pNode->m_pNextNode != nullptr)
        {
            pLink->push_back((pNode->m_pElement->getValue()));
            pNode = pNode->m_pNextNode;
        }
    }
    pLink->setSize(list.getSize());

    pOldLink->m_pHeadNode = pLink->m_pHeadNode;
    pOldLink->m_pTailNode = pLink->m_pTailNode;

    return *pLink;
}

template
void CLinkList::operator+= (const CLinkList& list)
{
    if (!list.empty())
    {
        LinkNode *pNode = list.m_pHeadNode->m_pNextNode;
        while (pNode->m_pNextNode != nullptr)
        {
            push_back(*(pNode->m_pElement));
            pNode = pNode->m_pNextNode;
        }
    }
    else
    {
        return;
    }
}
 //test2.cpp
#include "LinkList.h"

int main()
{
    CLinkList list1;
    CLinkList list2(1);
    CLinkList list3 = list2;


    system("pause");
    return 0;
}
0 条评论
发表一条评论