page6.html

来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 146 行 · 第 1/2 页

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 used
to represent mathematical expressions
and illustrates the relationships between traversals and
the various expression notations (prefix, infix and postfix).
<P>
Chapter&nbsp;<A HREF="page299.html#chapsrchtree" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page299.html#chapsrchtree"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> addresses trees as <em>searchable containers</em>.
Again, the power of <em>algorithmic abstraction</em> is demonstrated
by showing the relationships between simple algorithms
and balancing algorithms.
This chapter also presents average case performance analyses
and illustrates the solution of recurrences by telescoping.
<P>
Chapter&nbsp;<A HREF="page352.html#chappqueues" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page352.html#chappqueues"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/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&nbsp;<A HREF="page387.html#chapsets" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page387.html#chapsets"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/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>
Techniques for dynamic storage management are presented in Chapter&nbsp;<A HREF="page416.html#chapheap" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page416.html#chapheap"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>.
This is a topic that is not found often in texts of this sort.
However, the features of C++ which allow the user to redefine
the <tt>new</tt> and <tt>delete</tt> operators make this topic approachable.
<P>
Chapter&nbsp;<A HREF="page440.html#chapalgorithms" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page440.html#chapalgorithms"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/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 of
an <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&nbsp;<A HREF="page483.html#chapsorting" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page483.html#chapsorting"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> covers the major sorting algorithms
in an object-oriented style based on the notion of
an <em>abstract sorter</em>.
Using the abstract sorter illustrates the relationships between
the various classes of sorting algorithm
and demonstrates the use of algorithmic abstractions.
<P>
Finally, Chapter&nbsp;<A HREF="page523.html#chapgraphs" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page523.html#chapgraphs"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/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 algorithms
and minimum-spanning-tree algorithms.
<P>
At the end of each chapter is a set of exercises and
a set of programming projects.
The exercises are designed to consolidate
the concepts presented in the text.
The programming projects generally
require the student to extend the implementation given in the text.
<P>
<HR><A NAME="tex2html1337" HREF="page7.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page7.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html1335" HREF="page3.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page3.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html1329" HREF="page5.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page5.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html1339" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html1340" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <P><ADDRESS>
<img src="bruno.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/bruno.gif" alt="Bruno" align=right>
<a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html  \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address.  \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html">Copyright &#169; 1997</a> by <a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html  \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address.  \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html">Bruno R. Preiss, P.Eng.</a>  All rights reserved.

</ADDRESS>
</BODY>
</HTML>