数据结构C语言版绪论要点解析.ppt

* * * 计算机科技的两大支柱·1、数据结构2、算法 ·程序＝数据结构＋算法 结点（数据元素）：由多个数据项构成，每个数据项表示该结点的某种性质。 * 大O 表示法： ·定义；如果存在着正的常数c 和自然数n0，当n >= n0时；有f (n) <= Cg(n) 成立，则称f( n ) = O（g( n )) 。在算法分析中，如果一个算法的时间复杂性是O(g( n ))，读作g( n ) “级”的或“阶”的。如：线性阶的、平方阶的、立方阶的…… * 本书采用以下格式定义抽象数据类型 抽象数据类型的定义： ADT抽象数据类型名{ 数据对象：<数据对象的定义> 数据关系：<数据逻辑关系的定义> 基本操作：<基本操作的定义> }ADT抽象数据类型名 基本操作的定义格式为：基本操作名（参数表）初始条件：<初始条件描述> 操作结果：<操作结果描述> 1.2 基本概念和术语 抽象数据类型三元组的定义： ADT Triplet{ 数据对象：D={e1,e2,e3|e1,e2,e3?ElemSet} 数据关系：R1={<e1,e2>,<e2,e3>} 基本操作： InitTriplet(&T,v1,v2,v3) 操作结果：构造了三元组T，元素e1,e2和e3分别赋以参数v1,v2和v3的值。 } ADT Triplet 1.2 基本概念和术语 ADT Triplet{ 数据对象：D={e1,e2,e3|e1,e2,e3?ElemSet} 数据关系：R1={<e1,e2>,<e2,e3>} 基本操作： Get(T，i，&e) 初始条件：三元组T已存在，1?i?3 操作结果：用e返回T的第i元的值。 } ADT Triplet 1.2 基本概念和术语 抽象数据类型可通过固有数据类型来表示和实现，即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。 由于本书在高级程序设计语言的虚拟层次上讨论抽象数据类型的表示和实现，并且讨论的数据结构及其算法主要是面向读者，故采用介于伪码和C语言之间的类C语言作为描述工具，有时也用伪码描述一些只含抽象操作的抽象算法。 抽象数据类型的实现包括数据结构的实现和操作的实现，因此不仅要借用高级语言中的数据类型来描述它的存储结构，也要利用高级语言中已经实现的固有数据类型的操作来实现抽象数据类型的操作。 1.3 抽象数据类型的表示和实现 本书采用的类C语言精选了C语言的一个核心子集，同时作了若干扩充，增强了语言的描述功能。以下对其作简要说明。 （1）预定义常量和类型 //函数结果状态代码 #define TRUE 1 #define FLASE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 // Status是函数的类型，其值是函数结果状态代码如OK等 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）结束语句