数据结构与算法分析——C语言描述(英文版第2版)
1推荐 收藏
11.5K阅读
图灵原版计算机科学系列

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

Mark Allen Weiss (作者) 陈越 (译者)
终止销售
本书是数据结构和算法分析方面的经典教材。第2版更加精炼并强化了本书创新的对算法和数据结构的讲授方法。通过C程序的实现,着重阐述了抽象数据类型(ADT)的概念,并对算法的效率、性能和运行时间进行了分析。本书适合作为本科数据结构课程或研究生第一年算法分析课程的教材。第1~9章为大多数本科一学期数据结构课程提供了足够的材料。多学时课程可讲授第10章。研究生的算法分析课程可以使用第6~12章的内容。

收藏本书能做什么?

有情况的时候会收到通知,比如电子书发布等。

纸质书
¥49.00

出版信息

  • 书  名数据结构与算法分析——C语言描述(英文版第2版)
  • 系列书名图灵原版计算机科学系列
  • 执行编辑关于本书的内容有任何问题,请联系 傅志红
  • 出版日期2005-08-17
  • 书  号7-115-13984-9
  • 定  价49.00 元
  • 页  数525
  • 开  本16开
  • 出版状态终止销售
  • 原书名Data Structures and Algorithm Analysis in C
  • 原书号0-201-49840-5

同系列书

目录

Adapter's Foreword
Preface

1 Introduction 1
1.1. What's the Book About? 1
1.2. A Brief Introduction to Recursion 3
Summary 7
Exercises 7
References 8

2 Algorithm Analysis 9
2.1. Mathematical Background 9
2.2. Model 12
2.3. What to Analyze 12
2.4. Running Time Calculations 14
2.4.1. A Simple Example 15
2.4.2. General Rules 15
2.4.3. Solutions for the Maximum Subsequence Sum Problem 18
2.4.4. Logarithms in the Running Time 22
2.4.5. Checking Your Analysis 27
2.4.6. A Grain of Salt 27
Summary 28
Exercises 29
References 33

3 Lists, Stacks, and Queues 35
3.1. Abstract Data Types (ADTs) 35
3.2. The List AnT 36
3.2.1. Simple Array Implementation of Lists 37
3.2.2. Linked Lists 37
3.2.3. Programming Details 38
3.2.4. Common Errors 43
3.2.5. Doubly Linked Lists 45
3.2.6. Circularly Linked Lists 46
3.2.7. Examples 46
3.2.8. Cursor Implementation of Linked Lists 50
3.3. The Stack ADT 56
3.3.1. Stack Model 56
3.3.2. Implementation of Stacks 57
3.3.3. Applications 65
3.4. The Queue AnT 73
3.4.1. Queue Model 73
3.4.2. Array Implementation of Queues 73
3.4.3. Applications of Queues 78
Summary 79
Exercises 79

4 Trees 83
4.1. Preliminaries 83
4.1.1. Terminology 83
4.1.2. Implementation of Trees 84
4.2. Binary Trees 85
4.2.1. Implementation 86
4.2.2. Expression Trees 87
4.2.3. Tree Traversals 90
4.3. The Search Tree ADT Binary Search Trees 97
4.3.1. MakeEmpty 97
4.3.2. Find 97
4.3.3. FindMin and FindMax 99
4.3.4. Insert 100
4.3.5. Delete 101
4.3.6. Average-Case Analysis        103
4.4. AVL Trees                 106
4.4.1. Single Rotation 108
4.4.2. Double Rotation 111
4.5. Splay Trees 119
4.5.1. A Simple Idea (That Does Not Work) 12 0
4.5.2. Splaying 12 2
4.6. B-Trees 128
Summary 133
Exercises 134
References 141

5 Priority Queues (Heaps) 145
5.1. Model 145
5.2. Simple Implementations 146
5.3. Binary Heap 147
5.3.1. Structure Property 147
5.3.2. Heap Order Property 148
5.3.3. Basic Heap Operations 150
5.3.4. Other Heap Operations 154
5.4. Applications of Priority Queues 157
5.4.1. The Selection Problem 157
5.4.2. Event Simulation 159
5.5. d-Heaps 160
5.6. Leftist Heaps 161
5.6.1. Leftist Heap Property 161
5.6.2. Leftist Heap Operations 162
5.7. Skew Heaps 168
5.8. Binomial Queues 170
5.8.1. Binomial Queue Structure 170
5.8.2. Binomial Queue Operations 172
5.8.3. Implementation of Binomial Queues 173
Summary 180
Exercises 180
References 184

