数据结构与算法详解

5星 · 超过95%的资源需积分: 13 83 浏览量更新于2024-07-24 1 收藏 1.11MB PDF 举报

“Data Structure and Algorithm”是一本关于数据结构和算法的高清英文原版书籍，由Granville Barnett和Luca Del Tongo合著。该书由DotNetSlackers提供，是一个专注于.NET文章和软件行业领先思想家新闻的平台。本书旨在深入探讨数据结构和算法，以下是其中的一些关键知识点： 1. **数据结构**：数据结构是组织和存储数据的方式，它决定了数据的访问效率和处理方式。在书中，作者详细介绍了两种链表数据结构：单链表和双链表。 - **单链表（Singly LinkedList）**：单链表每个节点包含数据和一个指向下一个节点的指针。书中讨论了单链表的插入、搜索、删除和遍历操作。插入操作通常涉及在链表中的特定位置添加新节点；搜索可能需要从头到尾遍历链表；删除需要找到目标节点并更新相邻节点的指针；遍历则意味着从头节点开始，按照指针顺序访问所有节点。 - **双链表（Doubly LinkedList）**：双链表与单链表相似，但每个节点有两个指针，分别指向前一个和后一个节点。这使得双向操作更为便捷。书中讨论了双链表的插入、删除和反向遍历。插入和删除的操作比单链表更复杂，因为需要处理两个指针；反向遍历则允许从尾节点开始向前遍历链表。 2. **算法**：算法是解决问题或执行任务的精确步骤集合。书中的例子通常会用伪代码来表示，这是一种介于自然语言和编程语言之间的描述方法，便于理解算法逻辑。 3. **大O符号（Big Oh Notation）**：这是衡量算法时间复杂度的工具，用于描述算法在最坏情况下的运行时间增长速度。在1.2.1节中，作者预设读者对大O符号有一定的了解。 4. **命令式编程语言（Imperative Programming Language）**：书中假设读者熟悉命令式编程，这是一种通过指令来改变程序状态的编程范式，例如C、Java和Python等。 5. **面向对象概念（Object-Oriented Concepts）**：面向对象编程是现代编程语言中常见的一种方法，包括类、对象、封装、继承和多态等概念。作者假设读者对此有一定基础。 6. **伪代码（Pseudocode）**：书中使用伪代码来描述算法，这是一种非正式的编程语言，用于清晰地表达算法逻辑，帮助读者理解算法步骤。 7. **测试**：在1.6节中提到了测试的重要性，确保实现的算法和数据结构能够正确工作。 8. **代码获取**：1.7节指出读者可以在何处获取相关代码实例进行实践。 “Data Structure and Algorithm”这本书覆盖了数据结构和算法的基础，适合有一定编程背景，尤其是对面向对象编程和大O符号熟悉的读者。通过详尽的例子和解释，读者可以深入理解数据结构如链表的工作原理，以及如何设计和分析算法。

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页未读，继续阅读

Norman163

粉丝: 0
资源: 10

数据结构与算法详解

Data Structure and Algorithm Analysis in C 习题答案

DataStructureAndAlgorithm

Data structure and algorithm

Data structure and algorithm analysis

data structure and algorithm java

DataStructureAndAlgorithm.zip

DataStructure：DataStructureAndAlgorithm

Algorithm-DataStructureAndAlgorithm.zip

Data Structure and Algorithm Analysis in Java

Data structure and algorithm notes中文版

最新资源