算法导论第十章数据结构--双向链表

看的概念挺朦胧的,没有明确好双链表到底需要哪些方法,其实针对这种结构应该可以写很多方法,并没有什么特定标准。

不过真是只看不练不行啊,一下手各种错误,各种溢出

#include<iostream>


using namespace std;
template<class T> struct Node
{
T value;
Node<T>* pre;
Node<T>* next;


};
template<class T> class Flist
{
private:
Node<T>* front;
Node<T>* end; //每写一个函数,遍历类中变量哪个要维护 
int count;

public:
Flist();   //defaut constructor
~Flist();
Flist(const Flist& C_list);//支持了这个,没有写支持 = 可以写个空的内联函数来放空这种行为,否则有相关操作时,编译器会自动产生 
inline void Deeply_Copy(const Flist& Copylist);
bool Isempty() const;
int Listsize() const;
T& Listfront()const;
T& Listend() const;  //返回引用是不是可以改首尾node的key值了 
void push_front(T N);
void push_back(T N);
void del_front();
void del_back();
//Node<T>* Listfind(T x); //搜索有key值x的节点 
T ShowKey(int n);   //输出第n个值 
 
};
template<class T> Flist<T>::Flist():count(0),front(0),end(0) //初始化顺序与类中声明有关与这无关 
{

}
template<class T> Flist<T>::~Flist()
{
Node<T>* temp;
while (front != 0)
{
temp = front;
delete temp;
front = front->next;
}
temp = NULL;
}
template<class T> bool Flist<T>::Isempty() const
{
return 0 == count;
}
template<class T> int Flist<T>::Listsize() const{
return count;
}
template<class T> Flist<T>::Flist(const Flist& C_list)
{
Deeply_Copy(C_list);

}
template<class T> T& Flist<T>::Listfront() const
{
return front->value;
}
template<class T> T& Flist<T>::Listend() const
{
return end->value;
}
template<class T> void Flist<T>::push_front(T N)
{
Node<T>* p = new Node<T>;
p->value = N;
p->next = front;
if (front != 0)
front->pre = p;
front = p;
if(end == 0)
end = p ;
p->pre = 0;
count++;
}
template<class T> void Flist<T>::push_back(T N)
{
Node<T>* p = new Node<T>;
p->value = N;
p->pre = end;
if (end != 0)   //一开始这里崩溃是因为end没有初始化0就用 
  end->next = p; 
end = p;
end->next = 0;
count++;
}
template<class T> void Flist<T>::del_front()
{
Node<T>* temp = front;
front = front->next;
count--;
front->pre = 0;
delete temp;
}
template<class T> void Flist<T>::del_back()
{
Node<T>* temp = end;
end = end->pre;
end->next = 0;
count--;
delete temp;
}

template<class T> T Flist<T>::ShowKey(int n)
{

/*
if (front == 0)
{
cout << "there is no element is the list.." << endl;
return ;                                          //未解决,size为0时,如何提示 
}*/
    if ((front !=0)  && (n <=count) && (n >= 1))
    {
    Node<T>* temp = front;
while(--n)                    //这里如果while(n--)就溢出崩溃,n用后再减,这里的用是判断,不要以为只是括号就可以前后随便用 
{
temp = temp->next;   //n大于size也会溢出 
}
return temp->value;
//这里temp指向了一个也有其他指针指向节点,可不要delete 
    }

}
template<class T> void Flist<T>::Deeply_Copy(const Flist& Copylist)
{
front = end = 0;
if (Copylist.front == 0)
return ;          //这里起到了结束函数的作用 
front = new Node<T>;
Node<T>* cp = Copylist.front;
Node<T>* np = front;
np->value = cp->value;
count = 1;
np->pre = 0;
cp = cp->next;
while (cp != 0)
{
np->next = new Node<T>;
count++;
(np->next)->pre = np;
np = np->next;
np->value = cp->value;
cp = cp->next;
}
end = np; 
}
int main()
{
Flist<int> listf;
int a[5] = {1,2,3,4,5};
for (int i = 0 ; i < 5 ; i++)
listf.push_front(a[i]);
cout << "lisrfsize: " << listf.Listsize() << endl;
for (int i = 0 ; i < 5 ; i++)
listf.push_back(a[i]); 
cout << "lisrfsize: " << listf.Listsize() << endl; 
cout << "listf is empty? : " << listf.Isempty() << endl; 
Flist<int> listf2(listf);
cout << "Listf2size : " << listf2.Listsize() << endl;
listf2.del_front();
listf2.del_back();
cout << "Listf2 front :" << listf2.Listfront() << endl;
cout << "Listf2 end :" << listf2.Listend() << endl;
cout << "Listf2 size :" << listf2.Listsize() << endl;
for (int i = 1; i <= listf2.Listsize(); i++) 
  cout << listf2.ShowKey(i) << endl;


return 0;
}

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。