具体描述
内容简介
本书强调问题的描述和程序的分析、设计、测试、验
证以及程序正确性，将深思熟虑的开发的基本思路融于具体
的程序设计之中。书中介绍了程序设计原理和软件工程知
识以及如何将这些原理和知识运用于程序（算法）设计，使
用大量实例介绍了几种主要数据结构：栈、表、树、图及主
要算法如递归、查找、排序、检索等，在介绍过程中注重运
用程序设计的先进思想和软件工程的解决方法。书中给出的
实例很有代表性，能覆盖大量程序设计原理。数据抽象是贯
穿全书的思想。本书还包括了如倾斜树、红黑树等很多新
的内容。最后，以一个完整的实例详细讨论了用递归、树、
栈等手段解决具体问题。附录中介绍了一些常用数学算法及
如何消除递归，并对C语言作了简单小结。
本书适合于计算机专业本科生作为学习数据结构的教材
或辅助教材。
作者简介
目录信息
PREFACE
Synopsis
Changes in the Second Edition
Course Structure
Book Production
Acknowledgments
CHAFTEltl
Programming Principles
1.1 Introduction
1.2 The Game of Life
1.2.1 Rules for the Game of Life
1.2.2 Examples
1.2.3 The Solution
1.2.4 Life: The Main Program
1.3 Programming Style
1.3.1 Names
1.3.2 Documentation and Fonnat
1.3.3 Refinement and Modularity
1.4 Coding, Testing, andFurther Refinement
1.4.1 Stubs
1.4.2 Counting Neighbors
1.4.3 Input and Output
1.4.4 Drivers
1.4.5 Program Tracing
1.4.6 Principles of Program Testing
Pointers and Pitfalls
Review Questions
References for Further Study
C
Programming Principles
The Game of Life
CHAPTER 2
Introduction to
Software Engineering
2.1 Program Maintenance
2.1.1 Review of the Life Program
2.1.2 A Fresh Start and a New Method for Life
2.2 Algorithm Development: A Second Version of Life
2.2.1 Lists: Specifications for a Data Structure
2.2.2 The Main Program
2.2.3 Information Hiding
2.2.4 Refinement: Development of the Subprograms
2.2.5 Verification of Algorithms
2.3 Coding
2.3.1 The List Functions
2.3.2 Error Processing
2.3.3 Demonstration and Testing
2.4 Ceding the Life Functions
2.5 Program Analysis and Comparison
2.6 Conclusions and Preview
2.6.1 The Game of Life
2.6.2 Program Design
2.6.3 C
Pointers ahd Pitfalls
Review Questions
References for Further Study
Contents
CHAFTER 3
Stacks and Recursion
3.1 Stacks
3.1.1 Introduction
3.1.2 First Example: Reversing a Line
3.1.3 Information Hiding
3.1.4 Specifications for a Stac-
3.1.5 Implementation of Stacks
3.1.6 Linked Stacks
3.2 Introduction to Recursion
3.2.1 Stack Frames for Subprograms
3.2.2 Tree of Subprogram Calls
3.2.3 Factorials: A Recursive Definition
3.2.4 Divide and Conquer:
The Towers of Hanoi
3.3 Backtracking: Postponing the Work
3.3.1 Solving the Eight-Queens Puzzle
3.3.2 Example: Four Queens
3.3.3 Backtracking
3.3.4 Refinement:
Choosing the Data Structures
3.3.5 Analysis of Backtracking
3.4 Principles of Recursion
3.4.1 Designing Recursive Algorithms
3.4.2 How Recursion Works
3.4.3 Tail Recursion
3.4.4 When Not to Use Recursion
3.4.5 Guidelines and Condusions
Pointers and Pitfalls
Review Questions
References for Further Study
CHAPTER 4
Queues and Linked Lists
4.1 Definitions
4.2 Implementations of Queues
4.3 Circular Queues in C
4.4 Application of Queues: Simulation
4.4.1 Introduction
4.4.2 Simulation of an Airport
4.4.3 The Main Program
4.4.4 Steps of the Simulation
4.4.5 Pseudo-Random Numbers
4.4.6 Sampie Results
4.5 Pointers and Linked Lists
4.5.1 Introduction and Survey
4.5.2 Pointers and Dynamic Memory in C
4.5.3 The Basics of Linked Lists
4.6 Linked Queues
4.7 Application: Polynomial Arithmetic
4.7.1 Purpose of the Project
4.7.2 The Main Program
4.7.3 Data Structures and Their Implementation
4.7.4 Reading and Writing Polynomials
4.7.5 Addition of Polynomials
4.7.6 Completing the Project
4.8 Abstract Data Types and
Their Implementations
4.8.1 Introduction
4.8.2 General Definitions '
4.8.3 Refinement of Data Specification
Pointers and Pitfalls
Review Questions
References for Further Study
CHAPTER 5
General Lists -
5.1 List Specifications
5.2 Implementation of Lists
5.2.1 Contiguous Implementation
5.2.2 Simply Linked Implementation
5.2.3 Variation: Keeping the Current Position
5.2.4 Doubly Linked Lists
5.2.5 Comparison of Implementations
5.3 Strings
5.4 Application: A Text Editor
5.4.1 Specifications
5.4.2 Implementation
5.5 Linked Lists in Arrays
5.6 Generating Permutations
Pointers and Pitfalls
Review Questions
References for Further Study
CHAPTER 6
Searching
6.1 Searching:
Introduction and Notation
6.2 Sequential Search
6.3 Coatrooms: A Project
6.3.1 Introduction and Specification
6.3.2 Demonstration and Testing
Programs
6.4 Binary Search
6.4.1 Algorithm Development
6.4.2 The Forgetful Version
6.4.3 Recognizing Equality
6.5 Comparison Trees
6.5.1 Analysis for n = 10
6.5.2 Generalization
6.5.3 Comparison of Methods
6.5.4 A General Relationship
6.6 Lower Bounds
6.7 Asymptotics
6.7.1 Introduction
6.7.2 The Big-O Notation
6.7.3 Imprecision of the Big-O Notation
6.7.4 Ordering of Common Functions
Pointers and Pitfalls
Review Questions
References for Further Study
CHAPTER 7
Sorting
7.1 Introduction and Notation
7.2 Insertion Sort
7.2.1 Ordered Lists
7.2.2 Sorting by Insertin.
7.2.3 Linked Version
7.2.4 Analysis
7.3 SelectionSort
7.3.1 TheAlgorithm
7.3.2 Contiguous Implementation
7.3.3 Analysis
7.3.4 Comparisons
7.4 Shell Sort
7.5 Lower Bounds
7.6 Divide-and-Conquer Sorting
7.6.1 TheMainldeas
7.6.2 An Example
7.7 Mergesort for Linked Lists
7.7.1 TheFunctions
7.7.2 Analysis of Mergesort
7.8 Quicksort for Contiguous Lists
7.8.1 The Main Function
7.8.2 Partitioning the List
7.8.3 Analysis of Quicksort
7.8.4 Average-Case Analysis of Quicksort
7.8.5 Comparison with Mergesort
7.9 Heaps and Heapsort
7.9.1 Two-Way Trees as Lists
7.9.2 Heapsort
7.9.3 Analysis of Heapsort
7.9.4 PriorityQueues
7.10 Review: Comparison of Methods
Pointers and Pitfalls
Review Questions
References for Further Study
CHAPTER 8
Tables and Information Retrieval
8.1 Introduction:
Breaking the Ig n Barrier
8.2 Rectangular Arrays
8.3 Tables of Various Shapes
8.3.1 Triangular Tables
8.3.2 Jagged Tables
8.3.3 Inverted Tables
8.4 Tables: A New Abstract Data Type
8.5 Application: Radix Sort
8.5.1 Theldea
8.5.2 Implementation
8.5.3 Analysis
8.6 Hashing
8.6.1 Sparse Tables
8.6.2 Choosing a Hash Function
8.6.3 Collision Resolution with
Open Addressing
8.6.4 Collision Resolution by Chaining
8.7 Analysis of Hashing
8.8 Conclusions:
Comparison of Methods
8.9 Application:
The Life Game Revisited
8.9.1 Choice of Algorithm
8.9.2 Specfication of Data Structures
8.9.3 The Main Program
8.9.4 Functions
Pointers and Pitfalls
Review Questions
References for Further Study
CHAPTER 9
Binary Trees
9.1 Introduction to Binarv Trees
9.1.1 Definitions
9.1.2 Traversal of Binary Trees
9.1.3 Linked Implementation of
BmaryTrees
9.2 Binary Search Trees
9.2.1 Ordered Lists and Implementations
9.2.2 Treesearch
9.2.3 Insertion into a Binary Search Tree
9.2.4 Treesort
9.2.5 Deletion from a Binary Search Tree
9.3 Building a Binary Search Tree
9.3.1 Getting Started
9.3.2 Declarations and the Main Function
9.3.3 Inserting a Node
9.3.4 Finishing the Task
9.3.5 Evaluation
9.3.6 Random Search Trees and
Optimality
9.4 Height Balance: AVL Trees
9.4.1 Definition
9.4.2 Insertion of a Node
9.4.3 Deletion of aNode
9.4.4 The Height of an AVL Tree
9.5 SplayTrees:
A Self-Adjusting Data Structure
9.5.1 Introduction
9.5.2 Splaying Steps
9.5.3 Splaying Algorithm
9.5.4 Amortized Algorithm Analysis:
Introduction
9.5.5 Amortized Analysis of Splaying
Pointers and Pitfalls
Review Questions
References for Further Study
CHAPTER 10
Multiway Trees
10.1 Orchards, Trees, and Binary Trees
10.1.1 OntheClassification of Spedes
10.1.2 Ordered Trees
10.1.3 Forests and Orehards
10.1.4 The Formal Correspondence
10.1.5 Rotations
10.1.6 Summary
10.2 Lexicographic Search Trees: Tries
10.2.1 Tries
10.2.2 Searching for a Key
10.2.3 CAlgorithm
10.2.4 Insertion into a Trie
10.2.5 Deletion from a Trie
10.2.6 AssessmentofTries
10.3 Extemal Searching: B-Trees
10.3.1 AccessTime
10.3.2 Multiway Search Trees
10.3.3 Balanced Multiway Trees
10.3.4 Insertion into a B-tree
10.3.5 CAlgorithms:
Searching and Insertion
10.3.6 Deletion from a B-tree
10.4 Red-Black Trees
10.4.1 Introduction
10.4.2 Definition and Analysis
10.4.3 Insertion
10.4.4 C Insertion
10.5 Tree-Structured Programs:
Look-Ahead in Games
10.5.1 GameTrees
10.5.2 The Minimax Method
10.5.3 Algorithm Development
10.5.4 Refinement
Pointers and Pitfalls
Review Questions
References for Further Study
CHAPTER 11
Graphs
11.1 Mathematical Background
11.1.1 Definitions and Examples
11.1.2 Undirected Graphs
11.1.3 Directed Graphs
11.2 Computer Representation
11.3 Graph Traversal
11.3.1 Methods
11.3.2 Depth-First Algorithm
11.3.3 Breadth-First Algorithm
11.4 Topological Sorting
11.4.1 TheProblem
11.4.2 Depth-First Algorithm
11.4.3 Breadth-First Algorithm
11.5 A Greedy Algorithm:
Shortest Paths
11.6 Graphs as Data Structures
Pointers and Pitfalls
Review Questions
References for Further Shudy
CHAPTER 12
Case Study: The Polish Notation
12.1 The Problem
12.1.1 The Quadratic Formula
12.2 The Idea
12.2.1 Expression Trees
12.2.2 Polish Notation
12.2.3 C Method
12.3 Evaluation of Polish Expressions
12.3.1 Evaluation of an Expression in
Prefix Form
12.3.2 C Conventions
12.3.3 C Function for Prefix Evaluation
12.3.4 Evaluation of Postfix Expressions
12.3.5 Proof of the Program:
Counting Stack Entries
12.3.6 Recursive Evaluation of
Postfix Expressions
12.4 Translation from Infix From to Polish
Fonn
12.5 An Interactive Expression
Evaluator
12.5.1 Overall Structure
12.5.2 Representation of the Data
12.5.3 Initialization and Auxiliary Tasks
12.5.4 Translation of the Expression
12.5.5 Evaluating the Expression
12.5.6 Graphing the Expression
References for Further Study
APPENDIX A
Mathematical Methods
A.l Sums of Powers of Integers
A.2 Logarithms
A.2.l Definition of Logarithms
A.2.2 Simple Properties
A.2.3 ChoiceofBase
A.2.4 Natural Logarithms
A.2.5 Notation
A.2.6 ChangeofBase
A.2.7 Logarithmic Graphs
A.2.8 Hannonic Numbers
A.3 Permutations, Combinations,
Factorials
A.3.l Permutations
A.3.2 Combinations
A.3.3 Factorials
A.4 Fibonacci Numbers
A.5 Catalan Numbers
A.5.1 ThevMain Result
A.5.2 The Proof by One-to-One
Correspondences
A.5.3 History
A.5.4 Numerical Results
References for Further Study
APPENDIX B
Removal of Recursion
B.l General Methods for Removing
Recursion
B.l.l Preliminary Assumptions
B.l.2 GeneralRules
B.1.3 Indirect Recursion
B.1.4 Towers of Hanoi
B.1.5 Further Simplifications
B.2 Recursion Removal by Folding
B.2.1 Program Schemata
B.2.2 Proof of the Transformation
B.2.3 Towers of Hanoi:
The Final Version
B.3 Nonrecursive Quicksort
B.4 Stackless Recursion Removal:
Mergesort
B.5 Threaded Binary Trees
B.5.1 Introduction
B.5.2 Threads
8.5.3 Inorder and Preorder Traversal
B.5.4 Insertion in a Threaded Tree
B.5.5 Postorder Traversal
References for Further Study
APPENDIX C
An Introduction to C
C.l Introduction
C.l.l Overview of a C Program
C.2 CElements
C.2.1 Reserved Words
C.2.2 Constants
C.3 Types and Declarations
C.3.1 Basic Types
C.3.2 Arrays
C.3-3 Enumerations
C.3 4 Structures
C.3.5 Unions
C.3.6 Type Definitions with typedef
C.4 Operators
C.5 Control Flow Statements
C.5.1 K-Else
C.5.2 Switch
C.5.3 Loops
C.5.4 Break and Continue
C.5.5 Goto
C.6 Pointers
C.6.1 Pointer to a Simple Variable
C.6.2 Pointer to an Array
C.6.3 Array of Pointers
C.6.4 Pointer to Structures
C.7 Functions
C.7.1 Arguments to Functions:
CallbyValue
C.7.2 Arguments to FUNctions:
Call by Reference
C.7.3 Function Prototypes and Include
Files
C.8 Pointers and Functions
C.8.1 Pointer to a FuCnction
C.8.2 Functions that Retum a Pointe
C.8.3 Pointer to a Pointer as an
Argument
References for Further Study
INDEX
· · · · · · (收起)
Synopsis
Changes in the Second Edition
Course Structure
Book Production
Acknowledgments
CHAFTEltl
Programming Principles
1.1 Introduction
1.2 The Game of Life
1.2.1 Rules for the Game of Life
1.2.2 Examples
1.2.3 The Solution
1.2.4 Life: The Main Program
1.3 Programming Style
1.3.1 Names
1.3.2 Documentation and Fonnat
1.3.3 Refinement and Modularity
1.4 Coding, Testing, andFurther Refinement
1.4.1 Stubs
1.4.2 Counting Neighbors
1.4.3 Input and Output
1.4.4 Drivers
1.4.5 Program Tracing
1.4.6 Principles of Program Testing
Pointers and Pitfalls
Review Questions
References for Further Study
C
Programming Principles
The Game of Life
CHAPTER 2
Introduction to
Software Engineering
2.1 Program Maintenance
2.1.1 Review of the Life Program
2.1.2 A Fresh Start and a New Method for Life
2.2 Algorithm Development: A Second Version of Life
2.2.1 Lists: Specifications for a Data Structure
2.2.2 The Main Program
2.2.3 Information Hiding
2.2.4 Refinement: Development of the Subprograms
2.2.5 Verification of Algorithms
2.3 Coding
2.3.1 The List Functions
2.3.2 Error Processing
2.3.3 Demonstration and Testing
2.4 Ceding the Life Functions
2.5 Program Analysis and Comparison
2.6 Conclusions and Preview
2.6.1 The Game of Life
2.6.2 Program Design
2.6.3 C
Pointers ahd Pitfalls
Review Questions
References for Further Study
Contents
CHAFTER 3
Stacks and Recursion
3.1 Stacks
3.1.1 Introduction
3.1.2 First Example: Reversing a Line
3.1.3 Information Hiding
3.1.4 Specifications for a Stac-
3.1.5 Implementation of Stacks
3.1.6 Linked Stacks
3.2 Introduction to Recursion
3.2.1 Stack Frames for Subprograms
3.2.2 Tree of Subprogram Calls
3.2.3 Factorials: A Recursive Definition
3.2.4 Divide and Conquer:
The Towers of Hanoi
3.3 Backtracking: Postponing the Work
3.3.1 Solving the Eight-Queens Puzzle
3.3.2 Example: Four Queens
3.3.3 Backtracking
3.3.4 Refinement:
Choosing the Data Structures
3.3.5 Analysis of Backtracking
3.4 Principles of Recursion
3.4.1 Designing Recursive Algorithms
3.4.2 How Recursion Works
3.4.3 Tail Recursion
3.4.4 When Not to Use Recursion
3.4.5 Guidelines and Condusions
Pointers and Pitfalls
Review Questions
References for Further Study
CHAPTER 4
Queues and Linked Lists
4.1 Definitions
4.2 Implementations of Queues
4.3 Circular Queues in C
4.4 Application of Queues: Simulation
4.4.1 Introduction
4.4.2 Simulation of an Airport
4.4.3 The Main Program
4.4.4 Steps of the Simulation
4.4.5 Pseudo-Random Numbers
4.4.6 Sampie Results
4.5 Pointers and Linked Lists
4.5.1 Introduction and Survey
4.5.2 Pointers and Dynamic Memory in C
4.5.3 The Basics of Linked Lists
4.6 Linked Queues
4.7 Application: Polynomial Arithmetic
4.7.1 Purpose of the Project
4.7.2 The Main Program
4.7.3 Data Structures and Their Implementation
4.7.4 Reading and Writing Polynomials
4.7.5 Addition of Polynomials
4.7.6 Completing the Project
4.8 Abstract Data Types and
Their Implementations
4.8.1 Introduction
4.8.2 General Definitions '
4.8.3 Refinement of Data Specification
Pointers and Pitfalls
Review Questions
References for Further Study
CHAPTER 5
General Lists -
5.1 List Specifications
5.2 Implementation of Lists
5.2.1 Contiguous Implementation
5.2.2 Simply Linked Implementation
5.2.3 Variation: Keeping the Current Position
5.2.4 Doubly Linked Lists
5.2.5 Comparison of Implementations
5.3 Strings
5.4 Application: A Text Editor
5.4.1 Specifications
5.4.2 Implementation
5.5 Linked Lists in Arrays
5.6 Generating Permutations
Pointers and Pitfalls
Review Questions
References for Further Study
CHAPTER 6
Searching
6.1 Searching:
Introduction and Notation
6.2 Sequential Search
6.3 Coatrooms: A Project
6.3.1 Introduction and Specification
6.3.2 Demonstration and Testing
Programs
6.4 Binary Search
6.4.1 Algorithm Development
6.4.2 The Forgetful Version
6.4.3 Recognizing Equality
6.5 Comparison Trees
6.5.1 Analysis for n = 10
6.5.2 Generalization
6.5.3 Comparison of Methods
6.5.4 A General Relationship
6.6 Lower Bounds
6.7 Asymptotics
6.7.1 Introduction
6.7.2 The Big-O Notation
6.7.3 Imprecision of the Big-O Notation
6.7.4 Ordering of Common Functions
Pointers and Pitfalls
Review Questions
References for Further Study
CHAPTER 7
Sorting
7.1 Introduction and Notation
7.2 Insertion Sort
7.2.1 Ordered Lists
7.2.2 Sorting by Insertin.
7.2.3 Linked Version
7.2.4 Analysis
7.3 SelectionSort
7.3.1 TheAlgorithm
7.3.2 Contiguous Implementation
7.3.3 Analysis
7.3.4 Comparisons
7.4 Shell Sort
7.5 Lower Bounds
7.6 Divide-and-Conquer Sorting
7.6.1 TheMainldeas
7.6.2 An Example
7.7 Mergesort for Linked Lists
7.7.1 TheFunctions
7.7.2 Analysis of Mergesort
7.8 Quicksort for Contiguous Lists
7.8.1 The Main Function
7.8.2 Partitioning the List
7.8.3 Analysis of Quicksort
7.8.4 Average-Case Analysis of Quicksort
7.8.5 Comparison with Mergesort
7.9 Heaps and Heapsort
7.9.1 Two-Way Trees as Lists
7.9.2 Heapsort
7.9.3 Analysis of Heapsort
7.9.4 PriorityQueues
7.10 Review: Comparison of Methods
Pointers and Pitfalls
Review Questions
References for Further Study
CHAPTER 8
Tables and Information Retrieval
8.1 Introduction:
Breaking the Ig n Barrier
8.2 Rectangular Arrays
8.3 Tables of Various Shapes
8.3.1 Triangular Tables
8.3.2 Jagged Tables
8.3.3 Inverted Tables
8.4 Tables: A New Abstract Data Type
8.5 Application: Radix Sort
8.5.1 Theldea
8.5.2 Implementation
8.5.3 Analysis
8.6 Hashing
8.6.1 Sparse Tables
8.6.2 Choosing a Hash Function
8.6.3 Collision Resolution with
Open Addressing
8.6.4 Collision Resolution by Chaining
8.7 Analysis of Hashing
8.8 Conclusions:
Comparison of Methods
8.9 Application:
The Life Game Revisited
8.9.1 Choice of Algorithm
8.9.2 Specfication of Data Structures
8.9.3 The Main Program
8.9.4 Functions
Pointers and Pitfalls
Review Questions
References for Further Study
CHAPTER 9
Binary Trees
9.1 Introduction to Binarv Trees
9.1.1 Definitions
9.1.2 Traversal of Binary Trees
9.1.3 Linked Implementation of
BmaryTrees
9.2 Binary Search Trees
9.2.1 Ordered Lists and Implementations
9.2.2 Treesearch
9.2.3 Insertion into a Binary Search Tree
9.2.4 Treesort
9.2.5 Deletion from a Binary Search Tree
9.3 Building a Binary Search Tree
9.3.1 Getting Started
9.3.2 Declarations and the Main Function
9.3.3 Inserting a Node
9.3.4 Finishing the Task
9.3.5 Evaluation
9.3.6 Random Search Trees and
Optimality
9.4 Height Balance: AVL Trees
9.4.1 Definition
9.4.2 Insertion of a Node
9.4.3 Deletion of aNode
9.4.4 The Height of an AVL Tree
9.5 SplayTrees:
A Self-Adjusting Data Structure
9.5.1 Introduction
9.5.2 Splaying Steps
9.5.3 Splaying Algorithm
9.5.4 Amortized Algorithm Analysis:
Introduction
9.5.5 Amortized Analysis of Splaying
Pointers and Pitfalls
Review Questions
References for Further Study
CHAPTER 10
Multiway Trees
10.1 Orchards, Trees, and Binary Trees
10.1.1 OntheClassification of Spedes
10.1.2 Ordered Trees
10.1.3 Forests and Orehards
10.1.4 The Formal Correspondence
10.1.5 Rotations
10.1.6 Summary
10.2 Lexicographic Search Trees: Tries
10.2.1 Tries
10.2.2 Searching for a Key
10.2.3 CAlgorithm
10.2.4 Insertion into a Trie
10.2.5 Deletion from a Trie
10.2.6 AssessmentofTries
10.3 Extemal Searching: B-Trees
10.3.1 AccessTime
10.3.2 Multiway Search Trees
10.3.3 Balanced Multiway Trees
10.3.4 Insertion into a B-tree
10.3.5 CAlgorithms:
Searching and Insertion
10.3.6 Deletion from a B-tree
10.4 Red-Black Trees
10.4.1 Introduction
10.4.2 Definition and Analysis
10.4.3 Insertion
10.4.4 C Insertion
10.5 Tree-Structured Programs:
Look-Ahead in Games
10.5.1 GameTrees
10.5.2 The Minimax Method
10.5.3 Algorithm Development
10.5.4 Refinement
Pointers and Pitfalls
Review Questions
References for Further Study
CHAPTER 11
Graphs
11.1 Mathematical Background
11.1.1 Definitions and Examples
11.1.2 Undirected Graphs
11.1.3 Directed Graphs
11.2 Computer Representation
11.3 Graph Traversal
11.3.1 Methods
11.3.2 Depth-First Algorithm
11.3.3 Breadth-First Algorithm
11.4 Topological Sorting
11.4.1 TheProblem
11.4.2 Depth-First Algorithm
11.4.3 Breadth-First Algorithm
11.5 A Greedy Algorithm:
Shortest Paths
11.6 Graphs as Data Structures
Pointers and Pitfalls
Review Questions
References for Further Shudy
CHAPTER 12
Case Study: The Polish Notation
12.1 The Problem
12.1.1 The Quadratic Formula
12.2 The Idea
12.2.1 Expression Trees
12.2.2 Polish Notation
12.2.3 C Method
12.3 Evaluation of Polish Expressions
12.3.1 Evaluation of an Expression in
Prefix Form
12.3.2 C Conventions
12.3.3 C Function for Prefix Evaluation
12.3.4 Evaluation of Postfix Expressions
12.3.5 Proof of the Program:
Counting Stack Entries
12.3.6 Recursive Evaluation of
Postfix Expressions
12.4 Translation from Infix From to Polish
Fonn
12.5 An Interactive Expression
Evaluator
12.5.1 Overall Structure
12.5.2 Representation of the Data
12.5.3 Initialization and Auxiliary Tasks
12.5.4 Translation of the Expression
12.5.5 Evaluating the Expression
12.5.6 Graphing the Expression
References for Further Study
APPENDIX A
Mathematical Methods
A.l Sums of Powers of Integers
A.2 Logarithms
A.2.l Definition of Logarithms
A.2.2 Simple Properties
A.2.3 ChoiceofBase
A.2.4 Natural Logarithms
A.2.5 Notation
A.2.6 ChangeofBase
A.2.7 Logarithmic Graphs
A.2.8 Hannonic Numbers
A.3 Permutations, Combinations,
Factorials
A.3.l Permutations
A.3.2 Combinations
A.3.3 Factorials
A.4 Fibonacci Numbers
A.5 Catalan Numbers
A.5.1 ThevMain Result
A.5.2 The Proof by One-to-One
Correspondences
A.5.3 History
A.5.4 Numerical Results
References for Further Study
APPENDIX B
Removal of Recursion
B.l General Methods for Removing
Recursion
B.l.l Preliminary Assumptions
B.l.2 GeneralRules
B.1.3 Indirect Recursion
B.1.4 Towers of Hanoi
B.1.5 Further Simplifications
B.2 Recursion Removal by Folding
B.2.1 Program Schemata
B.2.2 Proof of the Transformation
B.2.3 Towers of Hanoi:
The Final Version
B.3 Nonrecursive Quicksort
B.4 Stackless Recursion Removal:
Mergesort
B.5 Threaded Binary Trees
B.5.1 Introduction
B.5.2 Threads
8.5.3 Inorder and Preorder Traversal
B.5.4 Insertion in a Threaded Tree
B.5.5 Postorder Traversal
References for Further Study
APPENDIX C
An Introduction to C
C.l Introduction
C.l.l Overview of a C Program
C.2 CElements
C.2.1 Reserved Words
C.2.2 Constants
C.3 Types and Declarations
C.3.1 Basic Types
C.3.2 Arrays
C.3-3 Enumerations
C.3 4 Structures
C.3.5 Unions
C.3.6 Type Definitions with typedef
C.4 Operators
C.5 Control Flow Statements
C.5.1 K-Else
C.5.2 Switch
C.5.3 Loops
C.5.4 Break and Continue
C.5.5 Goto
C.6 Pointers
C.6.1 Pointer to a Simple Variable
C.6.2 Pointer to an Array
C.6.3 Array of Pointers
C.6.4 Pointer to Structures
C.7 Functions
C.7.1 Arguments to Functions:
CallbyValue
C.7.2 Arguments to FUNctions:
Call by Reference
C.7.3 Function Prototypes and Include
Files
C.8 Pointers and Functions
C.8.1 Pointer to a FuCnction
C.8.2 Functions that Retum a Pointe
C.8.3 Pointer to a Pointer as an
Argument
References for Further Study
INDEX
· · · · · · (收起)
读后感
评分
评分
评分
评分
评分
用户评价
评分
作为一本工具书，它的参考价值是毋庸置疑的。我经常在项目遇到性能瓶颈时，会翻开相应章节，重新审视自己选择的数据结构是否最优。这本书的排版清晰，图示虽然朴素，但指向性极强，每一张结构图都精确地对应着代码中的逻辑分支。我记得在学习堆（Heap）结构时，作者对“上滤”和“下滤”操作的描述，简洁到极致，但效率极高。与我之前看的那些界面华丽的教材不同，这里的重点完全聚焦在了“效率”和“正确性”上，没有一丝多余的装饰。这种务实到近乎冷酷的教学态度，反而培养了我一种更注重本质的思考方式。我发现，当我不再被花哨的界面分散注意力时，我的思维反而能更专注于算法的核心逻辑。对于已经有一定编程经验，想要从“会用”升级到“精通”数据结构的人来说，这本书无疑是一个绝佳的“纠错器”和“深化器”。
评分与其他版本相比，我感觉这本教材的语言风格非常“硬核”，它几乎没有使用任何花哨的比喻或者轻松的语调来稀释技术难度。它假设读者已经具备一定的C语言基础，并且愿意沉浸在逻辑的深处。这对我这种喜欢直面挑战的人来说，简直是福音。书中对各种经典排序算法的比较分析，不只是停留在时间复杂度上，还深入到了缓存命中率、指令流水线等更微观的层面，这在其他教材中是很少见的。我特别喜欢它在讲解二叉搜索树时，如何用实际的C代码来模拟节点的插入和删除，那种清晰的指针操作，让我感觉自己真的在直接和内存地址打交道。虽然阅读过程偶尔会感到吃力，需要反复查阅C语言的语法细节，但这就像是攀登一座技术高峰，每向上攀爬一米，视野就开阔一分。这本书的深度和广度，让我相信，如果能完全掌握其中的内容，应对未来任何更高级的算法挑战都会更有底气。
评分这本厚重的书摆在桌上，沉甸甸的，光是封面设计就透露着一种严谨的气息。初翻几页，那种C语言的冷峻和数据结构抽象概念的碰撞感就扑面而来。我记得自己一开始对着链表和树的章节感到一阵晕眩，指针的指来指去，内存的分配与释放，简直像是在迷宫里找出口。但是，作者的讲解方式非常有耐心，不是那种高高在上地抛出理论，而是像一位经验丰富的老教授，一步一步地帮你搭建思维框架。特别是书中对于算法复杂度的分析，不是简单地给出一个大O表示法就草草了事，而是会深入到每一步操作的成本，这一点对于想真正理解程序性能的读者来说，简直是醍醐灌顶。我花了好几天时间，对照着书上的例题，在IDE里一行一行地敲代码，调试，直到那些原本晦涩难懂的概念，比如AVL树的旋转或者图的深度优先搜索，真正“活”了起来，不再是纸面上的符号。这本书的价值就在于，它迫使你不仅仅是“知道”这些结构是什么，而是“懂得”它们是如何在机器底层运作的，这种扎实的功底，比单纯背诵几个算法口诀要有用得多。
评分这本书的英文原版特性，也带来了一种独特的阅读体验。它保留了计算机科学领域最原始、最精确的术语表达，没有经过太多“本土化”的翻译加工，这使得我们在学习国际标准概念时，能够直接对接学术前沿。我感觉自己阅读的不仅仅是一本教材，更像是在阅读一份经典的技术规范。特别是书中对于抽象数据类型（ADT）的定义和实现边界的划分，处理得非常干净利落，让人一眼就能分辨出概念的本质和实现的具体细节。虽然有时需要结合一本C语言参考手册一起阅读，来对照一些晦涩的C语言特性，但这反而强化了跨学科学习的习惯。总而言之，这本书不是那种让你轻松读完就搁置一旁的消遣读物，它更像是一副需要你不断打磨的精密刻刀，只有反复使用，才能真正体会到它雕琢出精妙程序的强大能力。它教会我如何用最精确的逻辑语言去构建复杂的世界。
评分拿到这本书时，我主要关注的是它对“程序设计”这个环节的侧重。市面上很多数据结构的书籍，内容偏向于纯粹的理论推导和数学证明，读起来像是在啃一本高深的数学著作，实践性不强。然而，这本“C语言描述”的版本，恰恰弥补了这一点。它不仅仅是告诉你“应该”怎么做，而是直接用最接近底层的C语言给你展示“如何”实现。我特别欣赏它在处理动态内存管理上的坦诚和细致，那些关于`malloc`和`free`的陷阱，书中都毫不留情地暴露出来，并给出了清晰的规避策略。这让我对C语言的敬畏之心油然而生——你必须对计算机的资源使用负责。记得有一次为了实现一个复杂的图算法，我光是调试内存泄漏就花了半个晚上，最后回头看书上的实现，才发现自己漏掉了一个关键的指针释放。这本书就像一面镜子，照出了我作为初学者的每一个粗心大意，强迫我养成严谨的编码习惯，这远比学会几个数据结构本身更有价值。
评分 评分 评分 评分 评分相关图书
本站所有内容均为互联网搜索引擎提供的公开搜索信息，本站不存储任何数据与内容，任何内容与数据均与本站无关，如有需要请联系相关搜索引擎包括但不限于百度，google,bing,sogou 等
© 2026 book.quotespace.org All Rights Reserved. 小美书屋 版权所有