数据结构与算法：阿霍版概览

需积分: 35 72 浏览量更新于2024-07-23 收藏 6.59MB PDF 举报

"《数据结构与算法》- Alfred V. Aho、John E. Hopcroft、Jeffrey D. Ullman合著" 本书是计算机科学领域的重要参考资料，由Alfred V. Aho、John E. Hopcroft和Jeffrey D. Ullman三位专家合作撰写，涵盖了数据结构和算法的核心内容。这三位作者都是计算机科学领域的权威，分别来自贝尔实验室、康奈尔大学和斯坦福大学。书中的章节安排如下： 1. 设计与分析算法：这部分介绍了如何设计和评估算法的效率，包括时间复杂性和空间复杂性分析，是理解算法性能的基础。 2. 基本数据类型：讲解了数组、链表、栈、队列等基本数据结构的实现和操作，这些是构建更复杂数据结构的基础。 3. 树：深入讨论了二叉树、平衡树（如AVL树和红黑树）以及树的遍历方法，这些都是处理分层数据的重要工具。 4. 集合的基本操作：涉及集合的定义、并集、交集和差集等操作，以及它们在数据组织中的应用。 5. 高级集合表示方法：可能包含位向量、哈希表等高效的数据结构，用于快速查找和操作元素。 6. 有向图：介绍了图的概念、遍历算法（深度优先搜索和广度优先搜索）、最短路径算法（如Dijkstra算法和Floyd-Warshall算法）等。 7. 无向图：包括图的特性、最小生成树（如Prim算法和Kruskal算法）以及网络流问题。 8. 排序：讲解了各种排序算法，如冒泡排序、插入排序、选择排序、归并排序、快速排序以及堆排序等，分析了它们的效率和适用场景。 9. 算法分析技术：进一步探讨算法分析的技巧和方法，如大O记法和渐进分析。 10. 算法设计技巧：包括动态规划、贪心算法、回溯法和分支限界法等解决问题的策略。 11. 外部存储的数据结构与算法：考虑到磁盘和硬盘等外部存储的特性，讨论如何优化对大量数据的处理。 12. 内存管理：涵盖内存分配、垃圾回收和内存优化等，对于理解和编写高效系统级程序至关重要。参考书目提供了进一步阅读的材料，帮助读者深入探索各个主题。此书不仅适合计算机科学专业的学生，也对软件工程师和其他希望提升算法和数据结构知识的专业人士极具价值。通过学习本书，读者能够掌握解决实际编程问题所需的关键技术和思维方法。

Data Structures and Algorithms: CHAPTER 1: Design and Analysis of Algorithms

sound alike, they have different meanings. In a programming language, the data type of a

variable is the set of values that the variable may assume. For example, a variable of type

boolean can assume either the value true or the value false, but no other value. The basic

data types vary from language to language; in Pascal they are integer, real, boolean, and

character. The rules for constructing composite data types out of basic ones also vary from

language to language; we shall mention how Pascal builds such types momentarily.

An abstract data type is a mathematical model, together with various operations defined

on the model. As we have indicated, we shall design algorithms in terms of ADT's, but to

implement an algorithm in a given programming language we must find some way of

representing the ADT's in terms of the data types and operators supported by the

programming language itself. To represent the mathematical model underlying an ADT we

use data structures, which are collections of variables, possibly of several different data

types, connected in various ways.

The cell is the basic building block of data structures. We can picture a cell as a box that

is capable of holding a value drawn from some basic or composite data type. Data

structures are created by giving names to aggregates of cells and (optionally) interpreting

the values of some cells as representing connections (e.g., pointers) among cells.

The simplest aggregating mechanism in Pascal and most other programming languages

is the (one-dimensional) array, which is a sequence of cells of a given type, which we shall

often refer to as the celltype. We can think of an array as a mapping from an index set (such

as the integers 1, 2, . . . , n) into the celltype. A cell within an array can be referenced by

giving the array name together with a value from the index set of the array. In Pascal the

index set may be an enumerated type, such as (north, east, south, west), or a subrange type,

such as 1..10. The values in the cells of an array can be of any one type. Thus, the

declaration

name: array[indextype] of celltype;

declares name to be a sequence of cells, one for each value of type indextype; the contents

of the cells can be any member of type celltype.

Incidentally, Pascal is somewhat unusual in its richness of index types. Many languages

allow only subrange types (finite sets of consecutive integers) as index types. For example,

to index an array by letters in Fortran, one must simulate the effect by using integer indices,

such as by using index 1 to stand for 'A', 2 to stand for 'B', and so on.

Another common mechanism for grouping cells in programming languages is the record

structure. A record is a cell that is made up of a collection of cells, called fields, of possibly

dissimilar types. Records are often grouped into arrays; the type defined by the aggregation

of the fields of a record becomes the "celltype" of the array. For example, the Pascal

declaration

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1201.htm (12 of 37) [1.7.2001 18:58:22]

