Tauruser

Enjoy Every Day
posts - 34, comments - 95, trackbacks - 0, articles - 5
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

双链表模版类的实现

Posted on 2006-05-08 12:47 Tauruser 阅读(1442) 评论(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                                                                                              

Feedback

# re: 双链表模版类的实现  回复  更多评论   

2006-05-08 13:05 by 小明
一点浅见。

using namespace std;
最好不要在头文件中using namespace,这样使用你的头文件的人被迫也
using namespace std了
这样用好了:std::cout

另外你使用std::cout,那么GUI的程序就不能看到任何讯息。总之不通用。

设计一个良好的类考虑的问题应该更全面一点





# re: 双链表模版类的实现  回复  更多评论   

2006-05-08 13:22 by 音乐虫子
库开发者和一般使用者要考虑的问题差别很大。

# re: 双链表模版类的实现  回复  更多评论   

2006-05-08 18:54 by Tauruser
@小明
谢谢指点。
另外想问一下,我想把出错信息返回来给调用用户的话,应该如果做才好呢?
上面的模板,我只考虑了在console下执行,所以用到了std::cout;

# re: 双链表模版类的实现  回复  更多评论   

2006-05-08 19:29 by iceboundrock
如果是类库,直接就把错误信息作为异常抛出去。

# re: 双链表模版类的实现  回复  更多评论   

2007-04-09 01:32 by 踏雪赤兔
与一般的实现想比,文中的“定位方法”比较有新意,不过写得太冗长了,想一想,如何精简一下,同时提高可读性。

# re: 双链表模版类的实现  回复  更多评论   

2011-09-26 15:14 by 周晓荣
问下:关于查找(search)那部分,我有点小问题要问,就是你直接就靠默认的比较操作符来比较,而你所用的是模版,链表支持各种类型,那么是字符串类型的链表或自定义类型的呢,你该怎么办

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理