java数据结构与算法的基础总结

谁借莪１个温暖的怀抱￠ 2022-06-07 03:20 160阅读 0赞

## java中的数据结构与算法 ##

本文参考文章：  
[Java数据结构与算法之学习路线][Java]  
[最全的数据结构解析与归纳][Link 1]

### 数据结构 ###

首先，要清楚数据结构的概念：数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。  
我们在清楚java数据结构后,可以通过选择使用适当的数据结构来提高程序的运行或者存储效率。

#### 数据结构与算法的学习路线(粗糙) ####

![学习路线][Center]

线性数据结构：  
![Center 1][]

#### 各类线性结构常用的使用场景 ####

数组：  
特点：元素在内存中线性连续存储，可以根据下标快速访问数组元素，但是增删效率不是很高，每一次增加或删除元素都需要  
大量移动元素空出插入位置或者填补删除元素的位置。

使用场景：频繁查询，很少进行增加或删除操作的情况

链表：  
特点：存储可以不连贯，根据索引将数据联系起来，当查询元素的时候需要从开头开始去查询，所以效率比较低，然而增加或删除  
元素的时候只需要修改索引就可以了。

使用场景：少查询，需要频繁插入或删除的情况

队列：  
特点：先进先出(FIFO/fisrt in first out),如同一个单向隧道，先进的车先出。

使用场景：多线程的阻塞队列管理非常有用

栈：  
特点：后进先出(LIFO/last in first out),就像一个箱子，先放进去的东西在底部，需要先拿出上面的东西，下面的东西才能拿出来

使用场景：实现递归以及表达式计算，android运用栈的原理实现back stack

#### 数组与链表的区别 ####

(1)数组连续，链表不连续  
(2)数组内存静态分配，链表内存动态分配  
(3)数组查询时间复杂度为O(1),链表为0(n)  
(4)数组增加删除的时间复杂度为O(n),链表为O(1)  
(5)数组从栈中分配空间，链表从堆中分配空间

### 数据结构与算法的关系 ###

参考文章：[数据结构与算法][Link 2]  
数据结构：数据与数据之间的结构关系（数组、队列、树、图等结构）

算法：解决问题的步骤

1、程序 = 数据结构 + 算法 。数据是程序的中心。数据结构和算法两个概念间的逻辑关系贯穿了整个程序世界，首先二者表现为不可分割的关系。没有数据间的有机关系，程序根本无法设计。

2、数据结构与算法关系：数据结构是底层，算法高层。数据结构为算法提供服务。算法围绕数据结构操作。

3、解决问题（算法）需要选择正确的数据结构。例如：算法中经常需要对数据进行增加和删除用链表数据结构效率高，数组数据结构因为增加和删除需要移动数字每个元素所有效率低。

4、数据结构特点：每种数据结构都具有自己的特点。例如：队列：先进先出。栈：先进后出。等等

5、算法的特性：算法具有五个基本特征：输入、输出、有穷性、确定性和可行性。

6、数据结构应用：数据结构往往同高效的检索算法、索引技术、排序算法有关

7、数据结构（逻辑数据结构）通过计算机语言来实现数据结构（存储数据结构）。例如：树型数据结构：通过计算机语言中的数组（节点）和指针（指向父节点）来实现。

8、存储结构：逻辑数据结构的实现。存储结构通过计算机语言实现。 例如：堆数据结构，堆是一棵完全二叉树，所以适宜采用顺序存储结构（顺序存储：数组），这样能够充分利用存储空间。

9、算法目的：算法是为数据结构服务。例如：数据结构通常伴随有查找算法、排序算法等

10、数据结构的优劣：一种数据结构的优劣是在实现其各种运算的算法中体现的。

二、数据结构：分为逻辑数据结构和存储数据结构两种  
（1）顺序存储方法（顺序存储结构）  
（2）链接存储方法（链式存储结构）  
同一种逻辑结构可采用不同的存储方法（以上两种之一或组合），这主要考虑的是运算方便及算法的时空要求。

[Java]: http://blog.csdn.net/qq_28057577/article/details/52692089
[Link 1]: http://blog.csdn.net/long316/article/details/52595248
[Center]: /images/20220607/65e2fec7a47e46c39b034cece7c92768.png
[Center 1]: /images/20220607/2e7ec152de8f48d7ac1b2db82adecb76.png
[Link 2]: http://www.cnblogs.com/chenweichu/p/6394026.html