基本数据结构StacksQueuesListsTrees课件_第1页
基本数据结构StacksQueuesListsTrees课件_第2页
基本数据结构StacksQueuesListsTrees课件_第3页
基本数据结构StacksQueuesListsTrees课件_第4页
基本数据结构StacksQueuesListsTrees课件_第5页
已阅读5页,还剩24页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、Elementary Data Structures1The Stack ADT (2.1.1)The Stack ADT stores arbitrary objectsInsertions and deletions follow the last-in first-out schemeThink of a spring-loaded plate dispenserMain stack operations:push(object): inserts an elementobject pop(): removes and returns the last inserted elementA

2、uxiliary stack operations:object top(): returns the last inserted element without removing itinteger size(): returns the number of elements storedboolean isEmpty(): indicates whether no elements are storedElementary Data Structures2Applications of StacksDirect applicationsvisited history in a Web br

3、owserUndo sequence in a text editorChain of method calls in the Java Virtual Machine or C+ runtime environmentIndirect applicationsAuxiliary data structure for algorithmsComponent of other data structuresElementary Data Structures3Array-based Stack (2.1.1)A simple way of implementing the Stack ADT u

4、ses an arrayWe add elements from left to rightA variable t keeps track of the index of the top element (size is t+1)S012tAlgorithm pop():if isEmpty() thenthrow EmptyStackException else t t 1return St + 1Algorithm push(o)if t = S.length 1 thenthrow FullStackException else t t + 1St oElementary Data S

5、tructures4Growable 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?incremental strategy: increase the size by a constant cdoubling strategy: double the sizeAlgorithm push

6、(o)if t = S.length 1 thenA new array ofsize for i 0 to t do Ai Si S At t + 1St oElementary Data Structures5Comparison of the StrategiesWe compare the incremental strategy and the doubling strategy by analyzing the total time T(n) needed to perform a series of n push operationsWe assume that we start

7、 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)/nElementary Data Structures6Analysis of the Incremental StrategyWe replace the array k = n/c timesThe total time T(n) of a serie

8、s 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)Elementary Data Structures7Direct Analysis of the Doubling StrategyWe replace the array k =

9、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 series12148Elementary Data Structures8The accounting method determines the amortized running time with

10、 a system of credits and debitsWe view a computer as a coin-operated device requiring 1 cyber-dollar for a constant amount of computing.Accounting Method Analysis of the Doubling StrategyWe set up a scheme for charging operations. This is known as an amortization scheme.The scheme must give us alway

