单链表的高效遍历及性能优化策略

LinkList<int> list;
for(int i=0; i<5; i++)
{
list.insert(0,i);
}
for(int i=0; i)
{
cout <get(i) << endl;
}

#ifndef LINKLIST
#define LINKLIST
#include "List.h"
#include "Object.h"
#include "Exception.h"
namespace DTLib
{
template
class LinkList : public List
{
protected:
struct Node : public Object
{
T value;
Node* next;
};
// mutable Node m_header;//加上mutable就允许在const成员函数中取m_header的地址了
/*这个类型的定义仅仅是为了头结点，非常巧妙。*/
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; p)
{
ret = ret->next;
}
return ret;
}
public:
LinkList()
{
m_header.next = NULL;
m_length = 0;
m_step = 1;
m_current = NULL;
}
bool insert(const T& e) //往线性表的尾部插入一个元素，因此将i省略掉。
{
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;
toDel->next = current->next;
delete toDel;
m_length--;
}
return ret;
}
bool set(int i, const T& e)
{
bool ret = ((0<=i) && (i<m_length));
if(ret)
{
Node* current= position(i);
current->next->value = e;
}
return ret;
}
T get(int i) const
{
T ret;
if(get(i,ret))
{
return ret;
}
else
{
THROW_EXCEPTION(IndexOutOfBoundsException,"invalid parameter i get element...");
}
return ret;
}
bool get(int i, T& e) const
{
bool ret = ((0<=i) && (i<m_length));
if(ret)
{
Node* current = position(i);
e = current->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;
}
bool move(int i, int step=1)
{
bool ret = (0 <= i) && (i 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 end() ))
{
m_current = m_current->next;
i++;
}
return (i == m_step);
}
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;
}
~LinkList()
{
clear();
}
};
}
#endif // LINKLIST

#include
#include
#include "LinkList.h"
using namespace std;
using namespace DTLib;
int main()
{
LinkList<int> list;
for(int i=0; i<5; i++)
{
list.insert(0,i);
}
/*将游标移动到第0个节点所在的位置list.move(0)
list.end()判断当前游标是否已达到末尾；
list.next()移动游标
意义就是先将指针指向第0个数据元素，打印第0个数据元素的值；
然后移动一次，移动一次后再来获取数据元素的值...时间复杂度就是O(n)
*/
for(list.move(0); !list.end(); list.next())
{
cout < endl;
}
//可以只遍历下标为偶数的数据元素
for(list.move(0,2); !list.end(); list.next())
{
cout < endl;
}
return 0;
}

virtual Node* create()
{
return new Node();
}
virtual void destory(Node* pn)
{
delete pn;
}