实验2二分检索的递归与迭代算法设计

1、湖南大学算法分析与设计实验报告9实验 2分检索的递归与迭代算法设计-1.int search(int array, int n, int v)功能 : 在 data 数组中检索 key 的二分检索、实验目的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 的二分检索递归算法 , 成功时返回位置索引 , 否则返回迭代算法 , 成功时返回位置索引 , 否则返回

3、 -1.树结构tstruct BSTreeNode ； / 树结构void Create(BSTree& tree, int data)；功能：创建结点或者添加结点，该结点值为关键字 data 的元素void CreateBSTree(int array, int array_len)； / 创建二叉树BSTreeNode* search_binaryTree(BSTree tree, int data)；功能: 用递归算法在二分检索树 t 中查找关键字为 data 的元素 , 成功时返回该树节点 p 指向该元素节点 , 否则 p 指向查找路径上最后一个节点或空节点。int searcher(

4、BSTree tree, int data)功能 : 用迭代算法在二分检索树 t 中查找关键字为 data 的元素 , 成功时返回 1, p 指 向该元素节点 , 否则 p 指向查找路径上最后一个节点并返回0。【二分线性查找】/ 先对无序数组进行快速排序void quickSort(int s, int l, int r)if (l r)int i = l, j = r, x = sl; /每次选最左边的值作为权值 xwhile (i j) /只要左边的在右边的左边while(i = x) /从右向左找第一个小于 x 的数j-;if(i j) / 符合“只要左边的在右边的左边” ，将在右边找的

5、元素 放到左边si+ = sj;while(i j & si x) /从左向右找第一个大于等于 x 的数i+;if(i j) /符合“只要左边的在右边的左边” ，将在左边找的元素放到右边sj- = si;si = x;quickSort(s, l, i - 1); /递归调用对左边比权值小的元素进行快排quickSort(s, i + 1, r);/递归调用对右边比权值大的元素进行快排/ 二分迭代搜索，在数组 array 的 n 个元素中搜索关键值为 V 的元素int search(int array, int n, int v)int left, right, middle;left = 0

6、, right = n - 1;左指针比右指针小取中间中值比 v 大，右指针变为中间的左边中值比 v 小，左指针变为中间的右边中值=v，返回该位置while (left v) / right = middle - 1;else if (arraymiddle v) / left = middle + 1;else / return middle;return -1;/二分递归搜索关键值为V的元素，数组array最低位置为low，最高位置为highint search_recurse(int array, int low, int high, int v)int middle;middle =

7、(low + high) / 2;if (low v) II中值比v大，右指针变为中间的左边，继续递归搜索return search_recurse(array, low, middle-1, v);else if (arraymiddle left_child = NULL; / tree-right_child = NULL; / tree-data = data;/elseif (tree-data data) /树左孩子为空右孩子为空赋值给根节点元素比结点值小 ，插入到左孩子Create(tree-left_child, data);else if (tree-data right_c

8、hild, data);elsereturn;/ 创建二叉树void CreateBSTree(int array, int array_len) / 元素依次插入到树中for (int i = 0; i data = data) /结点值与查找元素符合，返回值 1return true;else if (tree-data data) / 查找元素比结点值小，从左孩子找 tree=tree-left_child;else / 查找元素比结点值大，从右孩子找tree=tree-right_child;/ 递归查找树查找 ,平均查找查找长度为 log2 (N+1 - 1 BSTreeNode*

9、search_binaryTree(BSTree tree, int data)if (tree = NULL) /树空，返回空树return NULL; coutdatadata = data) /输出经过的结点值结点值与查找元素符合，返回此子树return tree;else if (tree-data data)/ 查找元素比结点值小，调用此函数继续在左孩子 中查找return search_binaryTree(tree-left_child, data);else / 查找元素比结点值大，调用此函数继续在右孩子中查找return search_binaryTree(tree-righ

10、t_child, data);三、阐述将递归算法改写成迭代算法的一般方法 .递归Fun(x)If( 结束条件)Return;Else每步递归操作；Fun( 变量变化 )迭代For (开始状态；结束状态；变量变化)每步迭代操作。四、用C+语言阐述分治法递归与迭代实现抽象控制策略问题p,子问题p合并merge(),简单解决 ADHOc(P)，递归函数funl (p),迭 代函数 fun2()void fun1(p)if(p=n0)return (ADHOc(P) ；elseDivide p into p0pk;For(i=0;ik;i+)Fun1(pi);Merge();void fun2()if(p=n0)return (ADHOc(P) ；For(变量i初值;结束条件；变量变化)/变量由小变大Divide p into p0pk accoring to i