单链表的优化(十三)-创新互联
我们在之前实现了单链表,那么我们如何遍历单链表中的每一个数据元素呢?肯定直接一个 for 循环就可以搞定啊,我们来看看当前基于我们实现的单链表遍历的方法,main.cpp 如下
创新互联是专业的铅山网站建设公司,铅山接单;提供成都网站设计、成都网站制作,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行铅山网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!#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、封装结点的申请和删除操作更有利于增强扩展性。
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
网站栏目:单链表的优化(十三)-创新互联
转载注明:http://myzitong.com/article/hhids.html