Java基础教程：数据结构和算法的初步探索

数据结构和算法对计算机科学至关重要，计算机科学是对数据的研究，在记忆中的表现以及从一种形式到另一种形式的转换。在编程中，我们使用数据结构来存储和组织数据，我们使用算法来处理这些结构中的数据。您对数据结构和算法的了解越多，Java程序的效率就越高。

本文发布了一个介绍数据结构和算法的三部分系列。在第1部分中，您将了解数据结构是什么以及数据结构如何分类。您还将学习一种算法，算法如何表示，以及如何使用时间和空间复杂度函数来比较类似的算法。

什么是数据结构？

数据结构基于抽象数据类型（ADT），维基百科定义如下：

ADT不关心其值的内存表示或其操作如何实现。它就像一个Java接口，它是一种与任何实现断开连接的数据类型。相比之下，数据结构是一个或多个ADT的具体实现，类似于Java类实现接口。

ADT的示例包括员工，车辆，阵列和列表。考虑列表ADT（也称为序列ADT），它描述共享一个共同类型的元素的有序集合。该集合中的每个元素都有自己的位置，允许重复的元素。列表ADT支持的基本操作包括：

• 创建一个新的和空的列表

• 将值附加到列表的末尾

• 在列表中插入一个值

• 从列表中删除一个值

• 迭代列表

• 破坏名单

可以实现List ADT的数据结构包括固定大小和动态大小的一维数组和单链表。（您将被引入第2部分中的数组，第3部分将链接列表引入）

分类数据结构

有多种数据结构，从单个变量到数组或包含多个字段的对象的链表。所有的数据结构都可以分为原始或聚合，有些则被分类为容器。

原始数据与聚合数据

最简单的数据结构存储单个数据项; 例如，存储布尔值的变量或存储整数的变量。我将这样的数据结构称为原语。

许多数据结构能够存储多个数据项。例如，数组可以在其各个时隙中存储多个数据项，并且对象可以通过其字段存储多个数据项。我将这些数据结构称为聚合。

我们将在本系列中看到的所有数据结构都是聚合。

集装箱

数据项存储和检索的任何内容都可以被认为是数据结构。示例包括从前面提到的Employee，Vehicle，Array和List ADT导出的数据结构。

许多数据结构被设计来描述各种实体。例如，Employee类的实例是用于描述各种雇员的数据结构。相比之下，一些数据结构作为其他数据结构的通用存储容器存在。例如，数组可以存储原始值或对象引用。我将后一类数据结构称为容器。

除了聚合之外，我们将在本系列中看到的所有数据结构都是容器。

设计模式和数据结构

使用设计模式将大学生引入数据结构变得相当普遍。布朗大学论文调查了几种有助于设计高质量数据结构的设计模式。除此之外，本文还展示了适配器模式在堆栈和队列的设计中很有用。演示代码如清单1所示。

清单1. DequeStack.java

