1、单链表遍历优化
遍历单链表中的每个一数据元素
LinkList<int> list;
for(int i = 0; i < 5; i++) // O(n)
{
list.insert(0, i); // O(1), 头部插入,不涉及循环
}
// 这里的遍历方法效率很低
for(int i = 0; i < list.length(); i++) // O(n^2)
{
cout << list.get(i) << endl; // O(n)
}
遍历链表的时间复杂度不是线性的,插入元素是线性,遍历就不是了。
不能以线性的时间复杂度完成单链表的遍历
新的需求:为单链表提供新的方法,在线性时间内完成遍历
设计思路(游标)
- 在单链表的内部定义一个游标
Node* m_current
- 遍历开始前将游标指向位置为0的数据元素
- 获取游标指向的数据元素
- 通过结点中的
next
指针移动游标
提供一组遍历相关的函数,以线性的时间复杂度遍历链表
遍历函数原型设计
bool move(int i, int step = 1);
bool end();
T current();
bool next(); // 移动次数根据step的值来确定
// i 目标位置,step 游标每次移动结点的数目
bool move(int i, int step = 1)
{
bool ret = ((i >= 0) && (i < m_length) && (step > 0));
if(ret)
{
// 将游标定位到目标位置i的地方
m_current = position(i)->next;
m_step = step;
}
return ret;
}
bool end()
{
return (m_current == NULL);
}
T current()
{
// 返回游标指向的位置的元素值
//if(m_current != NULL)
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++;
}
// i的值和m_step的值是一样的,就表示移动成功
return (i == m_step);
}
// 新的遍历使用方法
for(list.move(0); !list.end(); list.next()) // O(n)
{
cout << list.current() << endl;
}
2、单链表内部的一次封装
virtual Node* creat()
{
return new Node();
}
virtual void destory(Node* pn)
{
delete pn;
}
3、小结
单链表的遍历需要在线性时间内完成
在单链表内部定义游标变量,通过游标变量提高效率
遍历相关的成员函数是相互依赖,相互配合的关系
封装结点的申请和删除操作更有利于增强扩展性
原文链接: https://www.cnblogs.com/chenke1731/p/9501433.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/279680
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!