算法I-IVC++ - CSDN文库

Algorithms

需积分: 10 120 浏览量更新于2023-07-13 评论收藏 7.45MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

Overview i

Overview

Robert Sedgewick has thoroughly rewritten and substantially expanded and updated his popular

work to provide current and comprehensive coverage of important algorithms and data

structures. Christopher Van Wyk and Sedgewick have developed new C++ implementations that

both express the methods in a concise and direct manner, and also provide programmers with

the practical means to test them on real applications.

Many new algorithms are presented, and the explanations of each algorithm are much more

detailed than in previous editions. A new text design and detailed, innovative figures, with

accompanying commentary, greatly enhance the presentation. The third edition retains the

successful blend of theory and practice that has made Sedgewick's work an invaluable resource

for more than 250,000 programmers!

This particular book, Parts 1n4, represents the essential first half of Sedgewick's complete work.

It provides extensive coverage of fundamental data structures and algorithms for sorting,

searching, and related applications. Although the substance of the book applies to programming

in any language, the implementations by Van Wyk and Sedgewick also exploit the natural match

between C++ classes and ADT implementations.

Highlights

 Expanded coverage of arrays, linked lists, strings, trees, and other basic data structures

 Greater emphasis on abstract data types (ADTs), modular programming, object-oriented

programming, and C++ classes than in previous editions

 Over 100 algorithms for sorting, selection, priority queue ADT implementations, and

symbol table ADT (searching) implementations

 New implementations of binomial queues, multiway radix sorting, randomized BSTs,

splay trees, skip lists, multiway tries, B trees, extendible hashing, and much more

 Increased quantitative information about the algorithms, giving you a basis for

comparing them

 Over 1000 new exercises to help you learn the properties of algorithms

Whether you are learning the algorithms for the first time or wish to have up-to-date reference

material that incorporates new programming styles with classic and new algorithms, you will find

a wealth of useful information in this book.

0201350882B04062001

ii Contents

Contents

Overview........................................................................................................................ i

Contents ....................................................................................................................... ii

Copyright ..................................................................................................................... vi

Dedication ...................................................................................................................vi

Use in the Curriculum.................................................................................................. viii

Algorithms of Practical Use.............................................................................................ix

Programming Language ..................................................................................................x

Acknowledgments ..........................................................................................................x

Part One: Fundamentals................................................................................................... 1

Chapter One. Introduction ............................................................................................ 1

1.1. Algorithms............................................................................................................. 2

1.2. A Sample Problem: Connectivity .............................................................................. 4

1.3. Union–Find Algorithms ............................................................................................ 8

1.4. Perspective...........................................................................................................25

1.5. Summary of Topics ................................................................................................27

Chapter Two. Principles of Algorithm Analysis ............................................................ 29

2.1. Implementation and Empirical Analysis ....................................................................30

2.2. Analysis of Algorithms............................................................................................34

2.3. Growth of Functions...............................................................................................37

2.4. Big-Oh Notation ....................................................................................................45

2.5. Basic Recurrences .................................................................................................52

2.6. Examples of Algorithm Analysis...............................................................................58

2.7. Guarantees, Predictions, and Limitations ..................................................................65

References for Part One ................................................................................................69

Part Two: Data Structures .............................................................................................. 71

Chapter Three. Elementary Data Structures ................................................................ 71

3.1. Building Blocks......................................................................................................73

3.2. Arrays..................................................................................................................84

3.3. Linked Lists ..........................................................................................................94

3.4. Elementary List Processing ................................................................................... 103

3.5. Memory Allocation for Lists...................................................................................114

3.6. Strings...............................................................................................................118

3.7. Compound Data Structures...................................................................................124

Chapter Four. Abstract Data Types............................................................................ 136

4.1. Abstract Objects and Collections of Objects ............................................................145

4.2. Pushdown Stack ADT ...........................................................................................148

4.3. Examples of Stack ADT Clients..............................................................................152

4.4. Stack ADT Implementations.................................................................................. 161

Contents iii

4.5. Creation of a New ADT .........................................................................................167

4.6. FIFO Queues and Generalized Queues.................................................................... 174

4.7. Duplicate and Index Items ................................................................................... 184

4.8. First-Class ADTs .................................................................................................. 191

4.9. Application-Based ADT Example ............................................................................205

4.10. Perspective ....................................................................................................... 212

Chapter Five. Recursion and Trees ............................................................................ 213

5.1. Recursive Algorithms ...........................................................................................214

5.2. Divide and Conquer .............................................................................................223

5.3. Dynamic Programming.........................................................................................242

5.4. Trees .................................................................................................................254

5.5. Mathematical Properties of Binary Trees ................................................................. 264

5.6. Tree Traversal ..................................................................................................... 269

5.7. Recursive Binary-Tree Algorithms ..........................................................................276

5.8. Graph Traversal................................................................................................... 283

5.9. Perspective.........................................................................................................292

References for Part Two ..............................................................................................293

Part Three: Sorting....................................................................................................... 295

Chapter Six. Elementary Sorting Methods ................................................................. 295

6.1. Rules of the Game...............................................................................................297

6.2. Selection Sort .....................................................................................................304

6.3. Insertion Sort ..................................................................................................... 306

6.4. Bubble Sort ........................................................................................................ 309

6.5. Performance Characteristics of Elementary Sorts.....................................................312

6.6. Shellsort ............................................................................................................319

6.7. Sorting of Other Types of Data ..............................................................................331

6.8. Index and Pointer Sorting..................................................................................... 337

6.9. Sorting of Linked Lists..........................................................................................346

6.10. Key-Indexed Counting........................................................................................351

Chapter Seven. Quicksort.......................................................................................... 355

