C++编程：数据结构与C++11新增关键字详解

4星 · 超过85%的资源需积分: 10 78 浏览量更新于2024-07-21 收藏 6.38MB PDF 举报

数据结构是计算机科学中的核心概念，它涉及到如何组织和管理数据以便有效地存储、操作和检索信息。在本资源中，"Data Abstraction & Problem Solving" by Frank M. Carrano的PDF文件提供了关于C++语言中数据结构的深入理解，特别是C++11及以后版本引入的新关键字和特性。 C++是一种广泛使用的编程语言，其保留了若干关键字，这些关键字具有特定的语义，不能被重新定义或用于其他用途。以下是部分重要的C++关键字及其含义： 1. **alignas**: 从C++11起，`alignas`用于指定对象的内存对齐方式，确保数据在内存中的正确布局，提高性能。 2. **decltype**: 这个关键字用于获取表达式的类型，常用于函数返回类型推导和模板元编程。 3. **namespace**: C++中的命名空间用于避免名称冲突，提供了一个隔离的作用域，可以组织相关的标识符。 4. **struct**: 结构体是自定义数据类型，用于组合不同类型的数据成员，常用于封装数据和行为。 5. **alignof**: 计算类型在内存中的字节对齐，对于优化内存使用至关重要。 6. **default**: 关键字`default`通常与`switch`语句一起使用，表示未匹配任何case的默认处理。 7. **new** 和 **delete**: 分别用于动态分配内存和释放内存，是内存管理的基础。 8. **noexcept**: 表示一个函数不抛出异常，编译器可以进行优化假设。 9. **template**: C++的关键字，用于创建模板，实现泛型编程，适用于多种数据类型。 10. **_eq** 和 **not_eq**: 这些是运算符重载的一部分，分别代表相等（==）和不等于(!=)。 11. **do** 和 **while**: 控制流语句，do...while循环至少执行一次，之后根据条件判断是否继续。 12. **mutable**: 允许在常量对象上修改特定成员，与const关键字相对。 13. **static_cast** 和 **reinterpret_cast**: 强制类型转换，静态_cast用于安全类型转换，reinterpret_cast则允许更宽松的类型转换。 14. **nullptr**: C++11引入的空指针常量，用于明确表示没有指向的对象。 15. **throw** 和 **try**/**catch**: 异常处理的关键部分，用于捕获并处理运行时错误。 16. **bitwise shift operators** (<< 和 >>): 左移和右移操作符，用于位操作。 17. **<, <=, >, >=**: 关系运算符，用于比较两个值。这些关键字展示了C++中数据结构设计与实现的核心语法要素，以及如何利用它们来抽象问题，设计高效的算法和数据结构。理解并熟练运用这些概念，是成为高级C++程序员的必要基础。通过深入学习，开发者能够构建出健壮、可维护的程序，并充分利用C++的灵活性和性能优势。

xiii

Acknowledgements

Naff, Paul Nagin, Abhaya Nayak, Rayno Niemi, Debbie Noonan, John O’Donnell, Andrew Oldroyd, Larry

Olsen, Raymond L. Paden, Roy Pargas, Brenda C. Parker, Thaddeus F. Pawlicki, Keith Pierce, Gary Pollock,

Albert Prichard, Lucasz Pruski, George B. Purdy, David Radford, Bina Ramamanthy, Steve Ratering, Hal

Records, Stuart Regis, Mateen Rizki, J. D. Robertson, Daniel Rosenkrantz, Robert A. Rossi, Jerry Roth, John

Rowe, Michael E. Rupp, Sharon Salveter, Charles Saxon, Chandra Sekharan, Linda Shapiro, Yujian Sheng,

Mary Shields, Ren-Ben Shiu, Dmitri Slobodin, Ronnie Smith, Carl Spicola, Richard Snodgrass, Neil Snyder,

Ken Sousa, Chris Spannabel, Paul Spirakis, Clinton Staley, Matt Stallman, Mark Stehlick, Benjamin Schomp,

Harriet Taylor, David Teague, Virginia Teller, David Tetreault, Hans-Joerg Tiede, Lindsey Triebel, Dwight

Tuinista, John Turner, Karen Van Houten, Robert Vincent, Susan Wallace, James E. Warren, Xiaoqiao Wei,

Joyce Wells, Jerry Weltman, Nancy Wiegand, Alicia Williams, Howard Williams, Brad Wilson, James Wirth,

Wally Wood, Kathie Yerion, Salih Yurttas, Wu Yusong, Rick Zaccone, and Alan Zaring.

Finally, we thank our families and friends—Doug, Ted, Vandee, Nancy, Sue, Tom, Joanne, Tita, Bobby,

Lorraine, and Marge—for giving us lives away from computers.

Thank you all.

F. M. C.

T . H .

xiv

Table of Contents

Contents

Chapter 1 Data Abstraction: The Walls 1

1.1 Object-Oriented Concepts 2

1.1.1 Object-Oriented Analysis and Design 2

1.1.2 Aspects of an Object-Oriented Solution 3

1.2 Achieving a Better Solution 4

1.2.1 Cohesion 4

1.2.2 Coupling 5

1.3 Speciﬁ cations 6

1.3.1 Operation Contracts 6

1.3.2 Unusual Conditions 8

1.3.3 Abstraction 8

1.3.4 Information Hiding 9

1.3.5 Minimal and Complete Interfaces 10

1.4 Abstract Data Types 11

1.4.1 Designing an ADT 14

1.4.2 ADTs That Suggest Other ADTs 16

1.5 The ADT Bag 17

1.5.1 Identifying Behaviors 18

1.5.2 Specifying Data and Operations 19

1.5.3 An Interface Template for the ADT 22

1.5.4 Using the ADT Bag 24

C++ Interlude 1 C++ Classes 31

C1.1 A Problem to Solve 32

C1.1.1 Private Data Fields 33

C1.1.2 Constructors and Destructors 33

C1.1.3 Methods 34

C1.1.4 Preventing Compiler Errors 35

C1.2 Implementing a Solution 36

C1.3 Templates 37

C1.4 Inheritance 40

C1.4.1 Base Classes and Derived Classes 40

C1.4.2 Overriding Base-Class Methods 42

C1.5 Virtual Methods and Abstract Classes 44

C1.5.1 Virtual Methods 44

C1.5.2 Abstract Classes 45

Chapter 2 Recursion: The Mirrors 47

2.1 Recursive Solutions 48

2.2 Recursion That Returns a Value 50

2.2.1 A Recursive Valued Function: The Factorial of n 5 0

2.2.2 The Box Trace 54

2.3 Recursion That Performs an Action 57

2.3 .1 A Recursive Void Function: Writing a String Backward 57

2.4 Recursion with Arrays 67

2.4.1 Writing an Array’s Entries in Backward Order 67

2.4.2 The Binary Search 68

2.4.3 Finding the Largest Value in an Array 72

2.4.4 Finding the kth Smallest Value of an Array 72

xvxv

2.5 Organizing Data 76

2.5.1 The Towers of Hanoi 76

2.6 More Examples 79

2.6.1 The Fibonacci Sequence (Multiplying Rabbits) 79

2.6.2 Organizing a Parade 82

2.6.3 Choosing k Out of n Things 83

2.7 Recursion and Efﬁ ciency 85

Chapter 3 Array-Based Implementations 95

3.1 The Approach 96

3.1.1 Core Methods 97

3.1.2 Using Fixed-Size Arrays 98

3.2 An Array-Based Implementation of the ADT Bag 98

3.2.1 The Header File 99

3.2.2 Deﬁ ning the Core Methods 100

3.2.3 Testing the Core Methods 103

3.2.4 Implementing More Methods 105

3.2.5 Methods That Remove Entries 107

3.2.6 Testing 110

3.3 Using Recursion in the Implementation 112

3.3.1 The Method getIndexOf 112

3.3.2 The Method getFrequencyOf 113

C++ Interlude 2 Pointers, Polymorphism, and Memory Allocation 117

C2.1 Memory Allocation for Variables and Early Binding of Methods 118

C2.2 A Problem to Solve 118

C2.3 Pointers and the Program’s Free Store 120

C2.3.1 Deallocating Memory 122

C2.3.2 Avoiding Memory Leaks 123

C2.3.3 Avoiding Dangling Pointers 127

C2.4 Virtual Methods and Polymorphism 128

C2.5 Dynamic Allocation of Arrays 130

C2.5.1 A Resizable Array-Based Bag 131

Chapter 4 Link-Based Implementations 133

4.1 Preliminaries 134

4.1.1 The Class Node 136

4.2 A Link-Based Implementation of the ADT Bag 137

4.2.1 The Header File 138

4.2.2 Deﬁ ning the Core Methods 139

4.2.3 Implementing More Methods 143

4.3 Using Recursion in Link-Based Implementations 148

4.3.1 Recursive Deﬁ nitions of Methods in LinkedBag 148

4.4 Testing Multiple ADT Implementations 150

4.5 Comparing Array-Based and Link-Based Implementations 153

Chapter 5 Recursion as a Problem-Solving Technique 159

5.1 Deﬁ ning Languages 160

5.1.1 The Basics of Grammars 160

5.1.2 Two Simple Languages 162

5.2 Algebraic Expressions 164

5.2.1 Kinds of Algebraic Expressions 164

Table of Contents

xvi

Table of Contents

5.2.2 Preﬁ x Expressions 166

5.2.3 Postﬁ x Expressions 170

5.2.4 Fully Parenthesized Expressions 171

5.3 Backtracking 172

5.3.1 Searching for an Airline Route 172

5.3.2 The Eight Queens Problem 177

5.4 The Relationship Between Recursion and Mathematical Induction 183

5.4.1 The Correctness of the Recursive Factorial Function 183

5.4.2 The Cost of Towers of Hanoi 184

Chapter 6 Stacks 193

6.1 The Abstract Data Type Stack 194

6.1.1 Developing an ADT During the Design of a Solution 194

6.1.2 Speciﬁ cations for the ADT Stack 196

6.2 Simple Uses of a Stack 201

6.2.1 Checking for Balanced Braces 201

6.2.2 Recognizing Strings in a Language 203

6.3 Using Stacks with Algebraic Expressions 205

6.3.1 Evaluating Postﬁ x Expressions 205

6.3.2 Converting Inﬁ x Expressions to Equivalent Postﬁ x Expressions 206

6.4 Using a Stack to Search a Flight Map 210

6.5 The Relationship Between Stacks and Recursion 216

C++ Interlude 3 Exceptions 227

C3.1 Background 228

C3.1.1 A Problem to Solve 228

C3.2 Assertions 229

C3.3 Throwing Exceptions 230

C3.4 Handling Exceptions 233

C3.4.1 Multiple catch Blocks 235

C3.4.2 Uncaught Exceptions 236

C3.5 Programmer-Deﬁ ned Exception Classes 239

Chapter 7 Stack Implementations 241

7.1 An Array-Based Implementation 242

7.2 A Link-Based implementation 245

7.3 Implementations That Use Exceptions 249

Chapter 8 Lists 253

8.1 Specifying the ADT List 254

8.2 Using the List Operations 259

8.3 An Interface Template for the ADT List 261

Chapter 9 List Implementations 265

9.1 An Array-Based Implementation of the ADT List 266

9.1.1 The Header File 266

9.1.2 The Implementation File 268

9.2 A Link-Based Implementation of the ADT List 272

9.2.1 The Header File 272

9.2.2 The Implementation File 274

9.2.3 Using Recursion in LinkedList Methods 281

9.3 Comparing Implementations 285

xviixvii

Chapter 10 Algorithm Efﬁ ciency 289

10.1 What Is a Good Solution? 290

10.2 Measuring the Efﬁ ciency of Algorithms 291

10.2.1 The Execution Time of Algorithms 292

10.2.2 Algorithm Growth Rates 293

10.2.3 Analysis and Big O Notation 294

10.2.4 Keeping Your Perspective 298

10.2.5 The Efﬁ ciency of Searching Algorithms 300

Chapter 11 Sorting Algorithms and Their Efﬁ ciency 305

11.1 Basic Sorting Algorithms 306

11.1.1 The Selection Sort 306

11.1.2 The Bubble Sort 309

11.1.3 The Insertion Sort 311

11.2 Faster Sorting Algorithms 313

11.2.1 The Merge Sort 313

11.2.2 The Quick Sort 318

11.2.3 The Radix Sort 327

11.3 A Comparison of Sorting Algorithms 329

C++ Interlude 4 Class Relationships and Reuse 333

C4.1 Inheritance Revisited 333

C4.1.1 Public, Private, and Protected Sections of a Class 338

C4.1.2 Public, Private, and Protected Inheritance 340

C4.1.3 Is-a and As-a Relationships 340

C4.2 Containment: Has-a Relationships 342

C4.3 Abstract Base Classes Revisited 343

Chapter 12 Sorted Lists and Their Implementations 347

12.1 Specifying the ADT Sorted List 348

12.1.1 An Interface Template for the ADT Sorted List 350

12.1.2 Using the Sorted List Operations 351

12.2 A Link-Based Implementation 352

12.2.1 The Header File 353

12.2.2 The Implementation File 354

12.2.3 The Efﬁ ciency of the Link-Based Implementation 357

12.3 Implementations That Use the ADT List 357

12.3.1 Containment 357

12.3.2 Public Inheritance 362

12.3.3 Private Inheritance 366

Chapter 13 Queues and Priority Queues 373

13.1 The ADT Queue 374

13.2 Simple Applications of the ADT Queue 377

13.2.1 Reading a String of Characters 377

13.2.2 Recognizing Palindromes 377

13.3 The ADT Priority Queue 379

13.3.1 Tracking Your Assignments 380

13.4 Application: Simulation 381

13.5 Position-Oriented and Value-Oriented ADTs 389

Table of Contents

剩余837页未读，继续阅读

baidu_33485171

粉丝: 0
资源: 1

C++编程：数据结构与C++11新增关键字详解

data structure in Java

Data Structure

data structure(普林斯顿大学)

data structure and algorithm analysis in c下载

write codes in python replace (in your data structure) all city names with a unique name that contains the word "City" followed by a unique number. e.g. City1 City2 City100 City101 City102 ...

Data Structure＝（D，S）

critical data structure corruption怎么解决？

how to use a data structure like a dictionary or a custom class to associate the data with the value.

how to map nested values with Jackson to flatten out a complex data structure

最新资源