数据结构与算法分析：C语言描述(英文版.第2版)

    书籍
    计算机书籍
本书曾被评为20世纪顶尖的30部计算机著作之一，作者在数据结构和算法分析方面卓有建树，他的数据结构和算法分析的著作尤其畅销，并受到广泛好评，已被世界500余所大学选作教材。
在本书中，作者精炼并强化了他对算法和数据结构方面创新的处理方法。通过C程序的实现，着重阐述了抽象数据类型的概念，并对算法的效率、性能和运行时间进行了分析。
本书特色
·着重讨论了算法设计技巧，包括贪婪算法、分治算法、动态规划、随机化算法以及回溯算法。
·系统介绍了当前流行的论题和新的数据结构，如斐波那契堆、斜堆、二项队列、跳跃表和伸展树。
·详细讨论了摊还分析，考查书中介绍的一些高级数据结构。
·增加了高级数据结构及其实现的内容，包括红黑树、自顶向下伸展树、treap树、k-d树、配对堆等。
·整合了堆排序平均情况分析的一些新结果。

作者：(美国)韦斯(Mark Allen Weiss)
Mark Alien Weiss，1987年在普林斯顿大学获得计算机科学博士学位，师从RobertSedgewick，现任美国佛罗里达国际大学计算与信息科学学院教授。他曾担任全美AP（Adval、CedPlacement）考试计算机学科委员会主席。其主要研究方向是数据结构、算法和教育学。

1 Introduction 1
1.1. What's the Book About? 1
1.2. Mathematics Review 3
1.2.1. Exponents 3
1.2.2. Logarithms 3
1.2.3. Series 4
1.2.4. Modular Arithmetic 5
1.2.5. The P Word 6
1.3. A Brief Introduction to Recursion
Summary 12
Exercises 12
References 13
2 Algorithm Analysis 15
2.1. Mathematical Background 15
2.2. Model 18
2.3. What to Analyze 18
2.4. Running Tune Calculations 20
2.4.1. A Simple Example 21
2.4.2. General Rules 21
2.4.3. Solutions for the Maximum Subsequence Sum Problem 24

