数据结构-链表.ppt

DataStructure,SoftwareCollegeNortheasternUniversity,Chapter3,LinkedLists,DataStructure,SoftwareCollegeNortheasternUniversity,Overview,LinkedListsProgrammingdetailsCommonErrorDoublyLinkedListsCircularlyLinkedListsexamplesCursorsImplementationofLinkedLists,DataStructure,SoftwareCollegeNortheasternUniversity,Variable-lengtharrays?,Directaccesstoelement(Byindexing)Arraysizeisfixed-length-Toexpandthem,youcreateanew,longerarray,andcopythecontentsoftheoldarrayintothenewarrayThisisusedbyfunctionrealloc()inCThisisslow!LineartimeInsertion/RemovalduetoshiftelementsduetocontiguousstorageinmemoryHalfofthelistneedstobemovedforeitheroperations,DataStructure,SoftwareCollegeNortheasternUniversity,Variable-lengtharrays?,Solution:-Thelistisnotneedtostorecontiguously.-Attachapointertoeachiteminthearray,whichpointstothenextitem.-providestheabilitytoaddorremovetheitemsanywhereinthelistinconstanttimeThisisalinkedlistLinkedlistsareunbounded(maximumnumberofitemslimitedonlybymemory),DataStructure,SoftwareCollegeNortheasternUniversity,TheLinkedListdatastructure,AndataitemplusitspointeriscalledanodeAnodecontainsdataitemandoneormorelinks.-Thelinkisareferencetoanode.-ThelinkoflastnodeissettoNULLa“head”whichisapointertothefirstnodeinthelinkedlist,DataStructure,SoftwareCollegeNortheasternUniversity,43,13,1,NULL,37,7,19,25,Header,AsimplesingleLinkedList,DataStructure,SoftwareCollegeNortheasternUniversity,MemoryStorageoflinkedlist,Wecanaccessallnodesthroughpointer“head”,Heap,DataStructure,SoftwareCollegeNortheasternUniversity,Linkedlists,Eachnodecontainstheaddressofthenextoneinthelist.Wecanaccessthefirstnodethroughpointer“head”twoimportantpointer:-head:thereferencetothefirstnode-tail:thereferencetothelastnode,DataStructure,SoftwareCollegeNortheasternUniversity,Howtoimplementate?,？,DataStructure,SoftwareCollegeNortheasternUniversity,Definitionoftheclass,UsingmulticlassClassofNode(ListNode)ClassofListClassofIteratorTypeofDefinitioncompoundinside,DataStructure,SoftwareCollegeNortheasternUniversity,classList;classListNodefriendclassList;private:intdata;ListNode*link;classListpublic:private:ListNode*first,*last;,ListisaFriendclass,DataStructure,SoftwareCollegeNortheasternUniversity,classListpublic:private:classListNodepublic:intdata;ListNode*link;ListNode*first,*last;,ListNodeisaclassinsideList,DataStructure,SoftwareCollegeNortheasternUniversity,LinkedList:Insertinganewnode(1),intList:Insert(constintx,constinti)Insertanodewithdataequaltoxafterthei-1thelement.(i.e.,wheni=1,insertthenodeasthefirstelement;whenindex=2,insertthenodeafterthefirstelement,andsoon)Iftheinsertionissuccessful,return1.Otherwise,return0.(Ifindexislength+1ofthelist,theinsertionwillfail.)StepsLocatei-1thelementAllocatememoryforthenewnodePointthenewnodetoitssuccessorPointthenewnodespredecessortothenewnode,newNode,ithelement,DataStructure,SoftwareCollegeNortheasternUniversity,InsertpositionCase1：insertinfrontofthefirstnodenewnodelink=first;first=newnode；,（Before）（After）,first,newnode,newnode,first,LinkedList:Insertinganewnode(2),DataStructure,SoftwareCollegeNortheasternUniversity,Case2：insertinthemiddleofthelistnewnodelink=plink;plink=newnode；,newnode,p,newnode,p,（Before）（After）,LinkedList:Insertinganewnode(3),DataStructure,SoftwareCollegeNortheasternUniversity,Case3：Insertintherearnewnodelink=plink;plink=last=newnode；,newnode,newnode,last,p,last,p,（Before）（After）,LinkedList:Insertinganewnode(4),DataStructure,SoftwareCollegeNortheasternUniversity,intList:Insert(constintx,constinti)/Insertanodewithdataequaltoxafterthei-1thListNode*p=first;intk=0;while(p!=NULL/Allocatememoryforthenewnode,LinkedList:Insertinganewnode(5),From0,DataStructure,SoftwareCollegeNortheasternUniversity,if(first=NULL|i=0)/Insertinthefrontoflistnewnodelink=first;if(first=NULL)last=newnode;first=newnode;else/elsenewnodelink=plink;if(plink=NULL)last=newnode;plink=newnode;return1;,LinkedList:Insertinganewnode(6),DataStructure,SoftwareCollegeNortheasternUniversity,whenweinsertanewnode：（1）insertbeforetheithelement，whichpointershouldwegetfirst？（2）illegalinsertingpositionis?Howcanwejudgeinsertingpositionisillegal？（3）Weshouldchangetwolinkswheninserting，Isthereanorder？,？,LinkedList:Insertinganewnode,DataStructure,SoftwareCollegeNortheasternUniversity,Case1:deletethefirstCase2:deletetheothernode,Deletetheithelement,Accordingthepointertoithelement,Canweaccomplishtheoperation？,LinkedList:Deletinganewnode(1),DataStructure,SoftwareCollegeNortheasternUniversity,intList:Remove(inti)/DeletetheithelementNode*p=first,*q;intk=0;while(p!=NULL/Updatefirst,LinkedList:Deletinganewnode(2),DataStructure,SoftwareCollegeNortheasternUniversity,elseq=plink;plink=qlink;if(q=last)last=p;/ifnecessaryupdatelastk=qdata;deleteq;/freethenodepointedbyqreturnk;,LinkedList:Deletinganewnode(3),DataStructure,SoftwareCollegeNortheasternUniversity,LinkedListwithheader,AnodelinkingtothefirstnodeiscalledHeader,theheadercellonlycontainsreferencestothefirst.,Non-emptylistemptylist,0,an,a1,first,last,first,0,last,DataStructure,SoftwareCollegeNortheasternUniversity,Insertinginalinkedlistwithheader,newnodelink=plink;if(plink=NULL)last=newnode;plink=newnode;,DataStructure,SoftwareCollegeNortheasternUniversity,q=plink;plink=qlink;deleteq;if(plink=NULL)last=p;,Deletinginalinkedlistwithheader,DataStructure,SoftwareCollegeNortheasternUniversity,Templateoflinkedlist(1),templateclassList;templateclassListNodefriendclassList;Typedata;/结点数据ListNode*link;/结点链接指针public:ListNode();/链表结点构造函数ListNode(constType/给出当前结点的下一结点地址,DataStructure,SoftwareCollegeNortheasternUniversity,voidInsertAfter(ListNode*p);/在当前结点后插入结点pListNode*RemoveAfter();/摘下当前结点的下一结点;templateclassListListNode*first,*last;public:ListNode*GetNode(constType/创建数据为item，指针为next的新结点,Templateoflinkedlist(2),DataStructure,SoftwareCollegeNortheasternUniversity,List(constType,Templateoflinkedlist(3),DataStructure,SoftwareCollegeNortheasternUniversity,templateListNode:ListNode():link(NULL)templateListNode:ListNode(constType,Implementationoflinkedlist(1),DataStructure,SoftwareCollegeNortheasternUniversity,templateListNode*ListNode:RemoveAfter()/摘下当前结点的下一结点ListNode*tempptr=link;if(link=NULL)returnNULL;/没有下一结点则返回空指针link=tempptrlink;/重新链接returntempptr;/返回下一结点地址,Implementationoflinkedlist(2),DataStructure,SoftwareCollegeNortheasternUniversity,templateListNode*List:GetNode(constType/链表置空，再删去表头结点,Implementationoflinkedlist(3),DataStructure,SoftwareCollegeNortheasternUniversity,templatevoidList:MakeEmpty()/删去链表中除表头结点外的所有其他结点ListNode*q;while(firstlink!=NULL)q=firstlink;firstlink=qlink;/将表头结点后第一个结点从链中摘下deleteq;/释放它last=first;/修改表尾指针,Implementationoflinkedlist(4),DataStructure,SoftwareCollegeNortheasternUniversity,templateintList:Length()const/求单链表的长度ListNode*p=firstlink;/检测指针p指示第一个结点intcount=0;while(p!=NULL)/逐个结点检测p=plink;count+;returncount;,Implementationoflinkedlist(5),DataStructure,SoftwareCollegeNortheasternUniversity,templateListNode*List:Find(Typevalue)/在链表中从头搜索其数据值为value的结点ListNode*p=firstlink;/检测指针p指示第一个结点while(p!=NULL/p在搜索成功时返回找到的结点地址/p在搜索不成功时返回空值,Implementationoflinkedlist(6),DataStructure,SoftwareCollegeNortheasternUniversity,templateListNode*List:Find(inti)/在链表中从头搜索第i个结点，不计头结点if(i*p=firstlink;intj=0;while(p!=NULL,Implementationoflinkedlist(7),DataStructure,SoftwareCollegeNortheasternUniversity,templateintList:Insert(Typevalue,inti)/将含value的新元素插入到链表第i个位置ListNode*p=Find(i-1);/p指向链表第i-1个结点if(p=NULL)return0;ListNode*newnode=/创建结点GetNode(value,plink);if(plink=NULL)last=newnode;plink=newnode;/重新链接return1;,Implementationoflinkedlist(7),DataStructure,SoftwareCollegeNortheasternUniversity,templateType*List:Remove(inti)/从链表中删去第i个结点ListNode*p=Find(i-1),*q;if(p=NULL|plink=NULL)returnNULL;q=plink;plink=qlink;/重新链接Typevalue=newType(qdata);if(q=last)last=p;deleteq;return,Implementationoflinkedlist(8),DataStructure,SoftwareCollegeNortheasternUniversity,templateType*List:Get(inti)/提取第i个结点的数据ListNode*p=Find(i);/p指向链表第i个结点if(p=NULL|p=first)returnNULL;elsereturn,Implementationoflinkedlist(8),DataStructure,SoftwareCollegeNortheasternUniversity,ArrayversusLinkedLists,Linkedlistsaremorecomplextocodeandmanagementthanarrays,buttheyhavesomedistinctadvantages.Dynamic:alinkedlistcaneasilygrowandshrinkinsize.-Wedontneedtoknowhowmanynodeswillbeinthelist.Theyarecreatedinmemoryasneeded.-Incontrast,thesizeofaCarrayisfixedatcompilationtime.Easyandfastinsertionsanddeletions-Toinsertordeleteanelementinanarray,weneedtocopytotemporaryvariablestomakeroomfornewelementsorclosethegapcausedbydeletedelements.-Withalinkedlist,noneedtomoveothernodes.Onlyneedtoresetsomepointers.,DataStructure,SoftwareCollegeNortheasternUniversity,Arraysversuslinkedlists,Space(storage)considerationsAlinkedlistrequirespointerstonodesAnarrayrequiresthemaximumnumberofelementstobeknowninadvance.Ifthatmaximumisnotrequired,spaceiswastedattheendofthearray.,DataStructure,SoftwareCollegeNortheasternUniversity,Arraysversuslinkedlists,TimeconsiderationsMostmethodsinalinkedlistrequiremorestatementsthanthoseinanarray,whichmayindicatemoretimerequiredArraysarequickeratfindingandalteringinthemiddleLinkedlistsarequickeratadditionsandremovalsinthemiddle,DataStructure,SoftwareCollegeNortheasternUniversity,Iteratorclassoflist,Iteratorclassoflistisusedtotraversenodesoflist.priciple：IteratorclassisfriendofListandListNodeIteratorrefertothenodesoflist。DatamembercurrentpointtothenodecurrentlyusedIteratorprividessometestandfindoperation,DataStructure,SoftwareCollegeNortheasternUniversity,enumBooleanFalse,True;templateclassList;templateclassListIterator;templateclassListNode/表结点friendclassList;friendclassListIterator;public:private:Typedata;ListNode*link;,Templatedefinition(1),DataStructure,SoftwareCollegeNortheasternUniversity,templateclassList/链表类public:private:ListNode*first,*last;templateclassListIteratorpublic:ListIterator(constList,Templatedefinition(2),DataStructure,SoftwareCollegeNortheasternUniversity,templateBooleanListIterator:NotNull()/检查链表中当前元素是否非空if(current!=NULL)returnTrue;elsereturnFalse;,current,current,case1returnTruecase2returnFalse,Templatedefinition(3),DataStructure,SoftwareCollegeNortheasternUniversity,templateBooleanListIterator:NextNotNull()/检查链表中下一元素是否非空if(current!=NULL,current,current,case1returnTruecase2returnFalse,Templatedefinition(4),DataStructure,SoftwareCollegeNortheasternUniversity,templateListNode*ListIterator:Firster()/返回链表中头结点的地址current=list.first;returncurrent;,list.first,current,listwithheader,Templatedefinition(5),DataStructure,SoftwareCollegeNortheasternUniversity,templateType*ListIterator:First()/返回链表中第一个元素的地址if(list.firstlink!=NULL)current=list.first-link;return,list.first,current,listwithheader,Templatedefinition(5),DataStructure,SoftwareCollegeNortheasternUniversity,templateType*ListIterator:Next()/返回链表中当前结点的下一个结点的地址if(current!=NULL,current,current,Templatedefinition(6),DataStructure,SoftwareCollegeNortheasternUniversity,intsum(constList,Calculatingusingiterator,DataStructure,SoftwareCollegeNortheasternUniversity,VariationsofLinkedLists,Twoproblems-wecantgetbacktothebeginningofthelist-fromtheend,andwecantgobackwardsthroughthelist.So,circularlinkedlistsanddoublylinkedlistswereinvented.,DataStructure,SoftwareCollegeNortheasternUniversity,VariationsofLinkedLists,CircularlinkedlistsThelastnodepointstothefirstnodeofthelistHowdoweknowwhenwehavefinishedtraversingthelist?(Tip:checkifthepointerofthecurrentnodeisequaltothehead.),Head,DataStructure,SoftwareCollegeNortheasternUniversity,templateclassCircList;templateclassCircListNodefriendclassCircList;public:CircListNode(Typed=0,CircListNode*next=NULL):data(d),link(next)/构造函数private:Typedata;CircListNode*link;,ImplementationofCircularlinkedlists(1),DataStructure,SoftwareCollegeNortheasternUniversity,templateclassCircListpublic:CircList(Typevalue);CircList();intLength()const;BooleanIsEmpty()returnfirstlink=first;BooleanFind(constType,ImplementationofCircularlinkedlists(2),DataStructure,SoftwareCollegeNortheasternUniversity,BooleanPrior();voidInsert(constType,插入,ImplementationofCircularlinkedlists(3),DataStructure,SoftwareCollegeNortheasternUniversity,VariationsofCircularLinkedLists,CircularlinkedlistsconstructanemptyCircularlinkedlist,CircList(constType,List(constType,DataStructure,SoftwareCollegeNortheasternUniversity,templateCircListNode*List:Find(Typevalue)/在链表中从头搜索其数据值为value的结点CircListNode*p=firstlink;/检测指针p指示第一个结点while(p!=first/p在搜索成功时返回找到的结点地址/p在搜索不成功时返回空值,LinkedLists:SearchinginaCLL,DataStructure,SoftwareCollegeNortheasternUniversity,VariationsofLinkedLists,DoublylinkedlistsEachnodepointstonotonlysuccessorbutthepredecessorTherearetwoNULL:atthefirstandlastnodesinthelistAdvantage:givenanode,itiseasytovisititspredecessor.Convenienttotraverselistsbackwards,Head,DataStructure,SoftwareCollegeNortheasternUniversity,p=plLinkrLink=prLinklLink,Non_emptylistemptylist,Doublylinkedlists,DataStructure,SoftwareCollegeNortheasternUniversity,templateclassDblList;templateclassDblNodefriendclassDblList;private:Typedata;/数据DblNode*lLink,*rLink;/指针DblNode(Typevalue,/构造函数DblNode*left,DblNode*right):data(value),lLink(left),rLink(right),ImplementationofDoublylinkedlists(1),DataStructure,SoftwareCollegeNortheasternUniversity,DblNode(Typevalue):data(value),lLink(NULL),rLink(NULL);templateclassDblListpublic:DblList(TypeuniqueVal);DblList();intLength()const;intIsEmpty()returnfirstrlink=first;intFind(constType,ImplementationofDoublylinkedlists(2),DataStructure,SoftwareCollegeNortheasternUniversity,voidFirster()current=first;intFirst();intNext();intPrior();intoperator!()returncurrent!=NULL;voidInsert(constType,ImplementationofDoublylinkedlists(3),DataStructure,SoftwareCollegeNortheasternUniversity,Doublylinkedlists:Searching,DataStructure,SoftwareCollegeNortheasternUniversity,DoublyLinkedLists:constructing,templateDblList:DblLIst(TypeuniqueVal)/双向循环链表的构造函数,创建表头结点first=newDblNode(uniqueVal);firstrLink=firstlLink=first;current=NULL;,DataStructure,SoftwareCollegeNortheasternUniversity,templateintDblList:Find(constType,DoublyLinkedLists:searching,Anothermethod?,DataStructure,SoftwareCollegeNortheasternUniversity,plLink=current;prLink=currentrLink;currentrLink=p;current=currentrLink;currentrLinklLink=current;,1,2,3,4,5,DoublyLinkedLists:Inserting(1),DataStructure,SoftwareCollegeNortheasternUniversity,templatevoidDblList:Insert(constType,DoublyLinkedLists:Inserting(2),DataStructure,SoftwareCollegeNortheasternUniversity,currentrLinklLink=currentlLink;currentlLinkrLink=currentrLink;,1,2,DoublyLinkedLists:Deleting(1),DataStructure,SoftwareCollegeNortheasternUniversity,templatevoidDblList:Remove()if(current!=NULL)DblNode*temp=current;/被删结点current=currentrLink;/下一结点currentlLink=templLink;/从链中摘下templLinkrLink=current;deletetemp;/删去if(current=first)if(IsEmpty()current=NULL;elsecurrent=currentrLink;,DoublyLinkedLists:Deleting(2),DataStructure,SoftwareCollegeNortheasternUniversity,templateintDblList:Length()const/求双向循环链表的长度(不计表头结点)DblNode*p=firstrLink;intcount=0;while(p!=first)p=prLink;count+;returncount;,DoublyLinkedLists:counting,DataStructure,SoftwareCollegeNortheasternUniversity,templateintDblList:First()if(!IsEmpty()/跳过表头结点的第一个current=firstrLink;return1;current=NULL;return0;templateintDblList:Next()if(currentrLink=first)current=NULL;return0;current=currentrLink;return1;,DoublyLinkedLists:Changing,DataStructure,SoftwareCollegeNortheasternUniversity,templateintDblList:Prior()if(currentlLink=first)current=NULL;return0;current=currentlLink;return1;,DoublyLinkedLists:Changing,DataStructure,SoftwareCollegeNortheasternUniversity,DLLcomparedtoSLL,Advantages:Canbetraversedineitherdirection(maybeessentialforsomeprograms)Someoperations,suchasdeletionandinsertingbeforeanode,becomeeasier,Disadvantages:RequiresmorespaceListmanipulationsareslower(becausemorelinksmustbechanged)Greaterchanceofhavingbugs(becausemorelinksmustbemanipulated),DataStructure,SoftwareCollegeNortheasternUniversity,Problem:InsertingorDeletingusenewanddeletetoobtainandreleaseapieceofspacedynamicmanagementIfoperationsofgettingorreturningarefrequently,itmayindicatemoretimerequiredTworesolvingway:CursorImplementationoflinkedlistsusingstaticmemoryInitiallyWeallocatemanynodestolinkedintosparelists,LinkedLists:CursorImplementation,DataStructure,SoftwareCollegeNortheasternUniversity,Towimportantfeaturesoflinkedlist:Thedataarestoredinacollectionofstructure,eachstructurecontainsdataandapointertothenextstructureAnewstructurecanbeobtainedfromthesystemsglobalmemorybyacalltonewandreleasedbyacalltodeleteImplementation:HaveaglobalarrayofstructureArrayindexcanbeusedinplaceofanaddress,LinkedLists:CursorImplementation,DataStructure,SoftwareCollegeNortheasternUniversity,GlobalarrayofstructuresAddress:Arrayindex,#defineSpaceSize1000typedefstructNodeElementTypedata;intnext;Node,CursorSpaceSpacesize;,LinkedLists:CursorImplementation,DataStructure,SoftwareCollegeNortheasternUniversity,Simulationofmallocandfree,Equivalentformallocandfreeincursorspacearray:Freelist:cellsthatarenotinanylistsUsecell0asaheaderoffreelistAvalueof0fornextisequivalenttoNULL,freelisthead,LinkedLists:CursorImplementation,header,DataStructure,SoftwareCollegeNortheasternUniversity,LinkedLists:CursorImplementation,CursorAlloctosimulatemalloc(),DataStructure,SoftwareCollegeNortheasternUniversity,intCursorAlloc(void)/allocateacellfromfreelistintp;p=CursorSpace0.next;CursorSpace0.next=CursorSpacep.next;returnp;/endofCursorAlloc,LinkedLists:CursorImplementation,DataStructure,SoftwareCollegeNortheasternUniversity,LinkedLists:CursorImplementation,CursorFreetosimulateFree(),DataStructure,SoftwareCollegeNortheasternUni