昨天阅读3小时，累计977小时
Chapter 1: Abstract Data Types. Introduces the concept of abstract data types(ADTs) for both simple types, those containing individual data fields, and the morecomplex types, those containing data structures. ADTs are presented in termsof their definition, use, and implementation. After discussing the importance ofabstraction, we define several ADTs and then show how a well-defined ADT canbe used without knowing how its actually implemented. The focus then turns tothe implementation of the ADTs with an emphasis placed on the importance ofselecting an appropriate data structure. The chapter includes an introduction tothe Python iterator mechanism and provides an example of a user-defined iteratorfor use with a container type ADT.
Chapter 2: Arrays. Introduces the student to the array structure, which is important since Python only provides the list structure and students are unlikely tohave seen the concept of the array as a fixed-sized structure in a first course usingPython. We define an ADT for a one-dimensional array and implement it using ahardware array provided through a special mechanism of the C-implemented version of Python. The two-dimensional array is also introduced and implementedusing a 1-D array of arrays. The array structures will be used throughout the textin place of the Python’s list when it is the appropriate choice. The implementation of the list structure provided by Python is presented to show how the variousoperations are implemented using a 1-D array. The Matrix ADT is introduced andincludes an implementation using a two-dimensional array that exposes the students to an example of an ADT that is best implemented using a structure otherthan the list or dictionary.
Chapter 3: Sets and Maps. This chapter reintroduces the students to boththe Set and Map (or dictionary) ADTs with which they are likely to be familiarfrom their first programming course using Python. Even though Python providesthese ADTs, they both provide great examples of abstract data types that can beimplemented in many different ways. The chapter also continues the discussion ofarrays from the previous chapter by introducing multi-dimensional arrays (thoseof two or more dimensions) along with the concept of physically storing theseusing a one-dimensional array in either row-major or column-major order. Thechapter concludes with an example application that can benefit from the use of athree-dimensional array.
Chapter 4: Algorithm Analysis. Introduces the basic concept and importanceof complexity analysis by evaluating the operations of Python’s list structure andthe Set ADT as implemented in the previous chapter. This information will be usedto provide a more efficient implementation of the Set ADT in the following chapter.The chapter concludes by introducing the Sparse Matrix ADT and providing a moreefficient implementation with the use of a list in place of a two-dimensional array.
Chapter 5: Searching and Sorting. Introduces the concepts of searching andsorting and illustrates how the efficiency of some ADTs can be improved whenworking with sorted sequences. Search operations for an unsorted sequence arediscussed and the binary search algorithm is introduced as a way of improving thisoperation. Three of the basic sorting algorithms are also introduced to furtherillustrate the use of algorithm analysis. A new implementation of the Set ADT isprovided to show how different data structures or data organizations can changethe efficiency of an ADT.
Chapter 6: Linked Structures. Provides an introduction to dynamic structuresby illustrating the construction and use of the singly linked list using dynamicstorage allocation. The common operations — traversal, searching, insertion, anddeletion — are presented as is the use of a tail reference when appropriate. Severalof the ADTs presented in earlier chapters are reimplemented using the singly linkedlist, 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 manystudents as it uses an array of sorted linked lists instead of a single Python list aswas done in an earlier chapter.
Chapter 7: Stacks. Introduces the Stack ADT and includes implementationsusing both a Python list and a linked list. Several common stack applicationsare then presented, including balanced delimiter verification and the evaluation ofpostfix expressions. The concept of backtracking is also introduced as part of theapplication for solving a maze. A detailed discussion is provided in designing asolution and a partial implementation.
Chapter 8: Queues. Introduces the Queue ADT and includes three differentimplementations: Python list, circular array, and linked list. The priority queueis introduced to provide an opportunity to discuss different structures and dataorganization for an efficient implementation. The application of the queue presentsthe concept of discrete event computer simulations using an airline ticket counteras the example.
Chapter 9: Advanced Linked Lists. Continues the discussion of dynamic structures by introducing a collection of more advanced linked lists. These include thedoubly linked, circularly linked, and multi linked lists. The latter provides anexample of a linked structure containing multiple chains and is applied by reimplementing the Sparse Matrix to use two arrays of linked lists, one for the rows andone for the columns. The doubly linked list is applied to the problem of designingand implementing an Edit Buffer ADT for use with a basic text editor.
Chapter 10: Recursion. Introduces the use of recursion to solve various programming problems. The properties of creating recursive functions are presentedalong with common examples, including factorial, greatest common divisor, andthe Towers of Hanoi. The concept of backtracking is revisited to use recursion forsolving the eight-queens problem.
Chapter 11: Hash Tables. Introduces the concept of hashing and the use of hashtables for performing fast searches. Different addressing techniques are presented,including those for both closed and open addressing. Collision resolution techniquesand hash function design are also discussed. The magic behind Python’s dictionarystructure, which uses a hash table, is exposed and its efficiency evaluated.
Chapter 12: Advanced Sorting. Continues the discussion of the sorting problemby introducing the recursive sorting algorithms—merge sort and quick sort—alongwith the radix distribution sort algorithm, all of which can be used to sort sequences. Some of the common techniques for sorting linked lists are also presented.
Chapter 13: Binary Trees. Presents the tree structure and the general binarytree specifically. The construction and use of the binary tree is presented alongwith various properties and the various traversal operations. The binary tree isused to build and evaluate arithmetic expressions and in decoding Morse Codesequences. The tree-based heap structure is also introduced along with its use inimplementing a priority queue and the heapsort algorithm.
Chapter 14: Search Trees. Continues the discussion from the previous chapterby using the tree structure to solve the search problem. The basic binary searchtree and the balanced binary search tree (AVL) are both introduced along withnew implementations of the Map ADT. Finally, a brief introduction to the 2-3multi-way tree is also provided, which shows an alternative to both the binarysearch and AVL trees.A
ppendix A: Python Review. Provides a review of the Python language andconcepts learned in the traditional first course. The review includes a presentationof the basic constructs and built-in data structures.
Appendix B: User-Defined Modules. Describes the use of modules in creatingwell structured programs. The different approaches for importing modules is alsodiscussed along with the use of namespaces.
Appendix C: Exceptions. Provides a basic introduction to the use of exceptionsfor handling and raising errors during program execution.
Appendix D: Classes. Introduces the basic concepts of object-oriented programming, including encapsulation, inheritance, and polymorphism. The presentationis divided into two main parts. The first part presents the basic design and useof classes for those instructors who use a “back to basics” approach in teachingdata structures. The second part briefly explores the more advanced features ofinheritance and polymorphism for those instructors who typically include these
topics in their course.
扫码加好友，拉您进群
全部版块
我的主页
