Posted on 2006-05-08 12:47
Tauruser 阅读(1698)
评论(6) 编辑 收藏 引用 所属分类:
算法与数据结构
在模版类加入curpt与curloc两个变量加速对链表的定位
#ifndef linklist_h_
#define linklist_h_
#include <iostream>
using namespace std;
template <class T> struct Element
{
T content;
Element* prelink; //predecesser link
Element* suclink; //successor link
};
template <class T> class dLinkList
{
public:
dLinkList();
~dLinkList();
void insert(const T &x,int loc);
void del(int loc);
void modify(const T &x, int loc);
bool IsEmpty();
//void list();
int search(const T &x,const int startloc );
int getsum();
T get(int loc);
private:
void locate(const int loc);//curpt定位于loc
Element<T>* head;//头指针
Element<T>* rear;//尾指针
Element<T>* curpt;//当前指针
int curloc;//当前指针位置
int sum;//链表元素总数
};
template <class T> dLinkList<T>::dLinkList()
{
head=NULL;
rear=NULL;
curpt=NULL;
curloc=0;
sum=0;
}
template <class T> dLinkList<T>::~dLinkList()
{
//如果堆栈非空，则不断del第一个元素直到为空
while(!IsEmpty())
{
del(1);
}
}
template <class T> void dLinkList<T>::locate(const int loc)
{
if(loc<1 || loc>sum)
{
cout<<"locate error"<<endl;
}else
{
int curlocdistance= (curloc-loc>0)?(curloc-loc):(loc-curloc); //当前位置与loc点距离
int rearlocdistance = sum-loc;//loc位置与表尾距离
//令curpt指向位置loc的节点
if( (loc-1<curlocdistance))//loc距离表头最近 ｛(loc-1)为loc与表头的距离｝
{
curpt=head;
for(int i=0; i<loc-1;i++)
curpt=curpt->suclink;
}else if( rearlocdistance<loc-1 && rearlocdistance < curlocdistance)//loc距离表尾最近
{
curpt=rear;
for(int i=0;i<rearlocdistance;i++)
curpt=curpt->prelink;
}else if(curloc-loc>0)//loc在curloc前面
{
for(int i=0;i<curlocdistance;i++)
curpt=curpt->prelink;
}else//loc在curloc后面
{
for(int i=0;i<curlocdistance;i++)
curpt=curpt->suclink;
}
curloc=loc;
}
return;
}
template <class T> void dLinkList<T>::insert(const T &x,int loc)
{
if( (loc<1) || (loc>sum+1))
{
cout<<"loc is out of range."<<endl;
return;
}
Element<T>* temp=new Element<T>;
temp->content=x;
if (sum==0)
{
temp->prelink=NULL;
temp->suclink=NULL;
head=temp;
rear=temp;
}else if(loc==sum+1)
{
rear->suclink=temp;
temp->suclink=NULL;
temp->prelink=rear;
rear=temp;
}else if(loc==1)
{
temp->prelink=NULL;
head->prelink=temp;
temp->suclink=head;
head=temp;
}else
{
locate(loc);//调用私用成员函数定位
//完成链接元素重新链接
temp->prelink=curpt->prelink;
curpt->prelink=temp;
temp->suclink=curpt;
temp->prelink->suclink=temp;
//令curpt指向当前插入元素。
}
sum++;
curpt=temp;
curloc=loc;
return;
}
template <class T> void dLinkList<T>::del(int loc)
{
if(loc<1 || loc>sum)
{
cout<<"del location error"<<endl;
return;
}
if(sum=1)
{
delete head;
head=NULL;
rear=NULL;
curpt=NULL;
curloc=0;
sum--;
}else if(loc==1)
{
curpt=head;
head=head->suclink;
head->prelink=NULL;
delete curpt;
curpt=head;
curloc=1;
sum--;
}else if(loc==sum)
{
curpt=rear;
rear=rear->prelink;
rear->suclink=NULL;
delete curpt;
curpt=rear;
curloc=sum-1;
sum--;
}else
{
locate(loc);
curpt->prelink->suclink=curpt->suclink;
curpt->suclink->prelink=curpt->prelink;
curpt=curpt->suclink;
curloc=loc;
sum--;
}
return;
}
template <class T> void dLinkList<T>::modify(const T &x,int loc)
{
if(loc<1 || loc>sum)
{
cout<<"modify location error"<<endl;
return;
}
locate(loc);
curpt->content=x;
}
template <class T> bool dLinkList<T>::IsEmpty()
{
return (!sum);
}
template <class T> T dLinkList<T>::get(int loc)
{
if(loc<1 || loc>sum)
{
cout<<"get location error"<<endl;
return NULL;
}
locate(loc);
return curpt->content;
}
template <class T> int dLinkList<T>::search(const T &x,const int startloc=1)
{
if(startloc<1 || startloc>sum)
{
cout<<"search start location error"<<endl;
return;
}
locate(startloc);
while(curpt->content!=x)
{
if(curpt->suclink==NULL)
{
return 0;
}
curpt=curpt->suclink;
curloc++;
}
return curloc;
}
template <class T> int dLinkList<T>::getsum()
{
return sum;
}
#endif