Java版数据结构精要指南：从基础到高级实现

需积分: 9 43 浏览量更新于2024-07-19 收藏 11.36MB PDF 举报

《数据结构指南：使用Java的简洁介绍》(2017年Springer出版)是一本面向大学本科计算机科学学生的教材，由James T. Streib和Takako Soma共同编写。该书旨在为学习计算机科学的学生提供一个系统且易于理解的数据结构基础，特别强调使用Java语言进行教学。书中的内容按照作者推荐的顺序展开，首先回顾和讨论初步概念，包括但不限于计算机科学的基础原理。接着，章节2和3分别介绍了基于数组实现的栈和队列，让学生掌握这两种基本数据结构的基本操作和应用场景。章节4探讨了基于数组的列表，这对于理解序列数据的存储和管理至关重要。第五章转向了列表的实现，使用引用和对象，让学生了解对象在数据结构中的作用以及如何通过链接方式管理元素。随后的第六章深入研究了链表，这是另一种重要的线性数据结构，有助于理解动态性和高效查找的特点。第七章继续讨论栈和队列，但这次是通过引用实现，展示了不同实现方式对性能的影响。第8章则引入了二叉树的概念，涉及树形数据结构的特性、遍历方法以及相关的操作。对于算法和效率的重视贯穿始终。第九章涵盖了排序算法，这在数据处理和数据库查询中至关重要，但可以根据教师的偏好或学生的背景灵活安排讲解时间。第十章讨论了堆，这是优先队列的一种常见实现，常用于高效的数据结构和算法中。最后一章介绍了哈希（散列）技术，这是一种用于快速查找和存储的数据结构，常用于数据库索引和缓存优化。该书的特色在于其简明扼要和现代化的教学方法，包含丰富的实例和练习题，以及国际专家组成的顾问团队的精心审阅。《Undergraduate Topics in Computer Science》系列旨在满足不同层次学生的学习需求，无论是作为自学者的参考资料，还是课堂上的教材，都能提供高质量的教育体验。此外，书后的附录A提供了术语表，方便查阅，附录B则包含了部分练习题的答案，便于读者检验理解和实践。

strings, and one and two-dimensional arrays. Lastly, a good background in

object-oriented programing is needed including data members, value-returning and

void methods, constructors, priva te, protected, and public data members and

methods, sending and receiving objects from a method, instance and class con-

stants, variables and methods, inheritance, abstract classes, and polymorphism.

The authors understand that learning data structures can be a bit intimidating at

times, so in many cases the authors will remind the reader of previous subtle points

and concepts to help in understanding the topic under considerat ion. However, if at

any time the reader feels deﬁcient in any of the areas mentioned above, it is

recommended that time be taken to review these concepts in an introductory text

such as Guide to Java [2] or other similar text. Although some readers might have

had some exposure to elementary algorithm analysis, abstraction, and interfaces,

these topics are reviewed here in this preliminary chapter to ensure that the reader is

ready for the ﬁrst chapter on stacks.

1.3 Elementary Algorithm Analysis

Just as there are different ways of storing data, there are different ways of processing

data. If an algorithm is running slow, what can be done to speed it up? A ﬁrst

response might be to get a faster processor and if a processor is twice as fast, then

one might expect the algorithm to be approximately twice as fast too. But what if

the goal was to have an algorithm run 1000 times faster? It might be difﬁcult and

expensive to ﬁnd a processor that runs that fast. If possible, an alternative is to write

a faster algorithm. Is there a way to determine whether one algorithm is faster than

another algorithm? The answer is yes, and it is through the process of algorithm

analysis. For example, if a program had two statements as follows, how fast is the

algorithm?

total = total + x;

i=i+1;

Although some operations might take longer than others and speed might vary

from computer to computer, assume that each operation (such as assignment,

comparison, and arithmetic) will count as one unit of time. In the current example,

each arithmetic statement would take 2 units (one for the arithmetic and one for the

assignment) for a total of 4 for the two statements. Continuing, what if there were

three statements as shown below?

x=y*z;

total = total + x;

i=i+1;

2 1 Preliminary Concepts

The additional statement adds 2 time units, which increases the total to 6.

Although the ﬁrst code segment is approximately 33% faster, is this a signiﬁcant

amount of time? In one sense it is, but in comparison to other algorithms it is not a

signiﬁcant increase. As will be seen shortly, regardless of how much data is pro-

cessed, each code segment is execute d in a ﬁxed amount of time and it can be said

that both of these code segments are executed in constant time.

A common notation, called Big O notation (pronounced Big Oh), uses the capital