　　Purpose/Goals This book describes data structures, methods of organizing large amounts of data, and algorithm analysis, the estimation of the running time of algorithms. As com- puters become faster and faster, the need for programs that can handle large amounts of input becomes more acute. Paradoxically, this requires more careful attention to efficiency, since inefficiencies in programs become most obvious when input sizes are large. By analyzing an algorithm before it is actually coded, students can decide if a particular solution will be feasible. For example, in this text students look at specific problems and see how careful implementations can reduce the time constraint for large amounts of data from 16 years to less than a second. Therefore, no algorithm or data structure is presented without an explanation of its running time. In some cases, minute details that affect the running time of the implementation are explored.
　　Once a solution method is determined, a program must still be written. As computers have become more powerful, the problems they must solve have become larger and more complex, requiring development of more intricate programs. The goal of this text is to teach students good programming and algorithm analysis skills simultaneously so that they can develop such programs with the maximum amount of efficiency.
　　This book is suitable for either an advanced data structures (CS7) course or a first-year graduate course in algorithm analysis. Students should have some know- ledge of intermediate programming, including such topics as pointers and recursion, and some background in discrete math.
　　Approach
　　I believe it is important for students to learn how to program for themselves, not how to copy programs from a book. On the other hand, it is virtually impossible to discuss realistic programming issues without including sample code. For this reason, the book usually provides about one-half to three-quarters of an implementation, and the student is encouraged to supply the rest. Chapter 12, which is new to this edition, discusses additional data structures with an emphasis on implementation details.
　　The algorithms in this book are presented in ANSI C, which, despite some flaws, is arguably the most popular systems programming language. The use of C instead of Pascal allows the use of dynamically allocated arrays (see, for instance, rehashing in Chapter 5). It also produces simplified code in several places, usually because the and (&&:) operation is short-circuited.
　　Most criticisms of C center on the fact that it is easy to write code that is barely readable. Some of the more standard tricks, such as the simultaneous assignment and testing against 0 via
　　if Cx=y) are generally not used in the text, since the loss of clarity is compensated by only a few keystrokes and no increased speed. I believe that this book demonstrates that unreadable code can be avoided by exercising reasonable care. Overview Chapter 1 contains review material on discrete math and recursion. I believe the only way to be comfortable with recursion is to see good uses over and over. Therefore, recursion is prevalent in this text, with examples in every chapter except Chapter 5.
　　Chapter 2 deals with algorithm analysis. This chapter explains asymptotic anal- ysis and its major weaknesses. Many examples are provided, including an in-depth explanation of logarithmic running time. Simple recursive programs are analyzed by intuitively converting them into iterative programs. More complicated divide- and-conquer programs are introduced, but some of the analysis (solving recurrence relations) is implicitly delayed until Chapter 7, where it is performed in detail.
　　Chapter 3 covers lists, stacks, and queues. The emphasis here is on coding these data structures using ADTS, fast implementation of these data structures, and an exposition of some of their uses. There are almost no programs (just routines), but the exercises contain plenty of ideas for programming assignments.
　　Chapter 4 covers trees, with an emphasis on search trees, including external search trees (B-trees). The UNIX file system and expression trees are used as examples. AVL trees and splay trees are introduced but not analyzed. Seventy-five percent of the code is written, leaving similar cases to be completed by the student. More careful treatment of search tree implementation details is found in Chapter 12. Additional coverage of trees, such as file compression and game trees, is deferred until Chapter 10. Data structures for an external medium are considered as the final topic in several chapters.
　　Chapter 5 is a relatively short chapter concerning hash tables. Some analysis is performed, and extendible hashing is covered at the end of the chapter.
　　Chapter 6 is about priority queues. Binary heaps are covered, and there is additional material on some of the theoretically interesting implementations of priority queues. The Fibonacci heap is discussed in Chapter 11, and the pairing heap is discussed in Chapter 12.
　　Chapter 7 covers sorting. It is very specific with respect to coding details and analysis. All the important general-purpose sorting algorithms are covered and compared. Four algorithms are analyzed in detail: insertion sort, Shellsort, heapsort, and quicksort. The analysis of the average-case running time of heapsort is new to this edition. External sorting is covered at the end of the chapter.
　　Chapter 8 discusses the disjoint set algorithm with proof of the running time. This is a short and specific chapter that can be skipped if Kruskal's algorithm is not discussed.
　　Chapter 9 covers graph algorithms. Algorithms on graphs are interesting, not only because they frequently occur in practice but also because their running time is so heavily dependent on the proper use of data structures. Virtually all of the standard algorithms are presented along with appropriate data structures, pseudocode, and analysis of running time. To place these problems in a proper context, a short discussion on complexity theory (including NP-completeness and undecidability) is provided.
　　Chapter 10 covers algorithm design by examining common problem-solving techniques. This chapter is heavily fortified with examples. Pseudocode is used in these later chapters so that the student's appreciation of an example algorithm is not obscured by implementation details.
　　Chapter 11 deals with amortized analysis. Three data structures from Chapters 4 and 6 and the Fibonacci heap, introduced in this chapter, are analyzed.
　　Chapter 12 is new to this edition. It covers search tree algorithms, the k-d tree, and the pairing heap. This chapter departs from the rest of the text by providing complete and careful implementations for the search trees and pairing heap. The material is structured so that the instructor can integrate sections into discussions from other chapters. For example, the top-down red black tree in Chapter 12 can be discussed under Ave trees (in Chapter 4).
　　Chapters 1-9 provide enough material for most one-semester data structures courses. If time permits, then Chapter 10 can be covered. A graduate course on algorithm analysis could cover Chapters 7-11. The advanced data structures analyzed in Chapter 11 can easily be referred to in the earlier chapters. The discussion of N?-completeness in Chapter 9 is far too brief to be used in such a course. Garey and Johnson's book on NP-completeness can be used to augment this text.

　　This example illustrates what we call randomized algorithms. At least onceduring the algorithm， a random number is used to make a decision. The runningtime of the algorithm depends not only on the particular input, but also on therandom numbers that occur.
　　The worst-case running time of a randomized algorithm is almost always thesame as the worst-case running time of the nonrandomized algorithm. The importantdifference is that a good randomized algorithm has no bad inputs, but only badrandom numbers （relative to the particular input）. This may seem like only aphilosophical difference, but actually it is quite important, as the following exampleshows.
　　Consider two variants of quicksort. Variant A uses the first element as pivot,while variant B uses a randomly chosen element as pivot. In both cases, the worst-case running time is （N2）, because it is possible at each step that the largestelement is chosen as pivot. The difference between these worst cases is that there is aparticular input that can always be presented to variant A to cause the bad runningtime. Variant A will run in （N2） time every single time it is given an already-sortedlist. If variant B is presented with the same input twice, it will have two differentrunning times, depending on what random numbers occur.
　　

　　插图：
　　This example illustrates what we call randomized algorithms. At least onceduring the algorithm, a random number is used to make a decision. The runningtime of the algorithm depends not only on the particular input, but also on therandom numbers that occur.
　　The worst-case running time of a randomized algorithm is almost always thesame as the worst-case running time of the nonrandomized algorithm. The importantdifference is that a good randomized algorithm has no bad inputs, but only badrandom numbers （relative to the particular input）. This may seem like only aphilosophical difference, but actually it is quite important, as the following exampleshows.
　　Consider two variants of quicksort. Variant A uses the first element as pivot,while variant B uses a randomly chosen element as pivot. In both cases, the worst-case running time is （N2）, because it is possible at each step that the largestelement is chosen as pivot. The difference between these worst cases is that there is aparticular input that can always be presented to variant A to cause the bad runningtime. Variant A will run in （N2） time every single time it is given an already-sortedlist. If variant B is presented with the same input twice, it will have two differentrunning times, depending on what random numbers occur.