Chapter 2-Elementary DataStructures.ppt

1、Chapter 2: Elementary Data Structures,Example,Spelling checker Look up words in a list of correctly-spelled words Add or remove words from the list How to implement? Operations needed? Insert Find Delete Called ADT Dictionary How to implement?,Abstract Data Types (ADTs),An abstract data type (ADT) i

2、s an abstraction of a data structure An ADT specifies: Data stored Operations on the data Error conditions associated with operations An ADT is implemented with various concrete data structures,Example: ADT modeling a simple stock trading system The data stored are buy/sell orders The operations sup

3、ported are order buy(stock, shares, price) order sell(stock, shares, price) void cancel(order) Error conditions: Buy/sell a nonexistent stock Cancel a nonexistent order,Chapter 2.1-2.4: Elementary Data Structures,Introduction Stacks Queues Lists and Sequences Trees,Example,Problem: Managing Call Fra

4、mes ADT? Implementation?,The Stack ADT (2.1.1),The Stack ADT stores arbitrary objects Insertions and deletions follow the last-in first-out scheme Think of a spring-loaded plate dispenser Main stack operations: push(object): inserts an element object pop(): removes and returns the last inserted elem

5、ent,Auxiliary stack operations: object top(): returns the last inserted element without removing it integer size(): returns the number of elements stored boolean isEmpty(): indicates whether no elements are stored,Exceptions,Attempting the execution of an operation of ADT may sometimes cause an erro

6、r condition, called an exception Exceptions are said to be “thrown” by an operation that cannot be executed,In the Stack ADT, operations pop and top cannot be performed if the stack is empty Attempting the execution of pop or top on an empty stack throws an EmptyStackException,Applications of Stacks

7、Direct applications Page-visited history in a Web browser Undo sequence in a text editor Chain of method calls in the Java Virtual Machine or C+ runtime environment Indirect applications Auxiliary data structure for algorithms Component of other data structures,Method Stack in the JVM,The Java Virt

8、ual Machine (JVM) keeps track of the chain of active methods with a stack When a method is called, the JVM pushes on the stack a frame containing Local variables and return value Program counter, keeping track of the statement being executed When a method ends, its frame is popped from the stack and

9、 control is passed to the method on top of the stack,main() int i = 5; foo(i); foo(int j) int k; k = j+1; bar(k); bar(int m) ,barPC = 1 m = 6,fooPC = 3 j = 5k = 6,mainPC = 2 i = 5,Array-based Stack (2.1.1),A simple way of implementing the Stack ADT uses an array We add elements from left to right A

10、variable t keeps track of the index of the top element (size is t+1),Algorithm pop():if isEmpty() thenthrow EmptyStackExceptionelse t t 1return St + 1,Algorithm push(o)if t = S.length 1 thenthrow FullStackExceptionelse t t + 1St o,Growable Array- based Stack (1.5),In a push operation, when the array

11、 is full, instead of throwing an exception, we can replace the array with a larger one How large should the new array be? incremental strategy: increase the size by a constant c doubling strategy: double the size,Algorithm push(o)if t = S.length 1 thenA new array ofsize for i 0 to t doAi SiS At t +

12、1St o,Comparison of the Strategies,We compare the incremental strategy and the doubling strategy by analyzing the total time T(n) needed to perform a series of n push operations We assume that we start with an empty stack represented by an array of size 1 We call amortized time of a push operation t

13、he average time taken by a push over the series of operations, i.e., T(n)/n,Analysis of the Incremental Strategy,We replace the array k = n/c times The total time T(n) of a series of n push operations is proportional to n + c + 2c + 3c + 4c + + kc = n + c(1 + 2 + 3 + + k) = n + ck(k + 1)/2 Since c i

14、s a constant, T(n) is O(n + k2), i.e., O(n2) The amortized time of a push operation is O(n),Direct Analysis of the Doubling Strategy,We replace the array k = log2 n times The total time T(n) of a series of n push operations is proportional to n + 1 + 2 + 4 + 8 + + 2k = n + 2k + 1 -1 = 2n -1 T(n) is

