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