数据:对客观事物的符号表示,在计算机学科中指所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素:数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。
数据项:数据的不可分割的最小单位。一个数据元素可由若干个数据项组成。
数据对象:性质相同的数据元素的集合,是数据的子集。
数据结构:相互之间存在一种或多种特定关系的数据元素的集合。
数据元素都不是孤立存在的,在他们之间存在着某种关系,这种数据元素相互之间的关系称为结构。
根据数据元素之间关系的不同特点,通常分以下四种基本结构:
集合:数据元素之间除“同属于一个集合”外,没有其他关系;
线性结构:数据元素之间存在一对一的关系;
树形结构:数据元素之间存在一对多的关系;
网状结构(图状结构):数据元素之间存在多对多的关系。
上述四种结构描述的是数据元素之间的逻辑关系,因此又称为数据的逻辑结构
数据结构在计算机中的表示(映像)称为数据的物理结构(存储结构)
数据元素之间的关系在计算机中有两种不同的表示方式:顺序表示和非顺序表示,由此得到两种不同的存储结构:顺序存储结构和链式存储结构。
算法:对特定问题求解步骤的一种描述,是指令的有限序列。
算法具有5个特性:
有穷性:一个算法必须在执行有穷步之后结束,且每一步都可以在有穷时间内完成。
确定性:算法中每一条指令必须有确切的含义,读者理解时不会产生二义性。
可行性:算法中描述的操作都可以通过已经实现的基本操作执行有限次来实现。
输入:一个算法有零个或多个输入。
输出:一个算法有一个或多个输出。
算法的时间量度(时间复杂度)记作T(n)=O(f(n))
它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同。
算法所需存储空间的量度(空间复杂度)记作S(n)=O(f(n)),其中n表示问题的规模。