数据结构63974.ppt

“数据结构”这门学科形成和发展的背景: 例2 人机对奕问题 例：整数的数据对象是{…-3，-2，-1，0，1，2，3，…} 英文字符类型的数据对象是{A，B，C，D，E，F，…} 结构（Structure):是数据之间彼此存在的相互关系。 数据结构(Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合。 这种关系体现在三个方面： 1、数据之间的逻辑关系 2、数据在计算机内的存储方式 3、数据在计算机内的运算 数据的结构主要指逻辑结构和物理结构 例：5个结点的顺序表示 D={d1,d2,d3,d4,d5} S={d1,d2,d2,d3,d3,d4,d4,d5} d1—d5为元素（结点），di,dj表示结点di与dj的关系. 例：5个结点的树型表示 D={d1,d2,d3,d4,d5} S={d1,d2,d1,d3,d1,d4,d3,d5} d1—d5为元素（结点），di,dj表示结点di与dj的关系. 算法与程序的区别与联系 ?一个程序不一定满足有穷性。例如，操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。 ?另一方面，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。 ?算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。 ?一个算法若用程序设计语言来描述，则它就是一个程序。 2、 算法设计的要求 时间复杂度的渐进表示法 大O表示法 加法规则 针对并列程序段T(n, m) = T1 (n) + T2 (m)= O(max (f (n), g (m))) 乘法规则 针对嵌套程序段  T (n, m) = T1 (n) * T2 (m)= O(f (n)*g (m))记号“O”是数学符号，其严格的数学定义是：若T(n)和f (n)是定义在正整数集合上的两个函数，当存在两个正的常数c和n0，使得对所有的n≥n0，都有T(n)≤cf(n)成立，则T(n)=O(f(n))。 复习提纲 练习 本书采用的类C语言精选了C语言的一个核心子集，同时作了若干扩充，增强了语言的描述功能。以下对其作简要说明。 （1）预定义常量和类型 //函数结果状态代码 #define TRUE 1#define FLASE 0 #define OK1#define ERROR 0 #define INFEASIBLE -1#define OVERFLOW-2 // Status是函数的类型，其值是函数结果状态代码 Typedef int Status; 1.3 抽象数据类型的表示和实现 （2）数据结构的表示用类型定义（typedef）描述。数据元素类型约定为Elemtype，由用户在使用该数据类型时定义。 （3）基本操作的算法都用以下形式的函数描述： 函数类型 函数名（函数参数表）{ //算法说明 语句序列 }//函数名 1.3 抽象数据类型的表示和实现（4）赋值语句有 简单赋值 变量名=表达式； 串值赋值 变量名1=变量名2=……=表达式 成组赋值 （变量名1，……）=（表达式1，……） 交换赋值 变量名变量名 条件赋值 变量名=条件表达式？表达式T：表达式F 1.3 抽象数据类型的表示和实现 （5）选择语句有 条件语句1 if（表达式）语句； 条件语句2 if（表达式）语句；Else 语句; 开关语句1 switch(表达式 ) {case 值1：语句序列1；break;…Default: 语句序列n+1;} 开关语句2 switch{case 条件1：语句序列1；break;…Default: 语句序列n+1;} 1.3 抽象数据类型的表示和实现 （6）循环语句有 For语句for（赋初值表达式；条件；修改表达式序列）语句； While 语句while（条件）语句； do-while语句do {语句序列;}while（条件）； 1.3 抽象数据类型的表示和实现 （7）结束语句 函数结束语句return 表达式； return； Case结束语句 break; 异常结束语句exit(异常代码) 8）输入和输出语句 输入语句 scanf([格式串]，变量1，变量n)； 输出语句 printf([格式串]，表达式1，表达式2)； 1.3 抽象数据类型的表示和实现 （9）注释 单行注释//文字序列 （10）基本函数有 求最大值max(表达式1，表达式n） 求最小值min(表达式1，表达式n） 求绝对值abs(表达式) 求不足整数值floor（表达式） 判定行结束eoln（文件变量）或eoln 1.3 抽象数据类型的表示和实现 （11）逻