数据结构与算法分析lecture3(链表)

Linkedlistimplementation用一组任意的存储单元存储线性表的数据元素(这组单元可以是连续的，也可以是不连续的)Singlylinkedlist:nextDoublylinkedlist:next,prev(previous)BheadCAfenceheadCBAfencelist=〔HAT，CAT，EAT，FAT，…...HAT,VAT，WAT〕以存储单元的地址为其值的变量，叫指针型变量。SinglylinkedlistimplementationBheadCA//Singly-linkedlistnodeTemplate<classElem>classLink{public:Elemelement; //valueforthisnodeLink*next; //pointertonextnodeinlistLink(constElem&elemval;Link*nextval=NULL){element=elemval;next=nextval;}Link(Link*nextval=NULL){next=nextval;}};CBA12323head1220fence15tail23head1020fence1215tail?insertLinkedlistimplementationTemplate<classElem>classLlist:publicList<Elem>{Private:Link<Elem>*head;//pointertolistheaderLink<Elem>*tail;//pointertolastelementinlistLink<Elem>*fence;//lastelementonleftsideintleftcnt; //sizeofleftpartitionintrightcnt; //sizeofrightpartitionVoidinit(){fence=tail=head=newLink<Elem>;

leftcnt=rightcnt=0;}Voidremoveall()//returnlinknodestofreestore{while(head!=NULL){fence=head;head=head->next;deletefence;}}Public:

Llist(intsize=DefaultListSize){init();}~Llist() {removeall();}//destructorvoidclear(){removeall();init()}

boolinsert(constElem&);

boolappend(constElem&);

boolremove(Elem&);voidsetStart(){fence=head;

rightcnt+=leftcnt;

leftcnt=0;}voidsetEnd(){fence=tail;

leftcnt+=rightcnt;

rightcnt=0;}Voidprev();Voidnext(){if(fence!=tail) //Don’tmovefenceifrightempty{fence=fence->next;rightcnt--;leftcnt++;}}intleftLength()const{returnleftcnt;}IntrightLength()const{returnrightcnt;}boolsetpos(intpos);boolgetvalue(Elem&it)const{if(rightLength()==0)returnfalse;it=fence->next->element;returntrue;}voidprint()const;};Fence->next=newLink<Elem>(item,fence->next);231220fence15tail231020fence1215tailfenceheadtailheadheadinsert未定义的链表类成员函数的实现template<classElem>//insertatfrontofrightpartitionboolLlist<Elem>::insert(constElem&item){

fence->next=newLink<Elem>(item,fence->next);If(tail==fence)tail=fence->next;//newtail

rightcnt++;returntrue;}template<classElem>//appendElemtoendofthelistboolLList<Elem>::append(constElem&item){tail=tail->next=newLink<Elem>(item,NULL);

rightcnt++;returntrue;}//removeandreturnfirstEleminrightpartitiontemplate<classElem>boolLlist<Elem>::remove(Elem&it){if(fence->next==NULL)returnfalse;//emptyrightit=fence->next->element;//remembervalueLink<Elem>*ltemp=fence->next;//rememberlinknodefence->next=ltemp->next;//removefromlistif(tail=ltemp)tail=fence;//resettaildeleteltemp;//reclaimspacerightcnt--;returntrue;}//movefenceonestepleft;nochangeifleftisemptytemplate<classElem>voidLlist<Elem>::prev(){Link<Elem>*temp=head;if(fence==head)return;//nopreviousElem

while(temp->next!=fence)temp=temp->next;fence=temp;

leftcnt--;

rightcnt++;}//setthesizeofleftpartitiontopostemplate<classElem>boolLList<Elem>::setpos(intpos){if((pos<0)||(pos>rightcnt+leftcnt))returnfalse;fence=head;for(inti=0;i<pos;i++)fence=fence->next;returntrue;}template<classElem>voidLList<Elem>::print()const{Link<Elem>*temp=head;cout<<“<〞;while(temp!=fence){cout<<temp->next->element<<“〞;temp=temp->next;}cout<<“|〞;while(temp->next!=NULL){cout<<temp->next->element<<“〞;temp=temp->next;}cout<<“>\n〞;}insert231210fence……插入10:231210fence……(3)(1)(2)fence->next=newLink<Elem>(item,fence->next);Link<Elem>*ltemp=fence->next;//rememberlinknodfence->next=ltemp->next;//removefromlistdelete231210fence……231210fence……(1)(2)DoublyLinkedlists231220fence15tailhead231220fence15tailheadDoublylinkedlistnodeimplementation//Doublylinkedlistnodewithfreelistsupporttemplate<classElem>classLink{private:staticLink<Elem>*freelist;//headofthefreelistpublic:Elemelement; //valueforthisnodeLink*next; //pointertonextnodeinlistLink*prev; //pointertopreviousnode

Link(constElem&e;Linkprevp=NULL,Link*nextval=NULL) {element=e;prev=prevp;next=nextp;} Link(Link*prevp=NULL,Link*nextp=NULL) {prev=prevp;next=nextp;}

//overloadnewanddeleteoperatorsforfreelist void*operationnew(size_t); voidoperationdelete(void*);};template<classElem>Link<Elem>*Link<Elem>::freelist=NULL;template<classElem>//overloadfornewoperationvoid*Link<Elem>::operationnew(size_t){ if(freelist==NULL)return::newLink;//createspace Link<Elem>*temp=freelist;//cantakefromfreelist freelist=freelist->next; returntemp; //returnthelink}template<classElem>//overloadfordeleteoperationvoidLink<Elem>::operationdelete(void*ptr){ ((Link<Elem>*)ptr)->next=freelist;//putonfreelist freelist=(Link<Elem*>)ptr;}insert201210fence……插入10:23201210fence……23(1)(2)(3)(4)(5)tail=tail->next=newLink<Elem>(item,tail,NULL);If(Itemp->next!=NULL)Itemp->next->prev=fence;elsetail=fence;//resettalfence->next=Itemp->next;//removefromlist

delete2012fence……232012fence……23itimplementationforinsertappendremoveandprevtemplate<classElem>//insertatfrontofrightpartitionboolLlist<Elem>::insert(constElem&item){fence->next=newLink<Elem>(item,fence,fence->next);if(fence->next->next!=NULL)//ifnotdeletingatendfence->next->next->prev=fence->next;if(tail=fence)//appendingnewelemtail=fence->next;//sosettail

rightcnt++;//addedtorightreturntrue;}template<classElem>//appendelemtoendofthelistboolLList<Elem>::append(constElem&item){tail=tail->next=newLink<Elem>(item,tail,NULL);rightcnt++;//addedtorightreturntrue;}//removeandreturnfirsteleminrightpartitiontemplate<classElem>boolLList<Elem>::remove(Elem&it){if(fence->next==NULL)

//emptyrightreturnfalse;//remembervalueit=fence->next->element;//rememberlinknodeLink<Elem>*itemp=fence->next;

if(itemp->next!=NULL)

itemp->next->prev=fence;elsetail=fence;//resettailfence->next=itemp->next;//removefromlistdeleteitemp;//reclaimspacerightcnt--;//removedfromrightreturntrue;}//movefenceonestepleft;no