Chapter8DataAbstractions?PearsonAddison-Wesley.Allrightsreserved第1頁Chapter8:DataAbstractions8.1DataStructureFundamentals8.2ImplementingDataStructures8.3AShortCaseStudy8.4CustomizedDataTypes8.5ClassesandObjects8.6PointersinMachineLanguage第2頁BasicDataStructuresHomogeneousarrayHeterogeneousarrayListStackQueueTree第3頁Figure8.1Lists,stacks,andqueues第4頁TerminologyforListsList:AcollectionofdatawhoseentriesarearrangedsequentiallyHead:ThebeginningofthelistTail:Theendofthelist第5頁TerminologyforStacksStack:AlistinwhichentriesareremovedandinsertedonlyattheheadLIFO:Last-in-first-outTop:Theheadoflist(stack)Bottomorbase:Thetailoflist(stack)Pop:ToremovetheentryatthetopPush:Toinsertanentryatthetop第6頁TerminologyforQueuesQueue:AlistinwhichentriesareremovedattheheadandareinsertedatthetailFIFO:First-in-first-out第7頁Figure8.2Anexampleofanorganizationchart第8頁TerminologyforaTreeTree:AcollectionofdatawhoseentrieshaveahierarchicalorganizationNode:AnentryinatreeRootnode:ThenodeatthetopTerminalorleaf

node:Anodeatthebottom第9頁TerminologyforaTree(continued)Parent:ThenodeimmediatelyaboveaspecifiednodeChild:AnodeimmediatelybelowaspecifiednodeAncestor:Parent,parentofparent,etc.Descendent:Child,childofchild,etc.Siblings:Nodessharingacommonparent第10頁TerminologyforaTree(continued)Binarytree:AtreeinwhicheverynodehasatmosttwochildrenDepth:Thenumberofnodesinlongestpathfromroottoleaf第11頁Figure8.3Treeterminology第12頁AdditionalConceptsStaticDataStructures:SizeandshapeofdatastructuredoesnotchangeDynamicDataStructures:SizeandshapeofdatastructurecanchangePointers:Usedtolocatedata第13頁Figure8.4Novelsarrangedbytitlebutlinkedaccordingtoauthorship第14頁StoringArraysHomogeneousarraysRow-majororderversuscolumnmajororderAddresspolynomialHeterogeneousarraysComponentscanbestoredoneaftertheotherinacontiguousblockComponentscanbestoredinseparatelocationsidentifiedbypointers第15頁Figure8.5Thearrayoftemperaturereadingsstoredinmemorystartingataddressx第16頁Figure8.6Atwo-dimensionalarraywithfourrowsandfivecolumnsstoredin

rowmajororder第17頁Figure8.7StoringtheheterogeneousarrayEmployee第18頁StoringListsContiguouslist:ListstoredinahomogeneousarrayLinkedlist:ListinwhicheachentriesarelinkedbypointersHeadpointer:PointertofirstentryinlistNILpointer:A“non-pointer”valueusedtoindicateendoflist第19頁Figure8.8Namesstoredinmemoryasacontiguouslist第20頁Figure8.9Thestructureofalinkedlist第21頁Figure8.10Deletinganentryfromalinkedlist第22頁Figure8.11Insertinganentryintoalinkedlist第23頁StoringStacksandQueuesStacksusuallystoredascontiguouslistsQueuesusuallystoredasCircularQueuesStoredinacontiguousblockinwhichthefirstentryisconsideredtofollowthelastentryPreventsaqueuefromcrawlingoutofitsallottedstoragespace第24頁Figure8.12Astackinmemory第25頁Figure8.13Aqueueimplementationwithheadandtailpointers

第26頁StoringBinaryTreesLinkedstructureEachnode=datacells+twochildpointersAccessedviaapointertorootnodeContiguousarraystructureA[1]=rootnodeA[2],A[3]=childrenofA[1]A[4],A[5],A[6],A[7]=childrenofA[2]andA[3]第27頁Figure8.14Thestructureofanodeinabinarytree第28頁Figure8.15Theconceptualandactualorganizationofabinarytreeusingalinked

storage

system第29頁Figure8.16Atreestoredwithoutpointers第30頁Figure8.17Asparse,unbalancedtreeshowninitsconceptualformandasitwouldbe

storedwithoutpointers第31頁ManipulatingDataStructuresIdeally,adatastructureshouldbemanipulatedsolelybypre-definedprocedures.Example:Astacktypicallyneedsatleastpushandpopprocedures.Thedatastructurealongwiththeseproceduresconstitutesacompleteabstracttool.第32頁Figure8.18Aprocedureforprintingalinkedlist第33頁CaseStudyProblem:Constructanabstracttoolconsistingofalistofnamesinalphabeticalorderalongwiththeoperations search,print,andinsert.第34頁Figure8.19ThelettersA

throughMarrangedinan

orderedtree第35頁Figure8.20Thebinarysearchas

itwouldappearifthelistwereimplementedasalinked

binarytree第36頁Figure8.21ThesuccessivelysmallertreesconsideredbytheprocedureinFigure8.18

whensearchingfortheletterJ第37頁Figure8.22Printingasearchtreeinalphabeticalorder第38頁Figure8.23Aprocedureforprintingthedatainabinarytree第39頁Figure8.24Insertingtheentry

MintothelistB,E,G,H,J,K,N,Pstoredasatree第40頁Figure8.25Aprocedureforinsertinganewentryinaliststoredasabinarytree第41頁User-definedDataTypeAtemplateforaheterogeneousstructureExample:

definetypeEmployeeTypetobe {charName[25]; intAge; realSkillRating; }第42頁AbstractDataTypeAuser-defineddatatypewithproceduresforaccessandmanipulationExample:

definetypeStackTypetobe {intStackEntries[20]; intStackPointer=0;

procedurepush(value) {StackEntries[StackPointer]←value; StackPointer?StackPointer+1; }

procedurepop... }第43頁ClassAn