数据结构-自学-自用

第一章 绪论

1 数据结构的研究内容

介绍有哪些内容是涉及到数据结构的事例

1.2数据结构的基本概念和术语

1. 数据：是客观事物的符号表示，是所有能输入计算机中并被计算机程序处理的符号的总称
2. 数据元素：数据的基本单位，也被称为元素，记录等
3. 数据项：组成数据元素的，有独立含义的，不可分割的最小单位
4. 数据对象：性质相同的数据元素的集合，是数据的一个子集
5. 数据结构的含义：相互之间存在一种或多种特定关系的数据元素的集合

数据结构

逻辑结构

逻辑结构怎么说呢，概念很简单，只要记住，从逻辑关系上描述数据，与数据的存储无关。
有两个要素：数据元素，关系

存储结构

概念：数据对象在计算机中的存储表示，也称为物理结构

顺序存储结构

借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，要求所有的元素依次存放在一片连续的存储空间中

链式存储结构

无须占用一整块存储空间，为了表示节点之间的关系，需要给每个节点附加指针字段，用于存放后继元素的存储地址

数据类型

概念：数据类型是一个值的集合和定义在这个值上的一组操作的总称

抽象数据类型 （ADT）

包含三个部分：数据对象，数据对象上关系的集合以及对数据对象的基本操作的集合
赋值参数只为操作提供输入值
引用函数以&开头

算法和算法分析

算法的定义：

为了解决某类问题而规定的一个有限长的操作序列

算法的特性：

1.有穷性：有穷步
2.确定性：操作有确切的规定
3.可行性：操作通过运算执行实现
4.输入：0或多个输入
5.输出：至少有一个或多个输出

评价算法优劣的基本标准

1.正确性：合理数据，好的算法，得到正确的结果
2.可读性：便于理解
3.健壮性：输入非法数据时能做出正确反应或进行相应处理
4.高效性：包括空间–空间复杂度，时间–时间复杂度

算法的时间复杂度

衡量算法效率的方法主要有：事后统计法和事前分析估算法

问题规模和语句频度

影响算法时间代价的最主要因素是问题规模
问题规模是算法求解问题输入量的多少，是问题大小的本质表示，一般用整数n表示

语句频度：一条语句的重复执行次数

时间复杂度：T（n)=O(f(n))
分为：最好时间复杂度
最坏时间复杂度
平均时间复杂度
空间复杂度：S（n）=O(f(n))