< Free Open Study > |
After studying this chapter, you should be able to
Describe a priority queue at the logical level and implement a priority queue as a list
Describe the shape and order properties of a heap, and implement a heap in a nonlinked tree representation in an array
Implement a priority queue as a heap
Compare the implementations of a priority queue using a heap, a linked list, and a binary search tree
Define the following terms related to graphs:
Directed graph
Undirected graph
Vertex
Edge
Path
Complete graph
Weighted graph
Adjacency matrix
Adjacency list
Implement a graph using an adjacency matrix to represent the edges
Explain the difference between a depth-first and a breadth-first search, and implement these searching strategies using stacks and queues for auxiliary storage
Implement a shortest-path operation, using a priority queue to access the edge with the minimum weight
Describe a set at the logical level and implement a set both explicitly and implicitly
We have examined several basic data types in depth, discussing their uses and operations, and investigating one or more implementations of each. As we have constructed these programmer-defined data structures out of the built-in types provided by our high-level language, we have noted variations that adapt them to the needs of different applications. In Chapter 8, we saw how a tree structure, the binary search tree, facilitates searching data stored in a linked structure. In this chapter, we consider how other branching structures are used to model a variety of applications.
We end the chapter by looking at the Set ADT, an abstract data type that models the mathematical entity called a set.
< Free Open Study > |
Converted from CHM to HTML with chm2web Pro 2.85 (unicode) |