《数据结构》课件第1章.ppt

2.分别编写两个程序，要求：(1)编程1：分步实现上述功能。(2)编程2：以最高效率实现上述功能。3.从可读性和时间复杂度上分别对两个算法进行性能分析。【算法分析】1.分步实现四个功能需要四个循环；2.为提高效率，可在一个循环中实现输入、求最大值、求和的功能，第四个功能必须建立在求出平均值的基础上，要另外使用一个循环来完成。【程序清单】算法一：#includestdio.h#defineM10 /*如要修改数组大小，不用修改程序其它部分*/main(){ inta[M],i,max,min,sum,count=0; floatavg; if(M=0)return(0); /*防止出现求平均值时除数为0的情况，保证算法健壮*/ for(i=0;iM;i++) /*输入元素值*/ { scanf(%d,a[i]); } max=min=a[0]; for(i=1;iM;i++) /*找出数组元素的最大值和最小值*/ { if(maxa[i])max=a[i]; if(mina[i])min=a[i]; } sum=0; for(i=0;iM;i++) /*求和*/ { sum+=a[i]; } avg=(float)sum/M; /*求平均*/ printf(max=%d,min=%d,average=%f\n,max,min,avg); printf(dataaverage:\n); for(i=0;iM;i++) /*找出所有小于平均值的元素并计数*/ if(a[i]avg){count++; printf(No.%d=%d\n,i,a[i]); } printf(%ddataaverage\n,count);}算法二：#includestdio.h#defineM10main(){ inta[M],i,max,min,sum,count=0; floatavg; if(M=0)return(0); /*防止出现求平均值时除数为0的情况*/ scanf(%d,a[0]); max=min=sum=a[0]; for(i=1;iM;i++) /*边输入边求和，并进行比较，求最大值和最小值*/{ scanf(%d,a[i]); sum+=a[i]; if(maxa[i])max=a[i]; if(mina[i])min=a[i]; } avg=(float)sum/M; printf(max=%d,min=%d,average=%f\n,max,min,avg); printf(dataaverage:\n); for(i=0;iM;i++) if(a[i]avg){count++; printf(No.%d=%d\n,i,a[i]); } printf(%ddataaverage\n,count);}2.可读性算法主要是为了人的阅读与交流，其次才是机器执行。即使算法已转变成机器可执行的程序，也需考虑人能较好地阅读理解。可读性好有助于人对算法的理解，这既有助于对算法中隐藏错误的排除，也有助于算法的交流和移植。3.健壮性算法应具有很强的容错能力，即算法能对非法数据的输入进行检查和处理，不会因非法数据的输入而导致异常中断或死机等现象。4.运行时间运行时间是指算法在计算机上运行所花费的时间，它等于算法中每条语句执行时间的总和。对于同一个问题如果有多个算法可供选择，应尽可能选择执行时间短的算法，一般来说，执行时间越短则算法的效率越高、性能越好。5.占用空间占用空间是指算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入、输出数据所占用的存储空间和算法运行过程中临时占用的存储空间。算法占用的存储空间是指算法执行过程中所需要的最大存储空间。对于一个问题如果有多个算法可供选择，应尽可能选择存储量需求低的算法。实际上，算法的时间效率和空间效率经常是一对矛盾体，相互抵触，有时增加辅助的存储空间可以加快算法的运行速度，即用空间换取时间；有时因为内存空间不够，必须压缩辅助的存储空间，从而降低了算法的运行速度，即用时间换取空间。通常把算法在运行过程中临时占用的存储空间的大小叫做算法的空间复