letter O to compare the relative order of magnitude of various algorithms. Algo-

rithms that are executed in constant time are said to be of order 1 or O(1). The

number 1 is used regardless of how many actual time units the algorithm took and

to indicate that the time is constant. So in answering the question whether one of the

above code segments is signiﬁcantly faster than the other, neither is because they

are both O(1) algorithms.

However, what if the above three lines of code were placed in a while loop

along with another line to initialize the variable i as shown below?

i=1;

while(i <= n) {

x=y*z;

total = total + x;

i=i+1;

}

In the above example, the ﬁrst assignment statement will take one time unit. As

before, the three arithmetic statements in the body of the while loop would take 6

time units. If the value of n was 3, then each statement in the body of the loop

would be executed three times, for a total of 18 time units. Further, how many times

does the while statement itself get executed? If one answered 3, that answer

would unfortunately be incorrect. Don’t forget that the ﬁnal value of i is checked

one last time before control is transferred to the bottom of the loop. The correct

answer is 4 times. Again, assuming the value of n is 3, the result is that it would

take 23 time units to execute the code segment as shown below:

i = 1; // 1 operation

while(i <= n) { // 3 times thru loop + 1 last check of i

x=y*z; //2operations * 3

total = total + x; // 2 operations * 3

i=i+1; //2operations * 3

}

An astute programmer might recognize that the ﬁrst assignment statement in the

body of the loop does not need to be calculated each time through the loop. As a

result, that statement could be moved prior to the execution of the loop as follows:

1.3 Elementary Algorithm Analysis 3

x=y*z;

i=1;

while(i <= n) {

total = total + x;

i=i+1;

}

Given this change, how many units of time would it take to execute this code

segment assuming again that the value of n is 3? Using the same method of analysis

discussed above, the correct answer is 19. Another way to look at it is that since the

x=y*zis executed only once instead of three times, there are 4 fewer operations

that need to be performed.

What if the value of n in the above two program segments were 10? The answers

would be 72 and 54, respectively. Again, the x=y*zwould be executed nine

fewer times which accounts for the speed up of 18 units in the second segment.

What about 100? The answers would be 702 and 504, respectively. In the ﬁrst

segment, notice that there are 7 operations for each iteration of the loop (the

comparison, the multiplication, the two additions, and the three assignments),

where 7 times 100 is 700. Plus there is the initialization of i and the last check of i

<nprior to exiting the loop, for a total of 702. Likewise with the second example,

there are 5 operat ions for each iteration of the loop (the two additions, two

assignments, and one comparison), plus the 4 extra operations outside the loop (the

two assignments, the multiplication and the last comparison before exiting the loop)

for a total of 504.

The result is that by careful programming, there can be some change in algo-

rithmic efﬁciency. In this case there is a 28.2% speed up. Is this a very large

change? Further, could the answers above be more generic in terms of n? The

answer to the second question is yes, where one might see the pattern in the

numbers above, especially when n equals 100. The ﬁrst algorithm would be 7n + 2

and the second algorithmwould be 5n + 4. In looking at these two expressions,

does the +2 or +4 make any signiﬁcant changes to its efﬁciency? It can be seen as

the value of n gets higher, say one million, the effects of these values are rather

insigniﬁcant.

Further, whether the result is 5n or 7n, they are both linear. Regardless if the

coefﬁcient is a 5 or a 7, the algorithm depends on the value of n. The result is that

both of these algorithms are considered to be order n or O(n). So in answ er to the

ﬁrst question in the preceding paragraph, in both cases these algorithms are con-

sidered to be the same order of magnitude and it is not a signiﬁcant change.

Does this mean that one does not need to do a detailed analysis of an algorithm?

Although these two algorithms can be determined by inspection to be of order n

because they both loop n times, there are some other very tricky algorithms where it

might be necessary to take the time to do a line-by-line analysis. Further, does this

mean that one should not try to increase the efﬁciency of an algorithm from 7n to

4 1 Preliminary Concepts

5n? As will be seen there are other algorithms that are faster than O(n), but if a

faster algorithm is not available and speed is a concern, then one should try to

increase an algorithm ’sefﬁciency, especially inside a loop or nested loops. How-

ever, as will be seen later in this text, sometimes there can be a dramatic increase in

the speed of an algorithm by using an alternative method.

In looking at some other algorithms, what would be the efﬁciency of the fol-

lowing code segment?

for(i=1;i<=n;i++) {

// some statements

}

for(i=1;i<=n;i++) {

// some statements

}

