lecture5 Doubly linked lists and stacks

《lecture5 Doubly linked lists and stacks》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、ListsCS122AlgorithmsandDataStructures
Alistisavarying-length,linearcollectionofhomogeneouselements.
Linearmeanseachlistelement(exceptthefirst)hasauniquepredecessor,andeachelement(exceptthelast)hasauniqueMW11:00am-12:15pm,MSEC101successorInstructor:XiaoQin
Inalinearstructure,compo

2、nentscanonlyLecture5:DoublyLinkedListsandbeaccessedsequentiallyoneaftertheotherLinkedStacks2AnInsertAlgorithmforSortedListsclassSortedList
Sortedlist:listelementssortedinSortedListascendingorderPrivatedata:~SortedListIsEmpty
Howwouldthealgorithmtoinserthead5817Printanitemintoasor

3、tedlinkedlist?InsertTopInsertDeleteTopDelete34ADTSortedListOperationsstructNodeType//SPECIFICATIONFILEDYNAMIC-LINKEDSORTEDLISTTransformers(slist.h)–InsertToptypedefintItemType;//Typeofeachcomponent–Insertchangestate//issimpletypeorstringtype–DeleteTop–DeletestructNodeType{ItemTyp

4、eitem;//Pointertoperson’snameObserversNodeType*next;//linktonextnodeinlist–Printobservestate};–IsEmptytypedefNodeType*NodePtr;651InsertalgorithmforInserting12intoaSortedListSortedListprevPtrcurrPtr
findproperpositionforthenewelementinthesortedlistusingtwopointersprevPtrandcurrPtr

5、,whereprevPtrtrailsbehindPrivatedata:currPtr
obtainanodeforinsertionandplaceitemhead5817init
insertthenodebyadjustingpointers78FindingProperPositionfor12FindingProperPositionfor12prevPtrcurrPtrprevPtrcurrPtrNULLPrivatedata:Privatedata:head5817head5817while(currPtr!=NULL&&item>cur

6、rPtr->info)while(currPtr!=NULL&&item>currPtr->info){{prevPtr=currPtr;prevPtr=currPtr;currPtr=currPtr->next;currPtr=currPtr->next;}}910Inserting’12’intoProperPositionFindingProperPositionfor12location->next=currPtr;if(prevPtr==NULL)head=location;prevPtrcurrPtrelseprevPtr->next=loc

7、ation;prevPtrcurrPtrPrivatedata:Privatedata:head5817head5817while(currPtr!=NULL&&item>currPtr->info){prevPtr=currPtr;12currPtr=currPtr->next;}11122voidSortedList::Insert(ItemTypeitem)//IMPLEMENTATIONDYNAMIC-LINKEDSORTEDLIST//Pre:itemisassigned&&listcomponentsinascendingorder//(sl

8、ist.cpp)//Post:newnodecontainingitemisin