[套装书]C程序设计语言（英文影印版）（第2版）+数据结构与算法分析：C语言描述(英文版.第2版)（2册）

作者
（美）Brian W.Kernighan, Dennis M.Ritchie(美)Mark Allen Weiss
丛书名
经典原版书库
出版社
机械工业出版社
ISBN
9781909291152
简要
简介
内容简介书籍计算机书籍 ---------------------------C程序设计语言（英文影印版）（第2版）--------------------------- 在计算机发展的历史上，没有哪一种程序设计语言像C语言这样应用广泛。本书是C语言的设计者之一Dennis M．Ritchie和著名的计算机科学家Brian W．Kernighan合著的一本介绍C语言的权威经典著作。我们现在见到的大量论述C语言程序设计的教材和专著均以此书为蓝本。本书第1版中介绍的C语言成为后来广泛使用的C语言版本——标准C的基础。人们熟知的“hello，World”程序就是由本书首次引入的。现在，这一程序已经成为众多程序设计语言入门的第一课。. 第2版根据1987年制定的ANSIC标准做了适当的修订，引入了最新的语言形式，并增加了新的示例。通过简洁的描述、典型的示例，作者全面、系统、准确地讲述了C语言的各个特性以及程序设计的基本方法。对于计算机从业人员来说，本书是一本必读的程序设计语言方面的参考书。... ---------------------------数据结构与算法分析：C语言描述(英文版.第2版)--------------------------- 本书曾被评为20世纪顶尖的30部计算机著作之一，作者在数据结构和算法分析方面卓有建树，他的数据结构和算法分析的著作尤其畅销，并受到广泛好评，已被世界500余所大学选作教材。 在本书中，作者精炼并强化了他对算法和数据结构方面创新的处理方法。通过C程序的实现，着重阐述了抽象数据类型的概念，并对算法的效率、性能和运行时间进行了分析。 本书特色 . ·着重讨论了算法设计技巧，包括贪婪算法、分治算法、动态规划、随机化算法以及回溯算法。 ·系统介绍了当前流行的论题和新的数据结构，如斐波那契堆、斜堆、二项队列、跳跃表和伸展树。 ·详细讨论了摊还分析，考查书中介绍的一些高级数据结构。 ·增加了高级数据结构及其实现的内容，包括红黑树、自顶向下伸展树、treap树、k-d树、配对堆等。 ·整合了堆排序平均情况分析的一些新结果。
目录



---------------------------C程序设计语言（英文影印版）（第2版）---------------------------


