數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)16-linkedl

數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)(16)王麗蘋lipingwang@4/21/20231.ImplementationofLinkedList2BookP225改進(jìn)的思路KeepingSupposeanapplicationprocesseslistentriesinorderorreferstothesameentryseveraltimesbeforeprocessinganotherentry.thelast-usedPositionRememberthelast-usedpositioninthelistand,ifthenextoperationreferstothesameoralaterposition,starttracingthroughthelistfromthislast-usedposition.4/21/20232.ImplementationofLinkedList2template<classList_entry>classList{public: ~List(); List(); List(constList<List_entry>©); voidoperator=(constList<List_entry>©); intsize()const; boolfull()const; boolempty()const; voidclear(); voidtraverse(void(*visit)(List_entry&)); Error_coderetrieve(intposition,List_entry&x)const; Error_codereplace(intposition,constList_entry&x); Error_coderemove(intposition,List_entry&x); Error_codeinsert(intposition,constList_entry&x);4/21/20233.ImplementationofLinkedList2protected://Datamembersforthelinkedlist//implementationnowfollow. intcount; mutableintcurrent_position; mutableNode<List_entry>*current; Node<List_entry>*head;//Thefollowingauxiliaryfunctionisusedto//locatelistpositions voidset_position(intposition)const;};4/21/20234.C++中的關(guān)鍵字：mutable關(guān)鍵字mutable的含義：類的mutable成員能夠被任何成員函數(shù)修改，即使是const修飾的常量成員函數(shù)也能夠?qū)λM(jìn)行修改。4/21/20235.ImplementationofLinkedList2List<List_entry>::List(){ count=0; head=NULL; current_position=0; current=NULL;}4/21/20236.ImplementationofLinkedList2template<classList_entry>voidList<List_entry>::set_position(intposition)const/*Pre:positionisavalidpositionintheList:0<=position<count.Post:ThecurrentNodepointerreferencestheNodeatposition.*/{ if(position<current_position){//muststartoveratheadoflist current_position=0; current=head; } for(;current_position!=position;current_position++) current=current->next;}4/21/20237.ImplementationofLinkedList2template<classList_entry>Error_codeList<List_entry>::insert(intposition,constList_entry&x){ if(position<0||position>count) returnrange_error; Node<List_entry>*new_node,*previous,*following; if(position>0){

set_position(position-1); previous=current; following=previous->next; } elsefollowing=head; new_node=newNode<List_entry>(x,following); if(new_node==NULL) returnoverflow;4/21/20238.ImplementationofLinkedList2 if(position==0){ head=new_node; //shouldbeadded current_position=0; current=head; } else{ previous->next=new_node; //shouldbeadded set_position(position); } count++; returnsuccess;}4/21/20239.ImplementationofLinkedList2

position-1 positionpreviousfollowingPosition>0Position=0followingheadnew_nodenew_node4/21/202310.ImplementationofLinkedList2template<classList_entry>Error_codeList<List_entry>::remove(intposition,List_entry&x){ if(position<0||position>=count) returnrange_error; Node<List_entry>*previous,*following; if(position>0){

set_position(position-1); previous=current; following=previous->next; previous->next=following->next; }4/21/202311.ImplementationofLinkedList2 else{ following=head; head=head->next; //shouldbeadded current_position=0; current=head; }x=following->entry; deletefollowing; count--; returnsuccess;}4/21/202312.ImplementationofLinkedList2 position-1 positionpreviousfollowingPosition>0Position=0Position=0followinghead4/21/202313.ImplementationofLinkedList2template<classList_entry>Error_codeList<List_entry>::retrieve(intposition,List_entry&x)const{ if(position<0||position>=count) returnrange_error; Node<List_entry>*p_node; set_position(position); x=current->entry; returnsuccess;}4/21/202314.ImplementationofLinkedList2目錄LinkList2下例程上機(jī)完成LinkList24/21/202315.進(jìn)一步的改進(jìn)Keepingthelast-usedPosition當(dāng)插入的位置在最后一次使用的位置之后時(shí)，效率較高。當(dāng)插入的位置在最后一次使用的位置之前時(shí)，需要從鏈表頭部重新計(jì)數(shù)。改進(jìn)方法：將單鏈表變?yōu)殡p鏈表4/21/202316.DoublyLinkedListsBOOKP227figure6.34/21/202317.DoublyLinkedLists//定義雙鏈表節(jié)點(diǎn)類型template<classNode_entry>structNode{//datamembers Node_entryentry; Node<Node_entry>*next; Node<Node_entry>*back;//constructors Node(); Node(Node_entryitem,Node<Node_entry>*link_back=NULL, Node<Node_entry>*link_next=NULL);};4/21/202318.DoublyLinkedListstemplate<classList_entry>voidList<List_entry>::set_position(intposition)const/*Pre:positionisavalidpositionintheList:0<=position<count.Post:ThecurrentNodepointerreferencestheNodeatposition.*/{ if(current_position<=position) for(;current_position!=position;current_position++) current=current->next; else for(;current_position!=position;current_position--) current=current->back;}4/21/202319.DoublyLinkedLists4/21/202320.DoublyLinkedLists(BOOKP229figure6.4)

Error_codeList<List_entry>::insert(intposition,constList_entry&x){ Node<List_entry>*new_node,*following,*preceding; if(position<0||position>count)returnrange_error; if(position==0){//在第0號(hào)位置插入的特殊情況 if(count==0)following=NULL; else{ set_position(0); following=current; } preceding=NULL; } else{//一般情況，在鏈表中間或者末尾插入 set_position(position-1); preceding=current; following=preceding->next; }//給following和preceding指針賦初始值。4/21/202321.DoublyLinkedLists(BOOKP229figure6.4)

new_node=newNode<List_entry>(x,preceding,following);//產(chǎn)生新節(jié)點(diǎn) if(new_node==NULL)returnoverflow; if(preceding!=NULL)preceding->next=new_node; if(following!=NULL)following->back=new_node; //調(diào)整current和current_position指針current=new_node; current_position=position;

//Shouldbeadded. if(position==0)head=new_node; count++; returnsuccess;}4/21/202322.DoublyLinkedLists

position-1 positionprecedingfollowingPosition>0Position=0Count！=0followingheadnew_nodenew_nodenew_nodePosition=0Count=04/21/202323.DoublyLinkedListsError_codeList<List_entry>::remove(intposition,List_entry&x){ if(position<0||position>=count) returnrange_error; Node<List_entry>*previous,*following; if(position>0){ set_position(position-1); previous=current; following=previous->next; previous->next=following->next; if(following->next)following->next->back=previous; }4/21/202324.DoublyLinkedLists else{ following=head; head=head->next; if(head)head->back=NULL; //shouldbeadded current_position=0; current=head; }x=following->entry; deletefollowing; count--; returnsuccess;}4/21/202325.DoublyLinkedLists position-1 positionpreviousfollowingPosition>0Position=0Position=0followinghead4/21/202326.DoublyLinkedListstemplate<classList_entry>classList{public: ~List(); List(); List(constList<List_entry>©); voidoperator=(constList<List_entry>©); intsize()const; boolfull()const; boolempty()const; voidclear(); voidtraverse(void(*visit)(List_entry&)); Error_coderetrieve(intposition,List_entry&x)const; Error_codereplace(intposition,constList_entry&x); Error_coderemove(intposition,List_entry&x); Error_codeinsert(intposition,constList_entry&x);4/21/202327.DoublyLinkedListsprotected://Datamembersforthelinkedlistimplementationnowfollow. intcount; mutableintcurrent_position; mutableNode<List_entry>*current; Node<List_entry>*head;//Thefollowingauxiliaryfunctionisusedt