E: ZM\Zmdoc\datastrulclass02>listdemo name stun age score zuofu100001801000 List length now is 1. name stun age score bobin100002801000 zuofu100001801000 List length now is 2 总结 抽象数据类型定义 象数据类型实现方法: C语言实 C语言实现 数据结构教程第三课算法及算法设计要求
E:\ZM\Zmdoc\datastru\class02>listdemo name stuno age score zmofun 100001 80 1000 List length now is 1. name stuno age score bobjin 100002 80 1000 zmofun 100001 80 1000 List length now is 2. 三、总结 抽象数据类型定义； 抽象数据类型实现方法：一、类 C 语言实现 二、C 语言实现 数据结构教程 第三课 算法及算法设计要求
本课主题算法及算法设计要求 教学月的:掌握算法的定义及特性,算法设计的要求 教学重点:算法的特性,算法设计要求 教学难点:算法设计的要求 授课内铧: 算法的定义及特性 ispass(int num[4[4) for(i=0i<4|++) for( j=0; j<4; j++) f(num[[]=*4+j+1)/*一条指令,多个*作* return 0; return 1. y/*上面是一个类似华容道游戏中判断游戏是否结束的算法* 算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或多个*作:此外,一个算法还具有下列五个重要特性: 2、算法的五个特性 有劳性个算法必须总是(对任何合法的输入值)在执行有穷步之后结束,且每一步都可在有 穷时间内完成 确定性算法中每一条指令必须有确切的含义,读者理解时不会产生二义性。有任何条件下,算 法只有唯一的一条执行路径,即对于相同的输入只能得出相同的输出 算法是能行的,即算法中描述的*作都是可以通过己经实现的基本运算执行有限次来 可行性 实现的 一个算法有零个或多个的输入,这些输入取自于某个特定的对象的集合。 个算法有一个或多个的输出。这些输出是同输入有着某些特定关系的量
本课主题： 算法及算法设计要求 教学目的： 掌握算法的定义及特性，算法设计的要求 教学重点： 算法的特性，算法设计要求 教学难点： 算法设计的要求 授课内容： 一、算法的定义及特性 1、定义： ispass(int num[4][4]) { int i,j; for(i=0;i<4;i++) for(j=0;j<4;j++) if(num[i][j]!=i*4+j+1)/*一条指令，多个*作*/ return 0; return 1; }/*上面是一个类似华容道游戏中判断游戏是否结束的算法*/ 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个*作；此外，一个算法还具有下列五个重要特性： 2、算法的五个特性： 有穷性 一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有 穷时间内完成； 确定性 算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。有任何条件下，算 法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。 可行性 一个算法是能行的，即算法中描述的*作都是可以通过已经实现的基本运算执行有限次来 实现的。 输入 一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集合。 输出 一个算法有一个或多个的输出。这些输出是同输入有着某些特定关系的量
U*only a joke, do nothing. 有穷性 { printf("请稍等…您将知道世界的未日."); while(1) haha float average int *a, int num) sum+=*(a++) 确定性 return sum/num { int score[10]={1,234,56,789,0} rinf( %f average(soore, 10) 可行性 输入 getsum(int num) 输出 }/*无输出的算法没有任何意义 二、算法设计的要求 1、正确性 算法正确性的四个层次 x( int a, int b, int c) if (a>b) 程序不含语法错误 Kif(a>c)return c else return a 程序对于几组输入数据能够得 max(int a, int b, nt c)
例： 有穷性 haha() {/*only a joke,do nothing.*/ } main() {printf("请稍等...您将知道世界的未日..."); while(1) haha(); } 确定性 float average(int *a,int num) {int i;long sum=0; for(i=0;i<num;i++) sum+=*(a++); return sum/num; } main() {int score[10]={1,2,3,4,5,6,7,8,9,0}; printf("%f",average(score,10); } 可行性 输入 输出 getsum(int num) { int i,sum=0; for(i=1;i<=num;i++) sum+=i; } /*无输出的算法没有任何意义， 二、算法设计的要求 1、正确性 算法正确性的四个层次 程序不含语法错误。 max(int a,int b,int c) { if (a>b) {if(a>c) return c; else return a; } } 程序对于几组输入数据能够得 max(int a,int b,int c)
出满足规格说明要求的结果 if (a>b) lif(a>c)return a }/*8,6,7*//*9,3,2* lax(int a, int b, int c) if (a>b) 程序对于精心选择的典型苛刻 而带有刁难性的几组输入数据 else return cr 够得出满足规格说明要求的 Rif(b>c)retum b: 程序对于一切合法的输入数据 都能产生满足规格说明要求的 2、可读性 3、健壮性 4、效率与低存储量需求 效率指的是算法执行时间。对于解决同一问题的多个算法,执行时间短的算法效率高 存储量需求指算法执行过程中所需要的最大存储空间 两者都与问题的规模有关 算法一 算法二 max(int a, int b, int c) max(int a[3D) [if (a>b) Mint c, int i; else return cr for(=1<3;++) 在三个整数中求最大者 if (a[]>c)c=a[i] retum C: else return C: /*需要两个额外的存储空间,两次比 /*无需额外存储空间,只 较,至少一次赋值* 需两次比较*/
出满足规格说明要求的结果。 { if (a>b) {if(a>c) return a; else return c; } } /* 8,6,7 */ /* 9,3,2 */ 程序对于精心选择的典型、苛刻 而带有刁难性的几组输入数据 能够得出满足规格说明要求的 结果。 max(int a,int b,int c) { if (a>b) {if(a>c) return a; else return c; } else {if(b>c) return b; else return c; } } 程序对于一切合法的输入数据 都能产生满足规格说明要求的 结果。 2、可读性 3、健壮性 4、效率与低存储量需求 效率指的是算法执行时间。对于解决同一问题的多个算法，执行时间短的算法效率高。 存储量需求指算法执行过程中所需要的最大存储空间。 两者都与问题的规模有关。 算法一 算法二 在三个整数中求最大者 max(int a,int b,int c) {if (a>b) {if(a>c) return a; else return c; } else {if(b>c) return b; else return c; }/*无需额外存储空间，只 需两次比较*/ max(int a[3]) {int c,int i; c=a[0]; for(i=1;i<3;i++) if (a[i]>c) c=a[i]; return c; } /*需要两个额外的存储空间，两次比 较，至少一次赋值*/
/*共需5个整型数空间 求100个整数中最大者同上的算法难写,难读 for(i=1;i<100;i++) if (a[>c)c=a[i] return c: /*共需102个整型数空间 总结 1、算法的特性 2、算法设计要求:正确性、可读性、健壮性、效率与低存储量需求 数据结构教程第四课算法效率的度量和存储空间需求 本课主题算法效率的度量和存储空间需求 教学目的掌握算法的渐近时间复杂度和空间复杂度的意义与作用 教学重点:渐近时间复杂度的意义与作用及计算方法 教学难点:渐近时间复杂度的意义 授课内容 算法效率的度量 算法执行的时间是算法优劣和问题规模的函数。评价一个算法的优劣,可以在相同的规模下,考察算法执行时间的长短来进行判断。而一个程序 的执行时间通常有两种方法: 1、事后统计的方法。 缺点:不利于较大范围内的算法比较。(异地,异时,异境) 2、事前分析估算的方法 程序在计算机上运行所需时间的影响因素 算法本身选用的策略
/*共需 5 个整型数空间*/ 求 100 个整数中最大者 同上的算法难写，难读 max(int a[100]) {int c,int i; c=a[0]; for(i=1;i<100;i++) if (a[i]>c) c=a[i]; return c; } /*共需 102 个整型数空间*/ 三、总结 1、算法的特性 2、算法设计要求：正确性、可读性、健壮性、效率与低存储量需求。 数据结构教程 第四课 算法效率的度量和存储空间需求 本课主题： 算法效率的度量和存储空间需求 教学目的： 掌握算法的渐近时间复杂度和空间复杂度的意义与作用 教学重点： 渐近时间复杂度的意义与作用及计算方法 教学难点： 渐近时间复杂度的意义 授课内容： 一、算法效率的度量 算法执行的时间是算法优劣和问题规模的函数。评价一个算法的优劣，可以在相同的规模下，考察算法执行时间的长短来进行判断。而一个程序 的执行时间通常有两种方法： 1、事后统计的方法。 缺点：不利于较大范围内的算法比较。（异地，异时，异境） 2、事前分析估算的方法。 程序在计算机上运行所需时间的影响因素 算法本身选用的策略