6 Sorting 187
6.1. Preliminaries 187
6.2. Insertion Sort 188
6.2.1. The Algorithm 188
6.2.2. Analysis of Insertion Sort 189
6.3. A Lower Bound for Simple Sorting Algorithms 189
6.4. Shellsort 190
6.4.1. Worst-Case Analysis of Shellsort 192
6.5. Heapsort 194
6.5.1. Analysis of Heapsort 196
6.6. Mergesort 198
6.6.1. Analysis of Mergesort 200
6.7. Quicksort 203
6.7.1. Picking the Pivot 204
6.7.2. Partitioning Strategy 205
6.7.3. Small Arrays 20 8
6.7.4. Actual Quicksort Routines 208
6.7.5. Analysis of Quicksort 209
6.7.6. A Linear-Expected-Time Algorithm for Selection 213
6.8. Sorting Large Structures 215
6.9. A General Lower Bound for Sorting 216
6.9.1. Decision Trees 217
6.10. Bucket Sort and Radix Sort 219
6.11. External Sorting 222
6.11.1. Why We Need New Algorithms 222
6.11.2. Model for External Sorting 222
6.11.3. The Simple Algorithm 222
6.11.4. Multiway Merge 224
6.11.5. Polyphase Merge 225
6.11.6. Replacement Selection 226
Summary 227
Exercises 229

7 Hashing 235
7.1. General Idea 235
7.2. Hash Function 237
7.3. Separate Chaining 239
7.4. Open Addressing 244
7.4.1. Linear Probing 244
7.4.2. Quadratic Probing 247
7.4.3. Double Hashing 251
7.5. Rehashing 252
7.6. Extendible Hashing 255
Summary 258
Exercises 259
References 262

8 The Disjoint Set AnT 265
8.1. Equivalence Relations 265
8.2. The Dynamic Equivalence Problem 266
8.3. Basic Data Structure 267
8.4. Smart Union Algorithms 271
8.5. Path Compression 273
8.6. Worst Case for Union-by-Rank and Path Compression 275
8.6.1. Analysis of the Union/Find Algorithm 275
8.7. An Application 281
Summary 281
Exercises 282
References 283

9 Graph Algorithms 285
9.1. Definitions 285
9.1.1. Representation of Graphs 286
9.2. Topological Sort 288
9.3. Shortest-Path Algorithms 292
9.3.1. Unweighted Shortest Paths 293
9.3.2. Dijkstra's Algorithm 297
9.3.3. Graphs with Negative Edge Costs 306
9.3.4. Acyclic Graphs 307
9.3.5. All-Pairs Shortest Path 310
9.4. Network Flow Problems 310
9.4.1. A Simple Maximum-Flow Algorithm 311
9.5. Minimum Spanning Tree 315
9.5.1. Prim's Algorithm 316
9.5.2. Kruskal's Algorithm 318
9.6. Applications of Depth-First Search 3:21
9.6.1. Undirected Graphs 322
9.6.2. Biconnectivity 324
9.6.3. Euler Circuits 328
9.6.4. Directed Graphs 331
9.6.5. Finding Strong Components 333
9.7. Introduction to NP-Completeness 334
9.7.2. The Class NP 336
9.7.3. NP-Complete Problems 337
Summary 339
Exercises 339
References 345

10 Algorithm Design Techniques 349
10.1. Greedy Algorithms 349
10.1.1. A Simple Scheduling Problem 350
10.1.2. Huffman Codes 353
10.1.3. Approximate Bin Packing 359
10.2. Divide and Conquer 367
10.2.1. Running Time of Divide and Conquer Algorithms 368
10.2.2. Closest-Points Problem 370
10.2.3. The Selection Problem 375
10.2.4. Theoretical Improvements for Arithmetic Problems 378
10.3. Dynamic Programming 382
10.3.1. Using a Table Instead of Recursion 382
10.3.2. Ordering Matrix Multiplications 385
10.3.3. Optimal Binary Search Tree 389
10.3.4. All-Pairs Shortest Path 392
10.4. Randomized Algorithms 394
10.4.1. Random Number Generators 396
10.4.2. Skip Lists 399
10.4.3. Primality Testing 401
10.5. Backtracking Algorithms 403
10.5.1. The Turnpike Reconstruction Problem 405
10.5.2. Games 407
Summary 415
Exercises 417
References 424

ll Amortized Analysis 429
11.1. An Unrelated Puzzle 430
11.2. Binomial Queues 430
11.3. Skew Heaps 435
11.4. Fibonacci Heaps 437
11.4.1. Cutting Nodes in Leftist Heaps 430
11.4.2. Lazy Merging for Binomial Queues 441
11.4.3. The Fibonacci Heap Operations 444
11.4.4. Proof of the Time Bound 445
11.5. Splay Trees 447
Summary 451
Exercises 452
References 453

