//////////////////////下面給出鏈表LINKEDLIST 的完整申明 LINKEDLIST.H，假設結點的申明在頭文件node.h中//////////
//////////////////////??? 掌握鏈表的必備知識點?? //////////////////////
////////////////////本人倉促整理 應該有不少錯誤,node.h會馬上給出//////////
#include<iostream.h>
#include<stdlib.h>?????????????? //exit(1) 退出函數。
#include"node.h"
template<class t>
enum boolean{false,true}???????? //將FALSE 和 TRUE 固定為0和1。
class linkedlist
{
?? private:
??? node<t> *front,*rear;??????? //指向表頭和表尾的指針。
??? node<t> *prevptr,*currtr;??? //用于訪問數據，插入和刪除結點的指針。
??? int size;
??? int position;
?????? node<t> *getnode(const t& item, node<t> *ptr==null);?? //申請及釋放結點空間的函數。
??? node<t> freenode(node<t> *p);
?? public:
??? linkedlist(void);
??? ~linkedlist(void);
??? linkedlist<t> & operator = (const linkedlist<t> &orglist);?????? //重載賦值運算賦。
?????? int size<void> const;
?????? boolean isempty(void) const;
??? int nextnode(void);??????????????????????????? // 重新定位結點
??? int setposition(int pos);
??? int getposition(void)const;????????
??? void insertat(const t& item);????????????????? //插入結點.
??? void insertafter(const t& item);
??? void deleteat(void);?????????????????????????? //刪除結點.
??? void deleteafter(void);
??? t getdata(void) const;???????????????????????? //修改和訪問數據的函數。
??? void setdata(const t& item);
?????? void clear(void);
};

template <class t>
node<t> *linkedlist<t>::getnode(const t&item ,node<t> *ptr);
{
?node<t> *newnode = new node<t>(item ptr);
?if(!newnode)
?{
??cerr<<"faied"<<e<endl;
??return null'
?}
?return newnode;?????????????????????????????????? // 返回指向新生成接點的指針
}

template <class t>
void *linkedlist<t>::freenode(node<t> *ptr)
{
?if(!ptr)
?{
??cerr<<"invalid node pointer!"<<endl;
??return 0;
?}
?delete ptr;
}

template <class t>??????????????????????????????????? //構造函數 建立一個空鏈表。
linkedlist<t>::linkedlist<void>:front(null),rear(null),prevter(null),currptr(null),size(0),position(-1)
{}

template <class t>
linkedlist::~linkedlist()
{
?clear();
}

