我们在之前实现了单链表,那么我们如何遍历单链表中的每一个数据元素呢?肯定直接一个 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