第一章：绪论
数据结构基本概念和术语
数据结构与算法那就是要研究数据之间的联系及设计高效率的算法 程序 = 算法 + 数据结构； 算法 = 逻辑 + 控制 常用的数据结构：数组、队列、文件、
1 数据 data
所有能被计算机识别的符号集合
2 数据元素
是数据（集合）中的一个“个体”
是数据结构中讨论的基本单位
3 数据项
是数据结构中讨论的最小的单位
数据元素可以是数据项的集合
4 数据项 data object
数据对象是具有相同性质的数据元素的集合，是数据的一个子集
5 数据结构
带结构的数据元素的集合，数据结构由一个四元组来表示
Data_Structure = (D,L,S,O)
D：数据的有限集，存储和操作的对象
L: logic structure（逻辑结构） 是数据元素集合D的数据元素之间客观存在的关系的有限集合
S: storage structure（存储结构/物理结构） 是数据元素 D 和数据逻辑关系在计算机里面的存储集合。
D：opration 是数据元素 D上面规定的一组操作
结论：数据结构由数据元素、数据元素之间的逻辑关系、逻辑关系在计算机中的存储表示、以及所规定的操作的四部分组成
6.逻辑结构
与数据在计算机如何存储无关，主要用例人们的理解和指导算法的分析和设计，主要归结为以下四类： 1. 线性结构：数据元素之间存在一对一的关系 2. 树形结构：数据元素之间存在一对多的关系——非线性 3. 图形结构（网状结构）：数据元素之间存在多对多的关系——非线性 4. 集合结构：数据元素的关系属于同一个集合，松散
7. 存储结构
数据结构在计算机中的存储表示，包括数据结构中元素的表示和元素关系的表示，主要用于算法实现。 1. 顺序存储结构：把逻辑上相邻的元素存储在物理位置相邻的存储单元中； 2. 链式存储结构：在数据元素中添加一些地址或辅助结构，用于存放数据元素之间的关系； 每一种逻辑结构都可以使用这两种任意的存储结构来实现，具体要根据实际问题来选择合适的结构搭配来实现最优算法。
8.数据结构的操作
数据元素的查找、插入、删除、遍历和排序
9.数据类型 (Data Type)
程序设计语言中用来刻画操作对象的特性的一个值的集合和定义在此集合上的一组操作的总称。 整型、浮点型等等，（已经封装好的数据结构）
10.抽象数据类型(ADT Abstract Data Type)
ADT一般包含数据元素、数据元素之间的关系及操作三要素（D、R、O） D:元素集合 R:D上的关系集合 O:对D的基本操作 特点：
抽象性（只考虑数据类型的数学抽象特点，在具体使用的时候在去实现具体细节
扩展性（用已有的数据类型扩展出新的数据类型）
11 学习数据结构的意义
是程序设计的基础
算法
算法用途：设计并实现一种用计算机来解决问题的方法
算法的特性：输入、输出、确定性、有限性
算法设计的过程就是将生活中问题的解决方法映射为计算机中的解决方法
计算机问题求解5步骤
问题的理解：清楚问题夫人输入、要求和输出
数据结构设计：一方面要选择或设计能有效表示和存储应用中所涉及的数据对象的数据结构，也是还要选择或设计能支持算法策略实现的数据结构。
算法设计：包括选择算法策略、用适当的方式描述和逐步细化算法步骤。
算法分析：发现有改进完善之处。返回第二步，重新选择或设计数据机构、重新设计算法；
程序实现：用某种计算机程序设计语言，定义数据结构、编写实现算法的代码，在计算机上调试和运行程序。
算法复杂度分析
好的算法应该具备以下特性： 1. 正确性 2. 可读性：好的算法应该层次分明、阅读和修改容易 3. 健壮性：对异常清楚下处理能力的评价，好的算法应该在出现异常或非法数据、或操作不当是都能适当处理； 4. 高效性：对求解太阳问题的不同伏安法所占用的时间或空间的评价。
时间复杂度：T（N,I）（问题规模、输入）
对输入 I 我们只分析最好、最坏和平均的情况 算法的复杂度分析是用渐进分析的方式来算的，并不是真正意义上精确的数据
Last updated