数据结构 + 算法 = 程序
1. 数据结构研究的内容
如何合理的组织数据，高效的处理数据，主要研究非数值计算问题，非数值计算问题无法用数学方程建立数学模型。
好的数据结构可以带来更快的运行或是存储效率。
2. 概念和术语
概念：
数据结构是计算机存储、组织数据的方式，是由相互之间存在着一种或多种关系的数据元素的集合和集合中数据元素之间的关系组成(元素和元素之间的关系)；
是相互之间存在一种或多种特定关系的数据元素的集合。
数据之间的关系称为结构。
中文名|英文名
---|---|--|
数据|Data|指能输入到计算机并且被计算机程序处理的符号的总称。
数据元素|Data Element|数据的基本单位，在计算机中通常作为一个整体进行考虑或处理。
数据项|Data Item|一个数据元素可以有若干个数据项组成。
数据对象|Data Object|性质相同的数据元素的集合，是数据的一个子集。
3. 数据结构包含的内容
- 数据的逻辑结构：数据之间的逻辑关系，算法的设计就需要依赖于逻辑结构。
- 数据的物理结构：数据在计算机中的表示，即存储结构，算法的实现需要依赖于物理结构。
- 数据的运算结构：暂时不讨论
文章所描述的数据结构：包括逻辑结构和物理结构两个层次；
1. 逻辑结构：
从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的，可看做是从具体问题中抽象出来的数学模型。
它有两大要素：数据元素和关系；
四类基本逻辑结构：
根据数据元素之间关系的不同特性，分为四类基本结构：
| 结构名称 | 特点 |
|---|---|
| 集合结构 | 属于同一结合别无其他关系； |
| 线性结构 | 数据元素之间存在一对一的关系； |
| 树结构 | 元素之间存在一对多的关系； |
| 图结构 | 元素之间存在多对多的关系； |
数据逻辑结构：分为线性和非线性结构
数据逻辑结构
2. 物理结构
数据对象在计算机中的存储表示称为数据的存储结构，也叫物理结构；
存储数据时既要存储数据元素的数据，又要存储数据元素之间的逻辑关系；
数据元素在计算机中有两种基本的存储结构：顺序存储结构、链式存储结构；
| 名称 | 特点 |
|---|---|
| 顺序存储结构 | 借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系；要求所有元素依次存放在一片连续的存储空间中； 一般借用程序设计语言中的数组类型表示； |
| 链式存储结构 | 借助指示元素存储地址的指针表示数据元素之间的逻辑关系，无需占用一整块连续的存储空间，但为了表示节点之间的关系，需要给每一个节点添加附加指针字段，用于存放后续元素的存储地址； 一般借助程序设计语言中的指针类型表示； |
任何一个算法的设计取决于选定的数据逻辑结构，而算法的实现依赖于采用的存储结构
3.数据类型
按值的不同特性，高级程序语言中的数据结构可分为两类：
1.非结构的原子类：原子类型的值是不可分解的。
2.结构类型：如自定义的数据类型。
4.抽象数据类型 （abstract data type）ADT
指一个数学模型以及定义在该模型上的一组操作。由一个值域和定义在该值域上的一组操作组成。
按其值得不同特性分为下列3类：
1.原子类型 atomic data type：该类型的变量的值是不可分解的。
2.固定聚合类型 fixed-aggregate data type:该类型的变量，其值由确定数目的成分按某种结构组成。
3.可变聚合类型 variable-aggregate data type:该类型的值的成分的数目是不确定的。
4. 程序
算法+数据结构 = 程序
1.算法和算法分析性
算法：Algorithm是为解决某类问题而规定的一个有限长的操作序列。
算法必须满足的5个特性：
| 编号 | 名称 | 解释 |
|---|---|---|
| 1 | 有穷性 | 一个算法必须总是在执行又穷步后结 束，且每一步都必须在有穷的时间内完成。 |
| 2 | 确定性 | 对于每一种情况所应执行的操作，在算 法中都有确切的规定，不会产生二义性，是算法的执行者或阅读者都能明确其含义以及如何执行 |
| 3 | 可行性 | 算法中的所有操作都可以通过已经实现的基本操作运算执行有限次来实现。 |
| 4 | 输入 | 0个或多个输入。 |
| 5 | 输出 | 1个或多个输出。 |
算法设计的要求：
| 编号 | 名称 | 说明 |
|---|---|---|
| 1 | 正确性 | 算法能正确反映需求 |
| 2 | 可读性 | 易于阅读 |
| 3 | 健壮性 | 当输入非法数据时，能正确的做出反映 |
2. 算法的评价标准：
| 名称 | 说明 |
|---|---|
| 正确性 | 在合理 的输入下，能够在有限的运行时间内得到正确的结果。 |
| 可读性 | 便于人们理解和交流。 |
| 健壮性 | 输入非法数据时，能适当的做出正确的反应或进行相应的处理。 |
| 高效性 | 时间和空间两个方面，时间方面指算法设计合理，执行效率高，可用时间复杂度来度量，空间方面指算法占用存储容量合理，空间复杂度衡量。 |
3. 数据结构中的堆栈：
在数据结构中，堆栈是：堆 和栈两种数据结构；
堆：是完全二叉树，堆中各元素是有序的。在这个二叉树中所有的双亲节点和孩子节点存在着大小关系，如所有的双亲节点都大于孩子节点则 为大头堆，如果所有的双亲节点都小于其孩子节点说明这是一个小头堆，建堆的过程就是一个排序的过程，堆得查询效率也很高。
栈：是一种先进后出的线性表。
网友评论