![](https://csdnimg.cn/release/download_crawler_static/88491573/bg12.jpg)
xvi PREFACE
Chapter 5: Searching and Sorting. Introduces the concepts of searching and
sorting and illustrates how the efficiency of some ADTs can be improved when
working with sorted sequences. Search operations for an unsorted sequence are
discussed and the binary search algorithm is introduced as a way of improving this
operation. Three of the basic sorting algorithms are also introduced to further
illustrate the use of algorithm analysis. A new implementation of the Set ADT is
provided to show how different data structures or data organizations can change
the efficiency of an ADT.
Chapter 6: Linked Structures. Provides an introduction to dynamic structures
by illustrating the construction and use of the singly linked list using dynamic
storage allocation. The common operations — traversal, searching, insertion, and
deletion — are presented as is the use of a tail reference when appropriate. Several
of the ADTs presented in earlier chapters are reimplemented using the singly linked
list, and the run times of their operations are compared to the earlier versions.
A new implementation of the Sparse Matrix is especially eye-opening to many
students as it uses an array of sorted linked lists instead of a single Python list as
was done in an earlier chapter.
Chapter 7: Stacks. Introduces the Stack ADT and includes implementations
using both a Python list and a linked list. Several common stack applications
are then presented, including balanced delimiter verification and the evaluation of
postfix expressions. The concept of backtracking is also introduced as part of the
application for solving a maze. A detailed discussion is provided in designing a
solution and a partial implementation.
Chapter 8: Queues. Introduces the Queue ADT and includes three different
implementations: Python list, circular array, and linked list. The priority queue
is introduced to provide an opportunity to discuss different structures and data
organization for an efficient implementation. The application of the queue presents
the concept of discrete event computer simulations using an airline ticket counter
as the example.
Chapter 9: Advanced Linked Lists. Continues the discussion of dynamic struc-
tures by introducing a collection of more advanced linked lists. These include the
doubly linked, circularly linked, and multi linked lists. The latter provides an
example of a linked structure containing multiple chains and is applied by reimple-
menting the Sparse Matrix to use two arrays of linked lists, one for the rows and
one for the columns. The doubly linked list is applied to the problem of designing
and implementing an Edit Buffer ADT for use with a basic text editor.
Chapter 10: Recursion. Introduces the use of recursion to solve various pro-
gramming problems. The properties of creating recursive functions are presented
along with common examples, including factorial, greatest common divisor, and
the Towers of Hanoi. The concept of backtracking is revisited to use recursion for
solving the eight-queens problem.