《Think Data Structures》：Java数据结构与算法解析

需积分: 10 28 浏览量更新于2024-07-18 收藏 5.16MB PDF 举报

"Data Structure - 英文原版Java数据结构与算法入门，2017年新版，作者Allen B Downey" 本书《ThinkDataStructures: Algorithms and Information Retrieval in Java》由Allen B. Downey撰写，是针对Java编程语言的数据结构和算法的入门教程，适合初学者和有一定基础的学习者。2017年的版本进行了更新，确保了内容的时效性和实用性。在数据结构部分，书中涵盖了以下核心概念： 1. 数组（Arrays）：这是最基础的数据结构，讲解了如何创建、访问和操作数组，包括一维数组和多维数组。 2. 链表（Linked Lists）：介绍了单链表和双链表，以及它们在内存中的表示和基本操作，如插入、删除和遍历。 3. 栈（Stacks）：阐述了栈的后进先出（LIFO）特性，并讨论了其在递归和回溯问题中的应用。 4. 队列（Queues）：讲解了先进先出（FIFO）的队列实现，如循环队列和优先级队列。 5. 树（Trees）：包括二叉树、平衡树（如AVL树和红黑树）以及搜索树的概念和操作。 6. 图（Graphs）：介绍图的表示方法（邻接矩阵和邻接表），以及图的遍历算法（深度优先搜索和广度优先搜索）。 7. 散列表（Hash Tables）：讲解了散列函数的设计、冲突解决策略以及散列表在实现快速查找中的作用。 8. 堆（Heaps）：讨论了最大堆和最小堆，以及它们在优先级队列和排序中的应用。在算法部分，书中深入探讨了以下主题： 1. 排序算法（Sorting Algorithms）：如冒泡排序、选择排序、插入排序、快速排序、归并排序等，分析了它们的时间复杂度和稳定性。 2. 查找算法（Search Algorithms）：包括线性查找、二分查找、哈希查找等，以及它们在不同数据结构上的应用。 3. 递归（Recursion）：讲解了递归的基本原理、递归函数的编写以及递归在解决复杂问题（如斐波那契数列、汉诺塔等）中的应用。 4. 动态规划（Dynamic Programming）：介绍了动态规划的思想，通过实例解释了如何用动态规划解决最优化问题。 5. 贪心算法（Greedy Algorithms）：讲解了贪心策略及其在解决问题时的适用性。此外，书中还涉及到了信息检索的主题，这可能包括： 1. 文本索引（Text Indexing）：如何构建和使用倒排索引来高效地进行文本搜索。 2. 数据压缩（Data Compression）：如霍夫曼编码和游程编码等压缩技术，以及它们在存储和传输大量数据时的作用。 3. 字符串匹配（String Matching）：包括朴素的字符串匹配算法和更高效的KMP算法。这本书以实践为导向，通过实际的代码示例来帮助读者理解和掌握这些概念。同时，它也强调了分析和评估算法性能的重要性，引导读者养成良好的编程习惯和思维模式。无论是对计算机科学专业的学生，还是对希望提升自己编程能力的开发者来说，都是一本非常有价值的参考书。

Interfaces in Java

A Java interface specifies a set of methods; any class that implements this interface has to

provide these methods. For example, here is the source code for Comparable, which is an

interface defined in the package java.lang:

public interface Comparable<T> {

public int compareTo(T o);

}

This interface definition uses a type parameter, T, which makes Comparable a generic type. In

order to implement this interface, a class has to

Specify the type T refers to, and

Provide a method named compareTo that takes an object as a parameter and returns an int.

For example, here’s the source code for java.lang.Integer:

public final class Integer extends Number implements Comparable<Integer> {

public int compareTo(Integer anotherInteger) {

int thisVal = this.value;

int anotherVal = anotherInteger.value;

return (thisVal<anotherVal ? -1 : (thisVal==anotherVal ? 0 : 1));

}

// other methods omitted

}

This class extends Number, so it inherits the methods and instance variables of Number; and it

implements Comparable<Integer>, so it provides a method named compareTo that takes an

Integer and returns an int.

When a class declares that it implements an interface, the compiler checks that it provides all

