常璐璐-数据结构-第一章.ppt

数据结构常璐璐 计算机科学;数据结构课程地位;无标题;教材内容划分：第一部分：数据结;1.1 数据结构讨论的范畴;1.1 数据结构讨论的范畴尼克;非数值计算的程序设计问题例一:;例二：计算机对弈算法：?模型：;例三：足协的数据库管理算法：?;概括地说： 数据结构是一门讨;1.2 基本概念一、数据与数;一、数据与数据结构所有能被输入;是数据（集合）中的一个“个体”;数据项：是数据结构中讨论的最小;数据对象： 数据的子集。;数据结构：带结构的数据元素的集;又例，在2行3列的二维数组{a;再例，在一维数组 {a1, a;数据的逻辑结构可归结为以下四类;数据结构的形式定义为:数据结构;例1 复数的二元组定义 ;例2 设有数据逻辑结构为: ;数据的存储结构 —— 逻辑结构;数据元素的映象方法：用二进制位;关系的映象方法：（表示?x, ;链式映象以附加信息(指针)表示;在不同的编程环境中，存储结构可;二、数据类型在用高级程序语言编;例如，C 语言中提供的基本数据;三、抽象数据类型 (Abs;例如，抽象数据类型复数的定义：;基本操作： Assign;GetImag( Z, Im;假设:z1和z2是上述定义的复;ADT 有两个重要特征:数据抽;抽象数据类型的描述方法抽象数据;ADT 抽象数据类型名 { ;赋值参数 只为操作提供输入值。;抽象数据类型的表示和实现 ;typedef struct;float GetReal( ;// -----基本操作的实现;1.3 算法和算法的衡量一、算;算法是为了解决某类问题而规定的;1．有穷性 对于任意一组合法;3．可行性 算法中的所有操作;5．有输出 它是一组与“输入”;二、算法设计的原则设计算法时，;1．正确性 首先，算法应;2. 可读性 算法主要是;3．健壮性 当输入的数据非;4.高效率与低存储量需求 通常;三、算法效率的衡量方法和准则通;和算法执行时间相关的因素：1．;算法的时间复杂度算法中包含简单;一个特定算法的“运行工作量”的;假如，随着问题规模 n 的增长;如何估算 算法的时间复杂度;算法 = 控制结构 + 原操作;从算法中选取一种对于所研究的问;推导时间复杂度遵循原则：（1）;算法时间复杂度例题：例1: ;例4for( i=1 ; i;例5i=1;while ( i;1. 熟悉各名词、术语的含义，