15、O(n) The amortized time of a push operation is O(n)/n = O(1),The accounting method determines the amortized running time with a system of credits and debits We view a computer as a coin-operated device requiring 1 cyber-dollar for a constant amount of computing.,Accounting Method Analysis of the Dou

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

17、charged) / (# operations),Amortization Scheme for the Doubling Strategy,Consider again the k phases, where 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 wa

18、nt to have saved i cyber-dollars, to pay for the array growth for the beginning of the next phase.,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 i

19、n O(1) amortized time; n pushes run in O(n) time.,Example,Problem: Managing Homework Grading ADT? Implementation?,Queues,18,Queues,The Queue ADT (2.1.2),The Queue ADT stores arbitrary objects Insertions and deletions follow the first-in first-out scheme Insertions are at the rear of the queue and re

20、movals are at the front of the queue Main queue operations: enqueue(object): inserts an element at the end of the queue object dequeue(): removes and returns the element at the front of the queue,Auxiliary queue operations: object front(): returns the element at the front without removing it integer

21、 size(): returns the number of elements stored boolean isEmpty(): indicates whether no elements are stored Exceptions Attempting the execution of dequeue or front on an empty queue throws an EmptyQueueException,Applications of Queues,Direct applications Waiting lines Access to shared resources (e.g.

22、 printer) Multiprogramming Indirect applications Auxiliary data structure for algorithms Component of other data structures,Singly Linked List,A singly linked list is a concrete data structure consisting of a sequence of nodes Each node stores element link to the next node,next,elem,node,A,B,C,D,Qu

23、eue with a Singly Linked List,We can implement a queue with a singly linked list The front element is stored at the first node The rear element is stored at the last node The space used is O(n) and each operation of the Queue ADT takes O(1) time,f,r,nodes,elements,Example,Problem: Netflix Queue ADT?

24、 Implementation?,List ADT (2.2.2),The List ADT models a sequence of positions storing arbitrary objects It allows 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,

25、 q) insertBefore(p, o), insertAfter(p, o), insertFirst(o), insertLast(o) remove(p),Doubly Linked List,A doubly linked list provides a natural implementation of the List ADT Nodes implement Position and store: element link to the previous node link to the next node Special trailer and header nodes,pr

26、ev,next,elem,trailer,header,nodes/positions,elements,node,Example,Problem: Parsing an arithmetic expression (1 + 2 + 2 (2 + 2) * 2 + 2) * 3 = ? Desired result? Algorithm?,Trees,Make Money Fast!,Stock Fraud,Ponzi Scheme,Bank Robbery,Trees (2.3),In computer science, a tree is an abstract model of a hi

27、erarchical structure A tree consists of nodes with a parent-child relation Applications: Organization charts File systems Programming environments,Tree Terminology,Root: node without parent (A) Internal node: node with at least one child (A, B, C, F) External node (a.k.a. leaf): node without childre

28、n (E, I, J, K, G, H, D) Ancestors of a node: parent, grandparent, grand-grandparent, etc. Depth of a node: number of ancestors Height of a tree: maximum depth of any node (3) Descendant of a node: child, grandchild, grand-grandchild, etc.,Subtree: tree consisting of a node and its descendants,subtre

29、e,Tree ADT (2.3.1),We use positions to abstract nodes Generic 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)

30、boolean isRoot(p) Update methods: swapElements(p, q) object replaceElement(p, o) Additional update methods may be defined by data structures implementing the Tree ADT,Preorder Traversal,A traversal visits the nodes of a tree in a systematic manner In a preorder traversal, a node is visited before it

