数据结构与算法详解：经典英文教程实例

需积分: 10 9 浏览量更新于2024-07-24 收藏 1.04MB PDF 举报

"《数据结构与算法：详注示例参考》是一本专为IT专业人士编写的英文版教材，由 Granville Barnett 和 Luca Del Tongo 合著，首次出版于2008年。该书旨在帮助读者理解和掌握基础的数据结构，如链表（单链表和双链表）、二叉搜索树、堆、集合（无序和有序）、队列、AVL树，以及核心算法，包括排序（如冒泡排序、归并排序、快速排序等）、数值算法（如素性测试、基数转换等）、搜索算法和字符串处理等。书中内容丰富，不仅提供了详细的概念解释，还配以实用的例子和伪代码，便于读者通过实践学习和理解这些概念。第1章是引言，明确了书籍的目标和预期读者的基础知识，如对大O表示法（Big Oh notation）的理解，以及对命令式编程语言（imperative programming language）和面向对象编程概念的熟悉。书中使用伪代码（pseudocode）来展示算法，以便于跨语言理解。作者还提供了一些阅读和实践建议，如如何有效地阅读代码示例，并概述了全书的结构和测试方法。数据结构部分深入探讨了各种数据结构的实现细节，如链表的插入、查找、删除操作，以及遍历方式，如顺序遍历和反向遍历。双链表的额外特性如双向链接也被介绍。二叉搜索树则重点讲解了插入、搜索、删除节点，以及查找最小值、最大值和节点父指针的方法，同时还涵盖了不同的遍历策略。算法章节涵盖了排序算法，如冒泡排序、归并排序和快速排序，以及插入排序、希尔排序和基数排序。对于数值算法，涉及了素数测试、不同进制间的转换、最大公约数计算、特定位数数字的最大值计算以及阶乘的求解。搜索部分讲解了顺序搜索和概率搜索的基本原理。字符串处理部分介绍了倒序单词、检测回文、单词计数、重复单词检测以及字符串匹配等实用技巧。此外，书中还提供了一些建立和分析算法的深入教程，如迭代和递归算法的区别，以及测试策略的重要性。这本书是IT学习者深入理解数据结构和算法的良好资源，不仅适合初学者系统学习，也适合有一定基础的开发者作为参考和实践工具。通过本书，读者能够掌握数据结构的核心概念，提升算法设计和问题解决能力。"

CHAPTER 1. INTRODUCTION 5

3. The type of parameters is inferred

4. All primitive language constructs are explicitly begun and ended

If an algorithm has a return type it will often be presented in the post-

condition, but where the return type is suﬃciently obvious it may be omitted

for the sake of brevity.

Most algorithms in this book require parameters, and because we assign no

explicit type to those parameters the type is inferred from the contexts in which

it is used, and the operations performed upon it. Additionally, the name of

the parameter usually acts as the biggest clue to its type. For instance n is a

pseudo-name for a number and so you can assume unless otherwise stated that

n translates to an integer that has the same number of bits as a WORD on a

32 bit machine, similarly l is a pseudo-name for a list where a list is a resizeable

array (e.g. a vector).

The last major point of reference is that we always explicitly end a language

construct. For instance if we wish to close the scope of a for loop we will

explicitly state end for rather than leaving the interpretation of when scopes

are closed to the reader. While implicit scope closure works well in simple code,

in complex cases it can lead to ambiguity.

The pseudocode style that we use within this book is rather straightforward.

All algorithms start with a simple algorithm signature, e.g.

1) algorithm AlgorithmName(arg1, arg2, ..., argN)

2) ...

n) end AlgorithmName

Immediately after the algorithm signature we list any Pre or Post condi-

tions.

1) algorithm AlgorithmName(n)

2) Pre: n is the value to compute the factorial of

3) n ≥ 0

4) Post: the factorial of n has been computed

5) // ...

n) end AlgorithmName

The example above describes an algorithm by the name of AlgorithmName,

which takes a single numeric parameter n. The pre and post conditions follow

the algorithm signature; you should always enforce the pre-conditions of an

algorithm when porting them to your language of choice.

Normally what is listed as a pre-conidition is critical to the algorithms opera-

tion. This may cover things like the actual parameter not being null, or that the

collection passed in must contain at least n items. The post-condition mainly

describes the eﬀect of the algorithms operation. An example of a post-condition

might be “The list has been sorted in ascending order”

Because everything we describe is language independent you will need to

make your own mind up on how to best handle pre-conditions. For example,

in the C# target we have implemented, we consider non-conformance to pre-

