Chapter 11 Tables and Priority Queues Data Abstraction Problem Solving with C Fifth Edition by Frank M Carrano Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 The ADT Table The ADT table or dictionary Uses a search key to identify its items Its items are records that contain several pieces of data Figure 11 1 An ordinary table of cities Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 2 The ADT Table Various sets of table operations are possible Figure 11 2 UML diagram for class Table Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 3 The ADT Table Our table assumes distinct search keys Other tables could allow duplicate search keys The traverseTable operation visits table items in a specified order One common order is by sorted search key A client defined visit function is supplied as an argument to the traversal Called once for each item in the table Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 4 The ADT Table KeyedItem class Same as for the ADT binary search tree Contains an item s search key and a method for accessing the search key data field Prevents modification of the search key value once an item is created Has only a constructor for initializing the search key Also true of a class that extends KeyedItem Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 5 Selecting an Implementation Linear implementations Four categories Unsorted array based or pointer based Sorted by search key array based or pointer based Figure 11 3 The data members for two sorted linear implementations of the ADT table for the data in Figure 11 1 a array based b pointer based Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 6 Selecting an Implementation Nonlinear implementations Binary search tree implementation Offers several advantages over linear implementations Figure 11 4 The data members for a binary search tree implementation of the ADT table for the data in Figure 11 1 Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 7 Selecting an Implementation The requirements of a particular application influence the selection of an implementation Questions to be considered about an application before choosing an implementation What operations are needed How often is each operation required Are frequently used operations efficient given a particular implementation Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 8 Comparing Linear Implementations Unsorted array based implementation Insertion is made efficiently after the last table item in an array Deletion usually requires shifting data Retrieval requires a sequential search Figure 11 5a Insertion for unsorted linear implementations array based Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 9 Comparing Linear Implementations Sorted array based implementation Both insertions and deletions require shifting data Retrieval can use an efficient binary search Figure 11 6a Insertion for sorted linear implementations array based Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 10 Comparing Linear Implementations Unsorted pointer based implementation No data shifts Insertion is made efficiently at the beginning of a linked list Deletion requires a sequential search Retrieval requires a sequential search Figure 11 5b Insertion for unsorted linear implementations pointer based Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 11 Comparing Linear Implementations Sorted pointer based implementation No data shifts Insertions deletions and retrievals each require a sequential search Figure 11 6b Insertion for sorted linear implementations pointer based Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 12 Selecting an Implementation Linear Easy to understand conceptually May be appropriate for small tables or unsorted tables with few deletions Nonlinear Is usually a better choice than a linear implementation A balanced binary search tree Increases the efficiency of the table operations Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 13 Selecting an Implementation Figure 11 7 The average case order of the ADT table operations for various implementations Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 14 Selecting an Implementation for a Particular Application A Frequent insertions and infrequent traversals in no particular order Unsorted linear implementation Sorted array based implementation Binary search Balanced binary search tree Binary search tree preferably balanced B Frequent retrievals C Frequent retrievals insertions deletions traversals Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 15 A Sorted Array Based Implementation of the ADT Table Default constructor and virtual destructor Copy constructor supplied by the compiler Has a typedef declaration for a visit function Public methods are virtual Protected methods setSize setItem and position Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 16 A Binary Search Tree Implementation of the ADT Table Reuses BinarySearchTree An instance is a private data member Default constructor and virtual destructor Copy constructor supplied by the compiler Public methods are virtual Protected method setSize Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 17 The ADT Priority Queue A Variation of the ADT Table Orders items by a priority value The deletion operation for a priority queue is different from the one for a table The item removed is the one having the highest priority value Priority queues do not have retrieval and traversal operations Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 18 The ADT Priority Queue A Variation of the ADT Table Figure 11 8 UML diagram for the class PriorityQueue Copyright 2007 Pearson Education Inc Publishing as Pearson Addison Wesley Ver 5 0 19 The ADT Priority Queue Possible Implementations Sorted linear implementations Appropriate if the number of items in the priority queue is small Array based implementation Maintains the items sorted in ascending order of priority value items size 1 has the highest