当前位置：首页 > article >正文

线性表-链式描述（C++）

article 2024/12/2 18:13:15

链式实现的线性表：

链式实现的线性表，即链表（Linked List），是一种通过节点（Node）的集合来存储数据的线性数据结构。在链表中，每个节点包含两部分：存储数据的域（数据域）和指向下一个节点的指针（指针域）。链表中的节点通过指针相互连接，形成一个序列。

优点

动态性：链表不需要在创建时指定大小，可以动态地增加或减少节点，非常适合用于需要频繁插入和删除操作的场景。
内存利用效率高：对于稀疏的数据集，链表可以通过只存储实际存在的元素来节省内存。
灵活的插入和删除操作：在链表中，插入和删除操作通常只需要修改相邻节点的指针，而不需要移动大量的数据。这使得链表在插入和删除操作上具有较高的效率。

缺点

访问速度慢：由于链表中的节点是通过指针相互连接的，因此访问链表中的某个元素通常需要从头节点开始遍历整个链表。这使得链表的访问速度相对较慢，特别是在需要频繁访问元素的场景中。
内存开销大：链表中的每个节点都需要额外的内存来存储指针，这增加了内存的开销。特别是在双向链表中，每个节点需要两个指针，进一步增加了内存的使用。
指针管理复杂：链表的操作需要频繁地修改指针，这增加了程序的复杂性。如果不小心管理指针，可能会导致内存泄漏、指针悬挂（dangling pointer）或野指针（wild pointer）等问题。

抽象类linearList

template<typename T>
class linearList
{
public:
    virtual ~linearList(){};
    virtual bool empty() const = 0;
    virtual int size() const = 0;
    virtual T& get(const int& theIndex) const = 0;
    virtual int indexOf(const T& theElement) const = 0;
    virtual void erase(const int& theIndex) const = 0;
    virtual void insert(const int& theIndex,const T& theElement) = 0;
    virtual void optput(std::ostream& out) const = 0;
};

节点类linkNode

template <typename T>
class linkNode
{
    T element;
    linkNode<T> *next;

    linkNode()
    {
        next = nullptr;
    }

    linkNode(const T& element)
    {
        this->elempent = element;
    }

    linkNode(const T& element, linkNode<T>* next)
    {
        this->elempent = element;
        this->next = next;
    }
};

派生类linkList

template<typename T>
class linkList : public linearList<T>
{
public:
    linkList(int initialCapacity = 10);
    linkList(const linkList<T>&);
    ~linkList();

    bool empty() const;
    int size() const;
    T &get(const int &theIndex) const;
    int indexOf(const T &theElement) const;
    void erase(const int &theIndex);
    void insert(const int &theIndex, const T &theElement);
    void optput(ostream &out) const;

    class iterator;
    iterator begin()
    {
        return iterator(firstNode);
    }

    iterator end()
    {
        return iterator(nullptr);
    }
private:
    void checkIndex(const int& theIndex) const;


private:
    linkNode<T>* firstNode;
    int listSize;
};

template<typename T>
linkList<T>::linkList(int initialCapacity)
{
    assert(initialCapacity > 0);
    firstNode = nullptr;
    listSize = 0;
}

template<typename T>
linkList<T>::linkList(const linkList<T> &theList)
{
    listSize = theList.listSize;

    if(listSize == 0)

    {
        firstNode = nullptr;
        return;
    }

    auto sourveNode = theList.firstNode;
    firstNode = new linkNode<T>(sourveNode->element);

    sourveNode = sourveNode->next;

    auto targetNode = firstNode;

    while (sourveNode != nullptr)
    {
        targetNode->next = new linkNode<T>(sourveNode->next);
        targetNode = targetNode->next;
        sourveNode = sourveNode->next;
    }
    targetNode->next = nullptr;
}

template<typename T>
linkList<T>::~linkList()
{
    while (firstNode != nullptr)
    {
        auto nextNode = firstNode->next;
        delete firstNode;
        firstNode = nextNode;
    }
}

template<typename T>
bool linkList<T>::empty() const
{
    return listSize == 0;
}

template<typename T>
int linkList<T>::size() const
{
    return listSize;
}

template<typename T>
T &linkList<T>::get(const int &theIndex) const
{
    checkIndex(theIndex);

    auto currentNode = firstNode;
    for(int i = 0; i < listSize; i++)
    {
        currentNode = currentNode->next;
        return currentNode->element;
    }
}

template<typename T>
int linkList<T>::indexOf(const T &theElement) const
{
    auto currentNode = firstNode;
    int index = 0;
    while(currentNode != nullptr && currentNode->element != theElement)
    {
        currentNode = currentNode->next;
        index++;
    }

    if(currentNode == nullptr)
    {
        return -1;
    }
    else
    {
        return index;
    }
}

template<typename T>
void linkList<T>::erase(const int &theIndex)
{
    checkIndex(theIndex);

    linkNode<T>* deleteNode;
    if(theIndex == 0)
    {
        deleteNode = firstNode;
        firstNode = firstNode->next;
    }
    else
    {
        auto p = firstNode;
        for(int i = 0; i < theIndex - 1; i++)
        {
            p = p->next;
        }


        deleteNode = p->next;
        p->next = p->next->next;
    }
    listSize--;
    delete deleteNode;
}

template<typename T>
void linkList<T>::insert(const int &theIndex, const T &theElement)
{
    assert(theIndex >= 0 && theIndex <= listSize);

    if(theIndex == 0)
    {
        firstNode = new linkNode<T>(theElement,firstNode);

    }
    else
    {
        auto p = firstNode;
        for(int i =0; i < theIndex - 1; i++)
        {
            p = p->next;
            p->next = new linkNode<T>(theElement,p->next);
        }
    }
    listSize++;
}

template<typename T>
void linkList<T>::optput(ostream &out) const
{
    for(auto currentNode = firstNode; currentNode != nullptr; currentNode = currentNode->next)
    {
        out << currentNode->element << " ";
    }
}

template<typename T>
void linkList<T>::checkIndex(const int &theIndex) const
{
    assert(theIndex >= 0 && theIndex < listSize);
}

template<typename T>
ostream& operator<<(ostream& out,const linkList<T>& theLinkList)
{
    theLinkList.optput(out);
    return out;
}

迭代器

template<typename T>
class iterator
{
public:
    typedef bidirectional_iterator_tag iterator_category;
    typedef ptrdiff_t difference_type;

    iterator(linkNode<T>* theNode = nullptr)
    {
        node = theNode;
    }

    T& operator*() const
    {
        return node->element;
    }

    T* operator->() const
    {

        return &node->element;
    }

    iterator& operator++()
    {
        node = node->next;
        return *this;
    }

    iterator operator++(int)
    {
        auto old = *this;
        node = node->next;
        return old;
    }

    bool operator!=(const iterator right) const
    {
        return node != right.node;
    }

    bool operator==(const iterator right) const
    {
        return node == right.node;
    }

protected:
    linkNode<T>* node;
};

查看全文

http://www.kler.cn/a/418787.html