《算法设计与分析案例》由会员分享，可在线阅读，更多相关《算法设计与分析案例（17页珍藏版）》请在金锄头文库上搜索。
1、实验一 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 上，并仍按同样顺序叠
2、置。四、实验步骤1 理解算法思想和问题要求；2 编程实现题目要求；3 上机输入和调试自己所编的程序；4 验证分析实验结果；5 整理出实验报告。实验提示1、#include inline void swap(int &a,int &b)int temp=a;a=b;b=temp;void perm(int list,int k,int m)if(k=m)for(int i=0;i 0)hanoi(n-1, a, c, b);move(a,b);hanoi(n-1, c, b, a);实验二 分治算法（4 学时）一、实验目的与要求1、熟悉二分搜索算法和快速排序算法；2、初步掌握分治算法；二、实验题
3、1、设 a0:n-1是一个已排好序的数组。请改写二分搜索算法，使得当搜索元素 x 不在数组中时，返回小于 x 的最大元素的位置 i 和大于 x 的最小元素位置 j。当搜索元素在数组中时，I 和 j 相同，均为 x 在数组中的位置。设有 n 个不同的整数排好序后存放于 t0:n-1中，若存在一个下标 i，0in，使得 ti=i，设计一个有效的算法找到这个下标。要求算法在最坏的情况下的计算时间为 O（ logn） 。2、在快速排序中，记录的比较和交换是从两端向中间进行的，关键字较大的记录一次就能交换到后面单元，关键字较小的记录一次就能交换到前面单元，记录每次移动的距离较大，因而总的比较和移动次数较
4、少。三、实验提示1、用 I，j 做参数，且采用传递引用或指针的形式带回值。bool BinarySearch(int a,int n,int x,int& i,int& j)int left=0;int right=n-1;while(leftamid)left=mid+1;elseright=mid-1;i=right;j=left;return false;int SearchTag(int a,int n,int x)int left=0; int right=n-1;while(leftamid)right=mid-1;elseleft=mid+1;return -1;2、templa
5、tevoid QuickSort (Type a, int p, int r)if (pint Partition (Type a, int p, int r)int i = p, j = r + 1; Type x=ap;/ 将 x 的元素交换到右边区域while (true) while (a+i x);if (i = j) break; Swap(ai, aj);ap = aj;aj = x;return j;实验三 归并排序的分治策略设计（4 学时）实验目的. 熟悉二分检索问题的线性结构表示和二分检索树表示;. 熟悉不同存储表示下求解二分检索问题的递归算法设计;. 通过实例转换, 掌握
6、将递归算法转换成迭代算法的方法;. 掌握应用递归或迭代程序设计实现分治法求解问题的抽象控制策略.预习要求. 认真阅读算法设计教材和数据结构教材内容, 熟悉不同存储表示下求解二分检索问题的原理或方法;. 针对线性结构表示和二分检索树表示设计递归算法;. 参考教材和课堂教学内容, 根据将递归算法转换成迭代算法的一般步骤将二分检索递归算法转换成相应的迭代算法.算法或程序设计参考线性结构int data10= /* 10 个互异的、无序的原始整数 */ ;typedef struct int s100; int top; STACK;int Partition(int *data, int low,
7、int high)功能: 将 datalow, high进行快速分 类划分, 返回枢轴记录 关键字的位置索引.int QSort1(int *data, int low, int high)功能: 将 datalow, high进行快速分 类的递归算法.int QSort2(int *data, int low, int high)功能: 将 datalow, high进行快速分 类的迭代算法.int BSearch1(int *data, int key)功能: 在 data 数组中检索 key 的二分检索递归算法, 成功时返回位置索引, 否则返回-1.int BSearch2(int *d
8、ata, int key)功能: 在 data 数组中检索 key 的二分检索迭代算法, 成功时返回位置索引, 否则返回-1.树结构typedef struct NODE int key; struct NODE *lch, *rch; TNODE, *BT;typedef struct Parameters BT *t; int key; BT f; BT *p PARA;typedef struct PARA s100; int top; STACK;int InsertBT(BT *t, int key)功能: 在二分检索树 t 中插入关键字为 key 的元素, 成功 时返回 1, 否则
9、返回 0.int TSearch1(BT *t, int key, BT f, BT *p)功能: 用 递归算法在二分检索树 t 中查找关键字为 key 的元素, 成功时返回 1, p 指向该元素节点, 否则 p 指向查找路径上最后一个 节点并返回 0, f 指向 t 的双亲, 其初始调用值为NULL.int TSearch2(BT *t, int key, BT f, BT *p)功能: 用迭代算法在二分检索树 t 中查找关键字为 key 的元素, 成功时返回 1, p 指向该元素节点, 否则 p 指向查找路径上最后一个 节点并返回 0, f 指向 t 的双亲, 其初始调用值为NULL.实验
10、步骤1. 调试线性结构表示下的快速分类与二分检索递归程序, 直至正确为止;2. 调试线性结构表示下的快速分类与二分检索迭代程序, 直至正确为止;3. 待各功能子程序调试完毕, 去掉测试程序, 将程序整理成功能模块存盘备用.实验报告要求1. 阐述实验目的和实验内容;2. 提交实验程序的功能模块;3. 阐述将递归算法改写成迭代算法的一般方法;4. 用类 C 语言阐述分治法递归 与迭代实现抽象控制策略. 思考与练习1. 怎样优化由递归程序改写的迭代程序?2. 设计二分检索树的构造与检索递归程序, 并将其改写成相应的迭代算法。实验四 哈夫曼编码的贪心算法设计（4 学时）实验目的. 根据算法设计需要,掌
11、握哈夫曼编码的二叉树结构表示方法;. 编程实现哈夫曼编译码器;. 掌握贪心算法的一般设计方法。预习要求1. 认真阅读数据结构教材和算法设计教材内容, 熟悉哈夫曼编码的原理;2. 设计和编制哈夫曼编译码器。参考数据类型或变量typedef ElemType char；typedef struct nodeint w;int flag;ElemType c;struct node *plink,*llink,*rlink;char codem;Node;Node *numn, *root;参考子程序接口与功能描述void SetTree( NODE *root )功能: 从终端读入字符集大小 n，
12、以及 n 个字符和 n 个权值，建立哈夫曼树void EnCode( Node *p )功能: 利用已建好的哈夫曼 树， 对输入的正文进行编码void DeCode( void )功能: 利用已建好的哈夫曼树，将输入的代码进行译码实验步骤1. 设计 SetTree 的测试方案和程序 ,输入测试数据,修改并调试程序,直至正确为止;2. 设计 EnCode 的测试方案和程序,输入测试数据,修改并调试程序,直至正确为止;3. 设计 DeCode 的测试方案和程序,输入测试数据,修改并 调试程序,直至正确为止;4. 将你的程序整理成功能模块存盘备用。实验报告要求1. 阐述实验目的和实验内容;2. 提交
13、实验程序的功能模块;3. 记录最终测试数据和测试结果。思考题1. 试证明哈夫曼问题具有贪心选择性质；试证明哈夫曼问题具有最优子结构性质。实验五 Kruskal 算法的设计（4 学时）实验目的. 根据算法设计需要, 掌握连通网的灵活表示方法;. 掌握最小生成树的 Kruskal 算法;. 基本掌握贪心算法的一般设计方法;. 进一步掌握集合的表示与操作算法的应用.预习要求. 认真阅读算法设计教材和数据结构教材内容, 熟习连通网的不同表示方法和最小生成树算法;. 设计 Kruskal 算法实验程序.参考数据类型或变量typedef NodeNumber int; /* 节点编号 */typedef
14、CostType int; /* 成本值类型 */typedef ElemType NodeNumber /* 实型或任意其它元素类型 */typedef struct int ElemType; int tag; NODE;typedef struct CostType cost; NodeNumber node1, node2; EDGE;NODE set=1,-1,n,-1; /* 节点集, n 为连通网的节点数 */ EDGE es =values of e1, values of em; /* 边集, m 为连通网的边数 */EDGE stn-1; /* 最小生成树的边集 */参考子
15、程序接口与功能描述int Find(NODE *set, ElemType elem)功能: 在数组 set 中顺序查找元素 elem, 如果不成功, 返回-1; 否则, 使用带压缩规则的查找算法,返回所在子集的根节点索引.int Union(NODE *set, ElemType elem1, ElemType elem2)功能: 应用 Find 算法首先找到 elem1 和 elem2 所在的子集 , 然后应用带加权规则的并运算算法合并两个子集. 不成功时, 返回-1; 否则, 返回并集的根节点索引.void Sort(EDGE *es, int n)功能: 用任意分类算法将连通 图的边集按成本值的非降次序分类.void Kruskal(EDGE *es, int m, NODE *set, int n, EDGE *st)功能: 对 有 n 个节点, m 条边的连通网, 应用 Kruskal 算法生成最小生成树, 最小生成树的边存储在数组 st 中.void Output(EDGE *st, int n)功能: 输出最小生成树的各条 边.实验步骤1. 设计测试问题,修改并调试程序, 输出最小生成树的各条边, 直至正确为止;2. 待各功能子程序调试完毕, 去掉测试程序, 将你的程序整理成
