1,2)基本概念和术语 例:复数: Complex=(CR 课题小组: group=(PR) 逻辑结构:关系 存储结构:表示(映象) (在高级语言层次上 顺序位置相邻(一维数组) 链式:指针(指针或数组) 计算设计:取决于选定的逻辑结构 算法实现:依赖于采用的存储结构
1.2 基本概念和术语 例: 复数: Complex=(C,R) 课题小组: Group=(P,R) 逻辑结构: 关系 存储结构: 表示(映象) (在高级语言层次上) 顺序: 位置相邻(一维数组) 链式: 指针(指针或数组) 计算设计: 取决于选定的逻辑结构 算法实现: 依赖于采用的存储结构
1,2)基本概念和术语 数据类型刻画了操作对象的特性 规定值的集合和一组操作 整数的范围:(16位)-32768~32767 操作:+ DIV、% 抽象数据类型(ADT):数学模型和一组操作。 “抽象”的定义在于数据类型的数学抽象特性) 分类∵原子类型:100整数。 固定聚合类型:复数(C1,C2) 可变聚合类型:有序整数类型。 抽象数据类型的形式定义∵ ADT=(D, S, P 其中D是数据对象;S是D上的关系集;P是对D的基本操作集 (用类C作为描述工具,来讨论数据结构及其算法
1.2 基本概念和术语 • 数据类型: 刻画了操作对象的特性 规定: 值的集合和一组操作 (整数的范围: (16位) -32768～32767 操作：+、-、 * 、DIV、%） 抽象数据类型（ADT）：数学模型和一组操作。 （“抽象”的定义在于数据类型的数学抽象特性） 分类：原子类型：100整数。 固定聚合类型：复数（C1，C2）。 可变聚合类型：有序整数类型。 抽象数据类型的形式定义： ADT=（D，S，P） 其中：D是数据对象；S是D上的关系集；P是对D的基本操作集。 （用类C作为描述工具，来讨论数据结构及其算法）
1.3算法和算法分析 算法;解题步骤的描述,指令的有限序列 算法的特性:有穷性、确定性、可行性、输入、输出。 算法评价标准佳可读性、健壮性效率(时间、空间) (前提:正确性 无语法错误 (2)随意数据 3)刻意数据 (4)切合法数据) 算法效率的度量 1)事后统计法 2)事前估算法(最大语句频度
1.3 算法和算法分析 • 算法：解题步骤的描述，指令的有限序列。 • 算法的特性：有穷性、确定性、可行性、输入、输出。 • 算法评价标准：可读性、健壮性、效率（时间、空间） （前提：正确性： （1）无语法错误 （2）随意数据 （3）刻意数据 （4）一切合法数据） • 算法效率的度量： （1）事后统计法 （2）事前估算法（最大语句频度）
1.3算法和算法分析 时间复杂度:T(n)=0(f(n) 例:(,=n n+ tor + n米(n {c[1j=0 n'n for(k-1: k<en, k++) n(n+1) c[0]+=alijlk]*b[kIG tnn (n)=2n3+3n2+2n+1=O(n (渐近时间复杂度、平均时间复杂度、最坏情况下的时间复杂度 空间复杂度S(n)=O((m)
1.3 算法和算法分析 • 时间复杂度：T（n）=O（f（n）） 例：for ( i=1; i<=n; i++) n+1 for ( j=1; j<=n; j++) n*(n+1) { c[i][j]=0; n*n for (k=1; k<=n; k++) n*n*(n+1) c[i][j]+=a[i][k]*b[k][j]; n*n*n } T(n)=2n3+3n2+2n+1=O( n3 ) （渐近时间复杂度、平均时间复杂度、最坏情况下的时间复杂度） • 空间复杂度：S（n）=O（f（n））
练习题 下列是几种用二元组表示的数据结构,画出它们分别对应的逻辑图形表 示,并指出它们分别属于何种结构 (1)A=(K,R)其中:K=a,b,,d,e;R= r=a, b>, b, c>, < c, d>,sd, e> (2)C(K,R 其中:K={1234R= r={12),(1,3),(2,4)(3,4)} 2.指出下列各算法的时间复杂度 1)=1 while (i = i3 ( 2) fact(int n) tif (n<=1) return(1); else return(n fact(n-1))
练习题 1. 下列是几种用二元组表示的数据结构，画出它们分别对应的逻辑图形表 示，并指出它们分别属于何种结构。 （1） A=（K，R） 其中：K={a，b，c，d，e}； R={r}； r={<a,b>,<b,c>,<c,d>,<d,e>} （2） C=( K,R ) 其中: K={1,2,3,4}; R={r}; r={(1,2),(1,3),(2,4),(3,4)} 2. 指出下列各算法的时间复杂度。 （1） i=1; while (i<=n) i=i*3; （2） fact(int n) { if (n<=1) return(1); else return(n*fact(n-1)); }