189 8069 5689

单链表的优化(十三)

        我们在之前实现了单链表,那么我们如何遍历单链表中的每一个数据元素呢?肯定直接一个 for 循环就可以搞定啊,我们来看看当前基于我们实现的单链表遍历的方法,main.cpp 如下

成都创新互联专注于秦淮企业网站建设,响应式网站设计,购物商城网站建设。秦淮网站建设公司,为秦淮等地区提供建站服务。全流程按需定制网站,专业设计,全程项目跟踪,成都创新互联专业和态度为您提供的服务

#include 
#include "LinkList.h"

using namespace std;
using namespace DTLib;

int main()
{
    LinkList list;

    for(int i=0; i<5; i++)      // O(1)
    {
        list.insert(0, i);
    }

    for(int i=0; i

        我们来看看输出结果,看看是不是遍历呢

单链表的优化(十三)

        结果是正确的,我们来分析下上面的测试代码的效率。第一个 for 循环,因为每次都是在 0 位置处插入数据元素,因此它的时间复杂度是 O(1);而第二个 for 循环,因为它要全部循环一遍,因此它的时间复杂度为 O(n)。我们就奇怪了,明明同样是两个 for 循环,效率竟然不相同。不能以线性的时间复杂度完成单链表的遍历,那么此时新的需求就产生了:为单链表提供新的方法,在线性时间内完成遍历。

        下来说说设计思路,利用游标的思想:

        1、在单链表的内部定义一个游标(Node* m_current);

        2、遍历开始前将游标指向位置为 0 的数据元素;

        3、获取游标指向的数据元素;

        4、通过结点中的 next 指针移动游标。


        提供一组遍历相关的函数,以线性的时间复杂度完成遍历链表,如下

单链表的优化(十三)

        遍历函数原型设计如下:

        bool move(int i, int step = 1);

        bool end();

        T current();

        bool next();

        下来我们来看看优化后的 LinkList.h 是怎样的,如下

LinkList.h 源码

#ifndef LINKLIST_H
#define LINKLIST_H

#include "List.h"
#include "Exception.h"

namespace DTLib
{

template < typename T >
class LinkList : public List
{
protected:
    struct Node : public Object
    {
        T value;
        Node* next;
    };

    mutable struct : public Object
    {
        char reserved[sizeof(T)];
        Node* next;
    } m_header;

    int m_length;
    int m_step;
    Node* m_current;

    Node* position(int i) const
    {
        Node* ret = reinterpret_cast(&m_header);

        for(int p=0; pnext;
        }

        return ret;
    }
public:
    LinkList()
    {
        m_header.next = NULL;
        m_length = 0;
        m_step = 1;
        m_current = NULL;
    }
    bool insert(const T& e)
    {
        return insert(m_length, e);
    }

    bool insert(int i, const T& e)
    {
        bool ret = ((0 <= i) && (i <= m_length));

        if( ret )
        {
            Node* node = new Node();

            if( node != NULL )
            {
                Node* current = position(i);

                node->value = e;
                node->next = current->next;
                current->next = node;

                m_length++;
            }
            else
            {
                THROW_EXCEPTION(NoEnoughMemoryException, "No memory to insert new element ...");
            }
        }
    }

    bool remove(int i)
    {
        bool ret = ((0 <= i) && (i < m_length));

        if( ret )
        {
            Node* current = position(i);
            Node* toDel = current->next;

            current->next = toDel->next;

            delete toDel;

            m_length--;
        }

        return ret;
    }

    bool set(int i, const T& e)
    {
        bool ret = ((0 <= i) && (i < m_length));

        if( ret )
        {
            position(i)->next->value = e;
        }

        return ret;
    }

    T get(int i) const
    {
        T ret;

        if( get(i, ret) )
        {
            return ret;
        }
        else
        {
            THROW_EXCEPTION(IndexOutOfBoundsException, "Invaild parameter i to get element ...");
        }
    }

    bool get(int i, T& e) const
    {
        bool ret = ((0 <= i) && (i < m_length));

        if( ret )
        {
            e = position(i)->next->value;
        }

        return ret;
    }

    int find(const T& e) const
    {
        int ret = -1;
        int i = 0;
        Node* node = m_header.next;

        while( node )
        {
            if( node->value == e )
            {
                ret = i;
                break;
            }
            else
            {
                node = node->next;
                i++;
            }
        }

        return ret;
    }

    int length() const
    {
        return m_length;
    }

    void clear()
    {
        while( m_header.next )
        {
            Node* toDel = m_header.next;

            m_header.next = toDel->next;

            delete toDel;
        }

        m_length = 0;
    }

    bool move(int i, int step = 1)
    {
        bool ret = (0 <= i) && (i < m_length) && (step > 0);

        if( ret )
        {
            m_current = position(i)->next;
            m_step = step;
        }

        return ret;
    }

    bool end()
    {
        return (m_current == NULL);
    }

    T current()
    {
        if( !end() )
        {
            return m_current->value;
        }
        else
        {
            THROW_EXCEPTION(INvalidOPerationException, "No value at current position ...");
        }
    }

    bool next()
    {
        int i = 0;

        while( (i < m_step) && !end() )
        {
            m_current = m_current->next;
            i++;
        }

        return (i == m_step);
    }

    ~LinkList()
    {
        clear();
    }
};

}

#endif // LINKLIST_H

 

main.cpp 源码

#include 
#include "LinkList.h"

using namespace std;
using namespace DTLib;

int main()
{
    LinkList list;

    for(int i=0; i<5; i++)      // O(1)
    {
        list.insert(0, i);
    }

    for(list.move(0); !list.end(); list.next()) // O(1)
    {
        cout << list.current() << endl;
    }

    return 0;
}

        我们来看看编译结果

单链表的优化(十三)

        我们看到结果还是正确的,证明我们上面代码的编写是没有错误的。我们再来分析下,它每次移动,移动后 current 指针就停在那块,等到下次移动的时候还是从这块开始移动。也就是说,每次遍历的时候,它只需要遍历一次就可以输出结果了,这样的话它遍历的时间复杂度就为 O(1) 了。我们再来将 new 和 delete 操作封装下,方便后面的使用,具体封装如下

virtual Node* create()    
{
    return new Node();
}

virtual void destroy (Node* pn)
{
    delete pn;
}

        然后将下面的 new 和 delete 操作全部换成 create 和 destory 函数。我们来试下将 main.cpp 测试代码中移动的 step 改为 2,那么它便输出的是偶数了。我们来看看结果

单链表的优化(十三)

        确实是输出的只有偶数。那么我们移动的 step 为 10 呢?那它就应该只输出 4 了,我们再来看看结果单链表的优化(十三)

        现在我们的 LinkList 类已经近乎完美了,优化后的效率遍历的时候极大的提高了。通过今天对 LinkList 优化的学习,总结如下:1、单链表的遍历需要在线性时间内完成;2、在单链表内部定义游标变量,通过游标变量提高效率;3、遍历相关的成员函数是相互依赖,相互配合的关系;4、封装结点的申请和删除操作更有利于增强扩展性。


文章标题:单链表的优化(十三)
文章URL:http://cdxtjz.cn/article/jicigg.html

其他资讯