数据结构与算法(java)

在编程过程中，通常会遇到的一个问题就是，性能瓶颈。很多时候考虑的都是怎么去做横向扩展，但偏偏忽略掉了最基本的问题就是系统是否真的已经达到了瓶颈？

性能瓶颈通常的表象是资源消耗过多外部处理系统的性能不足；或者资源消耗不多但程序的响应速度却仍达不到要求。

而调优的方式就是 寻找过度消耗资源的代码 和 寻找未充分使用资源但程序执行慢的原因和代码。

基础决定高度

就拿汽车来比较，通常不懂变速箱、发动机的原理但也是能开车，同样一个不懂数据结构和算法的人也能编程。很多人觉得基本的数据结构及操作已经在高级语言中封装,都可以直接调用库函数，那么到底有没有必要好好学习数据结构？

数据结构+算法＝程序

通常在程序中，遇到一个实际问题，充分利用数据结构，将数据及其之间的关系有效地存储在计算机中，然后选择合适的算法策略，并用程序高效实现，这才是提高程序性能的主要方式。

• 如何有效地存储数据，不同的数据结构产生什么样的算法复杂性，有没有更好的存储方法提高算法的效率？

如果没有具备这块相应的知识，怎么完成上述的实现？如果脱离了原有的调用，怎么完成程序的高效实现？而所有的应用实现都依赖于基础，基础就是数据结构和算法。了解这块，才能做到无惧任何技术的演变。所有说基础决定高度！

首先讲一些基本的概念

数据结构表示数据在计算机中的存储和组织形式，主要描述数据元素之间和位置关系等。选择适当的数据结构可以提高计算机程序的运行效率（时间复杂度）和存储效率（空间复杂度）。

数据结构的三种层次：

1. 逻辑结构--抽象层： 主要描述的是数据元素之间的逻辑关系

• 集合结构（集）： 所有的元素都属于一个总体，除了同属于一个集合外没有其他关系。集合结构不强调元素之间的任何关联性。
• 线性结构（表）： 数据元素之间具有一对一的前后关系。结构中必须存在唯一的首元素和唯一的尾元素。
• 树形结构（树）： 数据元素之间一对多的关系
• 网状结构（图）： 图状结构或网状结构 结构中的数据元素之间存在多对多的关系

1. 物理结构--存储层： 主要描述的是数据元素之间的位置关系

• 顺序结构：顺序结构就是使用一组连续的存储单元依次存储逻辑上相邻的各个元素
• 优点：只需要申请存放数据本身的内存空间即可，支持下标访问，也可以实现随机访问。
• 缺点：必须静态分配连续空间，内存空间的利用率比较低。插入或删除可能需要移动大量元素，效率比较低
• 链式结构：链式存储结构不使用连续的存储空间存放结构的元素，而是为每一个元素构造一个节点。节点中除了存放数据本身以外，还需要存放指向下一个节点的指针。
• 优点：不采用连续的存储空间导致内存空间利用率比较高，克服顺序存储结构中预知元素个数的缺点 插入或删除元素时，不需要移动大量的元素。
• 缺点：需要额外的空间来表达数据之间的逻辑关系， 不支持下标访问和随机访问。
• 索引结构：除建立存储节点信息外，还建立附加的索引表来标节点的地址。索引表由若干索引项组成。
• 优点：是用节点的索引号来确定结点存储地址，检索速度块
• 缺点：增加了附加的索引表,会占用较多的存储空间。
• 散列结构：由节点的关键码值决定节点的存储地址。散列技术除了可以用于查找外，还可以用于存储。
• 优点：散列是数组存储方式的一种发展，采用存储数组中内容的部分元素作为映射函数的输入，映射函数的输出就是存储数据的位置, 相比数组，散列的数据访问速度要高于数组
• 缺点：不支持排序，一般比用线性表存储需要更多的空间，并且记录的关键字不能重复。

1. 运算结构--实现层： 主要描述的是如何实现数据结构

• 分配资源，建立结构，释放资源
• 插入和删除
• 获取和遍历
• 修改和排序

每种逻辑结构采用何种物理结构来实现，并没有具体的规定。当一个结构，在逻辑结构中只有一种定义，而在物理结构中却有两种选择，那么这个结构就属于逻辑结构；

数组

栈(后进先出)

队列(先进先出)

链表

二叉树(由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成)

堆(也被称为优先队列(队列+排序规则)，图一最大堆，图二最小堆)

红黑树(每节点五元素，颜色(如果一个节点是红的，则它的两个儿子都是黑的)、键值、左子节点、右字节的、父节点)

数据结构比较

常用的数据结构：

数据结构选择：

数组

在Java中，数组是用来存放同一种数据类型的集合，注意只能存放同一种数据类型。

//只声明了类型和长度
数据类型 [] 数组名称 = new 数据类型[数组长度];
//声明了类型，初始化赋值，大小由元素个数决定
数据类型 [] 数组名称 = {数组元素1，数组元素2，......}

大小固定，不能动态扩展(初始化给大了，浪费；给小了，不够用)，插入块，删除和查找慢