第02章基本数据结构StacksQueuesListsTrees.ppt
《第02章基本数据结构StacksQueuesListsTrees.ppt》由会员分享,可在线阅读,更多相关《第02章基本数据结构StacksQueuesListsTrees.ppt(30页珍藏版)》请在三一文库上搜索。
1、Elementary Data Structures,Stacks, Queues, & Lists Amortized analysis Trees,Elementary Data Structures,2,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(obje
2、ct): inserts an element object pop(): removes and returns the last inserted element,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,Elemen
3、tary Data Structures,3,Applications of Stacks,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 str
4、uctures,Elementary Data Structures,4,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 variable t keeps track of the index of the top element (size is t+1),Algorithm pop(): if isEmpty() then throw EmptyStackException else t t 1 re
5、turn St + 1,Algorithm push(o) if t = S.length 1 then throw FullStackException else t t + 1 St 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 one How large should the
6、 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 then A new array of size for i 0 to t do Ai Si S A t t + 1 St o,Elementary Data Structures,6,Comparison of the Strategies,We compare the incremental strategy
7、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 the average time taken by a push over the series of operations, i.e., T(
8、n)/n,Elementary Data Structures,7,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 is a constant, T(n) is O(n + k2), i.e., O(n
9、2) The amortized time of a push operation is O(n),Elementary Data Structures,8,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 O(n) The amor
10、tized time of a push operation is O(1),Elementary Data Structures,9,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
11、the Doubling 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) (t
12、otal $ charged) / (# operations),Elementary Data Structures,10,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 ne
13、xt 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 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 o
14、f 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 (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 removals are at
15、 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 size(): retu
16、rns 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,Elementary Data Structures,12,Applications of Queues,Direct applications Waiting lines Access to share
17、d resources (e.g., printer) Multiprogramming Indirect applications Auxiliary data structure for algorithms Component of other data structures,Elementary Data Structures,13,Singly Linked List,A singly linked list is a concrete data structure consisting of a sequence of nodes Each node stores element
18、link 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 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 Que
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 02 基本 数据结构 StacksQueuesListsTrees
链接地址:https://www.31doc.com/p-2546773.html