计算机科学概论原版(第九版)课件

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+twochildpointersAccessedviaapointertorootnodeContiguousarraystructureA1=rootnodeA2,A3=childrenofA1A4,A5,A6,A7=childrenofA2andA3,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:definetypeEmployeeTypetobecharName25;intAge;realSkillRating;,AbstractDataType,Auser-defineddatatypewithproceduresforaccessandmanipulationExample:definetypeStackTypetobeintStackEntries20;intStackPointer=0;procedurepush(value)StackEntriesStackPointervalue;StackPointerStackPointer+1;procedurepop.,Class,AnabstractdatatypewithextrafeaturesCharacteristicscanbeinheritedContentscanbeencapsulatedConstructormethodstoinitializenewobjects,Figure8.26AstackofintegersimplementedinJavaandC#,PointersinMachineLanguage,Immediateaddressing:InstructioncontainsthedatatobeaccessedDirectaddressing:InstructioncontainstheaddressofthedatatobeaccessedIndirectaddressi