数据结构与算法（一）——数据结构基础知识

柔情只为你懂 2023-06-20 06:42 23阅读 0赞

注：本篇内容参考了《Java常用算法手册》一书。

本人水平有限，文中如有错误或其它不妥之处，欢迎大家指正！

记得几年前曾学过数据结构和算法，看的是《Java常用算法手册》，当时在武汉也是找了几个书店才买到。学了一段时间觉得书还不错，自己也明白了不少编程的知识。但时间一久，工作中也用的很少，慢慢的就忘记了好多。现在也需要重新学学了，毕竟工作这些年了，至少要必须要掌握一些常用的数据结构。

一是充实自己；二是认为想要把Java以及相关的知识学的深一点，数据结构是必须的一个知识点，比如讲HashMap的原理，如果你对散列表本来就理解的比较深入，把理解HashMap就很容易了。

**目录**

1，数据结构概念

2，数据结构中的基本概念

2，1 数据（Data）

2，2 数据元素（Data Element）

2，3 数据项（Data Item）

2，4 数据结构（Data Structure）

2，5 直接前驱（Immediate Predecessor）

2，6 直接后继（Immediate Successor）

3，数据结构的内容

3，1 数据的逻辑结构（Logical Structure）

3，2 数据的存储结构（Storage Structure）

3，3 数据的运算

4，数据结构是一个有机整体

4，1 同个逻辑结构可以有不同的存储结构

4，2 同一种逻辑结构也可以有不同的数据运算集合

5，数据结构的分类

5，1 线性结构

5，2 非线性结构

6，数据结构的存储方式

6，1 顺序存储方式（Sequential Storage Structure）

6，2 链接存储方式（Linked Storage Structure）

6，3 索引存储方式（Index Storage Structure）

6，4 散列存储方式

6，5 四种存储方式的比较

7，常用数据结构

7，1 数组（Array）

7，2 栈（Stack）

7，3 队列（Queue）

7，4 链表（Linked List）

7，5 树（Tree）

7，6 图（Graph）

7，7 堆（Head）

7，8 散列表（Hash）

--------------------

# 1，数据结构概念 #

Sartaj Sahni在其经典著作《数据结构、算法与应用》一书中提出：数据结构是数据对象、存在于该对象的实例以及组成实例的数据元素之间的各种关系，并且这种关系可以通过定义相关的函数来给出。

Clifford A.Shaffer在其《数据结构与算法分析》一书中认为：数据结构是抽象数据类型ADT的物理实现。其中抽象数据类型ADT，英文全称为Abstract Data Type，简称ADT。

计算机科学家尼克劳斯·沃思（Nikiklaus Wirth）提出了“数据结构+算法=程序”的著名公式。

数据结构是数据的组织形式，是计算机中对数据的一种存储和组织形式，同时也泛指相互之间存在一种或多种特定关系的数据的集合。可以用来表征特定的数据对象。合理的数据结构能够提高算法的执行效率，还可以提高数据的存在效率。

# 2，数据结构中的基本概念 #

下面以我们常见的数据表格来说明数据结构中的基本概念。下面先画一个表格。

### **2，1 数据（Data）** ###

数据是信息的载体，其能被计算机识别、存储和加工处理，是计算机程序加工的“原材料”。数据包含的类型非常广泛，如整数、字符、字符串、实数、图像、声音等。数据可认为是由若干个数据元素组成的。上述表格就是一个数据，其中每一行可以看做是一个数据元素，也可叫做记录或结点，每一行这个数据元素是由序号、姓名、地址、电话数据项构成。

### **2，2 数据元素（Data Element）** ###

数据元素是数据的基本单位，其也称元素、结点、顶点、记录等。一般来讲，一个数据元素由若干个数据项组成。在上述表格中每一行可看作是一个数据元素。由序号、姓名、地址、电话数据项构成。

### **2，3 数据项（Data Item）** ###

数据项是具有独立含义的最小标识单位，也称为字段、域、属性等。在上述表格中，每一行每一列所在的单元格可看作是一个数据项。

### **2，4 数据结构（Data Structure）** ###

数据结构是数据之间的相互关系，也是数据的组织形式。

### **2，5 直接前驱（Immediate Predecessor）** ###

