计算机科学概论原版第九版ppt课件.ppt

Chapter8 DataAbstractions 2007PearsonAddison Wesley Allrightsreserved Chapter8 DataAbstractions 8 1DataStructureFundamentals8 2ImplementingDataStructures8 3AShortCaseStudy8 4CustomizedDataTypes8 5ClassesandObjects8 6PointersinMachineLanguage BasicDataStructures HomogeneousarrayHeterogeneousarrayListStackQueueTree Figure8 1Lists stacks andqueues TerminologyforLists List AcollectionofdatawhoseentriesarearrangedsequentiallyHead ThebeginningofthelistTail Theendofthelist TerminologyforStacks Stack AlistinwhichentriesareremovedandinsertedonlyattheheadLIFO Last in first outTop Theheadoflist stack Bottomorbase Thetailoflist stack Pop ToremovetheentryatthetopPush Toinsertanentryatthetop TerminologyforQueues Queue AlistinwhichentriesareremovedattheheadandareinsertedatthetailFIFO First in first out Figure8 2Anexampleofanorganizationchart TerminologyforaTree Tree AcollectionofdatawhoseentrieshaveahierarchicalorganizationNode AnentryinatreeRootnode ThenodeatthetopTerminalorleafnode Anodeatthebottom TerminologyforaTree continued Parent ThenodeimmediatelyaboveaspecifiednodeChild AnodeimmediatelybelowaspecifiednodeAncestor Parent parentofparent etc Descendent Child childofchild etc Siblings Nodessharingacommonparent TerminologyforaTree continued Binarytree AtreeinwhicheverynodehasatmosttwochildrenDepth Thenumberofnodesinlongestpathfromroottoleaf Figure8 3Treeterminology AdditionalConcepts StaticDataStructures SizeandshapeofdatastructuredoesnotchangeDynamicDataStructures SizeandshapeofdatastructurecanchangePointers Usedtolocatedata Figure8 4Novelsarrangedbytitlebutlinkedaccordingtoauthorship StoringArrays HomogeneousarraysRow majororderversuscolumnmajororderAddresspolynomialHeterogeneousarraysComponentscanbestoredoneaftertheotherinacontiguousblockComponentscanbestoredinseparatelocationsidentifiedbypointers Figure8 5Thearrayoftemperaturereadingsstoredinmemorystartingataddressx Figure8 6Atwo dimensionalarraywithfourrowsandfivecolumnsstoredinrowmajororder Figure8 7StoringtheheterogeneousarrayEmployee StoringLists Contiguouslist ListstoredinahomogeneousarrayLinkedlist ListinwhicheachentriesarelinkedbypointersHeadpointer PointertofirstentryinlistNILpointer A non pointer valueusedtoindicateendoflist Figure8 8Namesstoredinmemoryasacontiguouslist Figure8 9Thestructureofalinkedlist Figure8 10Deletinganentryfromalinkedlist Figure8 11Insertinganentryintoalinkedlist StoringStacksandQueues StacksusuallystoredascontiguouslistsQueuesusuallystoredasCircularQueuesStoredinacontiguousblockinwhichthefirstentryisconsideredtofollowthelastentryPreventsaqueuefromcrawlingoutofitsallottedstoragespace Figure8 12Astackinmemory Figure8 13Aqueueimplementationwithheadandtailpointers StoringBinaryTrees LinkedstructureEachnode datacells twochildpointersAccessedviaapointertorootnodeContiguousarraystructureA 1 rootnodeA 2 A 3 childrenofA 1 A 4 A 5 A 6 A 7 childrenofA 2 andA 3 Figure8 14Thestructureofanodeinabinarytree Figure8 15Theconceptualandactualorganizationofabinarytreeusingalinkedstoragesystem Figure8 16Atreestoredwithoutpointers Figure8 17Asparse unbalancedtreeshowninitsconceptualformandasitwouldbestoredwithoutpointers ManipulatingDataStructures Ideally adatastructureshouldbemanipulatedsolelybypre definedprocedures Example Astacktypicallyneedsatleastpushandpopprocedures Thedatastructurealongwiththeseproceduresconstitutesacompleteabstracttool Figure8 18Aprocedureforprintingalinkedlist CaseStudy Problem Constructanabstracttoolconsistingofalistofnamesinalphabeticalorderalongwiththeoperationssearch print andinsert Figure8 19ThelettersAthroughMarrangedinanorderedtree Figure8 20Thebinarysearchasitwouldappearifthelistwereimplementedasalinkedbinarytree Figure8 21ThesuccessivelysmallertreesconsideredbytheprocedureinFigure8 18whensearchingfortheletterJ Figure8 22Printingasearchtreeinalphabeticalorder Figure8 23Aprocedureforprintingthedatainabinarytree Figure8 24InsertingtheentryMintothelistB E G H J K N Pstoredasatree Figure8 25Aprocedureforinsertinganewentryinaliststoredasabinarytree User definedDataType AtemplateforaheterogeneousstructureExample definetypeEmployeeTypetobe charName 25 intAge realSkillRating AbstractDataType Auser defineddatatypewithproceduresforaccessandmanipulationExample definetypeStackTypetobe intStackEntries 20 intStackPointer 0 procedurepush value StackEntries StackPointer value StackPointer StackPointer 1 procedurepop Class AnabstractdatatypewithextrafeaturesCharacteristicscanbeinheritedContentscanbeencapsulatedConstructormethodstoinitializenewobjects Figure8 26AstackofintegersimplementedinJavaandC PointersinMachineLanguage Immediateaddressing InstructioncontainsthedatatobeaccessedDirectaddressing InstructioncontainstheaddressofthedatatobeaccessedIndirectaddressing Instructioncontainsthelocat