第一节 数据结构和算法基本概念
一、数据结构的基本概念
1、数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并且被计算机程序处理的符号的总称。
2、数据元素：数据元素是数据的基本单位。一个数据元素可由若干个数据项组成。
3、数据项：数据项是构成数据元素不可分割的最小单位。
4、数据对象：性质相同数据元素的集合。
5、数据结构：在任何人问题中数据元素都是不可孤立存在的，而是他们之间存在着某种关系，这种数据元素之间的某种关系称之为数据结构。数据结构包括了3个方面的内容：逻辑结构、存储结构、数据的运算。
6、数据的逻辑结构：数据的逻辑结构是对数据之间逻辑的描述，他与数据的存储结构无关，同一种逻辑结构可以有多种存储结构。
（1）、逻辑结构的分类
a、线性结构：是一个数据元素的有序集合。
- 集合中必存在唯一的一个第一个元素。
- 集合中必存在唯一的一个最后一个元素。
- 除最后一个元素之外，其他数据元素均有唯一的“后缀元素”。
- 除第一个元素之外，其他的数据元素均有唯一的“前缀元素”
数据结构中，线性结构是指数据元素之间存在这“一对一”的线性关系的数据结构
b、非线性结构：非线性结构中的节点存在着一对多，多对多的关系。集合、树、图是典型的非线性结构。
7、数据的存储结构（物理结构）
（1）定义：数据的物理结构又称存储结构，是数据逻辑结构在计算机中的表示，它包含数据元素的表示和数据关系的表示。
（2）存储方法：数据元素之间的关系在计算机中有两种不同的表示方法（顺序映像、非顺序映像）。对应的两种不同的存储结构分别是顺序存储结构和链式存储结构。顺序映像是借助数据元素之在存储器中相对位置来表示数据元素之间的逻辑关系。非顺序映像是借助指针来表示数据元素之间的逻辑关系。
4 种常见的存储方法：
1、顺序存储方法 ：该方法把逻辑上相邻的节点在物理上存储上也存到相邻的物理存储单元中。节点之间的逻辑关系由存储单元的邻接关系来体现。
优点：随机存取，每个元素占用最少存储空间。
缺点：易产生较多的外部邻接碎片。
2、链式存储方法：该方法不要求逻辑上相邻的节点物理上也相邻，节点之间的关系是通过指针字段表示的。
优点：不会出现碎片现象，充分利用所有存储单元。
缺点：每个元素因额外的指针占用了额外的存储单元，并且只能实现顺序存取。
3、索引存储方法：在存储索引元素的同时还建立附加的索引表。
优点：检索速度快。
缺点：增加了附加的索引表，会占用较多的存储空间。同时在增删数据时会增加对索引表的操作，浪费时间。
4、散列存储：根据关键字直接计算出该元素的存储地址，又称为Hash存储。
优点：检索和增删操作很快。
缺点：可能会出现存储单元冲突，而解决冲突会增加时间和空间开销。
二、算法的特征
1、有穷性：一个算法必须保证有限个步骤之后结束，且每步在有穷时间内完成。
2、确定性：算法的每一步必须有确定的含义，不会产生二义性。
3、可行性：算法中描述的操作是可以通过已经实现的基本运算执行有限次来实现。
4、输入：一个算法有零个或者多个输入。
5、输出：一个算法有一个或者多个的输出，这个输出是同输入有着某种关系的特定量。
三、算法的设计目标
1、正确性：算法要能正确的执行预先设定好功能和性能要求。
2、可读性：算法要易于人的理解。
3、健壮性：算法要很好的容错性，能够对不合理的数据进行检查。
4、高效率与低存储量要求：算法的执行时间要快，需要执行内存要小。