软件技术基础实验指导书1.doc

1 软件技术基础实验指导书 2014 年9月1日 2 目录实验一斐波那契数列的实现算法及分析………………………… 3 实验二顺序表的实现与应用……………………………………… 5 实验三链表的实现和应用………………………………………… 7 实验四栈的实现和应用…………………………………………… 9 实验五队列………………………………………………………… 11 实验六二叉树的创建和遍历……………………………………… 12 实验七图…………………………………………………………… 15 实验八哈夫曼树及哈夫曼编码…………………………………… 16 实验九查找算法的实现…………………………………………… 19 实验十内部排序算法的实现……………………………………… 26 实验十一迷宫问题…………………………………………………… 29 实验十二 B+ 树程序设计……………………………………………… 30 实验十三四叉树程序设计…………………………………………… 31 实验十四修路方案问题……………………………………………… 32 3 实验一斐波那契数列的实现算法及分析实验目的: 1. 掌握分别用递归和非递归方法计算斐波那契( i )数列。 2. 掌握算法性能测试的方法,并能进行算法分析和比较。实验环境(硬/ 软件要求): Windows 2000, VisualC++ 实验内容: 二阶 i 数列的定义如下: F0=1 , F1=1, F2=2,F3=3,F4=5, 。。。。, Fi=F ( i-1 ) =F(i-2) ( i>=1 ). 试用递归法和非递归法两种方法写出计算 Fn 的函数。实验要求: 1. 完成计算 Fn 的递归函数 Fib-rec. 2. 完成计算 Fn 的非递归数列 Fib-ite. n=10,15,20,25,30,35,40,45 时测试以上两种算法执行的时间, 并把测试结果填写在附表 1-1 中。附表 1-1 测试表 N 函数 10 15 20 25 30 35 40 45 89 987 10946 121393 1346269 14930352 165580141 183631190 3 Fib-re c 运行时间 Fib-it e 运行时间注:表格中填写的是测试时间,单位μ m. 4. 试解释两种算法在执行时间上的不同,并对两种算法进行算法分析。【C 语言源程序】#include <> #include <> L ong Fib-rec(int n) { if( n==0||n==1 ) return(1) ; else return(Fib-rec(n-1) + Fib-rec(n-2) ); } long Fib-ite(int n) { long fib1,fib2,fib ; int i; fib1=1 ; fib2=1 ; for (i=3 ; i<=n,i ++) {fib=fib1+fib2 ;4 fib1=fib2 ; fib2=fib ; } return fib ; }v oid main (){ clock-t us1, us2 ; int n; printf( “请输入 n: \n”); scanf( “%d,&n) ; us1=clock( ); printf( “递归函数计算结果: %1d\n ”,Fib-rec(n) ); us2=clock( ); printf( “递归函数执行时间%1d 毫秒\n”, us2-us1) ; us1=clock( ); printf( “非递归函数计算结果: %1d\n ”,Fib-ite(n) ); us2=clock( ); printf( 非递归函数执行时间%1d 毫秒\n”, us2-us1) ; } 5 实验二顺序表的实现与应用实验目的: 1. 掌握线性表的概念。 2. 熟练掌握线性表的顺序存储结构。 3. 熟练掌握线性表在顺序存储结构上的运算。 4. 了解测试的思想。实验环境(硬/ 软件要求): Windows 2000,Visual C++ 实验内容: 1. 编写算法实现顺序表中元素的逆置。要求按用户输入的数据建立一个顺序表。在逆置的过程中使用最少的辅助存储单元。测试数据为: 10,9,8,7,6,5,4,3,2,1 。 2. 编写算法, 在非递减有序的顺序表中, 插入一个给定的元素, 插入后该顺序表仍然递增有序。有序表中的数据为: 12,16,24,33,45,66,68,89 ;需要进行测试的插入数据分别是: 9,13,25,33,88,91 实验要求: 1. 完成顺序表的结构定义。 2. 完成顺序表的就地逆置函数和主函数。 3. 完成在非递减有序表中的插入数据的函数和主函数。【