Since the speciﬁc statements in the body of the loops are not included, it is not

possible to do a detailed analysis. However, by inspection it should be clear that the

ﬁrst loop would be O(n) and the second loop would also be O(n). But what is the

efﬁciency when they are combined? Since they are both of O(n) and one follows the

other, the two are added and the result woul d appea r to be n + n or of order 2n.

Further, as discussed earlier the coefﬁcient can be dropped and the algorithm

consisting of the two non-nested loops is O(n). In another example, consider the

following algorithm that also consists of two for loops. What is its algorithmic

efﬁciency?

for(i=1;i<=n;i++)

for(j=1;j<=n;j++) {

// some statements

}

Unlike the previous code segm ent, the loops in this segment are nested. If the

answer is not readily apparent, it is sometimes helpful to pick a value for n to help

determine how many times the statements in the inner loop are executed. The key is

not to pick a number too small where the pattern might not be evident, nor pick a

number too large in case one has to manually walk through the code. If the value for

n was 3, how many times would the statements in the inner loop be executed? The

outer loop would execute three times, and for each time through the outer loop, the

inner loop would execute three times too. The result is that the statements in the

inner loop would be executed nine times. What if the v alue of n was 10? Then the

statements in the inner loop would be executed 100 times. The result is that for any

value n, the inner statements would be executed n  norn

times and thus the

segment is O(n

). Given the previous two example, consider the following:

1.3 Elementary Algorithm Analysis 5

for(i=1;i<=n;i++)

for(j=1;j<=n;j++) {

// some statements

}

for(i=1;i<=n;i++) {

// some statements

}

At ﬁrst it might appear that the answer might be O(n

) because there are three

loops. However, notice that the ﬁrst two loops are nested and the last one is not

nested. Since the ﬁrst two are nested they are n

and since the last loop is not nested

it is n. The result is that the two are added to form n

+ n. But what is this in Big O

notation? When there are more than one term in the resulting analys is, only the

most dominate term is used in Big O notation, or in other words the slowest term is

used. The result is that the above algorithm is O(n

). In anothe r example, if an

algorithm was analyzed to be 3 + log n + 2n, what would it be in Big O notation?

The answer would be O(n) because 2n is the dominate term (slowest) and as before

the coefﬁcient is not included.

Continuing, what would the efﬁciency be for the following loop?

i=n;

while(i>1){

// some statements

i=i/2;

}

At ﬁrst it might appear that the inner statements are execu ted ½ n times due to

the division by 2, but this would be a mistake. As mentioned above, it is sometimes

helpful to pick a number for n and walk through the code segment. If one chose 4,

then one might have also come to the conclusion that the answer is ½ n since it

would loop 2 times. However, as mentioned previously, one does not want to pick a

number that is too small where a pattern might not be seen. Instead, try the number

16 for the value of n. The ﬁrst time through the value of i would be 16. The second

time through the value of i would be 8. The third time through it would be 4,

followed by the value of 2 the fourth time through the loop. The loop does not

iterate a ﬁfth time because the value of i would be 1 which makes the relation in

the while statement false. The result is that when n is 16, the loop iterates 4

times. How many times would it iterate when n was 32? As one might suspect, the

answer is 5. If 2

is equal to 16, then log

of 16 is 4. Likewise, if 2

is equal to 32,

then log

32 is equal to 5. The resul t is that the above code segment is logarithmic

and is of order log

n or O(log n). Notice that if the subscript 2 is left off the

logarithm, because in the ﬁeld of computer science, log is assumed to be log

6 1 Preliminary Concepts

剩余384页未读，继续阅读

WindStand

粉丝: 35
资源: 367

Java版数据结构精要指南：从基础到高级实现

Tarjan-data_structures_and_network_algorithms.pdf

Python库 | captif_data_structures-0.7-py3-none-any.whl

[]_Dassault_Systemes_Inc._Introduction_to_Abaqus(z-lib.org).pdf

leetcode下载-Play-with-Data-Structures_TS:Play-with-Data-Structures_TS

Oracle_Database11g-Administration_Workshop_I-2-1212.pdf

Oracle_Database11g-Administration_Workshop_I-1-1212.pdf

Data-Structures-and-Algorithms-with-Python-Undergraduate-Topics-in-Computer-Science.pdf.pdf

data_structures_and_algorithms_in_java_4th_edition.4630586266.pdf

Fundamentals_of_Python_From_First_Programs_through_Data_Structures_2009.pdf.pdf

TypeScript_基础数据结构以及部分排序算法_Data-Structures-And-Algorithm.zip

最新资源