第一章：数据结构与算法概述

??本文参考内容是Java数据结构与算法第二版（已经比较老的内容），以及数据结构第三版内容。如果观看者又更好的资料请联系Qq:1101165230，我将及时更新。

??表1.1 数据结构的特征

数据结构	优点	缺点
数组（顺序存储）线性	插入快，如果知道下标，可以非常快地存取	查找慢，删除慢，大小固定
有序数组	比无序的数组查找快	删除和插入慢，大小固定
栈	提供后进先出方式的存取	存取其他项很慢
队列	提供先进先出方式的存取	存取其他项很慢
链表	插入快、删除快	查找慢
二叉树	查找、删除（如果树保持平衡）、插入快	删除算法复杂
红-黑树	查找、插入、删除都快（树总是平衡的）	算法复杂
2-3-4树	查找、插入、删除都快（树总是平衡的。类似的树对磁盘存储有用）	算法复杂
哈希表（散列存储）	如果关键字已知存取极快。插入快	删除慢，如果不知道关键字则存取很慢，对存储空间使用不充分
堆	插入、删除快，对最大的数据项存取很快	对其他数据项存取慢
图	对现实世界建模	有些算法慢且复杂

?? 数据结构分为：存储结构、逻辑接口。也可以分为（线性结构和非线性结构）

?? 分类一：线性结构与非线性结构（逻辑结构）

线性结构

?? 1. 有一个唯一的开始节点（第一个节点）；
?? 2. 有一个唯一的结束节点（最后一个节点）；
?? 3. 除结尾元素外，其他元素都一个后继节点；
?? 4. 除开始元素外，其他元素都有一个前驱节点；

非线性结构

??树（二叉树）、图（网）；
??一个节点元素可能有多个前驱或多个后继节点；
??分类二：集合结构、线性结构、网状结构、图形结构
??线性：一对一结构
??网状：一对多
??集合： 唯一的、无序的、确定的
??图形：多对多

??存储结构：常见的存储结构有：顺序存储、链式存储、散列存储、索引存储

??算法概述

??? 许多将要讨论到的算法直接适用于某些特殊的数据结构。对于大多数数据结构来说，都需要知道如何

1. ?? 插入一条新的数据项。
2. ?? 寻找某一特定的数据项。
3. ?? 删除某一特定的数据项。
   ?? 还需要知道如何迭代地访问某一数据结构中的各数据项，以便进行显示或其他操作（排序），还有就是递归，递归在某些算法中非常重要。
   表1.2 Java中的基础数据类型

名称	大小（以位计）	取值范围
boolean	1	true或false
byte	8	-128~+127
char	16	‘000’~‘’
short	16	-32768~+32767
int	32	-2147483648~+2147483647
long	64	-9223372036854775808~+9223372036854775807
float	32	约10的-38次方~10的+38；7位有效数字
double	64	约10的-308次方~10的+308;15位有效数字

注意：而我们常用的String不是基础数据类型。

要点

??? 数据结构是指数据在计算机内存空间中或磁盘中的组织形式。
??? 正确选择数据结构会使程序的效率大大提高。
??? 数据结构的例子有数组、栈和链表。
??? 算法是完成特定任务的过程。
??? 在Java 中，算法经常通过类的方法实现。
??? 一些数据结构的用途是作为程序员的工具:它们帮助执行算法。
??? 其他数据结构可以模拟现实世界中的情况，例如城市之间的电话线网。
??? 数据库是指由许多类似的记录组成的数据存储的集合。
??? 一条记录经常表示现实世界中的一个事物，例如一名雇员或一个汽车零件。
??? 一条记录被分成字段。每个字段都存储了由这个记录所描述事物的一条特性。
??? 一个关键字是一条记录中的一个字段，通过它可以对数据执行许多操作。例如，人事记录可以通过 LastName 字段进行排序。