數據結構和編程設計·應用C語言(第二版)
本書以C++為描述語言，系統介紹數據結構的有關內容及程序設計方法。每章都是先引入實例，然后結合實例講解知識點，每章后都附有指針和陷阱的內容，還配有復習思考題，以檢驗讀者的學習效果和培養讀者的程序設計能...
本書以C++為描述語言，系統介紹數據結構的有關內容及程序設計方法。每章都是先引入實例，然后結合實例講解知識點，每章后都附有指針和陷阱的內容，還配有復習思考題，以檢驗讀者的學習效果和培養讀者的程序設計能力。此外，每章后還有深入學習本章知識點的閱讀參考資料，有利于讀者加深對本章知識點的理解。全書既注重原理又重視實踐，內容敘述詳細，并配有大量的實例和習題。書中所有算法均在計算機上運行通過，且程序中做了較詳細的注解，有利于讀者理解算法的實質和編程思想。
本書既可作為高等學校計算機及相關專業學生的教材，亦可供從事計算機應用的工程技術人員參考。
《數據結構和編程設計——應用C語言(第2版)》以C++為描述語言，系統介紹數據結構的有關內容及程序設計方法。每章都是先引入實例，然后結合實例講解知識點，每章后都附有指針和陷阱的內容，還配有復習思考題，以檢驗讀者的學習效果和培養讀者的程序設計能力。此外，每章后還有深入學習本章知識點的閱讀參考資料，有利于讀者加深對本章知識點的理解。全書既注重原理又重視實踐，內容敘述詳細，并配有大量的實例和習題。書中所有算法均在計算機上運行通過，且程序中做了較詳細的注解，有利于讀者理解算法的實質和編程思想。本書由克魯斯等著。
PREFACE
Synopsis
Changes in the Second Edition
Course Structure
Book Production
Acknowledgments
CHAPTER 1 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 Format
1.3.3 Refinement and Modularity
1.4 Coding,Testing,and Further 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 Coding 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 and Pitfalls
Review Questions
References for Further Study
CHAPTER 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 Stack
3.1.5 Implementation of Stacks
3.1.6 Linked Stacks
3.2 Introduction to Recursion
3.2.1 Stack Frames for SubprogralTts
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 AnalVsis of Backtracking
3.4 Principles of Recursion
3.4.1 DesiSntng 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 Conclusions
Pointrs 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 Airpoort
4.4.3 The Main Program
4.4.4 Steps of the Simulation
4.4.5 Pseudo-Random Numbers
4.4.6 Sample 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 Comparisonn 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 Insertion
7.2.3 Linked Version
7.2.4 Analysis
7.3 Selection Sort
7.3.1 The Algorithm
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 The Main Ideas
7.6.2 An Example
7.7 Mergesorft for Linked Lists
7.7.1 The Functions
7.7.2 AnalVsis of Mergsort
7.8 Quicksort for Contiguous Lists
7.8.1 The Main Function
7.8.2 Partitioning the List
7.8.3 Analysis of QLlickSort
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 Priority Queues
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 lgnbarrier
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 The Idea
8.5.2 Implementation
8.5.3 Analvsis
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 Conision 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 Algorithn
8.9.2 Specification of Data Structures
8.9.3 The Main Program
8.9.4 Functions
POinters and Pitfalls
Review Questions
References for Further Study
CHAPTER 9 Binarv Trees
9.1 Introduction to Binary Trees
9.1.1 Definitions
9.1.2 Traversal of Binary Trees
9.1.3 Linked Implementation of Billarv Trees
9.2 BinarV Search Trees
9.2.1 ordered Lists and Implementations
9.2.2 Treesearch
9.2.3 Insertion into a BinarV Search Tree
9.2.4 Treesort
9.2.5 Deletion from a Binarv 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 Optimalit
9.4 Height Balance:AVL Trees
9.4.1 Definition
9.4.2 Insertion of a Node
9.4.3 Deletion of a Node
9.4.4 The Height of an AVL Tree
9.5 Splav Trees:A Self-Adj usting Data Stlllcture
9.5.1 Introduction
9.5.2 Splayillg Steps
9.5.3 Splaying Algorithm
9.5.4 AmOrtized Algorithm AnalVsis: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 on the Classification of Species
10.1.2 Ordered Trees
10.1.3 Forests and Orchards
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 C Algorithm
10.2.4 Insertion into a Trie
10.2.5 Deletion from a Trie
10.2.6 Assessment of Tries
10.3 External Searchiring:B-Trees
10.3.1 Access Time
10.3.2 Multiway Search Trees
10.3.3 Balanced Multiway Trees
10.3.4 Insertion into a B-tree
10.3.5 C Algorithms: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 Game Trees
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 Defimtions 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 T0p010gical Sorting
11.4.1 The Problem
11.4.2 Depth-First Algorithm
11.4.3 Br.eadth.First AlgOrithm
11.5 A Greedy Algorithm:Shortest Paths
11.6 Graphs as Data Structures
P0interS and Pitfalls
Review Questions
References for Funher Study
CHAPTER 12 Case Study:The Polish Notation
12.1 The PrOblem
12.1
