双向循环链表
双向链表按位置插入时出问题,只有两个数据的时候,Length()函数在Insert函数里居然能达到3（所以判断条件里不得不-1)如果只2个或3个数据,Length（）函数在主函数里输出时正常.不最主要还是按位置插入时，那段代码检查了几遍找不到哪里错了.
#include <iostream>
using namespace std;
template <class T>
class Double;
template <class T>
class DoubleNode
{
friend Double<T>;
private :
T data;
DoubleNode<T> *right,*left;
};
template <class T>
class Double
{
public:
Double(){LeftEnd=RightEnd=0;}
~Double();
int Length();
bool Find(int k,T& x)const;
int Serach(const T& x)const;
Double<T>& Delete(int k,T& x);
Double<T>& Insert(int k,const T& x);
void Output(ostream& out) const;
private:
DoubleNode<T> *LeftEnd,*RightEnd;
};
template <class T>
Double<T>::~Double()
{
DoubleNode<T> *t;
t=LeftEnd;
while(t)
{
t=LeftEnd->right;
delete LeftEnd;
LeftEnd=t;
}
}
template <class T>
Double<T>& Double<T>::Insert(int k,const T&x)
{
DoubleNode<T> *t;
t=new DoubleNode<T>;
t->data=x;
if(k==0)
{
t->right=0;
t->left=0;
LeftEnd=t;
}
if(k==1)
{
t->right=0;
t->left=LeftEnd;
LeftEnd->right=t;
RightEnd=t;
}
if(k>1&&k==Length())
{
t->left=RightEnd;
t->right=0;
RightEnd->right=t;
RightEnd=t;
}
if(k>1&&k<Length()-1) //按位置插入就这段代码处理，我是没找问题出在哪了
{
DoubleNode<T> *c;
DoubleNode<T> *cr;
c=LeftEnd;
for(int i=0;i<k-1;i++)
c=c->right;
cr=c->right;
t->left=c;
t->right=cr;
c->right=t;
cr->left=t;
}
return *this;
}
template <class T>
void Double<T>::Output(ostream& out) const
{
DoubleNode<T> *t;
t=LeftEnd;
if(!t->right&&!t->left)
cout<<t->data<<" ";
else
{
while(t->right)
{
cout<<t->data<<" ";
t=t->right;
}
cout<<t->data<<" ";
}
cout<<endl;
}
template <class T>
int Double<T>::Length()
{
int l=1;
DoubleNode<T> *t;
t=LeftEnd;
if(!t->right&&!t->left) return l;
else
{
while(t->right)
{
l++;
t=t->right;
}
return l;
}
}
template <class T>
ostream& operator<<(ostream&out,const Double<T>& x)
{
x.Output(out);
return out;
}
int main()
{
Double<int> d;
d.Insert(0,1).Insert(1,2).Insert(2,3).Insert(3,4).Insert(4,5).Insert(5,6);
cout<<d;
d.Insert(3,13); 按位置插入时出问题
cout<<d;
cout<<d.Length()<<endl;
return 0;
}
[ 本帖最后由 mfkblue 于 2009-8-11 18:24 编辑 ]
