数据结构与算法分析

数据结构与算法分析:C语言描述(英文第2版) 韦斯著

C 算法 数据结构
浏览人数:395
读者: ...
  《数据结构与算法分析:C语言描述》曾被评为20世纪顶尖的30部计算机著作之一,作者在数据结构和算法分析方面卓有建树,他的数据结构和算法分析的著作尤其畅销,并受到广泛好评,已被世界500余所大学选作教材。 \n  在《数据结构与算法分析:C语言描述》中,作者精炼并强化了他对算法和数据结构方面创新的处理方法。通过C程序的实现,着重阐述了抽象数据类型的概念,并对算法的效率、性能和运行时间进行了分析。 \n  《数据结构与算法分析:C语言描述》特色:着重讨论了算法设计技巧,包括贪婪算法、分治算法、动态规划、随机化算法以及回溯算法。系统介绍了当前流行的论题和新的数据结构,如斐波那契堆、斜堆、二项队列、跳跃表和伸展树。详细讨论了摊还分析,考查书中介绍的一些高级数据结构。增加了高级数据结构及其实现的内容,包括红黑树、自顶向下伸展树、treap树、k-d树、配对堆等。整合了堆排序平均情况分析的一些新结果。
Introduction   
1.1. Whats the Book About?   
1.2. Mathematics Review   
1.2.1. Exponents   
1.2.2. Logarithms   
1.2.3. Series   
1.2.4. Modular Arithmetic   
1.2.5. The P Word   
1.3. A Brief Introduction to Recursion   
Summary   
Exercises   
References   
2 Algorithm Analysis   
2.1. Mathematical Background   
2.2. Model   
2.3. What to Analyze   
2.4. Running Tune Calculations   
2.4.1. A Simple Example   
2.4.2. General Rules   
2.4.3. Solutions for the Maximum Subsequence Sum Problem   
2.4.4. Logarithms in the Running Tune   
2.4.5. Checking Your Analysis   
2.4.6. A Grain of Salt   
Summary   
Exercises   
References   
3 Lists, Stacks, and Queues   
3.1. Abstract Data Types (AnTs)   
3.2. The List ADT   
3.2.1. Simple Array Implementation of Lists   
3.2.2. Linked Lists   
3.2.3. Programming Details   
3.2.4. Common Errors   
3.2.5. Doubly Linked Lists   
3.2.6. Circularly Unked Lists   
3.2.7. Examples   
3.2.8. Cursor Implementation of Linked Lists   
3.3. The Stack ADT   
3.3.1. Stack Model   
3.3.2. Implementation of Stacks   
3.3.3. Applications   
3.4. The Queue ADT   
3.4.1. Queue Model   
3.4.2. Array Implementation of Queues   
3.4.3. Applications of Queues   
Summary   
Exercises   
4 Trees   
4.1. Preliminaries   
4.1.1. Implementation of Trees   
4.1.2. Tree Traversals with an Application   
4.2. Binary Trees   
4.2.1. Implementation   
4.2.2. Expression Trees   
4.3. The Search Tree ADT-Binary Search Trees   
4.3.1. MakeEmpty   
4.3.2. Find   
4.3.3. FindMin and FindMax   
4.3.4. Insert   
4.3.5. Delete   
4.3.6. Average-Case Analysis   
4.4. AvI Trees   
4.4.1. Single Rotation   
4.4.2. Double Rotation   
4.5. Splay Trees   
4.5.1. A Simple Idea (That Does Not Work)   
4.5.2. Splaying   
4.6. Tree Traversals (Revisited)   
4.7. B-Trees   
Summary   
Exercises   
References   
5 Hashing   
5.1. General Idea   
5.2. Hash Function   
5.3. Separate Chaining   
5.4. Open Addressing   
5.4.1. Linear Probing   
5.4.2. Quadratic Probing   
5.4.3. Double Hashing   
5.5. Rehashing   
5.6. Extendible Hashing   
Summary   
Exercises   
References   
6 Priority Queues (Heaps)   
6.1. Model   
6.2. Simple Implementations   
6.3. Binary Heap   
6.3.1. Strocture Property   
6.3.2. Heap Order Property   
6.3.3. Basic Heap Operations   
6.3.4. Other Heap Operations   
6.4. Applications of Priority Queues   
6.4.1. The Selection Problem   
6.4.2. Event Simulation   
6.5. d-Heaps   
6.6. Leftist Heaps   
6.6.1. Leftist Heap Properly   
6.6.2. Leftist Heap Operations   
6.7. Skew Heaps   
6.8. Binomial Queues   
6.8.1. Binomial Queue Structure   
6.8.2. Binomial Queue Operations   
6.8.3. Implementation of Binomial Queues   
Summary   
Exercises   
References   
7 Sorting   
7.1. Preliminaries   
7.2. Insertion Sort   
7.2.1. The Algorithm   
7.2.2. Analysis of Insertion Sort   
7.3. A Lower Bound for Simple Sorting Algorithms   
7.4. SheUsort   
7.4.1. Worst-Case Analysis of Shellsort   
7.5. Heapsort   
7.5.1. Analysis of Heapsort   
7.6. Mergesort   
7.6.1. Analysis of Mergesort   
7.7. Quicksort   
7.7.1. Picking the Pivot   
7.7.2. Partitioning Strategy   
7.7.3. Small Arrays   
7.7.4. Actual Quicksort Routines   
7.7.5. Analysis of Quicksort   
7.7.6. A Linear-Expected-Time Algorithm for Selection   
7.8. Sorting Large Structures   
7.9. A General Lower Bound for Sorting   
7.9.1. Decision Trees   
7.10. Bucket Sort   
7.11. External Sorting   
7.11.1. Why We Need New Algorithms   
7.11.2. Model for External Sorting   
8 The Disjoint Set ADT   
9 Graph Algorithms   
10 Algorithm Design Techniques   
11 Amortized Analysis   
12 Advanced Data Structures and Implementation   
作者简介
评论