文档介绍：兰州新天地电脑学校兰州新天地电脑学校??????主主编编第第 1 1 章章算法与数据结构基础算法与数据结构基础 算法的基本概念算法的基本概念 数据结构基础数据结构基础 线线性性表表 栈栈和和队队列列 树树 1. 6 排序排序 1. 7 查找查找考点考点 1 1 算法算法一、算法的概念: 一、算法的概念: 算法就是计算机解决问题的过程算法就是计算机解决问题的过程或步骤即解题方案的准确而完整的描述。或步骤即解题方案的准确而完整的描述。 1 1算法的基本特征: 算法的基本特征: 可行性、确定性、有穷性、拥有足够的情报可行性、确定性、有穷性、拥有足够的情报 2 2 算法的基本要素: 算法的基本要素: ( (1 1)对数据对象的运算和操作:每个算法实际上是按照)对数据对象的运算和操作:每个算法实际上是按照解题要求从环境能进行的所有操作中选择合适的操作所组解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列。成的一组指令序列。( (2 2)算法的控制结构:算法中各操作之间的执行顺序。)算法的控制结构:算法中各操作之间的执行顺序。二、算法的复杂度二、算法的复杂度算法的复杂度包括时间复杂度和空间复杂度算法的复杂度包括时间复杂度和空间复杂度 1 1。算法的时间复杂度指算法的时间耗费。算法的时间复杂度指算法的时间耗费(执行算法所需要的计算工作量)。(执行算法所需要的计算工作量)。一般情况下, 一般情况下, 算法所执行的基本运算次数算法所执行的基本运算次数是问题规模是问题规模 n n的某个函数的某个函数 f(n) f(n) ,记作: ,记作: T(n) = O(f(n)) T(n) = O(f(n)) 它表示随问题规模它表示随问题规模 n n的增大,算法执的增大,算法执行时间的增长率和行时间的增长率和 f(n) f(n) 的增长率相同。的增长率相同。 2 2。。算法的空间复杂度描述算法的存算法的空间复杂度描述算法的存储空间需求(执行这个算法所需要的内存储空间需求(执行这个算法所需要的内存空间) 空间) 。。运行完一个程序所需要的内存大小是问题运行完一个程序所需要的内存大小是问题规模规模 n n的某个函数的某个函数 g(n) g(n) ,记作: ,记作: S(n) = O(g(n)) S(n) = O(g(n)) 它表示随着问题规模它表示随着问题规模 n n的增大,算法的增大,算法运行所需存储空间的增长率运行所需存储空间的增长率 S(n) S(n) 与与 g(n) g(n) 的增的增长率相同。长率相同。 数据结构基础数据结构基础数据: 数据: 数据是信息的载体,是描述客数据是信息的载体,是描述客观事物的数、字符,以及所有能输入到计观事物的数、字符,以及所有能输入到计算机中,被计算机程序识别和处理的符号算机中,被计算机程序识别和处理的符号的集合。数据包括数值性数据和非数值性的集合。数据包括数值性数据和非数值性数据。数据。数据元素(也称为元素、接点、顶点、数据元素(也称为元素、接点、顶点、记录): 记录): 数据元素是数据的基本单位。一数据元素是数据的基本单位。一个数据元素可以由若干个数据项组成。个数据元素可以由若干个数据项组成。数据项: 数据项: 数据项是具有独立含义的最数据项是具有独立含义的最小标识单位。小标识单位。数据对象: 数据对象: 数据的子集,是具有相同数据的子集,是具有相同性质的数据成员(数据元素)的集合。性质的数据成员(数据元素)的集合。数据结构的定义:数据结构是指相关数据结构的定义:数据结构是指相关有关联的数据元素的集合(数据之间的相有关联的数据元素的集合(数据之间的相互关系),一个数据结构应包含以下两方互关系),一个数据结构应包含以下两方面的信息: 面的信息: 1 1、表示数据元素的信息、表示数据元素的信息 2 2、表示各数据元素之间的前后件关系、表示各数据元素之间的前后件关系爷爷父亲儿子数据的逻辑结构:用来描述数据元素数据的逻辑结构:用来描述数据元素之间的逻辑关系。之间的逻辑关系。数据的存储结构: 数据的存储结构: 用来描述数据元素用来描述数据元素及数据元素之间的关系在存储器中的存储及数据元素之间的关系在存储器中的存储形式。形式。数据的运算: 数据的运算: 即对数据元素施加的操即对数据元素施加的操作。作。数据结构的图形表示: 数据结构的图形表示: 用图形来直观用图形来直观地表示数据及其之间的关系。地表示数据及其之间的关系。数据结构研究的主要包括数据存储存储结构、数据逻辑结构和数据元素之间的三方面联系。