page6.html
来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 146 行 · 第 1/2 页
HTML
146 行
<HTML>
<HEAD>
<TITLE>Outline</TITLE>
</HEAD>
<BODY bgcolor="#FFFFFF">
<img src="cover75.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cover75.gif" alt="Logo" align=right>
<b>Data Structures and Algorithms
with Object-Oriented Design Patterns in C++</b><br>
<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> <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="page619.html#tucker" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page619.html#tucker">38</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, and
AL8: Problem-Solving Strategies.
The breadth and depth of coverage is typical of
what should appear in the second or third year
of 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="page34.html#chapmodel" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page34.html#chapmodel"><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> develops several models and illustrates with examples
how these models predict performance.
Both average-case and worst-case analyses of running time are considered.
Recursive algorithms are discussed
and 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="page56.html#chapasymptotic" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page56.html#chapasymptotic"><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> introduces asymptotic (big-oh) notation
and shows by comparing with Chapter <A HREF="page34.html#chapmodel" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page34.html#chapmodel"><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>
that the results of asymptotic analysis are consistent
with models of higher fidelity.
In addition to <IMG WIDTH=28 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58163" SRC="img1.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1.gif" >,
this chapter also covers other asymptotic notations
( <IMG WIDTH=26 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58165" SRC="img2.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img2.gif" >, <IMG WIDTH=27 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58167" SRC="img3.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img3.gif" > and <IMG WIDTH=23 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58169" SRC="img4.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img4.gif" >)
and develops the asymptotic properties of polynomials and logarithms.
<P>
Chapter <A HREF="page79.html#chapfds" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page79.html#chapfds"><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> introduces the <em>foundational data structures</em>--the array and the linked list.
Virtually all the data structures in the rest of the book
can be implemented using either one of these foundational structures.
This chapter also covers multi-dimensional arrays and matrices.
<P>
Chapter <A HREF="page107.html#chapadts" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page107.html#chapadts"><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> deals with abstraction and data types.
It presents the recurring design patterns used throughout the text
as well a unifying framework for the data structures presented
in the subsequent chapters.
In particular, all of the data structures
are viewed as <em>abstract containers</em>.
<P>
Chapter <A HREF="page130.html#chapstacks" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page130.html#chapstacks"><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> discusses stacks, queues and deques.
This chapter presents implementations based on both
foundational data structures (arrays and linked lists).
Applications for stacks and queues and queues are presented.
<P>
Chapter <A HREF="page166.html#chaplists" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page166.html#chaplists"><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 ordered lists, but 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="page203.html#chaphashing" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page203.html#chaphashing"><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> introduces hashing and the notion of a hash table.
This chapter addresses the design of hashing functions
for the various basic data types as well as for the abstract data types
described in Chapter <A HREF="page107.html#chapadts" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page107.html#chapadts"><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>.
Both scatter tables and hash tables are covered in depth
and analytical performance results are derived.
<P>
Chapter <A HREF="page250.html#chaptrees" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page250.html#chaptrees"><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> introduces trees and describes their many forms.
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?