数据结构实验8：测试算法的实际执行时间.docx

实验 7：Haffman 树的编码一 、实验目的1．分析任意两个可以实现查找功能的算法的时间复杂度2．分别测试这两个算法的实际运行时间3．学会 C 语言中 time.h 头文件中 clock、CLOCKS_PER_SEC 等变量的用法4． 将算法用 C 语言编写完整程序并上机运行，记录实验过程与数据二、实验仪器：1.硬件：Lenovo 通用 PC 机，2.软件：WINDOWS7，WORD，GCC 编译器三、实验原理：在 time.h 中有几个常用的函数、类型或常量：1. clock()函数这个函数返回从“开启这个程序进程”到“程序中调用 clock()函数”时之间的 CPU 时钟计时单元（clock tick）数，在 MSDN 中称之为挂钟时间（wal-clock） 2．clock_t其中 clock_t 是用来保存时间的数据类型，实际是个长整型数据比如可以定义一个 clock_t 类型的变量 start 记录某个程序的开始3. CLOCKS_PER_SEC在 time.h 文件中，还定义了一个常量 CLOCKS_PER_SEC，它用来表示一秒钟会有多少个时钟计时单元四、实验步骤：1.设定对数组 s[]={4,13,25,27,46,66,79,97}，查找 46 是否存在于序列中。

2．设计顺序查找与二分查找的算法3．根据算法设计函数4．分别测试两个算法所对应的函数使用的实际时间五、数据处理及结论1.主函数设计：《 此处写代码 》2.输出：《 你看到输出结果 》六、思考题：1.时间复杂度能否能精确反应某一算法的实际执行效率？示例代码：#include #include void algorithm(int m){while(m>0){m--;}printf("DONE.\n");} void main(void){int i,n=10,m=10000000;clock_t start,end;//start 和 end 两个变量分别记录函数开始与结束时的 CPU 时钟数double duration;//记录两个程序间经过了多久start=clock();//开始时的时钟数for(i=1;i#include int seachingOne(int s[],int a){int i;s[0]=a;for(i=8;s[i]!=a;i--);return i;}int seachingTwo(int s[],int a){int high,low,mid;low=1;high=8;mid=(low+high)/2;while(s[mid]!=a){if(low>=high) return 0;if(s[mid]a)high=mid-1;mid=(low+high)/2;}return mid;}int seachingTwo2(int s[],int a){int high,low,mid;low=1;high=8;while(high>=low){mid=(low+high)/2;if(s[mid]a)high=mid-1;else return mid;}return 0;}void main(void){//clock_t start,end;time_t start,end;int i,n=10,m=100000,j;double duration;int s[9]={0,4,13,25,27,46,66,79,97};printf("%d \n",seachingOne(s,46));start=time(NULL);printf("start=%d ",start);for(i=0;i