算法设计与分析实验指导书(2011)

算法设计与分析实验指导书实验一C/C++环境及递归算法（4学时）一、实验目的与要求1、熟悉C/C++语言的集成开发环境；2、通过本实验加深对递归过程的理解二、实验内容：掌握递归算法的概念和基本思想，分析并掌握排列问题的递归算法和Hanoi塔问题的递归算法。三、实验题1、设计一个递归算法生成n个元素{r1,r2,…,rn}的全排列。任意输入一串整数或字符，输出结果能够用递归方法实现整数或字符的全排列。2、设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,…,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。四、实验步骤1．理解算法思想和问题要求；2．编程实现题目要求；3．上机输入和调试自己所编的程序；4．验证分析实验结果；5．整理出实验报告。实验提示1、#includeiostream.hinlinevoidswap(int&a,int&b){inttemp=a;a=b;b=temp;}voidperm(intlist[],intk,intm){if(k==m){for(inti=0;i=m;i++)coutlist[i];coutendl;}elsefor(inti=k;i=m;i++){swap(list[k],list[i]);perm(list,k+1,m);swap(list[k],list[i]);}}voidmain(){intlist[3]={1,2,3};perm(list,0,2);}2、voidhanoi(intn,inta,intb,intc){if(n0){hanoi(n-1,a,c,b);move(a,b);hanoi(n-1,c,b,a);}}实验二分治算法（4学时）一、实验目的与要求1、熟悉二分搜索算法和快速排序算法；2、初步掌握分治算法；二、实验题1、设a[0:n-1]是一个已排好序的数组。请改写二分搜索算法，使得当搜索元素x不在数组中时，返回小于x的最大元素的位置i和大于x的最小元素位置j。当搜索元素在数组中时，I和j相同，均为x在数组中的位置。设有n个不同的整数排好序后存放于t[0:n-1]中，若存在一个下标i，0≤i＜n，使得t[i]=i，设计一个有效的算法找到这个下标。要求算法在最坏的情况下的计算时间为O（logn）。2、在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较少。三、实验提示1、用I，j做参数，且采用传递引用或指针的形式带回值。boolBinarySearch(inta[],intn,intx,int&i,int&j){intleft=0;intright=n-1;while(leftright){intmid=(left+right)/2;if(x==a[mid]){i=j=mid;returntrue;}if(xa[mid])left=mid+1;elseright=mid-1;}i=right;j=left;returnfalse;}intSearchTag(inta[],intn,intx){intleft=0;intright=n-1;while(leftright){intmid=(left+right)/2;if(x==a[mid])returnmid;if(xa[mid])right=mid-1;elseleft=mid+1;}return-1;}2、templateclassTypevoidQuickSort(Typea[],intp,intr){if(pr){intq=Partition(a,p,r);QuickSort(a,p,q-1);//对左半段排序QuickSort(a,q+1,r);//对右半段排序}}templateclassTypeintPartition(Typea[],intp,intr){inti=p,j=r+1;Typex=a[p];//将x的元素交换到左边区域//将x的元素交换到右边区域while(true){while(a[++i]x);while(a[--j]x);if(i=j)break;Swap(a[i],a[j]);}a[p]=a[j];a[j]=x;returnj;}实验三归并排序的分治策略设计（4学时）[实验目的]１.熟悉二分检索问题的线性结构表示和二分检索树表示;２.熟悉不同存储表示下求解二分检索问题的递归算法设计;３.通过实例转换,掌握将递归算法转换成迭代算法的方法;４.掌握应用递归或迭代程序设计实现分治法求解问题的抽象控制策略.[预习要求]１.认真阅读算法设计教材和数据结构教材内容,熟悉不同存储表示下求解二分检索问题的原理或方法;２.针对线性结构表示和二分检索树表示设计递归算法;３.参考教材和课堂教学内容,根据将递归算法转换成迭代算法的一般步骤将二分检索递归算法转换成相应的迭代算法.[算法或程序设计参考]线性结构intdata[10]={/*10个互异的、无序的原始整数*/};typedefstruct{ints[100];inttop;}STACK;intPartition(int*data,intlow,inthigh)功能:将data[low,high]进行快速分类划分,返回枢轴记录关键字的位置索引.intQSort1(int*data,intlow,inthigh)功能:将data[low,high]进行快速分类的递归算法.intQSort2(int*data,intlow,inthigh)功能:将data[low,high]进行快速分类的迭代算法.intBSearch1(int*data,intkey)功能:在data数组中检索key的二分检索递归算法,成功时返回位置索引,否则返回-1.intBSearch2(int*data,intkey)功能:在data数组中检索key的二分检索迭代算法,成功时返回位置索引,否则返回-1.树结构typedefstructNODE{intkey;structNODE*lch,*rch;}TNODE,*BT;typedefstructParameters{BT*t;intkey;BTf;BT*p}PARA;typedefstruct{PARAs[100];inttop;}STACK;intInsertBT(BT*t,intkey)功能:在二分检索树t中插入关键字为key的元素,成功时返回1,否则返回0.intTSearch1(BT*t,intkey,BTf,BT*p)功能:用递归算法在二分检索树t中查找关键字为key的元素,成功时返回1,p指向该元素节点,否则p指向查找路径上最后一个节点并返回0,f指向t的双亲,其初始调用值为NULL.intTSearch2(BT*t,intkey,BTf,BT*p)功能:用迭代算法在二分检索树t中查找关键字为key的元素,成功时返回1,p指向该元素节点,否则p指向查找路径上最后一个节点并返回0,f指向t的双亲,其初始调用值为NULL.[实验步骤]1.调试线性结构表示下的快速分类与二分检索递归程序,直至正确为止;2.调试线性结构表示下的快速分类与二分检索迭代程序,直至正确为止;3.待各功能子程序调试完毕,去掉测试程序,将程序整理成功能模块存盘备用.[实验报告要求]1.阐述实验目的和实验内容;2.提交实验程序的功能模块;3.阐述将递归算法改写成迭代算法的一般方法;4.用类C语言阐述分治法递归与迭代实现抽象控制策略.[思考与练习]1.怎样优化由递归程序改写的迭代程序?2.设计二分检索树的构造与检索递归程序,并将其改写成相应的迭代算法。实验四哈夫曼编码的贪心算法设计（4学时）[实验目的]１.根据算法设计需要,掌握哈夫曼编码的二叉树结构表示方法;２.编程实现哈夫曼编译码器;３.掌握贪心算法的一般设计方法。[预习要求]1.认真阅读数据结构教材和算法设计教材内容,熟悉哈夫曼编码的原理;2.设计和编制哈夫曼编译码器。[参考数据类型或变量]typedefElemTypechar；typedefstructnode{intw;intflag;ElemTypec;structnode*plink,*llink,*rlink;charcode[m];}Node;Node*num[n],*root;[参考子程序接口与功能描述]voidSetTree(NODE*root)功能:从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树voidEnCode(Node*p)功能:利用已建好的哈夫曼树，对输入的正文进行编码voidDeCode(void)功能:利用已建好的哈夫曼树，将输入的代码进行译码[实验步骤]1.设计SetTree的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止;2.设计EnCode的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止;3.设计DeCode的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止;4.将你的程序整理成功能模块存盘备用。[实验报告要求]1.阐述实验目的和实验内容;2.提交实验程序的功能模块;3.记录最终测试数据和测试结果。[思考题]1.试证明哈夫曼问题具有贪心选择性质；试证明哈夫曼问题具有最优子结构性质。实验五Kruskal算法的设计（4学时）[实验目的]１.根据算法设计需要,掌握连通网的灵活表示方法;２.掌握最小生成树的Kruskal算法;３.基本掌握贪心算法的一般设计方法;４.进一步掌握集合的表示与操作算法的应用.[预习要求]１.认真阅读算法设计教材和数据结构教材内容,熟习连通网的不同表示方法和最小生成树算法;２.设计Kruskal算法实验程序.[参考数据类型或变量]typedefNodeNumberint;/*节点编号*/typedefCostTypeint;/*成本值类型*/typedefElemTypeNodeNumber/*实型或任意其它元素类型*/typedefstruct{intElemType;inttag;}NODE;typedefstruct{CostTypecost;NodeNumbernode1,node2;}EDGE;NODEset[]={{1,-1},…,{n,-1}};/*节点集,n为连通网的节点数*/EDGEes[]={{valuesofe1},…,{valuesofem}};/*边集,m为连通网的边数*/EDGEst[n-1];/*最小生成树的边集*/[参考子程序接口与功能描述]intFind(NODE*set,ElemTypeelem)功能:在数组set中顺序查找元素elem,如果不成功,返回-1;否则,使用带压缩规则的查找算法,返回所在子集的根节点索引.intUnion(NODE*set,ElemTypeelem1,ElemTypeelem2)功能:应用Find算法首先找到elem1和elem2所在的子集,然后应用带加权规则的并运算算法合并两个子集.不成功时,返回-1;否则,返回并集的根节点索引.voidSort(EDGE*es,intn)功能:用任意分类算法将连通图的边集按成本值的非降次序分类.voidKruskal(EDGE*es,intm,NODE*set,intn,EDGE*st)功能:对有n个节点,m条边的连通网,应用Kruskal算法生成最小生成树,最小生成树的边存储在数组st中.voidOutput(EDGE*st,intn)功能:输出最小生成树的各条边.[实验步骤]1.设计测试问题,修改并调试程序,输出最小生成树的各条边,直至正确为止;2.待各功能子程序调试完毕,去掉测试程序,将你的程序整理成功能模块存盘备用.[实验报告要求]1.阐述实验目的和实验内容;2.阐述Kruskal算法的原理方法;3.提交实验程序的功能模块;4.提供测试数据和相应的最小生成树.[思