[原创] 一个链表类....
自己折腾了一天，还是不如人意.....算是练练手吧，这个类原本是写上迭代器的，后面加了又删，删了又加，始终写不好...最后就不要了....不过作为学习来说，目的算是达到了-----异常安全.能帮忙加上迭代器的就加加...谢谢 ^ ^.
[quote][font=新宋体][size=1.5][color=#008000]/*****************************************************************
** HighlightCodeV3.0 software by yzfy(雨中飞燕) http://yzfy.org **
*****************************************************************/
[/color][color=#FF0000]#ifndef [/color][color=#800080]DATASTRUCT_H_
[/color][color=#FF0000]#define [/color][color=#800080]DATASTRUCT_H_
[/color][color=#FF0000]#include<iostream>
[/color][color=#FF0000]#include<vector>
[/color][color=#FF0000]#include<cassert>
[/color][color=#0000FF]template[/color]<typename _Ty>
[color=#0000FF]class [/color]Linklist
[color=#800000]{
[/color][color=#0000FF]struct [/color]node_
[color=#800000]{
[/color]_Ty value_;
node_* next,*pre;
node_ * first;
[color=#008080]node_[/color]([color=#0000FF]const [/color]_Ty& value): [color=#008080]value_[/color](value)
[color=#800000]{
[/color]pre=next=first=[color=#800080]0[/color];
[color=#800000]}
[/color]~[color=#008080]node_[/color]()[color=#800000]{ [/color][color=#FF0000]std[/color]::[color=#FF0000]cout[/color]<<[color=#FF00FF]" destroty......"[/color]<<[color=#FF0000]std[/color]::[color=#FF0000]endl[/color];[color=#800000]}
} [/color];
[color=#0000FF]typedef [/color]typename Linklist<_Ty>::node_* pointer;
[color=#0000FF]typedef [/color]typename Linklist<_Ty>::node_ [color=#0000FF]const[/color]* const_pointer;
[color=#0000FF]typedef [/color]typename Linklist<_Ty>::node_& reference;
[color=#0000FF]typedef [/color]typename Linklist<_Ty>::node_& const_reference;
[color=#0000FF]public[/color]:
[color=#008080]Linklist[/color]();
[color=#008080]Linklist[/color]([color=#0000FF]const [/color]Linklist<_Ty>& source);
Linklist<_Ty>& [color=#0000FF]operator[/color]=([color=#0000FF]const [/color]Linklist<_Ty>& source);
~[color=#008080]Linklist[/color]();
[color=#0000FF]bool [/color][color=#008080]empty[/color]() [color=#0000FF]const [/color][color=#800000]{ [/color][color=#0000FF]return [/color](head_==[color=#800080]0[/color]); [color=#800000]}
[/color][color=#0000FF]int [/color][color=#FF8000]size[/color]() [color=#0000FF]const [/color][color=#800000]{ [/color][color=#0000FF]return [/color]size_; [color=#800000]}
[/color]pointer [color=#FF8000]begin[/color]() [color=#800000]{ [/color][color=#0000FF]return [/color]head_; [color=#800000]}
[/color]pointer [color=#FF8000]end[/color]() [color=#800000]{ [/color][color=#0000FF]return [/color]tail_; [color=#800000]}
[/color]const_pointer [color=#FF8000]begin[/color]() [color=#0000FF]const [/color][color=#800000]{ [/color][color=#0000FF]return [/color]head_; [color=#800000]}
[/color]const_pointer [color=#FF8000]end[/color]() [color=#0000FF]const [/color][color=#800000]{ [/color][color=#0000FF]return [/color]tail_; [color=#800000]}
[/color][color=#0000FF]void [/color][color=#008080]Insert[/color]([color=#0000FF]const [/color]_Ty& value,pointer at_);
[color=#0000FF]void [/color][color=#008080]Delete[/color](pointer at_);
pointer Linklist<_Ty>::[color=#008080]Find[/color]([color=#0000FF]int [/color]pos)
[color=#800000]{
[/color][color=#0000FF]return [/color][color=#FF8000]find[/color](pos);
[color=#800000]}
[/color]const_pointer [color=#008080]Find[/color]([color=#0000FF]int [/color]pos) [color=#0000FF]const
[/color][color=#800000]{
[/color][color=#0000FF]return [/color][color=#FF8000]find[/color](pos);
[color=#800000]}
[/color][color=#0000FF]void [/color][color=#008080]print[/color]() [color=#0000FF]const
[/color][color=#800000]{
[/color][color=#0000FF]for[/color](node_* it=head_;it!=[color=#800080]0[/color];it=it->next )
[color=#FF0000]std[/color]::[color=#FF0000]cout[/color]<<it->value_<<[color=#FF00FF]" "[/color];
[color=#FF0000]std[/color]::[color=#FF0000]cout[/color]<<[color=#FF0000]std[/color]::[color=#FF0000]endl[/color];
[color=#800000]}
[/color][color=#0000FF]private[/color]:
pointer [color=#008080]link[/color](pointer at_f,pointer at_,pointer at_l)
[color=#800000]{
[/color][color=#0000FF]if[/color](at_f!=[color=#800080]0[/color]) at_f->next=at_;
[color=#0000FF]if[/color](at_l!=[color=#800080]0[/color]) at_l->pre=at_;
at_->pre=at_f;
at_->next=at_l;
at_->first=head_;
[color=#0000FF]return [/color]at_;
[color=#800000]}
[/color]pointer [color=#008080]allocated[/color]()
[color=#800000]{
[/color][color=#0000FF]return [/color]static_cast<pointer>(::[color=#0000FF]operator new[/color]([color=#0000FF]sizeof[/color](node_)));
[color=#800000]}
[/color][color=#0000FF]void [/color][color=#008080]destroy[/color](pointer des_)
[color=#800000]{
[/color]des_->~[color=#008080]node_[/color]();
[color=#800000]}
[/color]pointer [color=#FF8000]find[/color]([color=#0000FF]int [/color]pos) [color=#0000FF]const
[/color][color=#800000]{
[/color][color=#008080]assert[/color](pos>[color=#800080]0[/color]&&pos<=size_);
[color=#0000FF]if[/color](pointer check=head_)
[color=#800000]{
[/color][color=#0000FF]for[/color](;pos>[color=#800080]1[/color];--pos) check=check->next;
[color=#0000FF]return [/color]check;
[color=#800000]}
[/color][color=#0000FF]return [/color][color=#800080]0[/color];
[color=#800000]}
[/color][color=#0000FF]void [/color][color=#008080]copy_[/color]([color=#0000FF]const [/color]Linklist<_Ty>& source);
[color=#0000FF]private[/color]:
pointer head_,tail_;
[color=#0000FF]int [/color]size_;
[color=#800000]}[/color];
[color=#008000]// 具体实现
[/color][color=#0000FF]template[/color]<typename _Ty>
[color=#0000FF]void [/color]Linklist<_Ty>::[color=#008080]copy_[/color]([color=#0000FF]const [/color]Linklist<_Ty>& source)
[color=#800000]{
[/color]pointer iter=[color=#FF8000]begin[/color](),iter_pre=[color=#FF8000]begin[/color](),h_=[color=#FF8000]begin[/color]();
[color=#0000FF]for[/color](const_pointer cPtr=source.[color=#FF8000]begin[/color]();cPtr!=[color=#800080]0[/color];cPtr=cPtr->next)
[color=#800000]{
[/color]iter=[color=#008080]allocated[/color]();
[color=#0000FF]new [/color](iter)[color=#008080]node_[/color](cPtr->value_);
[color=#0000FF]if[/color](h_)
[color=#800000]{
[/color]iter_pre=[color=#008080]link[/color](iter_pre,iter,[color=#800080]0[/color]);
iter_pre->first=h_;
[color=#800000]}
[/color][color=#0000FF]else
[/color][color=#800000]{
[/color]iter_pre=[color=#008080]link[/color](iter_pre,iter,[color=#800080]0[/color]);
iter_pre->first=h_=iter_pre;
[color=#800000]}
[/color]iter=iter->next;
[color=#800000]}
[/color]head_=iter_pre?iter_pre->first:[color=#800080]0[/color];
tail_=iter_pre;
size_=source.size_;
[color=#800000]}
[/color][color=#0000FF]template[/color]<typename _Ty>
[color=#0000FF]inline [/color]Linklist<_Ty>::[color=#008080]Linklist[/color]():[color=#008080]head_[/color]([color=#800080]0[/color]),[color=#008080]tail_[/color]([color=#800080]0[/color]),[color=#008080]size_[/color]([color=#800080]0[/color])
[color=#800000]{
}
[/color][color=#0000FF]template[/color]<typename _Ty>
Linklist<_Ty>::[color=#008080]Linklist[/color]([color=#0000FF]const [/color]Linklist<_Ty>& source):[color=#008080]head_[/color]([color=#800080]0[/color]),[color=#008080]tail_[/color]([color=#800080]0[/color]),[color=#008080]size_[/color]([color=#800080]0[/color])
[color=#800000]{
[/color][color=#008080]copy_[/color](source);
[color=#800000]}
[/color][color=#0000FF]template[/color]<typename _Ty>
Linklist<_Ty>& Linklist<_Ty>::[color=#0000FF]operator[/color]=([color=#0000FF]const [/color]Linklist<_Ty>& source)
[color=#800000]{
[/color][color=#0000FF]if[/color]( [color=#0000FF]this[/color]!=&source) [color=#008080]copy_[/color](source);
[color=#0000FF]return [/color]*[color=#0000FF]this[/color];
[color=#800000]}
[/color][color=#0000FF]template[/color]<typename _Ty>
Linklist<_Ty>::~[color=#008080]Linklist[/color]()
[color=#800000]{
[/color][color=#0000FF]for[/color](node_* d=[color=#FF8000]begin[/color](),*t;d!=[color=#800080]0[/color];d=t)
[color=#800000]{
[/color]t=d->next;
[color=#008080]destroy[/color](d);
;;[color=#0000FF]operator delete[/color](d);
[color=#800000]}
}
[/color][color=#0000FF]template[/color]<typename _Ty>
[color=#0000FF]void [/color]Linklist<_Ty>::[color=#008080]Insert[/color]([color=#0000FF]const [/color]_Ty& value,pointer at_)
[color=#800000]{
[/color]node_* node=[color=#008080]allocated[/color]();
[color=#0000FF]new [/color](node)[color=#008080]node_[/color](value);
[color=#0000FF]if[/color]( head_==[color=#800080]0[/color])
[color=#800000]{
[/color]head_=tail_=[color=#008080]link[/color]([color=#800080]0[/color],node,[color=#800080]0[/color]);
node->first=head_;
[color=#800000]}
[/color][color=#0000FF]else if[/color]( at_==head_)
[color=#800000]{
[/color]head_=[color=#008080]link[/color]([color=#800080]0[/color],node,head_);
[color=#0000FF]for[/color](;node;node=node->next)
node->first=head_;
[color=#800000]}
[/color][color=#0000FF]else if[/color]( at_==tail_) tail_=[color=#008080]link[/color](at_,node,[color=#800080]0[/color]);
[color=#0000FF]else [/color][color=#008080]link[/color](at_->pre,node,at_);
size_++;
[color=#800000]}
[/color][color=#0000FF]template[/color]<typename _Ty>
[color=#0000FF]void [/color]Linklist<_Ty>::[color=#008080]Delete[/color](pointer at_)
[color=#800000]{
[/color][color=#008080]assert[/color](at_!=[color=#800080]0[/color]);
[color=#0000FF]if[/color]( head_==[color=#800080]0[/color]) [color=#0000FF]throw [/color][color=#FF00FF]"it is empty so that delete...."[/color];
[color=#0000FF]if[/color]( at_==head_)
[color=#800000]{
[/color][color=#0000FF]if[/color](tail_==head_ ) tail_=[color=#800080]0[/color];
head_=head_->next;
[color=#0000FF]for[/color](node_* t_=head_;t_;t_=t_->next)
t_->first=head_;
[color=#800000]}
[/color][color=#0000FF]else if[/color]( at_=tail_) tail_=[color=#008080]link[/color](tail_->pre->pre,tail_->pre,[color=#800080]0[/color]);
[color=#0000FF]else [/color][color=#008080]link[/color](at_->pre->pre,at_->pre,at_->next);
[color=#008080]destroy[/color](at_);
::[color=#0000FF]operator delete[/color](at_);
size_--;
[color=#800000]}
[/color][color=#FF0000]#endif[/color][/size][/font][/quote]
[[it] 本帖最后由 中学者 于 2008-6-8 11:44 编辑 [/it]]
next,*pre;
就够了吧，多了一个 first不是浪费空间吗？ ......是写来为不相交集合作对象的....想把不相交集合用链表和树都做一遍.
页:
[1]