例如对一个表格，对表中任意一个结点，其直接前驱结构最多只有一个，直接前驱结点也就是与它相邻且在它前面的结点。表格中第一个结点没有直接前驱，也就是开始结点。在上述表格中，李四的直接前驱是张三。

### **2，6 直接后继（Immediate Successor）** ###

例如对一个表格，对表中任意一个结点，直接后继结点最多只有一个，直接后继结点是与它相邻且在它后面的结点。表中最后一个结点没有直接后继，也就是终端结点。在上述表格中，李四的直接后继是王五。

# 3，数据结构的内容 #

一般来说，数据结构包含三方面的内容：数据的逻辑结构、数据的存储结构、数据的运算。

### **3，1 数据的逻辑结构（Logical Structure）** ###

也就是数据元素（Data Element）之间的逻辑关系。是从逻辑关系上对数据进行描述，与数据在计算机中是如何存储无关，它是独立计算机的抽象概念。从数据分析的角度来看，数据的逻辑结构可以看做是从具体的问题抽象出来的数据模型。

### **3，2 数据的存储结构（Storage Structure）** ###

是数据元素及其逻辑关系在计算机存储器中的表示形式。数据的存储依赖于计算机语言，是逻辑结构用计算机语言的实现。一般来讲，只有在高级语言的层次上才会讨论存储结构，在低级的机器语言中，存储结构是具体的。

### **3，3 数据的运算** ###

对数据施加操作。数据的运算的基础在于数据的逻辑结构，因为每种逻辑结构都可以归纳一个运算的集合。在数据结构范畴内，最常用的运算包括检索、插入、删除、更新、排序等。

# 4，数据结构是一个有机整体 #

数据的逻辑结构、数据的存储结构和数据的运算是一个整体，孤立的去理解这三者中的任何一个都是不全面的。

### **4，1 同个逻辑结构可以有不同的存储结构** ###

比如线性表是最简单的一种逻辑结构，如果线性表采用顺序方式存储，这种数据结构就是顺序表；如果采用链式方式存储，这种数据结构就是链表；如果线性表采用散列方式存储，这种数据结构就是散列表。

### **4，2 同一种逻辑结构也可以有不同的数据运算集合** ###

相同的数据逻辑结构和存储结构，采用不同的运算集合及运算性质，将会有全新的数据结构。比如线性表，若将线性表的插入运算限制在表的一段，而删除操作限制在表的另一端，那这种数据结构就是队列；若将线性表的插入和删除都限制在表的同一段，那这种数据结构就是栈。

所以数据结构中这三个方面是一个有机的整体，缺一不可。数据的逻辑结构、数据的存储结构和数据的运算任何一个发生变化都将导致一个全新的数据结构出现。

# 5，数据结构的分类 #

数据结构有多种，按照数据的逻辑结构来对其进行简单分类，包含线性结构和非线性结构两类。

### **5，1 线性结构** ###

线性结构就是各个结点具有线性关系，比如一维数组、栈、队列和串都是线性结构。它包含以下几个特点：

*  线性结构是非空集；
 *  线性结构有且仅有一个开始结点和终端结点，即开始结点和结束结点都是唯一的；
 *  线性结构所有结点最多只有一个直接前驱结点和直接后继结点，即结构中各元素之间存在一对一的关系，且是相连的；
 *  存储结构包含顺序存储结构和链式存储结构，顺序存储的线性表称为顺序表，顺序表中的元素都是连续的，按照逻辑顺序依次存放在计算机的一组连续的存储单元中；链式存储的线性表称为链表，链表中存储的元素不一定是连续的，元素节点中存放着数据元素以及相邻元素的地址信息。

比如一维数组a1,a2......an，a1是开始结点，an是终端（结束）结点，且这两个都是唯一的，a2只有一个直接前驱a1，a2也只有一个直接后继a3，数据中的元素是连续的。

![20191209172029946.png][]

### **5，2 非线性结构** ###

非线性结构就是各个结点之间具有多个对应关系，多维数组、广义表、树、图都是非线性结构。它有以下几点特点：

*  非线性结构是非空集；
 *  非线性结构的一个结点可能有多个直接前驱结点和直接后继结点，即结构中各元素可能有多个指向关系，还可能有层次关系。

