《实验2二分检索的递归与迭代算法设计》由会员分享，可在线阅读，更多相关《实验2二分检索的递归与迭代算法设计（7页珍藏版）》请在金锄头文库上搜索。
1、湖南大学 算法分析与设计实验报告 1实验 2 二分检索的递归与迭代算法设计一、实验目的1、熟悉二分检索问题的线性结构表示和二分检索树表示;2、熟悉不同存储表示下求解二分检索问题的递归算法设计;3、通过实例转换, 掌握将递归算法转换成迭代算法的方法;4、掌握应用递归或迭代程序设计实现分治法求解问题的抽象控制策略.二、实验内容1、认真阅读算法设计教材和数据结构教材内容, 熟悉不同存储表示下求解二分检索问题的原理或方法;2、针对线性结构表示和二分检索树表示设计递归算法;3、参考教材和课堂教学内容, 根据将递归算法转换成迭代算法的一般步骤将二分检索递归算法转换成相应的迭代算法.算法或程序设计参考 【模
2、块】线性结构线性结构int data10= /* 10 个互异的、无序的原始整数 */ ;void quickSort(int s, int l, int r)功能: 将 datalow, high进行快速分类的递归算法.int search_recurse(int array, int low, int high, int v)功能: 在 data 数组中检索 v 的二分检索递归算法, 成功时返回位置索引, 否则返回-1.int search(int array, int n, int v)功能: 在 data 数组中检索 key 的二分检索迭代算法, 成功时返回位置索引, 否则返回-1.树
3、结构树结构tstruct BSTreeNode；/树结构void Create(BSTree if(i v) /中值比 v 大，右指针变为中间的左边right = middle - 1;else if (arraymiddle v) /中值比 v 大，右指针变为中间的左边，继续 递归搜索return search_recurse(array, low, middle-1, v);else if (arraymiddle left_child = NULL; /左孩子为空tree-right_child = NULL; /右孩子为空tree-data = data; /赋值给根节点elseif
4、(tree-data data) /元素比结点值小 ，插入到左孩子Create(tree-left_child, data);else if (tree-data right_child, data);elsereturn;/创建二叉树void CreateBSTree(int array, int array_len)湖南大学 算法分析与设计实验报告 5 /元素依次插入到树中for (int i = 0; i data = data) /结点值与查找元素符合，返回值 1return true;else if (tree-data data) /查找元素比结点值小，从左孩子找tree=tree
5、-left_child;else /查找元素比结点值大，从右孩子找tree=tree-right_child;/递归查找树查找,平均查找查找长度为log2 (N+1 - 1BSTreeNode* search_binaryTree(BSTree tree, int data)if (tree = NULL) /树空，返回空树return NULL;coutdatadata = data) /结点值与查找元素符合，返回此子树return tree;湖南大学 算法分析与设计实验报告 6else if (tree-data data)/查找元素比结点值小，调用此函数继续在左孩子中查找return s
6、earch_binaryTree(tree-left_child, data);else /查找元素比结点值大，调用此函数继续在右孩子中查找return search_binaryTree(tree-right_child, data);三、阐述将递归算法改写成迭代算法的一般方法. 递归 Fun(x)If(结束条件）Return;Else每步递归操作；Fun(变量变化)迭代For（开始状态；结束状态；变量变化）每步迭代操作。4、用 C+语言阐述分治法递归与迭代实现抽象控制策略问题 p，子问题 p，合并 merge()，简单解决 ADHOc(P)，递归函数 fun1（p） ，迭代函数 fun2(
7、)void fun1(p)if(p=n0)return (ADHOc(P)；elseDivide p into p0pk;For(i=0;ik;i+)湖南大学 算法分析与设计实验报告 7Fun1(pi);Merge(); void fun2()if(p=n0)return (ADHOc(P)；For(变量 i 初值;结束条件；变量变化) /变量由小变大Divide p into p0pk accoring to i;For(i=0;ik;i+)If(pi)no)ADHOc(P);ElseMerge();Merge();五、思考题1. 怎样优化由递归程序改写的迭代程序?解答：将每步递归的操作的模块化进行调用。可以独立成块的功能独立开来。2. 设计二分检索树的构造与检索递归程序, 并将其改写成相应的迭代算法.解答：如上已经实现了。
