24_单链表的遍历与优化

2018-01-26 10:30:19来源:https://www.jianshu.com/p/e3469504b17a作者:jacob2359人点击

分享

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


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 destory(Node* pn) // 单链表内部进行delete封装
{
delete pn;
}

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


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






最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台