24_单链表的遍历与优化

关键词：单链表遍历的优化、结点的封装

1. 当前单链表的遍历方法

遍历单链表的时间复杂度为O(n^2)。
遗憾的事实：不能以线性的时间复杂度完成单链表的遍历。
新的需求：为单链表提供新的方法，在线性时间内完成遍历。

2. 设计思路（游标）

1） 在单链表的内部定义一个游标（Node* m_current)
2） 遍历开始前将游标指向位置为0的数据元素
3） 获取有游标指向的数据元素
4） 通过结点中的next指针移动游标
提供一组遍历相关的函数，以线性的时间复杂度遍历链表

函数	函数原型	功能说明
nove()	bool move(int i, int step = 1)	将游标定位到目标位置
next()	bool next()	移动游标
current()	T current()	获取游标所指向的数据元素
end()	bool end()	游标是否到达尾部（是否为空）

    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(InvalidOperationExcetion, "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);
    }

3. 单链表内部创造结点和删除结点的封装

    virtual Node* create()      //   单链表内部进行create封装
    {
        return new Node();
    }

    virtual void destroy(Node* pn)  //   单链表内部进行delete封装
    {
        delete pn;
    }

4. 小结

• 单链表的遍历需要在线性时间内完成
• 在单链表内部定义游标变量，通过游标变量提高效率
• 遍历相关的成员函数是相互依赖、相互配合的关系
• 封装结点的申请和删除操作更有利于增强扩展性

声明：此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记，文章中包含狄泰软件资料内容，一切版权归狄泰软件所有！
实验环境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4