数据结构

基本定义:

数据结构，就是一种程序设计优化的方法论，研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，目的是加快程序的执行速度、减少内存占用的空间。

数据结构的应用:

• 算机的主要工作就是把数据（Data）经过某种运算处理转换为实用的信息（Information）。具体介绍一些数据结构的应用：

1）树形结构

树形结构是一种相当重要的非线性数据结构，广泛运用在人类社会的族谱、机关的组织结构、计算机的操作系统结构、平面绘图应用、游戏设计等方面。

• 上图：地形与四叉树的对应关系

2）最短路径

• 最短路径是指在众多不同的路径中距离最短或者所花费成本最少的路径。寻找最短路径最常见的应用是公共交通运输系统的规划或网络的架设，如都市公交系统、铁路运输系统、通信网络系统等。
• 现在很多汽车和手机都安装了GPS导航，用于定位和路况查询。其中路程的计算就是以最短路径的理论作为程序设计的依据，为旅行者提供不同的路径作为选择方案。

3）搜索理论

• 所谓“搜索引擎”，是一种自动从因特网的众多网站中查找信息，再经过一定的整理后提供给用户进行查询的系统，例如百度、谷歌、搜狗等。
• 注意，Search这个单词在网络上习惯上翻译为“搜索”，如搜索引擎。而在数据结构的算法描述中，习惯翻译成“查找”。在计算机科学中，“搜索”和“查找”大部分情况下可以互相转换。

概述:

程序能否快速而高效地完成预定的任务，取决于是否选对了数据结构，而程序是否能清楚而正确地把问题解决，则取决于算法。算法是计算机处理信息的本质，因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务。

总结：

“Algorithms + Data Structures = Programs”（出自：Pascal之父Nicklaus Wirth）

• 算法是为了解决实际问题而设计的，

• 数据结构是算法需要处理的问题载体。

数据间的逻辑结构

• 集合结构
• 线性结构
• 树形结构
• 图形结构

1.集合结构

集合结构中的数据元素处理同属于一个集合崴，它们之间没有其他关系。各个数据元素是“平等”的，它们的共同属性是“同属于一个集合”。数据结构中的集合关系就类似于数学中的集合

2.线性结构

线性结构中的数据元素之间是一对一的关系

• 对应Java中的线性表：顺序表、链表、栈、队列

3.树形结构

树形结构中的数据元素之间存在一种一对多的层次关系

4.图形结构

图形结构的数据元素是多对多的关系

数据的存储结构(或物理结构)

物理结构又叫存储结构，分为四种，

• 顺序存储结构
• 链式存储结构
• 索引结构
• 散列结构

1) 顺序存储结构

一段连续的内存空间

• 优点：随机访问
• 缺点：插入删除效率低，大小固定

2) 链式存储结构

不连续的内存空间

• 优点：大小动态扩展，插入删除效率高
• 缺点：不能随机访问

3) 索引存储结构

为了方便查找，整体无序，但索引块之间有序，需要额外空间，存储索引表。

• 优点：对顺序查找的一种改进，查找效率高
• 缺点：需额外空间存储索引

4) 散列存储结构

散列存储，又称hash存储，是一种力图将数据元素的存储位置与关键码之间建立确定对应关系的查找技术。

• 优点：查找基于数据本身即可找到，查找效率高，存取效率高。
• 缺点：存取随机，不便于顺序查找。