//////////////////////下面給出鏈表LINKEDLIST 的完整申明 LINKEDLIST.H，假設(shè)結(jié)點(diǎn)的申明在頭文件node.h中//////////
//////////////////////??? 掌握鏈表的必備知識(shí)點(diǎn)?? //////////////////////
////////////////////本人倉促整理 應(yīng)該有不少錯(cuò)誤,node.h會(huì)馬上給出//////////
#include<iostream.h>
#include<stdlib.h>?????????????? //exit(1) 退出函數(shù)。
#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;??? //用于訪問數(shù)據(jù)，插入和刪除結(jié)點(diǎn)的指針。
??? int size;
??? int position;
?????? node<t> *getnode(const t& item, node<t> *ptr==null);?? //申請(qǐng)及釋放結(jié)點(diǎn)空間的函數(shù)。
??? node<t> freenode(node<t> *p);
?? public:
??? linkedlist(void);
??? ~linkedlist(void);
??? linkedlist<t> & operator = (const linkedlist<t> &orglist);?????? //重載賦值運(yùn)算賦。
?????? int size<void> const;
?????? boolean isempty(void) const;
??? int nextnode(void);??????????????????????????? // 重新定位結(jié)點(diǎn)
??? int setposition(int pos);
??? int getposition(void)const;????????
??? void insertat(const t& item);????????????????? //插入結(jié)點(diǎn).
??? void insertafter(const t& item);
??? void deleteat(void);?????????????????????????? //刪除結(jié)點(diǎn).
??? void deleteafter(void);
??? t getdata(void) const;???????????????????????? //修改和訪問數(shù)據(jù)的函數(shù)。
??? 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;?????????????????????????????????? // 返回指向新生成接點(diǎn)的指針
}

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

template <class t>??????????????????????????????????? //構(gòu)造函數(shù) 建立一個(gè)空鏈表。
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>?????????????????????????????????? //重載賦值運(yùn)算符的函數(shù).
linkedlist<t> &linkedlist<t>::operator = (const linkedlist<t> *orglist)
{
?node<t> *p = orglist.front;
?clear();???????????????????????????????????????? //這里清空鏈表是為了給復(fù)制做好準(zhǔn)備么？
?while(p)? //??????????????????????????????????? 這里想不明白，大家?guī)臀以敿?xì)解釋下？?
?{
??insertafter(p->data);
??p=p->nextnode();
?}??????? //???????????????????????????????????? ENDL；
setposition(orglist.position);?????????????????????? //這又是什么意思？要去復(fù)習(xí)重載了。
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++;?????????????????????????????????? //將當(dāng)前結(jié)點(diǎn)往后移了一位。
??????? prevptr = currptr;
??currptr = currptr->nextnode();
?}
?else
?{
??position = size;??????????????????????????????? //否則將此結(jié)點(diǎn)設(shè)置為最后結(jié)點(diǎn)。
??????? return position;
?}
}

template <class t>?????????????????????????????????? //鏈表中重置當(dāng)前結(jié)點(diǎn)位置的函數(shù)。
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>?????????????????????? //重要：鏈表中在當(dāng)前結(jié)點(diǎn)處插入新結(jié)點(diǎn)的函數(shù)；
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;????????????????? //新插入的結(jié)點(diǎn)為當(dāng)前結(jié)點(diǎn)
}

?

template <class t>?????????????????????? //重要：鏈表中在當(dāng)前結(jié)點(diǎn)后插入新結(jié)點(diǎn)的函數(shù)；
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)????????????????? //重要：刪除當(dāng)前結(jié)點(diǎn)的函數(shù)
{
?node<t> *oldnode;
?if(!currptr)???????????????????????????????????? //若表為空或者已到表尾，則給出錯(cuò)誤提示并返回
?{
??cerr<<"currptr position is invalid!"<<endl;
??return;
?}
?if(!prevtr)?????????????????????????????????????? //刪除表頭結(jié)點(diǎn)。
?{
??oldnode = front;
??front = currptr->nextnode();
?}
?else
?{
??oldnode = prevptr->deleteafter();??????????? //刪除的是表中結(jié)點(diǎn)；
?}
?if(oldnode == rear)
?{
??rear = prevptr;????????????????????????????? //刪除的是表尾結(jié)點(diǎn)，則修改表尾指針和當(dāng)前位置結(jié)點(diǎn)值
??position--;
?}
?currptr = oldnode->nextnode();????????????????? //后續(xù)結(jié)點(diǎn)作為新的當(dāng)前結(jié)點(diǎn)
?freenode(oldnode);????????????????????????????? //釋放原當(dāng)前結(jié)點(diǎn)
?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();??????????????? //保存被刪除結(jié)點(diǎn)的指針并從鏈表中刪除該結(jié)點(diǎn)。
?if(oldnode == rear)
?{
??rear == currptr;????????????????????????????? //刪除的是表尾結(jié)點(diǎn)。
?}
?freenode(oldnode);
?size--;
}

?

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

?
template <class t>??????????????????????????????? //鏈表中修改當(dāng)前結(jié)點(diǎn)數(shù)據(jù)的函數(shù)
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;??????????????? //修改空鏈表數(shù)據(jù)
??? size = 0;
?position = -1;
}