page6.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 147 行
HTML
147 行
<HTML><HEAD><TITLE>Outline</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html1271" HREF="page7.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html1269" HREF="page3.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html1263" HREF="page5.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html1273" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION000330000000000000000">Outline</A></H2><P>This book presents material identified in the<em>Computing Curricula 1991</em>report of the ACM/IEEE-CS Joint Curriculum Task Force[<A HREF="page610.html#tucker">47</A>].The book specifically addresses the following <em>knowledge units</em>:AL1: Basic Data structures,AL2: Abstract Data Types,AL3: Recursive Algorithms,AL4: Complexity Analysis,AL6: Sorting and Searching, andAL8: Problem-Solving Strategies.The breadth and depth of coverage is typical ofwhat should appear in the second or third yearof an undergraduate program in computer science/computer engineering.<P>In order to analyze a program,it is necessary to develop a model of the computer.Chapter <A HREF="page36.html#chapmodel"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> develops several models and illustrates with exampleshow these models predict performance.Both average-case and worst-case analyses of running time are considered.Recursive algorithms are discussedand it is shown how to solve a recurrence using repeated substitution.This chapter also reviews arithmetic and geometric series summations,Horner's rule and the properties of harmonic numbers.<P>Chapter <A HREF="page58.html#chapasymptotic"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> introduces asymptotic (big-oh) notationand shows by comparing with Chapter <A HREF="page36.html#chapmodel"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>that the results of asymptotic analysis are consistentwith models of higher fidelity.In addition to <IMG WIDTH=27 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline57621" SRC="img1.gif" >,this chapter also covers other asymptotic notations( <IMG WIDTH=26 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline57623" SRC="img2.gif" >, <IMG WIDTH=27 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline57625" SRC="img3.gif" >, and <IMG WIDTH=23 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline57627" SRC="img4.gif" >)and develops the asymptotic properties of polynomials and logarithms.<P>Chapter <A HREF="page81.html#chapfds"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> introduces the <em>foundational data structures</em>--the array and the linked list.Virtually all the data structures in the rest of the bookcan be implemented using either one of these foundational structures.This chapter also covers multi-dimensional arrays and matrices.<P>Chapter <A HREF="page111.html#chapadts"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> deals with abstraction and data types.It presents the recurring design patterns used throughout the textas well a unifying framework for the data structures presentedin the subsequent chapters.In particular, all of the data structuresare viewed as <em>abstract containers</em>.<P>Chapter <A HREF="page130.html#chapstacks"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> discusses stacks, queues, and deques.This chapter presents implementations based on both foundational data structures (arrays and linked lists).Applications for stacks and queues are presented.<P>Chapter <A HREF="page168.html#chaplists"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> covers ordered lists, both sorted and unsorted.In this chapter, a list is viewed as a <em>searchable container</em>.Again several applications of lists are presented.<P>Chapter <A HREF="page205.html#chaphashing"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> introduces hashing and the notion of a hash table.This chapter addresses the design of hashing functionsfor the various basic data types as well as for the abstract data typesdescribed in Chapter <A HREF="page111.html#chapadts"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.Both scatter tables and hash tables are covered in depthand analytical performance results are derived.<P>Chapter <A HREF="page251.html#chaptrees"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> introduces trees and describes their many forms.Both depth-first and breadth-first tree traversals are presented.Completely generic traversal algorithms based on the use of the <em>visitor</em>design pattern are presented,thereby illustrating the power of <em>algorithmic abstraction</em>.This chapter also shows how trees are usedto represent mathematical expressionsand illustrates the relationships between traversals andthe various expression notations (prefix, infix, and postfix).<P>Chapter <A HREF="page298.html#chapsrchtree"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> addresses trees as <em>searchable containers</em>.Again, the power of <em>algorithmic abstraction</em> is demonstratedby showing the relationships between simple algorithmsand balancing algorithms.This chapter also presents average case performance analysesand illustrates the solution of recurrences by telescoping.<P>Chapter <A HREF="page351.html#chappqueues"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> presents several priority queue implementations,including binary heaps, leftist heaps, and binomial queues.In particular this chapter illustrates how a more complicated data structure(leftist heap) extends an existing one (tree).Discrete-event simulation is presented as an application of priority queues.<P>Chapter <A HREF="page386.html#chapsets"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> covers sets and multisets.Also covered are partitions and disjoint set algorithms.The latter topic illustrates again the use of algorithmic abstraction.<P>Garbage collection is discussed in Chapter <A HREF="page415.html#chapgarbage"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.This is a topic that is not found often in texts of this sort.However, because the Python language relies on garbage collection,it is important to understand how it worksand how it affects the running times of programs.<P>Chapter <A HREF="page433.html#chapalgorithms"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> surveys a number of algorithm design techniques.Included are brute-force and greedy algorithms,backtracking algorithms (including branch-and-bound),divide-and-conquer algorithms, and dynamic programming.An object-oriented approach based on the notion ofan <em>abstract solution space</em>and an <em>abstract solver</em> unifies much of the discussion.This chapter also covers briefly random number generators, Monte Carlo methods,and simulated annealing.<P>Chapter <A HREF="page478.html#chapsorting"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> covers the major sorting algorithmsin an object-oriented style based on the notion ofan <em>abstract sorter</em>.Using the abstract sorter illustrates the relationships betweenthe various classes of sorting algorithmand demonstrates the use of algorithmic abstractions.<P>Finally, Chapter <A HREF="page519.html#chapgraphs"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> presents an overview of graphs and graph algorithms.Both depth-first and breadth-first graph traversals are presented.Topological sort is viewed as yet another special kind of traversal.Generic traversal algorithms based on the <em>visitor</em>design pattern are presented,once more illustrating <em>algorithmic abstraction</em>.This chapter also covers various shortest path algorithmsand minimum-spanning-tree algorithms.<P>At the end of each chapter is a set of exercises anda set of programming projects.The exercises are designed to consolidatethe concepts presented in the text.The programming projects generallyrequire the student to extend the implementation given in the text.<P><HR><A NAME="tex2html1271" HREF="page7.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html1269" HREF="page3.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html1263" HREF="page5.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html1273" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright © 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.</ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?