Data Structures and Algorithms: CHAPTER 1: Design and Analysis of Algorithms

var

reclist: array[l..4] of record

data: real;

next: integer

end

declares reclist to be a four-element array, whose cells are records with two fields, data and

next.

A third grouping method found in Pascal and some other languages is the file. The file,

like the one-dimensional array, is a sequence of values of some particular type. However, a

file has no index type; elements can be accessed only in the order of their appearance in the

file. In contrast, both the array and the record are "random-access" structures, meaning that

the time needed to access a component of an array or record is independent of the value of

the array index or field selector. The compensating benefit of grouping by file, rather than

by array, is that the number of elements in a file can be time-varying and unlimited.

Pointers and Cursors

In addition to the cell-grouping features of a programming language, we can represent

relationships between cells using pointers and cursors. A pointer is a cell whose value

indicates another cell. When we draw pictures of data structures, we indicate the fact that

cell A is a pointer to cell B by drawing an arrow from A to B.

In Pascal, we can create a pointer variable ptr that will point to cells of a given type, say

celltype, by the declaration

var

ptr: ↑ celltype

A postfix up-arrow is used in Pascal as the dereferencing operator, so the expression ptr↑

denotes the value (of type celltype) in the cell pointed to by ptr.

A cursor is an integer-valued cell, used as a pointer to an array. As a method of

connection, the cursor is essentially the same as a pointer, but a cursor can be used in

languages like Fortran that do not have explicit pointer types as Pascal does. By treating a

cell of type integer as an index value for some array, we effectively make that cell point to

one cell of the array. This technique, unfortunately, works only when cells of arrays are

pointed to; there is no reasonable way to interpret an integer as a "pointer" to a cell that is

not part of an array.

We shall draw an arrow from a cursor cell to the cell it "points to." Sometimes, we shall

also show the integer in the cursor cell, to remind us that it is not a true pointer. The reader

should observe that the Pascal pointer mechanism is such that cells in arrays can only be

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1201.htm (13 of 37) [1.7.2001 18:58:22]

Data Structures and Algorithms: CHAPTER 1: Design and Analysis of Algorithms

"pointed to" by cursors, never by true pointers. Other languages, like PL/I or C, allow

components of arrays to be pointed to by either cursors or true pointers, while in Fortran or

Algol, there being no pointer type, only cursors can be used.

Example 1.3. In Fig. 1.10 we see a two-part data structure that consists of a chain of cells

containing cursors to the array reclist defined above. The purpose of the field next in reclist

is to point to another record in the array. For example, reclist[4].next is 1, so record 4 is

followed by record 1. Assuming record 4 is first, the next field of reclist orders the records

4, 1, 3, 2. Note that the next field is 0 in record 2, indicating that there is no following

record. It is a useful convention, one we shall adopt in this book, to use 0 as a "NIL

pointer," when cursors are being used. This idea is sound only if we also make the

convention that arrays to which cursors "point" must be indexed starting at 1, never at 0.

Fig. 1.10. Example of a data structure.

The cells in the chain of records in Fig. 1.10 are of the type

type

recordtype = record

cursor: integer;

ptr: ↑ recordtype

end

The chain is pointed to by a variable named header, which is of type ↑ record-type; header

points to an anonymous record of type recordtype.

† That record has a value 4 in its cursor

field; we regard this 4 as an index into the array reclist. The record has a true pointer in

field ptr to another anonymous record. The record pointed to has an index in its cursor field

indicating position 2 of reclist; it also has a nil pointer in its ptr field.

1.4 The Running Time of a Program

When solving a problem we are faced frequently with a choice among algorithms. On what

basis should we choose? There are two often contradictory goals.

1. We would like an algorithm that is easy to understand, code, and debug.

2. We would like an algorithm that makes efficient use of the computer's resources,

especially, one that runs as fast as possible.

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1201.htm (14 of 37) [1.7.2001 18:58:22]

Data Structures and Algorithms: CHAPTER 1: Design and Analysis of Algorithms

When we are writing a program to be used once or a few times, goal (1) is most

important. The cost of the programmer's time will most likely exceed by far the cost of

running the program, so the cost to optimize is the cost of writing the program. When

presented with a problem whose solution is to be used many times, the cost of running the

program may far exceed the cost of writing it, especially, if many of the program runs are

given large amounts of input. Then it is financially sound to implement a fairly complicated

algorithm, provided that the resulting program will run significantly faster than a more

obvious program. Even in these situations it may be wise first to implement a simple

algorithm, to determine the actual benefit to be had by writing a more complicated

program. In building a complex system it is often desirable to implement a simple

prototype on which measurements and simulations can be performed, before committing

oneself to the final design. It follows that programmers must not only be aware of ways of

making programs run fast, but must know when to apply these techniques and when not to

bother.

Measuring the Running Time of a Program

The running time of a program depends on factors such as:

1. the input to the program,

