C++数据结构第24课、单链表的遍历和优化

问题：如何遍历单链表中的每一个数据元素

当前单链表的遍历方法：

LinkList<int> list; for(int i = 0;i < 5;i++) //只在0位置处插入，时间复杂度O(n) { list.insert(0, i); } 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();

函数实现：

protected: Node* m_current; int m_step; public: LinkList() { m_current = nullptr; m_step = 1; } 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 == nullptr); } 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); }

main.cpp

#include <iostream> #include "LinkList.h" using namespace std; using namespace DTLib; int main() { LinkList<int> list; for(int i = 0; i < 5; i++) { list.insert(i); } for(list.move(0, 2); !list.end(); list.next()) //时间复杂度为 O(n) { cout << list.current() << endl; } return 0; }

单链表内部的一次封装 virtual Node* creat() { return new Node(); } virtual void destroy(Node* pn) { delete pn; }

提出问题：封装 creat 和 destroy 函数的意义是什么？

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