数据结构练习--双向链表的实现

自上次实现单向链表之后，开始看双向链表，无非就是增加了一个逆序的节点，这次编程比上次能严禁和结构清晰一些，也是慢慢编程应该培养的东西

#include<iostream>

using namespace std;

template<class T>

class Node

{

public:

T data;

Node<T>*next;

Node<T>*prior;

};

template<class T>

class myslist

{

private:

Node<T>*phead;

Node<T>*ptail;

unsigned int length;

public:

myslist();

~myslist();

bool IsEmpty();

int GetLength();

void Output();

void add_head(T e);

void add_tail(T e);

Node<T>*GetNode(int pos);

void add_x(int pos,T e);

void DeleteNode(int pos);

};

template<class T>

myslist<T>::myslist()

{

phead=NULL;

ptail=NULL;

length=0;

};

template<class T>

bool myslist<T>::IsEmpty()

{

if(length==0)

return true;

else

return false;

};

template<class T>

myslist<T>::~myslist()

{

cout<<"Debug:析構函數"<<endl;

Node<T>*p1=phead;

Node<T>*p2;

while(p1!=ptail)

{

p2=p1;

p1=p1->next;

delete(p2);

}

delete(ptail);

};

template<class T>

int myslist<T>::GetLength()

{

return length;

};

template<class T>

void myslist<T>::Output()

{

cout<<"-------------------------------------------"<<endl;

cout<<"鏈表中的元素:";

Node<T>*p=phead;

while(p!=NULL)

{

cout<<p->data<<' ';

p=p->next;

}

cout<<"\n-------------------------------------------"<<endl;

};

template<class T>

void myslist<T>::add_head(T e)

{

Node<T>*p=new Node<T>();

p->data=e;

if(length==0)

{

p->next=phead;

p->prior=phead;

phead=p;

ptail=p;

}

else

{

p->next=phead;

p->prior=phead->prior;

phead=p;

}

length++;

};

template<class T>

void myslist<T>::add_tail(T e)

{

Node<T>*p=new Node<T>();

p->data=e;

if(ptail==NULL)

{

phead=p;

ptail=p;

}

else

{

ptail->next=p;

p->prior=ptail;

ptail=p;

}

length++;

};

template<class T>

Node<T>*myslist<T>::GetNode(int pos)

{

if(pos>length||pos<0)

return NULL;

Node<T>*p=phead;

for(int i=0;i<(pos-1);++i)

{

p=p->next;

}

return p;

};

template<class T>

void myslist<T>::add_x(int pos,T e)

{

if(pos<=1)

{

return  add_head(e);

}

else if(pos>length)

{

return add_tail(e);

}

else

{

Node<T>*p1=GetNode(pos-1);

Node<T>*p2=GetNode(pos);

Node<T>*p=new Node<T>();

p->data=e;

p->next=p2;

p->prior=p1;

p2->prior=p;

p1->next=p;

length++;

}

};

template<class T>

void myslist<T>::DeleteNode(int pos)

{

if(pos<1||pos>length)

return;

Node<T>*p1=GetNode(pos-1);

Node<T>*p2=GetNode(pos);

if(p2==ptail)

{

delete p2;

length--;

ptail=p1;

ptail->next=NULL;

}

else

{

p1->next=p2->next;

p2->next->prior=p1;

delete p2;

length--;

}

};

int main()

{

  myslist<int> ilist;

  ilist.add_head(8);

  ilist.add_head(9);

  ilist.add_tail(7);

  ilist.GetNode(2);

  ilist.add_x(2,6);

  ilist.DeleteNode(2);

  cout<<(ilist.IsEmpty()?"鏈表為空？":"鏈表不空")<<endl;

    cout<<"鏈表長度為："<<ilist.GetLength()<<endl;

  ilist.Output();

  return 0;

}