公共 类 DequeStack 实现 Stack {

清单1摘录了布朗大学论文的DequeStack课程，演示了适配器模式。请注意Stack并且Deque是描述Stack和Deque ADT的接口。MyDeque是一个实现的类Deque。

DequeStack适应MyDeque，使其可以实现Stack。所有DequeStack的方法都是对Deque接口方法的单行调用。然而，有一个小的皱纹，其中Deque异常被转换为Stack异常。

什么是算法？

历史上用作数学计算的工具，算法与计算机科学，特别是数据结构密切相关。的算法是一个指令序列即它在有限的时间周期的任务。算法的质量如下：

• 接收零个或多个输入

• 产生至少一个输出

• 包含明确和明确的说明

• 在有限数量的步骤后终止

• 一个人可以使用铅笔和纸张进行基本的操作

请注意，虽然程序本质上可能是算法的，但许多程序不会在没有外部干预的情况下终止。

许多代码序列符合算法。一个例子是打印报告的代码序列。更着名的是，欧几里得的算法用于计算数学最大公约数。甚至可能会发生数据结构的基本操作（如阵列槽中的存储值）是算法。在这个系列中，我将主要关注用于处理数据结构的更高级别的算法，例如二进制搜索和矩阵乘法算法。

代表算法

你如何表示一个算法？在完全了解其底层算法之前编写代码可能会导致错误，那么什么是更好的选择？两个选项是流程图和伪代码。

使用流程图

甲流程图是一种算法的控制流程的可视化表示。该表示法说明需要执行的语句，需要进行的决策，逻辑流程（用于迭代和其他目的）以及指示起点和终点的终端。图1显示了流程图用于可视化算法的各种符号。

杰夫·弗里森

图1.流程图使用符号来表示语句，决策，逻辑流程和终端

考虑一个将计数器初始化为0的算法，读取字符直到\n看到换行符（）字符，增加所读取的每个数字字符的计数器，并在读取换行符后打印计数器的值。图2中的流程图说明了该算法的控制流程。

杰夫·弗里森

图2.该流程图显示如何从0到9

流程图的简单性及其在视觉上呈现算法控制流的能力（使其易于遵循）是其主要优点。但是，流程图还有几个缺点：

• 由于与绘制相关联的细节，因此很容易将错误或不准确性引入到高度详细的流程图中。

• 即使使用工具来加速此流程，需要时间来定位，标注和连接流程图符号。这种延迟可能会减慢您对算法的理解。

• 流程图属于结构化程序设计时代，在面向对象的环境中不是有用的。相比之下，统一建模语言（UML）更适合于创建面向对象的视觉表示。

使用伪代码

流程图的替代方案是伪代码，它是逼近最终源代码的算法的文本表示。伪代码可用于快速写下算法的表示。因为语法不是一个问题，所以编写伪代码没有硬而快的规则。

编写伪代码时应努力保持一致。一致性将使得将伪代码转换为实际的源代码更容易。例如，考虑以前的面向对象流程图的以下伪代码：

DECLARE CHARACTER CH = '' DECLARE INTEGER 计数 = 0 DO

伪代码首先提出了几个DECLARE引入变量的语句，ch并count初始化为默认值。然后它呈现一个DO执行UNTIL ch包含\n（换行符）的循环，此时循环结束，一个PRINT语句输出count值。

对于每个循环迭代，READ导致从键盘读取一个字符（或者一个文件 - 在这种情况下，什么构成底层输入源并不重要）并分配给它ch。如果这个字符是数字（0通过一个9），count则递增1。

选择正确的算法

您使用的数据结构和算法严重影响应用程序中的两个因素：

1. 内存使用（用于数据结构）。

2. CPU时间（与这些数据结构相互作用的算法）。

因此，您应该特别注意用于处理大量数据的应用程序的算法和数据结构。这些包括用于数据和物联网的应用程序。

测量算法效率

一些算法比其他算法表现更好。例如，二进制搜索算法几乎总是比线性搜索算法更有效 - 您将在第2部分中看到自己。您希望为应用程序的需求选择最有效的算法，但是这种选择可能不如很明显，你会想。

例如，从效率的角度来看，对于选择排序算法（也在第2部分中介绍），在给定机器上排序10,000个整数的时间为0.4秒是什么意思？该基准仅对运行算法的机器，实现本身以及输入数据的大小有效。

计算机科学家通过使用复杂性函数抽象实现和运行时环境细节来衡量算法在时间复杂度和空间复杂性方面的效率。复杂度函数根据输入数据的数量，揭示算法时间和空间要求的差异：

• 一时间复杂度函数测量算法的时间复杂度 --meaning的算法需要多长时间才能完成。

• 一个空间的复杂功能测量算法的空间复杂度 --meaning的内存开销由算法来执行其任务所需的量。

这两个复杂度函数都基于输入（n）的大小，这反映了输入数据的数量。考虑以下用于阵列打印的伪代码：

DECLARE INTEGER I，X [] = [ 10，15，-1，32 ] FOR I = 0 TO LENGTH（X） - 1

转：
http://www.tuicool.com/articles/2aQB7j7

1、具有1-5工作经验的，面对目前流行的技术不知从何下手，

需要突破技术瓶颈的可以加。2、在公司待久了，过得很安逸，

但跳槽时面试碰壁。需要在短时间内进修、跳槽拿高薪的可以加。

3、如果没有工作经验，但基础非常扎实，对java工作机制，

常用设计思想，常用java开发框架掌握熟练的，可以加。

4、觉得自己很牛B，一般需求都能搞定。

但是所学的知识点没有系统化，很难在技术领域继续突破的可以加。

5. 群号：高级架构群 469691824备注好信息！

6.阿里Java高级大牛直播讲解知识点，分享知识，

多年工作经验的梳理和总结，带着大家全面、

科学地建立自己的技术体系和技术认知！