2. the quality of code generated by the compiler used to create the object program,

3. the nature and speed of the instructions on the machine used to execute the program,

and

4. the time complexity of the algorithm underlying the program.

The fact that running time depends on the input tells us that the running time of a

program should be defined as a function of the input. Often, the running time depends not

on the exact input but only on the "size" of the input. A good example is the process known

as sorting, which we shall discuss in Chapter 8. In a sorting problem, we are given as input

a list of items to be sorted, and we are to produce as output the same items, but smallest (or

largest) first. For example, given 2, 1, 3, 1, 5, 8 as input we might wish to produce 1, 1, 2,

3, 5, 8 as output. The latter list is said to be sorted smallest first. The natural size measure

for inputs to a sorting program is the number of items to be sorted, or in other words, the

length of the input list. In general, the length of the input is an appropriate size measure,

and we shall assume that measure of size unless we specifically state otherwise.

It is customary, then, to talk of T(n), the running time of a program on inputs of size n.

For example, some program may have a running time T(n) = cn

, where c is a constant. The

units of T(n) will be left unspecified, but we can think of T(n) as being the number of

instructions executed on an idealized computer.

For many programs, the running time is really a function of the particular input, and not

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1201.htm (15 of 37) [1.7.2001 18:58:22]

Data Structures and Algorithms: CHAPTER 1: Design and Analysis of Algorithms

just of the input size. In that case we define T(n) to be the worst case running time, that is,

the maximum, over all inputs of size n, of the running time on that input. We also consider

avg

(n), the average, over all inputs of size n, of the running time on that input. While

avg

(n) appears a fairer measure, it is often fallacious to assume that all inputs are equally

likely. In practice, the average running time is often much harder to determine than the

worst-case running time, both because the analysis becomes mathematically intractable and

because the notion of "average" input frequently has no obvious meaning. Thus, we shall

use worst-case running time as the principal measure of time complexity, although we shall

mention average-case complexity wherever we can do so meaningfully.

Now let us consider remarks (2) and (3) above: that the running time of a program

depends on the compiler used to compile the program and the machine used to execute it.

These facts imply that we cannot express the running time T(n) in standard time units such

as seconds. Rather, we can only make remarks like "the running time of such-and-such an

algorithm is proportional to n

." The constant of proportionality will remain unspecified

since it depends so heavily on the compiler, the machine, and other factors.

Big-Oh and Big-Omega Notation

To talk about growth rates of functions we use what is known as "big-oh" notation. For

example, when we say the running time T(n) of some program is O(n

), read "big oh of n

squared" or just "oh of n squared," we mean that there are positive constants c and n

such

that for n equal to or greater than n

, we have T(n) ≤ cn

Example 1.4. Suppose T(0) = 1, T(1) = 4, and in general T(n) = (n+l)

. Then we see that

T(n) is O(n

), as we may let n

= 1 and c = 4. That is, for n ≥ 1, we have (n + 1)

≤ 4n

, as

the reader may prove easily. Note that we cannot let n

= 0, because T(0) = 1 is not less

than c0

= 0 for any constant c.

In what follows, we assume all running-time functions are defined on the nonnegative

integers, and their values are always nonnegative, although not necessarily integers. We say

that T(n) is O(f(n)) if there are constants c and n

such that T(n) ≤ cf(n) whenever n ≥ n

. A

program whose running time is O(f (n)) is said to have growth rate f(n).

Example 1.5. The function T(n)= 3n

+ 2n

is O(n

). To see this, let n

= 0 and c = 5.

Then, the reader may show that for n ≥ 0, 3n

+ 2n

≤ 5n

. We could also say that this T(n)

is O(n

), but this would be a weaker statement than saying it is O(n

As another example, let us prove that the function 3

is not O (2

). Suppose that there

were constants n

and c such that for all n ≥ n

, we had 3

≤ c2

. Then c ≥ (3/2)

for any n

≥ n

. But (3/2)

gets arbitrarily large as n gets large, so no constant c can exceed (3/2)

for

http://www.ourstillwaters.org/stillwaters/csteaching/DataStructuresAndAlgorithms/mf1201.htm (16 of 37) [1.7.2001 18:58:22]

剩余619页未读，继续阅读

txp914

粉丝: 22
资源: 703

数据结构与算法：阿霍版概览

Alfred V. Aho - Data Structures and Algorithms

Data Structures and Algorithms - Alfred V. Aho_C++_TheFirst_源码

国外数据结构和算法合集书籍的种子

Data Structures and Algorithms_algorithms_

Essential Books on Algorithms and Data Structures(part2)(chm version)

Essential Books on Algorithms and Data Structures(part1)(chm version)

Aho算法与数据结构详解

数据结构与算法：Aho, Hopcroft, Ullman经典著作

阿利夫·A. 阿霍的《数据结构与算法》概览

计算之美：图灵奖得主John E. Hopcroft的算法与数据结构贡献

最新资源