11、s enough money to pay for the actual cost of the operation.The total cost of the series of operations is no more than the total amount charged.(amortized time) (total $ charged) / (# operations)Elementary Data Structures9Amortization Scheme for the Doubling StrategyConsider again the k phases, where

12、 each phase consisting of twice as many pushes as the one before.At the end of a phase we must have saved enough to pay for the array-growing push of the next phase.At the end of phase i we want to have saved i cyber-dollars, to pay for the array growth for the beginning of the next phase.02456731$0

13、245678911310121314151$ 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.Elementary Data Structures

14、10The Queue ADT (2.1.2)The Queue ADT stores arbitrary objectsInsertions and deletions follow the first-in first-out schemeInsertions are at the rear of the queue and removals are at the front of the queueMain queue operations:enqueue(object): inserts an element at the end of the queueobject dequeue(

15、): removes and returns the element at the front of the queueAuxiliary queue operations:object front(): returns the element at the front without removing itinteger size(): returns the number of elements storedboolean isEmpty(): indicates whether no elements are storedExceptionsAttempting the executio

16、n of dequeue or front on an empty queue throws an EmptyQueueExceptionElementary Data Structures11Applications of QueuesDirect applicationsWaiting linesAccess to shared resources (e.g., printer)MultiprogrammingIndirect applicationsAuxiliary data structure for algorithmsComponent of other data structu

17、resElementary Data Structures12Singly Linked ListA singly linked list is a concrete data structure consisting of a sequence of nodesEach node storeselementlink to the next nodenextelemnodeABCDElementary Data Structures13Queue with a Singly Linked ListWe can implement a queue with a singly linked lis

18、tThe front element is stored at the first nodeThe rear element is stored at the last nodeThe space used is O(n) and each operation of the Queue ADT takes O(1) timefrnodeselementsElementary Data Structures14List ADT (2.2.2)The List ADT models a sequence of positions storing arbitrary objectsIt allows

19、 for insertion and removal in the “middle” Query methods:isFirst(p), isLast(p)Accessor methods:first(), last()before(p), after(p)Update methods:replaceElement(p, o), swapElements(p, q) insertBefore(p, o), insertAfter(p, o),insertFirst(o), insertLast(o)remove(p)Elementary Data Structures15Doubly Link

20、ed ListA doubly linked list provides a natural implementation of the List ADTNodes implement Position and store:elementlink to the previous nodelink to the next nodeSpecial trailer and header nodesprevnextelemtrailerheadernodes/positionselementsnodeElementary Data Structures16Trees (2.3)In computer

21、science, a tree is an abstract model of a hierarchical structureA tree consists of nodes with a parent-child relationApplications:Organization chartsFile systemsProgramming environmentsComputers”R”UsSalesR&DManufacturingLaptopsDesktopsUSInternationalEuropeAsiaCanadaElementary Data Structures17Tree A

22、DT (2.3.1)We use positions to abstract nodesGeneric methods:integer size()boolean isEmpty()objectIterator elements()positionIterator positions()Accessor methods:position root()position parent(p)positionIterator children(p)Query methods:boolean isInternal(p)boolean isExternal(p)boolean isRoot(p)Updat

23、e methods:swapElements(p, q)object replaceElement(p, o)Additional update methods may be defined by data structures implementing the Tree ADTElementary Data Structures18Preorder Traversal (2.3.2)A traversal visits the nodes of a tree in a systematic mannerIn a preorder traversal, a node is visited be

24、fore 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)Elementary Data Structures19Postorder Traversal (2.3.2

25、)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.java25Kh1c.doc3Kh1nc.doc2KRobot.java20K9

26、31724568Elementary Data Structures20Binary Trees (2.3.3)A binary tree is a tree with the following properties:Each internal node has two childrenThe children of a node are an ordered pairWe call the children of an internal node left child and right childAlternative recursive definition: a binary tre

27、e is eithera tree consisting of a single node, ora tree whose root has an ordered pair of children, each of which is a binary treeApplications:arithmetic expressionsdecision processessearchingABCFGDEHIElementary Data Structures21Arithmetic Expression TreeBinary tree associated with an arithmetic exp

28、ressioninternal nodes: operatorsexternal nodes: operandsExample: arithmetic expression tree for the expression (2 (a - 1) + (3 b)+-2a13bElementary Data Structures22Decision TreeBinary tree associated with a decision processinternal nodes: questions with yes/no answerexternal nodes: decisionsExample:

29、 dining decisionWant a fast meal?How about coffee?On expense account?StarbucksIn N OutAntoinesDennysYesNoYesNoYesNoElementary Data Structures23Properties of Binary TreesNotationnnumber of nodesenumber of external nodesinumber of internal nodeshheightProperties:e = i + 1n = 2e - 1h ih (n - 1)/2e 2hh

30、log2 eh log2 (n + 1) - 1Elementary Data Structures24Inorder TraversalIn an inorder traversal a node is visited after its left subtree and before its right subtreeApplication: draw a binary treex(v) = inorder rank of vy(v) = depth of vAlgorithm inOrder(v)if isInternal (v)inOrder (leftChild (v)visit(v

31、)if isInternal (v)inOrder (rightChild (v)312567984Elementary Data Structures25Euler 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:on the left (preorder)from below (inorder)on the right (postorder)+-25132LBRElementary Data Structures26Printing Arithmetic ExpressionsSpecialization of an inorder

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论