数据结构与算法-深入浅出数据结构

2020-10-07 本文已影响0人 Shawn_Shawn

前言

在数据结构与算法开篇的部分，我们了解到数据结构的一些基本概念。

数据结构就是指一组数据的存储结构，而算法，就是用来操作数据的方法。
数据结构是为了算法服务的，算法要作用在特定的数据结构之上。
数据结构和算法解决的是如何更省、更快地存储和处理数据的问题。
之前也只是了解了数据结构的基本概念，本篇主要是深入理解一下数据结构。

数据结构的术语

数据：数据不仅仅表示整型，字符串等这些我们常见的数据信息，还可以用来表示声音，图像，视频等信息。实际上，一切能输入到计算机里，并且能被计算机正确处理，输出的就是数据。
数据元素：是组成数据的基本单位，通常被看成一个整体。
数据项： 一个数据元素可以由若干个数据项组成。数据项是数据不可分割的最小单位。但真正讨论问题时，数据元素才是数据结构中建立数据模型的着眼点。
数据对象：是性质相同的数据元素的集合，是数据的子集。
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

在计算机中，数据元素并不是孤立、杂乱无序的，而是具有内在联系的数据集合。数据元素之间存在的一种或多种特定关系，也就是数据的组织形式。

结构：指各个组成部分相互搭配和排列的方式。简单的理解就是关系，比如分子结构，就是说组成分子的原子之间的排列方式。

逻辑结构和物理结构

实际上数据结构是区分逻辑结构和物理结构的。物理结构实际上就是数据结构实际的存储结构，但是逻辑上不一定就是跟存储结构一样的。物理结构一般都是数组和链表，数组和链表作为最基本的数据结构，例如队列，如果是基于数组实现的队列，就被称之为顺序队列，如果是基于链表实现的队列则被称之为链式队列。下面具体来论述下逻辑结构和物理结构。

逻辑结构

逻辑结构指的是数据对象中数据元素之间的相互关系。
逻辑结构分为四种：

集合结构：集合结构中的数据元素除了同属于一个集合外没有其他关系。各个数据元素是“平等”的，共同属性是“同属于一个集合”。集合关系就类似于数学中的集合。数组，链表，散列表。
线性结构：线性结构中的数据元素之间是一对一的关系。队列，栈。
树形结构：树形结构中的数据元素之间存在一种一对多的层次关系。树。
图形结构：图形结构的数据元素是多对多的关系。图。

逻辑结构是针对具体问题的，是为了解决某个问题，在对问题理解的基础上，选择一个合适的数据结构表示数据元素之间的逻辑关系。

物理结构

数据是数据元素的集合，根据物理结构的定义，实际上就是如何把数据元素存储到计算机的存储器中。
数据的存储结构应正确反映数据元素之间的逻辑关系。
数据元素的存储结构形式有两种：

顺序存储结构：是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。实际上就是基于数组实现的数据结构
链式存储结构：是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。数据元素的存储关系并不能反映其逻辑关系，需要用一个指针存放数据元素的地址，通过地址就可以找到相关联数据元素的位置。实际上就是基于链表实现的数据结构。

逻辑结构是面向问题的，而物理结构是面向计算机的，其基本的目标就是将数据及其逻辑关系存储到计算机的内存中。

抽象数据类型

抽象数据类型(abstract data type，ADT)是数据结构的一种抽象表示，它仅说明支持哪些接口，具体的数据结构实现必须遵循这些接口。
抽象数据类型只规范接口，并不规范具体实现细节，也不规范具体用哪种语言来实现。
抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。
一个抽象数据类型定义了：一个数据对象、数据对象中各数据元素之间的关系及对数据元素的操作。

对比java中定义的抽象数据类型：

抽象	实现
`List`	`ArrayList,LinkedList`
`Queue`	`ArrayDeque,LinkedList`
`Map`	`HashMap,TreeMap`

线性表和非线性表

线性表

线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。
线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储，但是把最后一个数据元素的尾指针指向了首位结点）。
在数据结构逻辑层次上细分，线性表可分为一般线性表和受限线性表。一般线性表也就是我们通常所说的“线性表”，可以自由的删除或添加结点。受限线性表主要包括栈和队列，受限表示对结点的操作受限制。

非线性表

只要不满足线性表的特性，都是非线性表，例如树，图，散列表。