《基本数据结构》PPT课件.ppt

《《基本数据结构》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《基本数据结构》PPT课件.ppt（30页珍藏版）》请在三一办公上搜索。

1、Elementary Data Structures,Stacks,Queues,&ListsAmortized analysisTrees,Elementary Data Structures,2,The 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):insert

2、s an elementobject pop():removes and returns the last inserted element,Auxiliary 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 stored,Elementary Data Structure

3、s,3,Applications of Stacks,Direct applicationsPage-visited history in a Web browserUndo 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 structures,Elementary Data St

4、ructures,4,Array-based Stack(2.1.1),A simple way of implementing the Stack ADT uses an arrayWe add elements from left to rightA variable t keeps track of the index of the top element(size is t+1),Algorithm pop():if isEmpty()thenthrow EmptyStackException else t t 1return St+1,Algorithm push(o)if t=S.

5、length 1 thenthrow FullStackException else t t+1St o,Elementary Data Structures,5,Growable 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

6、size by a constant cdoubling strategy:double the size,Algorithm push(o)if t=S.length 1 thenA new array ofsize for i 0 to t do Ai Si S At t+1St o,Elementary Data Structures,6,Comparison of the Strategies,We compare the incremental strategy and the doubling strategy by analyzing the total time T(n)nee

7、ded 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)/n,Elementary Data Structures,7,Analysis of the Incremental Stra

8、tegy,We 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),Elementary Data Structures,8,Direct Analysis of the Doublin

9、g Strategy,We 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),Elementary Data Structures,9,The accounting method determines the amortized running time with a syst

10、em 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 Strategy,We set up a scheme for charging operations.This is known as an amortization scheme.The scheme must give us always enou

11、gh 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 Structures,10,Amortization Scheme for the Doubling Strategy,Consider again the k phases,where each ph

12、ase 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.,We charge$3 for a

13、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,11,The Queue ADT(),The Queue ADT stores arbitrary o

14、bjectsInsertions 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():removes and returns the element at the front of the qu

15、eue,Auxiliary 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 execution of dequeue or front on an empty queue throws an EmptyQueu

16、eException,Elementary Data Structures,12,Applications of Queues,Direct applicationsWaiting linesAccess to shared resources(e.g.,printer)MultiprogrammingIndirect applicationsAuxiliary data structure for algorithmsComponent of other data structures,Elementary Data Structures,13,Singly Linked List,A si

17、ngly linked list is a concrete data structure consisting of a sequence of nodesEach node storeselementlink to the next node,next,elem,node,A,B,C,D,Elementary Data Structures,14,Queue with a Singly Linked List,We can implement a queue with a singly linked listThe front element is stored at the first

18、nodeThe rear element is stored at the last nodeThe space used is O(n)and each operation of the Queue ADT takes O(1)time,f,r,nodes,elements,Elementary Data Structures,15,List ADT(),The List ADT models a sequence of positions storing arbitrary objectsIt allows for insertion and removal in the“middle”Q

19、uery 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 Structures,16,Doubly Linked List,A doubly linked list provides a natural imp

20、lementation of the List ADTNodes implement Position and store:elementlink to the previous nodelink to the next nodeSpecial trailer and header nodes,prev,next,elem,trailer,header,nodes/positions,elements,node,Elementary Data Structures,17,Trees(2.3),In computer science,a tree is an abstract model of

21、a hierarchical structureA tree consists of nodes with a parent-child relationApplications:Organization chartsFile systemsProgramming environments,Elementary Data Structures,18,Tree ADT(),We use positions to abstract nodesGeneric methods:integer size()boolean isEmpty()objectIterator elements()positio

22、nIterator positions()Accessor methods:position root()position parent(p)positionIterator children(p),Query methods:boolean isInternal(p)boolean isExternal(p)boolean isRoot(p)Update methods:swapElements(p,q)object replaceElement(p,o)Additional update methods may be defined by data structures implement

