#ifndef NODE
#define NODE
#include"base.h"
//模板类,链表--
template
class Node
{
public:
T value;
Node* prev;//前驱
Node* next;//后继
Node()
{
prev=NULL;
next=NULL;
}
~Node(){}
};
template
class LinkList
{
private:
Node* link;
Node* real;
int len;
public:
LinkList()
{
len=0;
real=link=new Node;
link->next=NULL;
link->prev=link;
}
~LinkList()
{
Node* pnode,*temp;
pnode = link->next;
while(pnode)
{
temp=pnode->next;
delete pnode;
pnode=temp;
}
delete link;
link=NULL;
len =0;
}
int InitLink();
// 头 尾 随机 插 改 删 等
int PushInfoFrount(T t);
T PopInfoFrount();
int PushInfoReal(T t);
T PopInfoReal();
int InsertInfo(const int count,T t);
T DeleteInfo(const int count);
int SetInfo(const int count,T t);//修改
T GetInfo(const int count); //返回指定位置对象
int isEmpty();
//获得前驱 后继
Node<T>* Next(const int count);
Node<T>* Prev(const int count);
int GetLen();
};
template
int LinkList::GetLen()
{
if(!isEmpty())
return -1;
return len;
}
template
int LinkList::isEmpty()
{
if(link == NULL)
return false;
return true;
}
template
int LinkList::InitLink()
{
Node* pnode,*temp;
pnode = link->next;
if(!isEmpty())
return false;
while(pnode!=link || pnode!=NULL)
{
temp=pnode->next;
delete pnode;
pnode=temp;
}
//第二种:可以使用 PopInfoFrount();
link->prev=link;
link->next=NULL;
len =0;
}
//----------------------------
//头 插 头删
template
int LinkList::PushInfoFrount(T t)
{
if(!isEmpty())return 0;
Node* newNode=new Node;
newNode->value =t;
newNode->next=link->next;
newNode->prev=link;
//如果是第一次插入
if(len == 0)
{
link->next=newNode;
//调整尾指针 因为如果一直头插入 real永远是最后一个,如果不调整,那他永远指向Link.
real=newNode;
len++;
return true;
}
//否则...
link->next->prev=newNode;
link->next=newNode;
len ++;
return true;
}
template
T LinkList::PopInfoFrount()
{
if( !isEmpty() || GetLen()<=0 )exit(-1);
Node<T>* pnode=link->next;
T t=pnode->value;
if(pnode->next!=NULL || pnode!=link)
pnode->next->prev=pnode->prev;
pnode->prev->next=pnode->next;//link->next = pnode->next;
delete pnode;
pnode =NULL;
len --;
//如果链表没有对象 设置尾指针
if(len == 0)
{
real=link;
}
return t;//返回对象
}
//尾插 尾删
template
int LinkList::PushInfoReal(T t)
{
if(!isEmpty())return -1;
Node<T>* newNode=new Node<T>;
newNode->value=t;
newNode->next=real->next;
newNode->prev=real;
real->next=newNode;
real=newNode;
len++;
return true;
}
template
T LinkList::PopInfoReal()
{
if(!isEmpty()|| GetLen()==0 ) exit(-1);
T t=real->value;
real->prev->next=real->next;
Node<T>* pnode=real;
real=real->prev;//指向前驱
delete pnode;
pnode =NULL;
len--;
return t;
}
template
int LinkList::InsertInfo(const int count,T t)
{
if(!isEmpty()|| count<=0 || count > GetLen() ) return -1;
int i=1;
Node* pnode=link->next;
Node* newNode=new Node;
newNode->value = t;
while(pnode!=NULL)
{
if(i==count)break;
pnode=pnode->next;
i++;
}
if(pnode==NULL || i>count)return -1;
//如果是最后一个位置
if(pnode->next==NULL)
{
newNode->next=pnode->next;
newNode->prev=pnode;
pnode->next=newNode;
len++;
real=newNode;//设置尾指针
return true;
}
newNode->next=pnode->next;
newNode->prev=pnode;
pnode->next->prev=newNode;
pnode->next=newNode;
len++;
return true;
}
template
T LinkList::DeleteInfo(const int count)
{
if(!isEmpty()|| GetLen()<=0 || count > GetLen()) exit(-1);
//如果是最后一个 直接PopInfoReal
if(count == GetLen())
{
return PopInfoReal();
}
//如果是头 直接PopInfoFrount;
if(count == 1)
{
return PopInfoFrount();
}
//否则执行其他位置的删除
int i=1;
T t;
Node<T>* pnode;
pnode=link->next;
while(pnode!=NULL)
{
if(i == count) break;
++i;
pnode=pnode->next;
}
if(pnode==NULL || i>count)exit(-1);
t=pnode->value;
pnode->next->prev=pnode->prev;
pnode->prev->next=pnode->next;
delete pnode;
pnode=NULL;
len--;
return t;
}
// 修改 set
template
int LinkList::SetInfo(const int count,T t)
{
if(!isEmpty()|| GetLen==0 || count> GetLen())return -1;
if(count == 1)
{
link->next->value=t;return true;
}
if(count == GetLen())
{
real->value=t;return true;
}
Node<T>* pnode=link->next;
int i=1;
while(pnode)
{
if(i == count)break;
i++;
pnode=pnode->next;
}
if(pnode==NULL || i>count)return -1;
pnode->value=t;
return true;
}
template
T LinkList::GetInfo(const int count)
{
if(!isEmpty()|| GetLen()==0 || count > GetLen()) exit(-1);
if(count ==1)
return link->next->value;
if(count==GetLen())
return real->value;
int i=1;
Node<T>* pnode=link->next;
while(pnode)
{
if(i == count)break;
i++;
pnode=pnode->next;
}
if(pnode == NULL || i>count)exit(-1);
return pnode->value;
}
//获取 前驱后继 返回节点指针
template
Node* LinkList::Next(const int count)
{
if(!isEmpty() || count <=0 || count>GetLen())exit(-1);
int i=1;
Node<T>* pnode=link;
while(pnode)
{
if(i == count)break;
i++;
pnode =pnode->next;
}
if(pnode==NULL || i>count)exit(-1);
return pnode->next;
}
template
Node* LinkList::Prev(const int count)
{
if(!isEmpty() || count <=0 || count>GetLen())exit(-1);
int i=1;
Node<T>* pnode=link->next;
while(pnode)
{
if(i == count)break;
i++;
pnode =pnode->next;
}
if(pnode==NULL || i>count)exit(-1);
return pnode->prev;
}
#endif