12 Advanced Data Structures and Implementation 455
12.1. Top-Down Splay Trees 455
12.2. Red Black Trees 459
12.2.1. Bottom-Up Insertion 464
12.2.2. Top-Down Red Black Trees 465
12.2.3. Top-Down Deletion 467
12.3. Deterministic Skip Lists 471
12.4. &A-Trees 478
12.5. Treaps 484
12.6. k-d Trees 487
12.7. Pairing Heaps 490
Summary 496
Exercises 497
References 499

相关文章

  • myxs 2推荐

    数据结构与算法分析 读书笔记(链表 栈 队列)

    数据结构与算法分析 读书笔记(链表 栈 队列) 标签: Data-Structures 不直接写链表,栈,队列的实现,直接把做课后题目以及想到的或遇到的问题实现了一下,只给出关键代码 1 逆转单链表 这里采用从第二个元素到最后一个元素逐个插入到头节点和第一个节点之间…...

  • myxs 1推荐

    数据结构与算法分析 读书笔记(树)

    摘要:本节包含二叉查找树,AVL树,伸展树以及B树 标签: Data-Structures 注意,笔记不是讲各种概念的,只是记录一下个人学习过程中遇到的问题和实现代码。需要知道基本概念,理解各种树的原理。 1 二叉查找树 struct TreeNode{ int E…...

  • 来,见证奇迹 3推荐

    PHP7数据结构与算法分析:前言

    ![enter image description here][1] 前言 PHP是非常流行的脚本语言!现在世界上数以万计的网络程序都有它的身影!而且它能力非凡!小到普通的个人博客、企业网站,大到电商平台、云计算!它都能身当重任!尤其是PHP新版本的发行--PHP7!带…...

  • 来,见证奇迹 2推荐

    PHP7数据结构与算法分析:第一章--数据结构和算法简介

    ![enter image description here][1] 第 1 章 数据结构和算法简介 当今世界是一个数字化的世界,科技已经影响了我们生活的方方面面,而这些科技背后运行的东西是程序!而程序本质是什么? 程序 = 数据结构 + 算法 是的,程序的本质就…...

  • 来,见证奇迹 2推荐

    PHP7数据结构与算法分析:第二章--算法天平:复杂度分析

    ![enter image description here][1] 第2章 算法天平:复杂度分析 在上一章中我们已经了解了算法的概念、特征及设计算法要秉持的原则!我们在最后也提示大家算法的设计原则也可以辅助我们评判算法的优劣!那么本章我会尽量详细的展示给大家具体的衡量算法…...

  • 来,见证奇迹 2推荐

    PHP7数据结构与算法分析:第三章--不一样的数组

    ![enter image description here][1] 第三章 不一样的数组 几乎所有的语言都原生支持数组,PHP也不例外!在本章中我们首先要对数组的一些基础知识进行回顾和熟悉,然后把PHP中有关数组的常用操作整理和归纳以便后面章节中学习使用。与基础学习不同的…...

  • 此书市和研究生使用。认为属的内容比较丰富,对于本科生学习有点困难,但还是可以用,虽然是英文原文,但书的用词简单,阅读没有特大障碍。但是书的纸张太透,定价有点高,封面设计也不是很吸引人。计划将此书推荐给学生做参考书。
    武卫东  发表于 2005-12-11 11:00:36
    推荐
    • 好像听说过你

      Junle8884  发表于 2018-05-07 14:35:10
  • A.教材比较:在这一段授课时间, 数据结构课程以William Ford 的《Data Structure with C++》为课本,《数据结构与算法分析—C 语言描述》为教学参考,《Data Structure with C++》过渡强调了c++语言的应用,以及经典数据结构的c++实现,而《数据结构与算法分析—C 语言描述》对基本的数据结构概念,数据结构的实现机制,数据结构与算法的相辅相成有更加深入的介绍,是教授其他计算机语言版本数据结构的有益补充。通过期末测验,发现本届学生对于数据结构概念的理解和运用程度优于上届。
    B.与原版书比较:与原书相比,篇幅变化不大,除删除1.2节Mathematics Review等比较基础的数学知识外(此部分意义不大,个人观点),其他主要内容完备,第3、4、5、7章有部分增加,所增加内容很实用,可以帮助学生增长新的知识点,作为中国大学的授课教材,个人认为还是比较合理的。
    C.总的来说,改动不大,更加适合中国教学情况,同时降低学生购原版书的经济负担,对出版社以及陈越老师表示感谢。
    D.本书的印刷质量以及纸张仍有改进的空间,定价合适
    cxs  发表于 2006-02-16 09:04:26
    推荐
  • 打算看一看,最近英文水平有了极大的提高
    Junle8884  发表于 2018-05-07 14:27:02
    推荐
    • 这么厉害

      Junle8884  发表于 2018-05-07 14:44:28