序.
第1版序
Introduetion
Chapter 1. A Tutorial Introduefion
1.1 Getting Staffed
1.2 Variables and Arithmctic Expressions
1.3 The For Statement
1.4 Symbolic Constants
1.5 Character Input and Output
1.6 Arrays
1.7 Functions
1.8 Arguments--Call by Value
1.9 Character Arrays
1.10 External Variables and Scope
Chapter 2. Types, Operators, and Expressions
2.1 Variable Names
2.2 Data Types and Sizes
2.3 Constants
2.4 Declarations
2.5 Arithmetic Operators
2.6 Relational and Logical Operators
2,7 Type Conversions
2.8 Increment and Decrement Operators
2.9 Bitwise Operators
2.10 Assignment Operators and Expressions
2.11 Conditional Expressions
2.12 Precedence and Order of Evaluation
Chapter 3. Control Flow
3.1 Statements and Blocks
3.2 If-Else
3.3 Else-lf
3.4 Switch
3.5 Loops--While and For
3.6 Loops-- Do-while
3.7 Break and Continue
3.8 Goto and Labels
Chapter 4. Functions and Program Structure
4.1 Basics of Functions
4.2 Functions Returning Non-integers
4.3 External Variables
4.4 Scope Rules
4.5 Header Files
4.6 Static Variables
4.7 Register Variables
4.8 Block Structure
4.9 Initialization
4.10 Rocursi6n
4.11 The C Preprocessor
Chapter 5. Pointers and Arrays
5.1 Pointers and Addresses ..
5.2 Pointers and Function Arguments
5.3 Pointers and Arrays
5.4 Address Arithmetic
5.5 Character Pointers and Functions
5.6 Pointer Arrays; Pointers to Pointers
5.7 Multi-dimensional Arrays
5.8 Initialization of Pointer Arrays
5.9 Pointers vs. Multi-dimensional Arrays
5.10 Command-line Arguments
5.11 Pointers to Functions
5.12 Complicated Declarations
Chapter 6. Structures
6.1 Basics of Structures
6.2 Structures and Functions
6.3 Arrays of Structures
6.4 Pointers to Structures
6.5 Self-referential Structures
6.6 Table Lookup
6.7 Typedef
6.8 Unions
6.9 Bit-fields
Chapter 7. Input and Output
7.1 Standard Input and Output
7.2 Formatted Output-Printf
7.3 Variable-length Argument Lists
7.4 Formatted Input--Scanf
7.5 File Access
7.6 Error Handling-Stderr and Exit
7.7 Line Input and Output
7.8 Miscellaneous Functions
Chapter 8. The UNIX System Interface
8.1 File Descriptors
8.2 Low Level I/O--Read and Write
8.3 Open, Creat, Close, Unlink
8.4 Random Access -- Lseek
8.5 Example--An Implementation of Fopen and Getc
8.6 Example--Listing Directories
8.7 Example--A Storage Allocator
Appendix A. Reference Manual
A1 Introduction
A2 Lexieal Conventions
A3 Syntax Notation
A4 Meaning of Identifiers
A5 Objects and Lvalues
A6 Conversions
A7 Expressions
A8 Declarations
A9 Statements
A10 External Declarations
A11 Scopeand Linkage
A12 Preprocessing
A13 Grammar
Appendix B. Standard Library
BI Input and Output: <stdio.h>
B2 Character Class Tests: <ctype.h>
B3 String Functions: <string.h>
B4 Mathematical Functions: <math.h>
B5 Utility Functions: <stdlib.h>
B6 Diagnostics: <assert.h>
B7 Variable Argument Lists: <stdarg.h>
B8 Non-local Jumps: <scrimp.h>
B9 Signals: <signal.h>
B10 Date and Time Functions: <time.h>
B11 Implementation-defined Limits: <limits.h> and <float.h>
Appendix C. Summary of Changes
Index...


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


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
2.4.4. Logarithms in the Running Time 28
2.4.5. Checking Your Analysis 33
2.4.6. A Grain of Salt 33
Summary 34
Exercises 35
References 39
3 Lists, Stacks, and Queues 41
3.1. Abstract Data Types (ADTs) 41
3.2. The List ADT 42
3.2.1. Simple Array Implementation of Lists 43
3.2.2. Linked Lists 43
3.2.3. Programming Details 44
3.2.4. Common Errors 49
3.2.5. Doubly Linked IJsts 51
3.2.6. Circularly Linked Lists 52
3.2.7. Examples 52
3.2.8. Cursor Implementation of Linked Lists 57
3.3. The Stack ADT 62
3.3.1. Stack Model 62
3.3.2. Implementation of Stacks 63
3.3.3. Applications 71
3.4. The Queue ApT 79
3.4.1. Quene Model 79
3.4.2. Array implementation of Queues 79
3.4.3. Applications of Queues 84
Summary 85
Exercises 85
4 Trees 89
4.1. Preliminaries 89
4.1.1. Implementation of Trees 90
4.1.2. Tree Traversals with an Application 91
4.2. Binary Trees 95
4.2.1. Implementation 96
4.2.2. Expression Trees 97
4.3. The Search Tree ADT-Binary Search Trees 100
4.3.1. MakeEmpty 101
4.3.2. Find 101
4.3.3. FindMin and FindMax 103
4.3.4. Insert 104
4.3.5. Delete 105
4.3.6. Average-Case Analysis 107
4.4. AVL Trees 110
4.4.1. Single Rotation 112
4.4.2. Double Rotation 115
4.5. Splay Trees 123
4.5.1. ASimpleldea (That Does Not Work) 124
4.5.2. Splaying 126
4.6. Tree Traversals (Revisited) 132
4.7. B-Trees 133
Summary 138
Exercises 139
References 146
5 Hashing 149
5.1. General Idea 149
5.2. Hash Function 150
5.3. Separate Chaining 152
5.4. Open Addressing 157
5.4.1. Linear Probing 157
5.4.2. Quadratic Probing 160
5.4.3. Double Hashing 164
5.5. Rehashing 165
5.6. Extendible Hashing 168
Summary 171
Exercises 172
References 175
6 Priority Queues (Heaps) 177
6.1. Model 177
6.2. Simple Implementations 178
6.3. Binary Heap 179
6.3.1. Structure Property 179
6.3.2. Heap Order Property 180
6.3.3. Basic Heap Operations 182
6.3.4. Other Heap Operations 186
6.4. Applications of Priority Queues 189
6.4.1. The Selection Problem 189
6.4.2. Event Simulation 191
6.5. d-Heaps 192
6.6. Leftist Heaps 193
6.6.1. Leftist Heap Property 193
6.6.2, Leftist Heap Operations 194
6.7. Skew Heaps 200
6.8. Binomial Queues 202
6.8.1. Binomial Queue Structure 202
6.8.2, Binomial Queue Operations 204
6.8.3. Implementation of Binomial Queues 205
Summary 212
Exercises 212
References 216
7 Sorting 219
7.1. Preliminaries 219
7.2. Insertion Sort 220
7.2.1. The Algorithm 220
7.2.2. Analysis of Insertion Sort 221
7.3. A Lower Bound for Simple Sorting Algorithms 221
7.4. Shellsort 222
7.4.1. Worst-Case Analysis of Shellsort 224
7.5. Heapsort 226
7.5.1. Analysis of Heapsort 228
7.6. Mergesort 230
7.6.1. Analysis of Mergesort 232
7.7. Quicksort 235
7.7.1. Picking the Pivot 236
7.7.2. Partitioning Strategy 237
7.7.3. Small Arrays 240
7.7.4. Actual Quicksort Routines 240
7.7.5. Analysis of Quicksort 241
7.7.6. A Linear-Expected-Time Algorithm for Selection 245
7.8. Sorting Large Structures 247
7.9. A General Lower Bound for Sorting 247
7.9.1. Decision Trees 247
7.10. Bucket Sort 250
7.11. External Sorting 250
7.11.1. Why We Need New Algorithms 251
7.11.2. Model for External Sorting 251
7.11.3. The Simple Algorithm 251
7.11.4. Multiway Merge 253
7.11.5. Polyphase Merge 254
7.11.6. Replacement Selection 255
Summary 256
Exercises 257
References 261
8 The Disjoint Set ADT 263
8.1. Equivalence Relations 263
8.2. The Dynamic Equivalence Problem 264
8.3. Basic Data Structure 265
8.4, Smart Union Algorithms 269
8.5. Path Compression 271
8.6. Worst Case for Union-by-Rank and Path Compression 273
8.6.1. Analysis of the Union/Find Algorithm 273
8.7. An Application 279
Summary 279
Exercises 280
References 281
9 Graph Algorithms 283
9.1. Definitions 283
9.1.1. Representation of Graphs 284
9.2. Topological Sort 286
9.3. Shortest-Path Algorithms 290
9.3.1. Unweighted Shortest Paths 291
9.3.2. Dijkstra's Algorithm 295
9.3.3. Graphs with Negative Edge Costs 304
9.3.4. Acyclic Graphs 305
9.3.5. All-Pairs Shortest Path 308
9.4. Network Flow Problems 308
9.4.1. A Simple Maximum-Flow Algorithm 309
9.5. Minimum Spanning Tree 313
9.5.1. Prim's Algorithm 314
9.5.2, Kruskal's Algorithm 316
9.6. Applications of Depth-First Search 319
9.6.1. Undirected Graphs 32O
9.6.2. Biconnectivity 322
9.6.3. Euler Circuits 326
9.6.4. Directed Graphs 329
9.6.5. Finding Strong Components 331
9.7. Introduction to NP-Completeness 332
9.7.1. Easyvs. Hard 333
9.7.2. The Class NP 334
9.7.3. NP-complete Problems 335
Summary 337
Exercises 337
References 343
10 Algorithm Design Techniques 347
10.1. Greedy Algorithms 347
10.1.1. A Simple Scheduling Problem 348
10,1.2. Huffsaan Codes 351
10.1.3. Approximate Bin Paddng 357
10.2. Divide and Conquer 365
10.2.1. Running Time of Divide and Conquer Algorithms 366
10.2.2. Closest-Points Problem 368
10.2.3. The Selection Problem 373
10.2.4. Theoretical Improvements for Arithmetic Problems 376
10.3. Dynamic Programming 380
10.3.1. Using a Table Instead of Recursion 380
10.3.2. Ordering Matrix Multiplications 383
10.3.3. Optimal Binary Search Tree 387
10.3.4. MI-Pairs Shortest Path 390
10.4. Randomized Algorithms 392
10.4.1. Random Number Generators 394
10.4.2. Skip Lists 397
10.4.3. Primality Testing 399
10.5. Backtracking Algorithms 401
1o.5.1. The Turnpike Reconstruction Problem 403
10.5.2. Games 407
Summary 413
Exercises 415
References 422
11 Amortized Analysis 427
11.1. An Unrelated Puzzle 428
11.2. Binomial Queues 428
11.3. Skew Heaps 433
11.4. Fibonacci Heaps 435
11.4.1. Cutting Nodes in Leftist Heaps 436
11.4.2. Lazy Merging for Binomial Queues 439
11.4.3. The Fibonacci Heap Operations 442
11.4.4. Proof of the Time Bound 443
11.5, Splay Trees 445
Summary 449
Exercises 450
References 451
12 Advanced Data Structures and Implementation 453
12.1. Top-Down Splay Trees 453
12.2. Red Black Trees 457
12.2.1. Bottom-Up Insertion 462
12.2.2. Top-Down Red Black Trees 463
12.2.3. Top-Down Deletion 465
12.3. Deterministic Skip Lists 469
12.4. hA-Trees 476
12.5. Treaps 482
12.6. k-d Trees 485
12.7. Pairing Heaps 488
Summary 494
Exercises 495
References 497
Index 501



有问题微信扫码联系

推荐

Understand China
桂ICP备20004708号-4