![format_png][]

如上面的树，A结构有多指向，它同时指向了B和C，且有四层关系。

# 6，数据结构的存储方式 #

数据的存储方式有以下四种：顺序存储方式、链接存储方式、索引存储方式和散列存储方式，这也是数据结构的物理结构。

### **6，1 顺序存储方式（Sequential Storage Structure）** ###

顺序存储方式就是一块连续的存储区域，一个接一个地存放数据。它把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现，所以它的存储利用率高，是静态分配的。顺序存储方式也称为顺序存储结构，一般采用数组或结构数组来描述。顺序存储的线性表称为顺序表，顺序表中的元素都是连续的。

顺序存储方式主要用于线性逻辑结构的数据存放，比如Java中的一维数组，像图、树这样的非线性结构则不适用。

![format_png 1][]

### **6，2 链接存储方式（Linked Storage Structure）** ###

链接存储比较灵活，因为它不要求逻辑上相邻的结点在物理位置上也相邻，结点间的逻辑关系由附加的引用字段来表示。即一个结点的引用 字段往往指向下一结点的存放位置。

链接存储方式也称为链式存储结构，一般在原数据项中增加引用类型来表示结点之间的位置。简而言之，就是链接存储方式中存储的元素不一定连续，结点中除了存储元素数据外还存储了下一个节点的地址信息。在存储上利用率不如顺序存储高，是动态分配的。

### **6，3 索引存储方式（Index Storage Structure）** ###

索引存储方法是采用附加的索引表的方式来存储结点信息。索引表由若干索引项组成，索引存储方式中索引项的一般形式为：（关键字、地址）。其中关键字能唯一标识一个结点的数据项。索引存储方式还可细分为两类：

稠密索引（Dense Index）：每个结点在索引表中都有一个索引项，其中索引项的地址指示结点所在位置信息；

稀疏索引（Spare Index）：一组结点在索引表中只对应一个索引项，其中索引项的地址指示一组结点的起始存储位置。

软件行业中的很多数据库的表都用到了索引，也是类似的一种存储方式。

### **6，4 散列存储方式** ###

散列存储方式是根据结点的关键点直接计算出该结点的存储地址的一种存储方式。像Java的HashTable的hashcode就是如此。

在实际应用中，往往需要根据具体的数据结构来决定采用哪种存储方式。同一逻辑结构采用不同的存储方式，可以得到不同的存储结构。以上四种存储方式即可单独使用，也可组合来使用。

### 6，5 四种存储方式的比较 ###

<table> 
 <tbody> 
  <tr> 
   <td style="width:80px;"><strong>存储方式</strong></td> 
   <td style="width:268px;"><strong>特点</strong></td> 
   <td style="width:201px;"><strong>存储空间利用率及分配</strong></td> 
   <td style="width:180px;"><strong>插入和删除操作</strong></td> 
   <td style="width:120px;"><strong>查询操作</strong></td> 
  </tr> 
  <tr> 
   <td style="width:80px;">顺序</td> 
   <td style="width:268px;">存储地址是连续的，元素相邻</td> 
   <td style="width:201px;">利用率高，静态分配，量大可能导致难以分配连续的存储空间</td> 
   <td style="width:180px;">慢，因为存储是连续的，插入和删除需要移动元素</td> 
   <td style="width:120px;">快，根据值返回位置</td> 
  </tr> 
  <tr> 
   <td style="width:80px;">链式</td> 
   <td style="width:268px;">存储地址不一定连续</td> 
   <td style="width:201px;">利用率低，动态分配，除了存储元素还要存储引用地址</td> 
   <td style="width:180px;">快，因为不是连续的，不需要移动元素</td> 
   <td style="width:120px;">慢，需要逐个查找</td> 
  </tr> 
  <tr> 
   <td style="width:80px;">索引</td> 
   <td style="width:268px;">附加索引表存储结点信息，索引由若干索引项组成，索引项包含关键字和地址</td> 
   <td style="width:201px;">利用率低，需要附加的索引表，动态分配</td> 
   <td style="width:180px;">慢，需要创建索引</td> 
   <td style="width:120px;">快，根据关键字查找</td> 
  </tr> 
  <tr> 
   <td style="width:80px;">散列</td> 
   <td style="width:268px;">根据结点的字段点计算该结点的存储地址</td> 
   <td style="width:201px;">利用率高，计算结点的地址信息，动态分配</td> 
   <td style="width:180px;">快，计算结点的地址信息</td> 
   <td style="width:120px;">快，根据计算出的地址信息查找</td> 
  </tr> 
 </tbody> 