31、s descendants Application: print a structured document,Make Money Fast!,1. Motivations,References,2. Methods,2.1 Stock Fraud,2.2 Ponzi Scheme,1.1 Greed,1.2 Avidity,2.3 Bank Robbery,1,2,3,5,4,6,7,8,9,Algorithm preOrder(v) visit(v) for each child w of vpreorder (w),Postorder Traversal,In a postorder t

32、raversal, a node is visited after its descendants Application: compute space used by files in a directory and its subdirectories,Algorithm postOrder(v) for each child w of vpostOrder (w) visit(v),cs16/,homeworks/,todo.txt 1K,programs/,DDR.java 10K,Stocks.java 25K,h1c.doc 3K,h1nc.doc 2K,Robot.java 20

33、K,9,3,1,7,2,4,5,6,8,Amortized Analysis of Tree Traversal,Time taken in preorder or postorder traversal of an n-node tree is proportional to the sum, taken over each node v in the tree, of the time needed for the recursive call for v. The call for v costs $(cv + 1), where cv is the number of children

34、 of v For the call for v, charge one cyber-dollar to v and charge one cyber-dollar to each child of v. Each node (except the root) gets charged twice: once for its own call and once for its parents call. Therefore, traversal time is O(n).,Binary Trees (2.3.3),A binary tree is a tree with the followi

35、ng properties: Each internal node has two children The children of a node are an ordered pair We call the children of an internal node left child and right child Alternative recursive definition: a binary tree is either a tree consisting of a single node, or a tree whose root has an ordered pair of

36、children, each of which is a binary tree,Applications: arithmetic expressions decision processes searching,A,B,C,F,G,D,E,H,I,Arithmetic Expression Tree,Binary tree associated with an arithmetic expression internal nodes: operators external nodes: operands Example: arithmetic expression tree for the

37、expression (2 (a - 1) + (3 b),Decision Tree,Binary tree associated with a decision process internal nodes: questions with yes/no answer external nodes: decisions Example: dining decision,Want a fast meal?,How about coffee?,On expense account?,Starbucks,Qdoba,Gibsons,Russ,Yes,No,Yes,No,Yes,No,Propert

38、ies of Binary Trees,Notation n number of nodes e number of external nodes i number of internal nodes h height,Properties: e = i + 1 n = 2e - 1 h i h (n - 1)/2 e 2h h log2 e h log2 (n + 1) - 1,Inorder Traversal,In an inorder traversal a node is visited after its left subtree and before its right subt

39、ree Application: draw a binary tree x(v) = inorder rank of v y(v) = depth of v,Algorithm inOrder(v) if v is not null inOrder (leftChild (v)visit(v) inOrder (rightChild (v),3,1,2,5,6,7,9,8,4,Euler Tour Traversal,Generic traversal of a binary tree Includes as special cases the preorder, postorder and

40、inorder traversals Walk 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,Printing Arithmetic Expressions,Specialization of an inorder traversal print operand or operator when visiting node print “(“ before trave

41、rsing left subtree print “)“ after traversing right subtree,Algorithm printExpression(v) if isInternal (v) print(“() inOrder (leftChild (v) print(v.element () if isInternal (v) inOrder (rightChild (v)print (“),(2 (a - 1) + (3 b),Linked Data Structure for Representing Trees (2.3.4),A node is represen

42、ted by an object storing Element Parent node Sequence of children nodes Node objects implement the Position ADT,B,D,A,C,E,F,Linked Data Structure for Binary Trees,A node is represented by an object storing Element Parent node Left child node Right child node Node objects implement the Position ADT,A

43、rray-Based Representation of Binary Trees,nodes are stored in an array,let rank(node) be defined as follows: rank(root) = 1 if 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,B

44、asic ADTs in C#,Interfaces ICollection, IComparer, IEnumerable, IDictionary, IList System.Collections Stack (implements ICollection, IEnumerable) Queue (implements ICollection, IEnumerable) ArrayList (implements ICollection, IEnumerable) Dictionary (generic, IDictionary interface) HashTable (hash table based Dictionary) SortedDictionary (tree based Dictionary),