methods defined by the interface.

As an aside, this implementation of compareTo uses the “ternary operator”, sometimes written ?:. If

you are not familiar with it, you can read about it at http://thinkdast.com/ternary.

List Interface

The Java Collections Framework (JCF) defines an interface called List and provides two

implementations, ArrayList and LinkedList.

The interface defines what it means to be a List; any class that implements this interface has to

provide a particular set of methods, including add, get, remove, and about 20 more.

ArrayList and LinkedList provide these methods, so they can be used interchangeably. A method

written to work with a List will work with an ArrayList, LinkedList, or any other object that

implements List.

Here’s a contrived example that demonstrates the point:

public class ListClientExample {

private List list;

public ListClientExample() {

list = new LinkedList();

}

private List getList() {

return list;

}

public static void main(String[] args) {

ListClientExample lce = new ListClientExample();

List list = lce.getList();

System.out.println(list);

}

ListClientExample doesn’t do anything useful, but it has the essential elements of a class that

encapsulates a List; that is, it contains a List as an instance variable. I’ll use this class to make a

point, and then you’ll work with it in the first exercise.

The ListClientExample constructor initializes list by instantiating (that is, creating) a new

LinkedList; the getter method called getList returns a reference to the internal List object; and

main contains a few lines of code to test these methods.

The important thing about this example is that it uses List whenever possible and avoids specifying

LinkedList or ArrayList unless it is necessary. For example, the instance variable is declared to

be a List, and getList returns a List, but neither specifies which kind of list.

If you change your mind and decide to use an ArrayList, you only have to change the constructor;

you don’t have to make any other changes.

This style is called interface-based programming, or more casually, “programming to an interface”

(see http://thinkdast.com/interbaseprog). Here we are talking about the general idea of an interface,

not a Java interface.

When you use a library, your code should only depend on the interface, like List. It should not

depend on a specific implementation, like ArrayList. That way, if the implementation changes in the

Exercise 1

Since this is the first exercise, we’ll keep it simple. You will take the code from the previous section

and swap the implementation; that is, you will replace the LinkedList with an ArrayList.

Because the code programs to an interface, you will be able to swap the implementation by changing

a single line and adding an import statement.

Start by setting up your development environment. For all of the exercises, you will need to be able to

compile and run Java code. I developed the examples using Java SE Development Kit 7. If you are

using a more recent version, everything should still work. If you are using an older version, you might

find some incompatibilities.

I recommend using an interactive development environment (IDE) that provides syntax checking,

auto-completion, and source code refactoring. These features help you avoid errors or find them

quickly. However, if you are preparing for a technical interview, remember that you will not have

these tools during the interview, so you might also want to practice writing code without them.

If you have not already downloaded the code for this book, see the instructions in “Working with the

Code”.

In the directory named code, you should find these files and directories:

build.xml is an Ant file that makes it easier to compile and run the code.

lib contains the libraries you’ll need (for this exercise, just JUnit).

src contains the source code.

If you navigate into src/com/allendowney/thinkdast, you’ll find the source code for this

exercise:

ListClientExample.java contains the code from the previous section.

ListClientExampleTest.java contains a JUnit test for ListClientExample.

Review ListClientExample and make sure you understand what it does. Then compile and run it. If

you use Ant, you can navigate to the code directory and run ant ListClientExample.

You might get a warning like:

List is a raw type. References to generic type List<E>

should be parameterized.

To keep the example simple, I didn’t bother to specify the type of the elements in the List. If this

warning bothers you, you can fix it by replacing each List or LinkedList with List<Integer> or

LinkedList<Integer>.

Review ListClientExampleTest. It runs one test, which creates a ListClientExample, invokes

getList, and then checks whether the result is an ArrayList. Initially, this test will fail because the

剩余193页未读，继续阅读

Harold2017

粉丝: 0
资源: 1

《Think Data Structures》：Java数据结构与算法解析

rhino bim structure

data structure in Java

EBG Structure

data structure

DATA STRUCTURE

Data structure

Data-Collection-Data-Structure-.zip_data structure

struct data structure

Python Data Structure

data structure ppt

最新资源