数据结构与算法详解：链表篇

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

"数据结构与算法是计算机科学的基础，涵盖了如何高效存储和处理数据的方法。本书《Data Structures and Algorithms: Annotated Reference with Examples》由Granville Barnett和Luca Del Tongo编写，旨在提供数据结构和算法的详细参考，并配有实例。内容包括但不限于链表、双向链表等常见数据结构的操作，以及相关的算法实现。" 数据结构与算法是计算机科学的核心，对于编写高效、优化的代码至关重要。在本书中，作者首先介绍了书籍的目的和预期读者的知识背景，强调了对大O表示法、命令式编程语言和面向对象概念的理解。大O表示法用于描述算法的时间复杂度，帮助我们评估算法的效率。命令式编程语言，如C、C++或Java，是实现数据结构和算法的常用工具，而面向对象概念则在许多现代编程语言中占据主导地位。书中的伪代码部分让读者能理解算法的逻辑而不必关注特定语言的语法细节。作者还给出了如何逐步分析和理解示例的提示，这对初学者尤其有用。此外，书中还概述了全书的内容，强调了测试的重要性，因为测试是确保算法正确性的关键步骤。代码可以在指定的网站获取，便于读者实践和学习。在数据结构章节中，作者详细讲解了链表这种基本的数据结构。单向链表（Singly Linked List）被介绍，包括插入、搜索、删除和遍历操作。插入节点涉及修改指针以连接新节点；搜索通常通过遍历链表来完成；删除需要调整指针以避免丢失链接；遍历链表是访问所有元素的常见需求。逆序遍历则需要反向跟踪链表。接着，作者探讨了双向链表（Doubly Linked List），它在每个节点中包含两个指针，分别指向前后节点。这使得插入和删除操作更为灵活，同时也支持反向遍历。双向链表的插入和删除涉及更新相邻节点的指针，而反向遍历则可以轻松实现。总结来说，《Data Structures and Algorithms: Annotated Reference with Examples》为读者提供了深入理解数据结构和算法的宝贵资源，通过实例教学，帮助读者掌握这些核心概念，并能够在实际项目中应用。无论是初学者还是有经验的开发者，都能从这本书中受益匪浅，提升自己的编程技能和解决问题的能力。

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

lu的博客

粉丝: 31
资源: 10

数据结构与算法详解：链表篇

Data Structures and Algorithms 数据结构与算法学习笔记.zip

data structures and algorithms with javascript

data structures and algorithms for python

data structures and algorithms in python

数据结构书籍和网课推荐

data structures and algorithms in java 2nd 编程作业

benjamin baka python data structures and algorithms

data structures and algorithms

请推荐一个免费python数据结构加算法的博客

数据结构与算法推荐课程

最新资源