23、ing the Tree ADT,Elementary Data Structures,19,Preorder Traversal(),A traversal visits the nodes of a tree in a systematic mannerIn a preorder traversal,a node is visited before its descendants Application:print a structured document,Make Money Fast!,1.Motivations,References,2.Methods,2.1 StockFraud

24、,2.2 PonziScheme,1.1 Greed,1.2 Avidity,2.3 BankRobbery,1,2,3,5,4,6,7,8,9,Algorithm preOrder(v)visit(v)for each child w of vpreorder(w),Elementary Data Structures,20,Postorder Traversal(),In a postorder traversal,a node is visited after its descendantsApplication:compute space used by files in a dire

25、ctory and its subdirectories,Algorithm postOrder(v)for each child w of vpostOrder(w)visit(v),cs16/,homeworks/,todo.txt1K,programs/,DDR.java10K,Stocks.java25K,h1c.doc3K,h1nc.doc2K,Robot.java20K,9,3,1,7,2,4,5,6,8,Elementary Data Structures,21,Binary Trees(),A binary tree is a tree with the following p

26、roperties: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 tree is eithera tree consisting of a single node,ora tree whose root has an ordered pair of children,eac

27、h of which is a binary tree,Applications:arithmetic expressionsdecision processessearching,A,B,C,F,G,D,E,H,I,Elementary Data Structures,22,Arithmetic Expression Tree,Binary tree associated with an arithmetic expressioninternal nodes:operatorsexternal nodes:operandsExample:arithmetic expression tree

28、for the expression(2(a-1)+(3 b),Elementary Data Structures,23,Decision Tree,Binary tree associated with a decision processinternal nodes:questions with yes/no answerexternal nodes:decisionsExample:dining decision,Want a fast meal?,How about coffee?,On expense account?,Starbucks,In N Out,Antoines,Den

29、nys,Yes,No,Yes,No,Yes,No,Elementary Data Structures,24,Properties of Binary Trees,Notationnnumber of nodesenumber of external nodesinumber of internal nodeshheight,Properties:e=i+1n=2e-1h ih(n-1)/2e 2hh log2 eh log2(n+1)-1,Elementary Data Structures,25,Inorder Traversal,In an inorder traversal a nod

30、e is visited after its left subtree and before its right subtreeApplication:draw a binary treex(v)=inorder rank of vy(v)=depth of v,Algorithm inOrder(v)if isInternal(v)inOrder(leftChild(v)visit(v)if isInternal(v)inOrder(rightChild(v),3,1,2,5,6,7,9,8,4,Elementary Data Structures,26,Euler Tour Travers

31、al,Generic 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),+,-,2,5,1,3,2,L,B,R,Elementary Data Structures,27,Printing Arithmetic Expres

32、sions,Specialization of an inorder traversalprint operand or operator when visiting nodeprint“(“before traversing left subtreeprint“)“after traversing right subtree,Algorithm printExpression(v)if isInternal(v)print(“()inOrder(leftChild(v)print(v.element()if isInternal(v)inOrder(rightChild(v)print(“)

33、,(2(a-1)+(3 b),Elementary Data Structures,28,Linked Data Structure for Representing Trees(),A node is represented by an object storingElementParent nodeSequence of children nodesNode objects implement the Position ADT,B,D,A,C,E,F,B,A,D,F,C,E,Elementary Data Structures,29,Linked Data Structure for Bi

34、nary Trees,A node is represented by an object storingElementParent nodeLeft child nodeRight child nodeNode objects implement the Position ADT,B,D,A,C,E,Elementary Data Structures,30,Array-Based Representation of Binary Trees,nodes are stored in an array,let rank(node)be defined as follows:rank(root)=1if node is the left child of parent(node),rank(node)=2*rank(parent(node)if node is the right child of parent(node),rank(node)=2*rank(parent(node)+1,1,2,3,6,7,4,5,10,11,