template <class t>?????????????????????????????????? //重載賦值運算符的函數.
linkedlist<t> &linkedlist<t>::operator = (const linkedlist<t> *orglist)
{
?node<t> *p = orglist.front;
?clear();???????????????????????????????????????? //這里清空鏈表是為了給復制做好準備么？
?while(p)? //??????????????????????????????????? 這里想不明白，大家幫我詳細解釋下？?
?{
??insertafter(p->data);
??p=p->nextnode();
?}??????? //???????????????????????????????????? ENDL；
setposition(orglist.position);?????????????????????? //這又是什么意思？要去復習重載了。
return *this;???????????????????????????????????????

template <class t>
int linkedlist<t>::size(void) const
{
?return size;
}

template <class t>
boolean linkedlist<t>::isempty(void) const
{
?return size?false:ture;
}

template <class t>
int linkedlist<t>::nextnode(void)
{
?if(position>=0 && position<size)
?{
??position++;?????????????????????????????????? //將當前結點往后移了一位。
??????? prevptr = currptr;
??currptr = currptr->nextnode();
?}
?else
?{
??position = size;??????????????????????????????? //否則將此結點設置為最后結點。
??????? return position;
?}
}

template <class t>?????????????????????????????????? //鏈表中重置當前結點位置的函數。
int linkedlist<t>::setpostion(int pos)
{
?if(!size)
??return -1;
?if(pos<0||pos>size-1)
?{
??cerr<<"error position"<<endl;
??return -1;
?}
?prevptr = null;
?currptr = front;
?position = 0;
?for(int k=0;k<pos;k++)
?{
??position++;
??prevptr = currptr;
??currptr = currptr->nextnode();
?}
?return position;
}

template <class t>
int linkedlist::getposition(void)const
{
?return position;
}

?

template <class t>?????????????????????? //重要：鏈表中在當前結點處插入新結點的函數；
void linkedlist<t>::insertat(const t& item)
{
?node<t> *newnode;
?if(!size)??????????????????????????? //空表中插入。
?{
??newnode = getnode(item, front);
??front = rear = newnode;
??position = 0;
?}
?else if(!prevptr)?????????????????? //在表頭插入?????????????????
?{
??newnode = getnode(item , front);
??????? front = newnode;
?}
?else??????????????????????????????? //在鏈表中間插入插入
?{?
??newnode = getnode(item , front);
??prevptr = insertafter(newnode);
?}
?size++;
?currptr = newnode;????????????????? //新插入的結點為當前結點
}

?

template <class t>?????????????????????? //重要：鏈表中在當前結點后插入新結點的函數；
void linkedlist<t>::insertafter(const t& item)
{
?node<t> *newnode;
?if(!size)??????????????????????????? //空表中插入。
?{
??newnode = getnode(item);
??front = rear = newnode;
??position = 0;
?}
?else if(currptr == rear||!currptr)?? //在鏈表尾插入
?{
??newnode = getnode(item);
??rear->insertafter(newnode);
??prevptr=newnode;
??rear = newnode;
??position = size;
?}
?else
?{
??newnode = getnode(item ,currptr->nextnode());??? //? 在表的中間插入
??currptr->insertafter(newnode);
??prevptr = currptr;
??position++
?}
??size++;
??currptr = newnode;
}

template <class t>
void linkedlist<t>::deleteat(void)????????????????? //重要：刪除當前結點的函數
{
?node<t> *oldnode;
?if(!currptr)???????????????????????????????????? //若表為空或者已到表尾，則給出錯誤提示并返回
?{
??cerr<<"currptr position is invalid!"<<endl;
??return;
?}
?if(!prevtr)?????????????????????????????????????? //刪除表頭結點。
?{
??oldnode = front;
??front = currptr->nextnode();
?}
?else
?{
??oldnode = prevptr->deleteafter();??????????? //刪除的是表中結點；
?}
?if(oldnode == rear)
?{
??rear = prevptr;????????????????????????????? //刪除的是表尾結點，則修改表尾指針和當前位置結點值
??position--;
?}
?currptr = oldnode->nextnode();????????????????? //后續結點作為新的當前結點
?freenode(oldnode);????????????????????????????? //釋放原當前結點
?size--;???????????????????????????????????????? //鏈表大小減1；
}

?

template <class t>
void linkedlist<t>::deleteafter(void)
{
?node<t> *oldnode;
?if(!currptr||currptr==rear)
?{
??cerr<<"current position is invalid!"<<endl;
??return;
?}
?oldnode = currptr->deleteafter();??????????????? //保存被刪除結點的指針并從鏈表中刪除該結點。
?if(oldnode == rear)
?{
??rear == currptr;????????????????????????????? //刪除的是表尾結點。
?}
?freenode(oldnode);
?size--;
}

?

template <class t>????????????????????????????????? //獲取當前結點的函數
T linkedlist<t>::getdata(void) const
{
?if(!size || !currptr)????????????????????????????? //若表為空或已經到達表尾之后，則出錯。
?{
??cerr<<"currptr node not exit!"<<endl;?????????? //給出錯誤信息并退出。
??exit(1);
?}
?return currptr->data;
}

?
template <class t>??????????????????????????????? //鏈表中修改當前結點數據的函數
void linkedlist<t>::setdata(const T& item)
{
?if(!size||!currptr)
?{
??cerr<<"data:current node not exit!"<<endl;
??exit(1);
?}
?currptr->data = item;
}

template <class t>
void linkedlist<t>::clear(void)
{
?node<t> *currptr=front,*nextnode;
?while(currnode)
?{
??nextnode = currnode->nextnode();
??freenode(currnode);
??currnode = nextnode;
?}
?front = rear = prevptr = currptr = null;??????????????? //修改空鏈表數據
??? size = 0;
?position = -1;
}