7.1. The Basic Algorithm.............................................................................................356

7.2. Performance Characteristics of Quicksort................................................................362

7.3. Stack Size ..........................................................................................................367

7.4. Small Subfiles..................................................................................................... 372

7.5. Median-of-Three Partitioning .................................................................................375

7.6. Duplicate Keys .................................................................................................... 381

7.7. Strings and Vectors .............................................................................................385

7.8. Selection ............................................................................................................388

Chapter Eight. Merging and Mergesort ...................................................................... 392

8.1. Two-Way Merging ................................................................................................394

8.2. Abstract In-Place Merge .......................................................................................396

8.3. Top-Down Mergesort............................................................................................399

iv Contents

8.4. Improvements to the Basic Algorithm .................................................................... 403

8.5. Bottom-Up Mergesort ..........................................................................................406

8.6. Performance Characteristics of Mergesort ...............................................................412

8.7. Linked-List Implementations of Mergesort ..............................................................415

8.8. Recursion Revisited .............................................................................................419

Chapter Nine. Priority Queues and Heapsort ............................................................. 421

9.1. Elementary Implementations ................................................................................ 425

9.2. Heap Data Structure ............................................................................................430

9.3. Algorithms on Heaps............................................................................................433

9.4. Heapsort ............................................................................................................443

9.5. Priority-Queue ADT..............................................................................................452

9.6. Priority Queues for Index Items ............................................................................459

9.7. Binomial Queues ................................................................................................. 464

Chapter Ten. Radix Sorting ....................................................................................... 478

10.1. Bits, Bytes, and Words .......................................................................................480

10.2. Binary Quicksort................................................................................................484

10.3. MSD Radix Sort ................................................................................................. 490

10.4. Three-Way Radix Quicksort ................................................................................. 500

10.5. LSD Radix Sort.................................................................................................. 505

10.6. Performance Characteristics of Radix Sorts ...........................................................510

10.7. Sublinear-Time Sorts..........................................................................................514

Chapter Eleven. Special-Purpose Sorting Methods .................................................... 520

11.1. Batcher's Odd–Even Mergesort............................................................................522

11.2. Sorting Networks...............................................................................................530

11.3. External Sorting ................................................................................................541

11.4. Sort–Merge Implementations ..............................................................................547

11.5. Parallel Sort–Merge............................................................................................555

References for Part Three............................................................................................559

Part Four: Searching .................................................................................................... 561

Chapter Twelve. Symbol Tables and Binary Search Trees.......................................... 561

12.1. Symbol-Table Abstract Data Type.........................................................................563

12.2. Key-Indexed Search...........................................................................................569

12.3. Sequential Search..............................................................................................573

12.4. Binary Search ................................................................................................... 581

12.5. Binary Search Trees (BSTs).................................................................................588

12.6. Performance Characteristics of BSTs .................................................................... 596

12.7. Index Implementations with Symbol Tables ..........................................................601

12.8. Insertion at the Root in BSTs............................................................................... 606

12.9. BST Implementations of Other ADT Functions .......................................................614

Chapter Thirteen. Balanced Trees ............................................................................. 625

13.1. Randomized BSTs ..............................................................................................629

13.2. Splay BSTs ....................................................................................................... 638

Contents v

13.3. Top-Down 2-3-4 Trees........................................................................................647

13.4. Red–Black Trees ................................................................................................654

13.5. Skip Lists..........................................................................................................666

13.6. Performance Characteristics................................................................................675

Chapter Fourteen. Hashing ....................................................................................... 678

14.1. Hash Functions.................................................................................................. 679

14.2. Separate Chaining .............................................................................................691

14.3. Linear Probing...................................................................................................696

14.4. Double Hashing ................................................................................................. 704

14.5. Dynamic Hash Tables .........................................................................................711

14.6. Perspective ....................................................................................................... 716

Chapter Fifteen. Radix Search ................................................................................... 721

15.2. Tries ................................................................................................................730

15.3. Patricia Tries .....................................................................................................741

15.4. Multiway Tries and TSTs...................................................................................... 753

15.5. Text-String–Index Algorithms..............................................................................773

Chapter Sixteen. External Searching ......................................................................... 778

16.1. Rules of the Game .............................................................................................780

16.2. Indexed Sequential Access.................................................................................. 782

16.3. B Trees.............................................................................................................786

16.4. Extendible Hashing ............................................................................................800

16.5. Perspective ....................................................................................................... 813

References for Part Four .............................................................................................816

剩余830页未读，继续阅读

arthashk

粉丝: 0
资源: 6

会员权益专享

算法 I-IV C++

评论0

会员权益专享

最新资源

算法 I-IV C++

评论0

算法I-IV(C++实现):基础数据结构排序和搜索(第3版)

算法Ⅰ-Ⅳ(C++ 实现)--基础、数据结构、排序和搜索

c++算法（排序 搜索）.pdf

C++ fftw_plan_r2r_1d

C++实现SHA-1算法

DES加密算法自动填充c++实现

c++zuc算法加密解密txt文本

aes加密算法c++语言实现

aes加密算法的c++实现

lblock加密算法代码c++

自己编写ZUC算法（C++）

aes128加解密算法c++实现

aes算法的c++实现

AES 加密解密算法c++实现

C++builder XE6如何进行AES加密并支持偏移量（IV）

请写出QT5 用AES和DES分别在ECB和CBC模式下的加解密算法

c++实现DES算法在CBC模式下】

请用c++实现SM3签名算法

c++买卖股票的最佳时机

不引用任何数据库，写出基于c++的AES加密算法

会员权益专享

最新资源

c++算法（排序搜索）.pdf