</table>

# 7，常用数据结构 #

平时工作中会涉及到一些常用的数据结构，这里先做简要说明，后面对有详细一点的说明及代码示例。

### **7，1 数组（Array）** ###

数组是一种聚合数据类型，将具有相同类型的若干变量有序的组织在一起的集合。数组可以说是最基本的数据结构了。在很多编程语言中都有对应。

一个数组可分解为多个数组元素，按照元素的类型，可分为整型数组、字符数组、对象数组等。还有一维、二维以及多维数据等。

### 7，2 栈（Stack） ###

栈是一种特殊的线性表，它只能在一个表的一个固定端进行数据结点的插入和删除操作（可操作的一端称为栈顶，另一端称为栈底）。栈按照后进先出（Last In First Out，LIFO）的原则来进行存储数据。即先插入的数据将被压入栈底，最后插入的数据在栈顶。读出数据时从栈顶开始逐个读出。在汇编语言中经常用于重要数据的现场保护。栈中没有数据时，称为空栈。

在栈结构中，只有栈顶元素是可以访问的，其基本操作操作有两个：

*  入栈（Push）：将数据保存到栈顶的操作；
 *  出栈（Pop）：将栈顶的数据弹出的操作。

到这里也知道了，常说的堆栈，其中是有堆和栈两个数据结构。

### 7，3 队列（Queue） ###

队列和栈类似，也是一种特殊的线性表。和栈不同的是队列史允许在表的一端进行插入操作，而在另一端进行删除操作。进行插入操作的一端称为队尾，进行删除操作的一端称为队头。队列中没有元素中称为空队列。

### 7，4 链表（Linked List） ###

链表是一种数据元素按照链式存储结构进行存储的数据结构，这种存储结构在物理上是非连接的。它由一系列数据结点组成，每个数据节点包括数据域和引用域两部分。其中引用域保存数据结构中下一个元素存储的地址。链表结构中数据元素的逻辑顺序是通过链表中的引用链接次序来实现的。

### 7，5 树（Tree） ###

树是典型的非线性结构，它是包含了n个结点的有空集合K。在树结构中，有且仅有一个根结点，该结点没有前驱结点。在树结构中的其它结点都是有且仅有一个前驱结点，而且可以有m个后继结点，m >= 0。如下图。

![format_png][]

### 7，6 图（Graph） ###

图是另一种非线性数据结构。在图结构中，数据结点一般称为顶点，而边是顶点的有序偶对。若两个项点之间存在一条边，那么就表示这两个顶点具有相邻的关系。

![20191209172047900.png][]

### 7，7 堆（Head） ###

堆是一种特殊的树型数据结构，平时讨论较多的树结构是二叉树。堆的特点是其根结点的值是所有结点中最小的或者最大的，并且根结点的两个子树也是一个堆结构。

### 7，8 散列表（Hash） ###

散列表源自于散列函数（Hash function），其思想是若在结构中存在关键字和T相等的记录，那么必定有F(T)的存储位置可以找到该记录，这样就可以不用进行比较而直接取得所要查找的记录了。

[20191209172029946.png]: https://img-blog.csdnimg.cn/20191209172029946.png
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9kc3MzLmJkc3RhdGljLmNvbS83MGNGdjhTaF9RMVlueEdrcG9XSzFIRjZoaHkvaXQvdT0yMzgwODk1MDc4LDI2ODEzNTA5JmZtPTI2JmdwPTAuanBn?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9zczAuYmRzdGF0aWMuY29tLzcwY0Z2SFNoX1ExWW54R2twb1dLMUhGNmhoeS9pdC91PTgyODkyMTMwOCw3NjgxMTk5MDImZm09MjYmZ3A9MC5qcGc?x-oss-process=image/format,png
[20191209172047900.png]: https://img-blog.csdnimg.cn/20191209172047900.png