conditions to be exceptional cases. We provide a message in the exception to

tell the caller why the algorithm has failed to execute normally.

CHAPTER 1. INTRODUCTION 6

1.4 Tips for working through the examples

As with most books you get out what you put in and so we recommend that in

order to get the most out of this book you work through each algorithm with a

pen and paper to track things like variable names, recursive calls etc.

The best way to work through algorithms is to set up a table, and in that

table give each variable its own column and continuously update these columns.

This will help you keep track of and visualise the mutations that are occurring

throughout the algorithm. Often while working through algorithms in such

a way you can intuitively map relationships between data structures rather

than trying to work out a few values on paper and the rest in your head. We

suggest you put everything on paper irrespective of how trivial some variables

and calculations may be so that you always have a point of reference.

When dealing with recursive algorithm traces we recommend you do the

same as the above, but also have a table that records function calls and who

they return to. This approach is a far cleaner way than drawing out an elaborate

map of function calls with arrows to one another, which gets large quickly and

simply makes things more complex to follow. Track everything in a simple and

systematic way to make your time studying the implementations far easier.

1.5 Book outline

We have split this book into two parts:

Part 1: Provides discussion and pseudo-implementations of common and uncom-

mon data structures; and

Part 2: Provides algorithms of varying purposes from sorting to string operations.

The reader doesn’t have to read the book sequentially from beginning to

end: chapters can be read independently from one another. We suggest that

in part 1 you read each chapter in its entirety, but in part 2 you can get away

with just reading the section of a chapter that describes the algorithm you are

interested in.

Each of the chapters on data structures present initially the algorithms con-

cerned with:

1. Insertion

2. Deletion

3. Searching

The previous list represents what we believe in the vast majority of cases to

be the most imp ortant for each respective data structure.

For all readers we recommend that before looking at any algorithm you

quickly look at Appendix E which contains a table listing the various symbols

used within our algorithms and their meaning. One keyword that we would like

to point out here is yield. You can think of yield in the same light as return.

The return keyword causes the method to exit and returns control to the caller,

whereas yield returns each value to the caller. With yield control only returns

to the caller when all values to return to the caller have been exhausted.

CHAPTER 1. INTRODUCTION 7

1.6 Testing

All the data structures and algorithms have been tested using a minimised test

driven development style on paper to ﬂesh out the pseudocode algorithm. We

then transcribe these tests into unit tests satisfying them one by one. When

all the test cases have been progressively satisﬁed we consider that algorithm

suitably tested.

For the most part algorithms have fairly obvious cases which need to be

satisﬁed. Some however have many areas which can prove to be more complex

to satisfy. With such algorithms we will point out the test cases which are tricky

and the corresponding portions of pseudocode within the algorithm that satisfy

that respective case.

As you become more familiar with the actual problem you will be able to

intuitively identify areas which may cause problems for your algorithms imple-

mentation. This in some cases will yield an overwhelming list of concerns which

will hinder your ability to design an algorithm greatly. When you are bom-

barded with such a vast amount of concerns look at the overall problem again

and sub-divide the problem into smaller problems. Solving the smaller problems

and then composing them is a far easier task than clouding your mind with too

many little details.

The only type of testing that we use in the implementation of all that is

provided in this book are unit tests. Because unit tests contribute such a core

piece of creating somewhat more stable software we invite the reader to view

Appendix D which describes testing in more depth.

1.7 Where can I get the code?

This book doesn’t provide any code speciﬁcally aligned with it, however we do

actively maintain an open source project

that houses a C# implementation of

all the pseudo code listed. The project is named Data Structures and Algorithms

(DSA) and can be found at http://codeplex.com/dsa.

1.8 Final messages

We have just a few ﬁnal messages to the reader that we hope you digest before

you embark on reading this book:

1. Understand how the algorithm works ﬁrst in an abstract sense; and

2. Always work through the algorithms on paper to understand how they

achieve their outcome

If you always follow these key points, you will get the most out of this book.

All readers are encouraged to provide suggestions, feature requests, and bugs so we can

further improve our implementations.

剩余111页未读，继续阅读

拼命小狼君

粉丝: 13
资源: 1

数据结构与算法详解：经典英文教程实例

Algorithms and Data Structures(15th) 无水印pdf

Algorithms-and-Data-Structures

C++ Data Structures and Algorithms

data structure and algorithms in java 6th pdf

jdk1.8 concurrenthashmap

数据结构书籍和网课推荐

bfd and dfs introduction pdf

ppandas.DataFrame

zobrist hashing

torch.tensor

最新资源