第1页 / 共666页
第2页 / 共666页
第3页 / 共666页
第4页 / 共666页
第5页 / 共666页
第6页 / 共666页
第7页 / 共666页
第8页 / 共666页
The Art Of Computer Programming Volume 1 Third Edition.pdf
Cover
Preface
Procedure for Reading
Contents
1.0 Basic Concepts
1.1 Algorithms
1.1 Exercises
1.2 Mathematical Preliminaries
1.2.1 Mathematical Induction
1.2.1 Exercises
1.2.2 Numbers, Powers, and Logarithms
1.2.2 Exercises
1.2.3 Sums and Products
1.2.3 Exercises - First set
1.2.3 Exercises - Second Set
1.2.4 Integer Functions and Elementary Number Theory
1.2.4 Exercises
1.2.5 Permutations and Factorials
1.2.5 Exercises
1.2.6 Binomial Coefficients
1.2.6 Exercises
1.2.7 Harmonic Numbers
1.2.7 Exercises
1.2.8 Fibonacci Numbers
1.2.8 Exercises
1.2.9 Generating Functions
1.2.9 Exercises
1.2.10 Analysis of an Algorithm
1.2.10 Exercises
1.2.11 Asymptotic Representations
1.2.11.1 The O-Notation
1.2.11.1 Exercises
1.2.11.2 Euler's Summation Formula
1.2.11.2 Exercises
1.2.11.3 Some asymptotic calculations
1.2.11.3 Exercises
1.3 MIX
1.3.1 Description of MIX
1.3.1 Exercises
1.3.2 The MIX Assembly Language
1.3.2 Exercises - First set
1.3.2 Exercises - Second set
1.3.3 Applications ot Permutations
1.3.3 Exercises
1.4 Some Fundamental programming Techniques
1.4.1 Subroutines
1.4.1 Exercises
1.4.2 Coroutines
1.4.2 Exercises
1.4.3 Interpretive Routines
1.4.3.1 A MIX simulator
1.4.3.1 Exercises
1.4.3.2 Trace Routines
1.4.3.2 Exercises
1.4.4 Input and Output
1.4.4 Exercises
1.4.5 History and Bibliography
2.0 Information Structures
2.1 Introduction
2.1 Exercises
2.2 Linear Lists
2.2.1 Stacks, Queues, and Deques
2.2.1 Exercises
2.2.2 Sequential Allocation
2.2.2 Exercises
2.2.3 Linked Allocation
2.2.3 Exercises
2.2.4 Circular Lists
2.2.4 Exercises
2.2.5 Doubly Linked Lists
2.2.5 Exercises
2.2.6 Arrays and Orthogonal Lists
2.2.6 Exercises
2.3 Trees
2.3 Exercises
2.3.1 Traversing Binary Trees
2.3.1 Exercises
2.3.2 Binary Tree Representaion of Trees
2.3.2 Exercises
2.3.3 Other Representations of Trees
2.3.3 Exercises
2.3.4 Basic Mathematical Properties of Trees
2.3.4.1 Free Trees
2.3.4.1 Exercises
2.3.4.2 Oriented trees
2.3.4.2 Exercises
2.3.4.3 The "infinity lemma"
2.3.4.3 Exercises
2.3.4.4 Enumeration of trees
2.3.4.4 Exercises
2.3.4.5 Path length
2.3.4.5 Exercises
2.3.4.6 History and bibliography
2.3.4.6 Exercises
2.3.5 Lists and Garbage Collection
2.3.5 Exercises
2.4 Multilinked Structures
2.4 Exercises
2.5 Dynamic Storage Allocation
2.5 Exercises
2.6 History and Bibliography
Answers to Exercises
1.0
1.1
1.2
1.2.1
1.2.2
1.2.3
1.2.4
1.2.5
1.2.6
1.2.7
1.2.8
1.2.9
1.2.10
1.2.11.1
1.2.11.2
1.2.11.3
1.3
1.3.1
1.3.2
1.3.3
1.4
1.4.1
1.4.2
1.4.3
1.4.3.1
1.4.3.2
1.4.4
2.0
2.1
2.2
2.2.1
2.2.2
2.2.3
2.2.4
2.2.5
2.2.6
2.3
2.3.1
2.3.2
2.3.3
2.3.4
2.3.4.1
2.3.4.2
2.3.4.3
2.3.4.4
2.3.4.5
2.3.4.6
2.3.5
2.4
2.5
Appendix A - Tables of Numerical Quantities
Appendix B - Index to Notations
Index and Glossary
•
DONALD E. KNUTH Stanford University
.I .......
' • .,
• ..,
., ' .
I •
• I • ••
• �
-
I •
A
TT
of Addison
An Imprint
ADDISON-WESLEY
Inc.
Wesley Longman,
Volume 1 / Fundamental
Algorithms
THE ART OF
COMPUTER PROGRAMMING
THIRD EDITION
I'
Reading, Massachusetts
Berkeley,
California
· Harlow, England · Menlo Park, California
Bonn · Amsterdam · Tokyo · Mexico City
· Don Mills, Ontario · Sydney
•
TEX is a trademark
of the American
METAFDNT is a trademark
of Addison-Wes ley
Mathematical Society
Cataloging-in-Publication
Library of Congress
The art of computer programming : fundamental algorithms I Donald
KnuthJ Donald ErvinJ
1938-
Data
Ervin Knuth. --3rd ed.
xx,650 p. 24 em.
Includes bibliographical
ISBN 0-201-89683-4
1. Electronic digital computers--Progr
references and index.
amming.
2. Computer
algorithms. I. Title.
QA76.6.K64 1997
005.1--dc21
97-2147
CIP
page http: I /www-cs-faculty.
information
about this book and related
books.
stanford. edu/ ... knuth/taocp
.html contains
Internet
current
Copyright
© 1997 by Addison
All rights reserved.
No part of this
or transmitted,
Wesley Longman
publica
system,
retrieval
photocopying,
Printed
in the United
recording,
without
'
.. Published
or otherwise,
of America
States
tion may be reproduced,
stored
mechanical,
of the publisher.
simultaneously
in Canada.
the prior
consent
in a
in any form, or by any means, electronic,
'
ISBN 0-201-89683-4
Text printed on acid-free paper
1 2 3 4 5 6 7 8 9 MA 00999897
First printing, May 1997
PREFACE
Here is your book, the one your thousands of letters have asked us
to publish. It has taken us years
to do, checking and rechecking
recipes to bring you only the best, only the interesting,
countless
only the perfect.
Now we can say, without a shadow of a doubt, that every single one of them,
as well
if you follow the directions
to the Jetter, will work
for you exactly
as it did for us, even
if you have never cooked before.
- McCall's Cookbook (1963)
THE PROCESS of preparing
tive, not only because it
also because it can be an aesthetic
music. This book is the first volume of a multi-volume
designed
programs for a digital
can be economically
experience
to train the reader in various skills
computer is especially
but
poetry or
and scientifically
much like composing
attrac
rewarding,
set of books that has been
that go into a programmer's
The following
chapters
are not meant to serve as
an introduction
craft.
to computer
programming;
are actually
prerequisites
in order to understand
possess:
the reader is supposed to have had some previous
experience. The
very simple,
but a beginner
requires time
and practice
the concept of a digital computer.
The reader should
a) Some idea of how a stored-program
digital
computer works; not necessarily
the electronics,
machine's
memory and successively
executed.
rather the manner in which instructions
can be kept in the
b) An ability
to put the solutions
to problems into such explicit
computer can "understand"
they do exactly as they are told, no more and no less. This
them. (These machines have no common sense;
hardest concept to grasp when one first tries to use a computer.)
c) Some knowledge
ing (performing
of the most elementary
a set of instructions
such as loop
computer techniques,
and
repeatedly), the use of subroutines,
fact is the
terms that a
the use of indexed variables.
d) A little knowledge of
"bits,'' "floating
the text are given brief definitions
point," ''overflow,"
common computer jargon-"memory," "registers,"
''software."
Most words
not defined in
in the index at the close of each volume.
can perhaps be summed up into the single requirement
These four prerequisites
that the reader should have already written and
grams for at least one computer.
I have tried to write this
set of books in such a way that it will fill several
tested at least, say, four pro
needs. In the first place, these books are reference
works that summarize
the
v
------ ------------�-
. Vl PREFACE
in several
important fields. In the second place,
courses in the computer
or for college
for self-study
that has been acquired
knowledge
they can be used as textbooks
and information
a large number of exercises
sciences.
of them. I have also made an effort to fill the pages with
answers for most
facts rather than with
To meet both of these objectives,
into the text and have furnished
I have incorporated
vague, general commentary:
is intended
This set of books
in computers,
interested
Indeed, one of my main goals has
more accessible
use of computers,
information
for people who will be more than just
casually
yet it is by no means only for the computer specialist.
been to make these programming
techniques
to the many people working in other fields who can make fruitful
yet who cannot afford the time to locate all of the necessary
that is buried in technical
journals.
We might call the subject of these books "nonnumerical
Comput
analysis.''
problems
interpolation
topics are not treated here except in passing.
etc., but such
is an extremely
been associated
computer programming
of numerical
numerical
with the solution
of the roots of an equation,
ers have traditionally
such as the calculation
and integration,
Numerical
panding field, and many books have been written about it. Since the early
have been used even more often for problems in which
1960s, however,
numbers occur only by coincidence;
are being used, rather than
for addition and
subtraction
need for multiplication
concerned
the nonnumerical
its ability to do arithmetic.
in nonnumerical
We have some use
but we rarely feel any
for they are present in the background
computer programming will
decision-making
benefit from a study of
the computer's
with numerical
and division.
techniques,
interesting
Of course, even a person who is primarily
of numerical
and rapidly ex
computers
problems,
capabilities
programs as welL
The results
of research
in nonnumerical
analysis
are scattered
throughout
journals.
My approach has been to try to distill
numerous technical
litP.rature
by studying
can be applied to many types of programming
coordinate
theory applies
this vast
that are most bMic, in the sense that
they
I have attempted
to
as well as to show how the
the ideas into more or less of a "theory,"
to a wide variety of practical
the techniques
situations.
problems.
Of course, ''nonnumerical
analysis"
is a terribly
negative name for
this field
processing"
"Information
of study; it is n1uch better to have a positive,
the subject.
I am considering,
to propose analysis
covered in
of particular
of algorithms
computer algorithms."
and "programming
descriptive
term that characterizes
is too broad a designation
for the material
techniques"
is too narrow. Therefore I wish
name for the subject matter
as an appropriate
these books. This name is meant to imply "the
theory of the properties
The complete
the following
Volun1e
general outline:
set of books, entitled The Art of Computer
1. Fundamental
Chapter 2. Information
Chapter 1. Basic Concepts
Algorithms
Structures
Programming,
has
PREFACE •• Vll
Volume
2. Seminumerical
Algorithms
Chapter
Chapter
3. Random Numbers
4. Arithmetic
Volume
3. Sorting
and Searching
Chapter 5. Sorting
Chapter
6. Searching
Volume
4. Combinatorial
Algorithms
Searching
Chapter
Chapter
7. Combinatorial
8. Recursion
Volume
5. Syntactical
Algorithms
Scanning
Chapter
Chapter
9. Lexical
10. Parsing
Volume 4 deals with such a large topic,
(Volumes 4A, 4B, and 4C). Two additional
are also planned:
it actually
volumes
I started
Volume 6, Tbe Theory
but I soon found that it was more
out in 1962 to write a single
three separate
books
topics
on more
of Languages;
book with this sequence
Volume 7, Compilers.
of chapters,
specialized
important to treat
in depth rather
represents
length
course;
contains
to publish
has become sensible
by itself
so it
text has meant that
for a one-semester
The resulting
more than enough material
the series
have only one or two chapters
than to skim over them lightly.
each chapter
college
I know that it is strange to
I have decided
cross-references.
specifically
computer courses;
with the
will be used in the abridged edition
as in the complete
work.
in separate
in an entire book, but
numbering in order to facilitate
1 through 5 is planned,
intended
and/ or text for undergraduate
in these
of the material
The same chapter
its contents
more specialized
of Volumes
reference
to retain
A shorter
to serve as a more general
will be a subset
the original
information
numbering
omitted.
chapter
version
books,
volumes.
the subjects
of the
Volume 1 is not only a reference
The present
volume may be considered
basic material
other hand, may be read independently
as the "intersection"
that is used in all
of the entire
set,
the other
books.
of each
with the
be used in connection
book to
5, on the
2 through
in the sense that it contains
Volumes
other.
remaining
volumes;
text on the subject
or as a text on the subject
of Sections
languag
it may also be used in college
of data structures
courses
(emphasizing
mathematics
of discrete
or for self-study
as a
Chapter
2),
the material of
the material
(emphasizing
of machine
1.1, 1.2, 1.3.3, and 2.3.4), or as a text on the subject
of Sections
1.3 and 1.4).
e programming (emphasizing
The point of view I have adopted
the material
while writing
that taken in most contemporary
I am not trying
concerned
rather
books about computer
how to use somebody
to teach the reader
with teaching
goal was to bring readers to the
how to write better software
of knowledge
frontiers
people
My original
from
programming
in that
software.
else's
I am
in every
subject
that was treated.
But it is extremely
difficult
to keep up with a
field
these chapters differs
themselves.
.. . vn1 PREFACE
profitable,
and the rapid rise of computer
The subject
contributed
science
has become a vast tapestry
by tens of thousands
has made
with tens of
of talented
people
of subtle
results
Therefore
that is economically
such a dream impossible.
thousands
all over the world.
techniques
describe
of each subject,
attempted
to choose
usage.
programming
I have tried to
and to provide
that are likely
my new goal
them as well as I can. In particular,
to remain
important
has been to concentrate
decades,
for many more
I have tried to trace the history
on "classic"
and to
a solid foundation
terminology
include
all of the
that is concise
for future progress.
I have
and consistent
with current
computer
known ideas about sequential
that are both beautiful
and easy to state.
A few words are in order
content
about the mathematical
of this set
of books.
so that persons with no more than a knowledge
read it, skimming
briefly
over the more mathematical
has been organized
algebra may
The material
of high-school
portions;
yet a reader
interesting
mathematical
level
exercises
and also by arranging
stated
to be found in a separate
so that the primarily
of presentation
section)
who is mathematically inclined
will learn about many
mathematics.
techniques
has been achieved
to discrete
in part by assigning
related
This dual
to each
of the
ratings
mathematical
ones are marked specifically
as such,
so that the main mathematical
results
most sections
are
before their proofs. The proofs are either
(with answers
or they are given at the end of a section.
left as exercises
A reader
who is interested
primarily
may stop reading
in programming
rather
most sections
than in the
math
as soon as the
recognizably
difficult
. On the other hand, a mathematically
about computer
of interesting
material
collected
here. Much of
and
has been faulty,
programming
in proper
readers
to be a mathematician,
mathematical
it is
my duty
of this book is to instruct
Since I profess
integrity
as well as I can.
of elementary
calculus
will suffice for most of the mathematics
since most of the other theory
that is needed
is developed
herein.
mathematics
will find a wealth
mathematics
associated
ematics
becomes
oriented reader
the published
one of the
approaches
to maintain
A knowledge
purposes
to this subject.
mathematical
in these books,
However, I do need to use deeper
theory,
textbooks
number theor
where those subjects
y, etc.,
theorems
of complex
probability
and in such cases I refer to appropriate
variable theory,
at times,
are developed.
these books con
of
The advantages
The hardest
decision
that I had to make
while preparing
and of an informal
to present
the various
techniques.
the manner in which
cerned
flow charts
known; for a discussion
of this,
in the ACiv1
formal, precise
language
Communications,
"Computer-Drawn
description
step-by-step
see the article
Vol. 6 (September 1963),
of an algorithm
are well
3. Yet a
pages 555-56
any computer
algorithm,
language,
is also necessary
whether to
Flowcharts"
to specify
to decide
or to use a machine-oriented
use an algebraic
language
such as ALGOL
for this purpose.
and I needed
experts
will disagree
Per
with my decision
to use a
or FORTRAN,
haps many of toda
y's computer
machine-oriented
language,
the correct
for the following
choice,
but I have become convinced
that it was definitely
reasons:
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
