什么是数据结构
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。 ——彭军、向毅《数据结构与算法》
“数据结构是数据对象，以及存在于该对象的实例和组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。”他将数据对象（data object）定义为“一个数据对象是实例或值的集合”。 ——Sartaj Sahni 《数据结构、算法与应用》
将一个数据结构的设计过程分成抽象层、数据结构层和实现层。其中，抽象层是指抽象数据类型层，它讨论数据的逻辑结构及其运算，数据结构层和实现层讨论一个数据结构的表示和在计算机内的存储细节以及运算的实现。 ——Robert L.Kruse在《数据结构与程序设计》
“数据结构是ADT（抽象数据类型Abstract Data Type） 的物理实现。” ——Clifford A.Shaffer在《数据结构与算法分析》
数据结构与解决问题方法
解决问题方法的效率，跟数据的组织方式有关
解决问题方法与空间的利用效率有关
解决问题方法的效率，跟算法的巧妙程度有关
数据结构的三大结构
逻辑结构（抽象层）、物理结构（结构层）、数据结构的基本操作
逻辑结构指人对数据之间关系的理解和看法，逻辑结构和计算机无关。集合结构、线性结构、树型结构、网状结构
物理结构描述计算机内部数据之间实际的关系。 顺序结构、链式结构
数据结构的基本操作：创建/销毁-分配资源、建立结构、释放资源；插入/删除 -增加、减少数据元素；获取/修改 -遍历、迭代、随机访问（增删改查）；排序/查找 -算法应用
数据结构的三大结构——逻辑结构
集合结构：集合结构中的元素除了同属于一个集合外没有其它关系，集合不强调元素之间的任何关联性，是一种松散的组合
线性结构：线性结构中的元素具有一对一的前后关系。结构规定：1.结构中必须存在唯一的元素；2. 必须存在唯一的尾元素；3.除首元素外，结构中每个元素有且仅有一个前趋元素；4.除尾元素外，结构中每个元素有且仅有一个后继元素。如线性表、栈、队列、串等
树型结构：树型结构中的元素具有一对多的父子关系。结构规定：1.结构中必须存在唯一的根元素；2.除根元素外，结构中的每个元素有且仅有一个前趋元素；3.除叶元素外，结构中的每个元素拥有一到多个后继元素。
网状结构：网状结构中的元素具有多对多的交叉映射关系。结构规定：1.结构中的每个元素都可以拥有任意数量的前趋和后继元素；2.结构中的任意两个元素之间均可建立关联
数据结构的三大结构——物理结构
顺序结构：顺序结构是把逻辑上相邻的元素放在物理位置上也相邻的存储单元中
链式结构：链式结构不使用连续的存储空间存放结构中的元素，而是为每个元素构造一个节点，节点中存放元素本身以外，还要存放指向下一个节点的指针。
数据对象在计算机中的组织方式：
逻辑结构：按照逻辑关系组织起来的一批数据
物理存储结构：按一定的存储方法把它存储在计算机中
在这些数据上定义了一个运算的集合
数据对象必定与一系列加在其上的操作相关联
完成这些操作所用的方法就是算法
什么是算法
一种方法：对特定问题求解过程的描述，是指令的有限序列
算法的特性
通用性：–对参数化输入进行问题求解 –保证计算结果的正确性
有效性：–算法是有限条指令组成的指令序列 –即由一系列具体步骤组成
确定性：–算法描述中的下一步应执行的步骤必须明确
有穷性：–算法的执行必须在有限步内结束 –换句话说，算法不能含有死循环
基本算法分类
穷举法：–顺序找 K 值
回溯、搜索：– 八皇后、树和图遍历
递归分治 ：–二分找 K 值、快速排序、归并排序
贪心法 ：– Huffman 编码树、最短路 Dijkstra 算法、最小生成树 Prim 算法
动态规划 ：– 最短路 Floyd 算法
算法好坏评判标准
空间复杂度S(n) —— 根据算法写成的程序在执行时占用存储单元的长度。这个长度往往与输入数据的规模有关。空间复杂度过高的算法可能导致使用的内存超限，造成程序非正常中断。
时间复杂度T(n) —— 根据算法写成的程序在执行时耗费时间的长度。这个长度往往也与输入数据的规模有关。时间复杂度过高的低效算法可能导致我们在有生之年都等不到运行结果。
时空权衡
增大空间开销可能改善算法的时间开销
可以节省空间，往往需要增大运算时间
数据结构与算法的选择
• 仔细分析所要解决的问题
– 特别是求解问题所涉及的数据类型和数据间逻辑关系—— 问题抽象、数据抽象
– 数据结构的初步设计往往先于算法设计
• 注意数据结构的可扩展性
– 考虑当输入数据的规模发生改变时，数据结构是否能够适应求解问题的演变和扩展
