Posted on 2006-05-08 12:47
Tauruser 閱讀(1715)
評論(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?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?