《第02章基本数据结构StacksQueuesListsTrees.ppt》由会员分享，可在线阅读，更多相关《第02章基本数据结构StacksQueuesListsTrees.ppt（30页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第02章基本数据结构StacksQueuesListsTrees Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望The Stack ADT(2.1.1)wThe Stack ADT stores arbitrary objectswInsertions and deletions follow the last-in first-out schemewThink of a spring-loaded plate dispenserwMain stack opera
2、tions:npush(object):inserts an elementnobject pop():removes and returns the last inserted elementwAuxiliary stack operations:nobject top():returns the last inserted element without removing itninteger size():returns the number of elements storednboolean isEmpty():indicates whether no elements are st
3、ored2Elementary Data StructuresApplications of StacksDirect applicationsnPage-visited history in a Web browsernUndo sequence in a text editornChain of method calls in the Java Virtual Machine or C+runtime environmentIndirect applicationsnAuxiliary data structure for algorithmsnComponent of other dat
4、a structures3Elementary Data StructuresArray-based Stack(2.1.1)wA simple way of implementing the Stack ADT uses an arraywWe add elements from left to rightwA variable t keeps track of the index of the top element(size is t+1)S01 2tAlgorithm pop():if isEmpty()thenthrow EmptyStackException else t t 1r
5、eturn St+1Algorithm push(o)if t=S.length 1 thenthrow FullStackException else t t+1St o4Elementary Data StructuresGrowable Array-based Stack(1.5)In a push operation,when the array is full,instead of throwing an exception,we can replace the array with a larger oneHow large should the new array be?ninc
6、remental strategy:increase the size by a constant cndoubling strategy:double the sizeAlgorithm push(o)if t=S.length 1 thenA new array ofsize for i 0 to t do Ai Si S At t+1St o5Elementary Data StructuresComparison of the StrategiesWe compare the incremental strategy and the doubling strategy by analy
7、zing the total time T(n)needed to perform a series of n push operationsWe assume that we start with an empty stack represented by an array of size 1We call amortized time of a push operation the average time taken by a push over the series of operations,i.e.,T(n)/n6Elementary Data StructuresAnalysis
8、 of the Incremental StrategyWe replace the array k=n/c timesThe total time T(n)of a series of n push operations is proportional ton+c+2c+3c+4c+kc=n+c(1+2+3+k)=n+ck(k+1)/2Since c is a constant,T(n)is O(n+k2),i.e.,O(n2)The amortized time of a push operation is O(n)7Elementary Data StructuresDirect Ana
9、lysis of the Doubling StrategyWe replace the array k=log2 n timesThe total time T(n)of a series of n push operations is proportional ton+1+2+4+8+2k=n+2k+1 1 =2n 1T(n)is O(n)The amortized time of a push operation is O(1)geometric series121488Elementary Data StructureswThe accounting method determines
10、 the amortized running time with a system of credits and debitswWe view a computer as a coin-operated device requiring 1 cyber-dollar for a constant amount of computing.Accounting Method Analysis of the Doubling StrategynWe set up a scheme for charging operations.This is known as an amortization sch
11、eme.nThe scheme must give us always enough money to pay for the actual cost of the operation.nThe total cost of the series of operations is no more than the total amount charged.w(amortized time)(total$charged)/(#operations)9Elementary Data StructuresAmortization Scheme for the Doubling StrategywCon
12、sider again the k phases,where each phase consisting of twice as many pushes as the one before.wAt the end of a phase we must have saved enough to pay for the array-growing push of the next phase.wAt the end of phase i we want to have saved i cyber-dollars,to pay for the array growth for the beginni
13、ng of the next phase.024 5 6 731$024 5 6 7 8 911310121314 151$We charge$3 for a push.The$2 saved for a regular push are“stored”in the second half of the array.Thus,we will have 2(i/2)=i cyber-dollars saved at then end of phase i.Therefore,each push runs in O(1)amortized time;n pushes run in O(n)time
14、.10Elementary Data StructuresThe Queue ADT(2.1.2)wThe Queue ADT stores arbitrary objectswInsertions and deletions follow the first-in first-out schemewInsertions are at the rear of the queue and removals are at the front of the queuewMain queue operations:nenqueue(object):inserts an element at the e
15、nd of the queuenobject dequeue():removes and returns the element at the front of the queuewAuxiliary queue operations:nobject front():returns the element at the front without removing itninteger size():returns the number of elements storednboolean isEmpty():indicates whether no elements are storedwE
16、xceptionsnAttempting the execution of dequeue or front on an empty queue throws an EmptyQueueException11Elementary Data StructuresApplications of QueuesDirect applicationsnWaiting linesnAccess to shared resources(e.g.,printer)nMultiprogrammingIndirect applicationsnAuxiliary data structure for algori
17、thmsnComponent of other data structures12Elementary Data StructuresSingly Linked ListA singly linked list is a concrete data structure consisting of a sequence of nodesEach node storesnelementnlink to the next nodenextelemnodeABCD13Elementary Data StructuresQueue with a Singly Linked ListWe can impl
18、ement a queue with a singly linked listnThe front element is stored at the first nodenThe rear element is stored at the last nodeThe space used is O(n)and each operation of the Queue ADT takes O(1)timefrnodeselements14Elementary Data StructuresList ADT(2.2.2)The List ADT models a sequence of positio
19、ns storing arbitrary objectsIt allows for insertion and removal in the“middle”Query methods:nisFirst(p),isLast(p)Accessor methods:nfirst(),last()nbefore(p),after(p)wUpdate methods:nreplaceElement(p,o),swapElements(p,q)ninsertBefore(p,o),insertAfter(p,o),ninsertFirst(o),insertLast(o)nremove(p)15Eleme
20、ntary Data StructuresDoubly Linked ListA doubly linked list provides a natural implementation of the List ADTNodes implement Position and store:nelementnlink to the previous nodenlink to the next nodeSpecial trailer and header nodesprevnextelemtrailerheadernodes/positionselementsnode16Elementary Dat
21、a StructuresTrees(2.3)In computer science,a tree is an abstract model of a hierarchical structureA tree consists of nodes with a parent-child relationApplications:nOrganization chartsnFile systemsnProgramming environmentsComputers”R”UsSalesR&DManufacturingLaptopsDesktopsUSInternationalEuropeAsiaCana
22、da17Elementary Data StructuresTree ADT(2.3.1)We use positions to abstract nodesGeneric methods:ninteger size()nboolean isEmpty()nobjectIterator elements()npositionIterator positions()Accessor methods:nposition root()nposition parent(p)npositionIterator children(p)Query methods:nboolean isInternal(p)
23、nboolean isExternal(p)nboolean isRoot(p)Update methods:nswapElements(p,q)nobject replaceElement(p,o)Additional update methods may be defined by data structures implementing the Tree ADT18Elementary Data StructuresPreorder Traversal(2.3.2)A traversal visits the nodes of a tree in a systematic mannerI
24、n a preorder traversal,a node is visited before its descendants Application:print a structured documentMake Money Fast!1.MotivationsReferences2.Methods2.1 StockFraud2.2 PonziScheme1.1 Greed1.2 Avidity2.3 BankRobbery123546789Algorithm preOrder(v)visit(v)for each child w of vpreorder(w)19Elementary Da
25、ta StructuresPostorder Traversal(2.3.2)In a postorder traversal,a node is visited after its descendantsApplication:compute space used by files in a directory and its subdirectoriesAlgorithm postOrder(v)for each child w of vpostOrder(w)visit(v)cs16/homeworks/todo.txt1Kprograms/DDR.java10KStocks.java2
26、5Kh1c.doc3Kh1nc.doc2KRobot.java20K93172456820Elementary Data StructuresBinary Trees(2.3.3)A binary tree is a tree with the following properties:nEach internal node has two childrennThe children of a node are an ordered pairWe call the children of an internal node left child and right childAlternativ
27、e recursive definition:a binary tree is eitherna tree consisting of a single node,orna tree whose root has an ordered pair of children,each of which is a binary treeApplications:narithmetic expressionsndecision processesnsearchingABCFGDEHI21Elementary Data StructuresArithmetic Expression TreeBinary
28、tree associated with an arithmetic expressionninternal nodes:operatorsnexternal nodes:operandsExample:arithmetic expression tree for the expression(2 (a 1)+(3 b)+2a13b22Elementary Data StructuresDecision TreeBinary tree associated with a decision processninternal nodes:questions with yes/no answerne
29、xternal nodes:decisionsExample:dining decisionWant a fast meal?How about coffee?On expense account?StarbucksIn N OutAntoinesDennysYesNoYesNoYesNo23Elementary Data StructuresProperties of Binary TreesNotationn number of nodese number of external nodesinumber of internal nodesh heightProperties:ne=i+1
30、nn=2e-1nh inh (n-1)/2ne 2hnh log2 enh log2(n+1)-124Elementary Data StructuresInorder TraversalIn an inorder traversal a node is visited after its left subtree and before its right subtreeApplication:draw a binary treenx(v)=inorder rank of vny(v)=depth of vAlgorithm inOrder(v)if isInternal(v)inOrder(
31、leftChild(v)visit(v)if isInternal(v)inOrder(rightChild(v)31256798425Elementary Data StructuresEuler Tour TraversalGeneric traversal of a binary treeIncludes a special cases the preorder,postorder and inorder traversalsWalk around the tree and visit each node three times:non the left(preorder)nfrom b
32、elow(inorder)non the right(postorder)+25132LBR26Elementary Data StructuresPrinting Arithmetic ExpressionsSpecialization of an inorder traversalnprint operand or operator when visiting nodenprint“(“before traversing left subtreenprint“)“after traversing right subtreeAlgorithm printExpression(v)if isI
33、nternal(v)print(“()inOrder(leftChild(v)print(v.element()if isInternal(v)inOrder(rightChild(v)print(“)+2a13b(2 (a 1)+(3 b)27Elementary Data StructuresLinked Data Structure for Representing Trees(2.3.4)A node is represented by an object storingnElementnParent nodenSequence of children nodesNode object
34、s implement the Position ADTBDACEFBADFCE28Elementary Data StructuresLinked Data Structure for Binary TreesA node is represented by an object storingnElementnParent nodenLeft child nodenRight child nodeNode objects implement the Position ADTBDACEBADCE29Elementary Data StructuresArray-Based Representation of Binary Treesnodes are stored in an arraynlet rank(node)be defined as follows:nrank(root)=1nif node is the left child of parent(node),rank(node)=2*rank(parent(node)nif node is the right child of parent(node),rank(node)=2*rank(parent(node)+112367451011AHGFEDCBJ30Elementary Data Structures