實(shí)驗(yàn)2二分檢索的遞歸與迭代算法設(shè)計(jì)

1、湖南大學(xué)算法分析與設(shè)計(jì)實(shí)驗(yàn)報(bào)告9實(shí)驗(yàn) 2分檢索的遞歸與迭代算法設(shè)計(jì)-1.int search(int array, int n, int v)功能 : 在 data 數(shù)組中檢索 key 的二分檢索、實(shí)驗(yàn)?zāi)康?、熟悉二分檢索問題的線性結(jié)構(gòu)表示和二分檢索樹表示;2、熟悉不同存儲(chǔ)表示下求解二分檢索問題的遞歸算法設(shè)計(jì);3、通過實(shí)例轉(zhuǎn)換 , 掌握將遞歸算法轉(zhuǎn)換成迭代算法的方法 ;4、掌握應(yīng)用遞歸或迭代程序設(shè)計(jì)實(shí)現(xiàn)分治法求解問題的抽象控制策略.、實(shí)驗(yàn)內(nèi)容1、認(rèn)真閱讀算法設(shè)計(jì)教材和數(shù)據(jù)結(jié)構(gòu)教材內(nèi)容, 熟悉不同存儲(chǔ)表示下求解二分檢索問題的原理或方法 ;2、針對(duì)線性結(jié)構(gòu)表示和二分檢索樹表示設(shè)計(jì)遞歸算法;3、參考

2、教材和課堂教學(xué)內(nèi)容 , 根據(jù)將遞歸算法轉(zhuǎn)換成迭代算法的一般步驟將二分檢索 遞歸算法轉(zhuǎn)換成相應(yīng)的迭代算法 . 算法或程序設(shè)計(jì)參考 【模塊】線性結(jié)構(gòu)int data10= /* 10個(gè)互異的、無序的原始整數(shù) */ ;void quickSort(int s, int l, int r)功能 : 將 datalow, high進(jìn)行快速分類的遞歸算法 .int search_recurse(int array, int low, int high, int v)功能 : 在 data 數(shù)組中檢索 v 的二分檢索遞歸算法 , 成功時(shí)返回位置索引 , 否則返回迭代算法 , 成功時(shí)返回位置索引 , 否則返回

3、 -1.樹結(jié)構(gòu)tstruct BSTreeNode ； / 樹結(jié)構(gòu)void Create(BSTree& tree, int data)；功能：創(chuàng)建結(jié)點(diǎn)或者添加結(jié)點(diǎn)，該結(jié)點(diǎn)值為關(guān)鍵字 data 的元素void CreateBSTree(int array, int array_len)； / 創(chuàng)建二叉樹BSTreeNode* search_binaryTree(BSTree tree, int data)；功能: 用遞歸算法在二分檢索樹 t 中查找關(guān)鍵字為 data 的元素 , 成功時(shí)返回該樹節(jié)點(diǎn) p 指向該元素節(jié)點(diǎn) , 否則 p 指向查找路徑上最后一個(gè)節(jié)點(diǎn)或空節(jié)點(diǎn)。int searcher(

4、BSTree tree, int data)功能 : 用迭代算法在二分檢索樹 t 中查找關(guān)鍵字為 data 的元素 , 成功時(shí)返回 1, p 指 向該元素節(jié)點(diǎn) , 否則 p 指向查找路徑上最后一個(gè)節(jié)點(diǎn)并返回0?！径志€性查找】/ 先對(duì)無序數(shù)組進(jìn)行快速排序void quickSort(int s, int l, int r)if (l r)int i = l, j = r, x = sl; /每次選最左邊的值作為權(quán)值 xwhile (i j) /只要左邊的在右邊的左邊while(i = x) /從右向左找第一個(gè)小于 x 的數(shù)j-;if(i j) / 符合“只要左邊的在右邊的左邊” ，將在右邊找的

5、元素 放到左邊si+ = sj;while(i j & si x) /從左向右找第一個(gè)大于等于 x 的數(shù)i+;if(i j) /符合“只要左邊的在右邊的左邊” ，將在左邊找的元素放到右邊sj- = si;si = x;quickSort(s, l, i - 1); /遞歸調(diào)用對(duì)左邊比權(quán)值小的元素進(jìn)行快排quickSort(s, i + 1, r);/遞歸調(diào)用對(duì)右邊比權(quán)值大的元素進(jìn)行快排/ 二分迭代搜索，在數(shù)組 array 的 n 個(gè)元素中搜索關(guān)鍵值為 V 的元素int search(int array, int n, int v)int left, right, middle;left = 0

6、, right = n - 1;左指針比右指針小取中間中值比 v 大，右指針變?yōu)橹虚g的左邊中值比 v 小，左指針變?yōu)橹虚g的右邊中值=v，返回該位置while (left v) / right = middle - 1;else if (arraymiddle v) / left = middle + 1;else / return middle;return -1;/二分遞歸搜索關(guān)鍵值為V的元素，數(shù)組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大，右指針變?yōu)橹虚g的左邊，繼續(xù)遞歸搜索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) /樹左孩子為空右孩子為空賦值給根節(jié)點(diǎn)元素比結(jié)點(diǎn)值小 ，插入到左孩子Create(tree-left_child, data);else if (tree-data right_c

8、hild, data);elsereturn;/ 創(chuàng)建二叉樹void CreateBSTree(int array, int array_len) / 元素依次插入到樹中for (int i = 0; i data = data) /結(jié)點(diǎn)值與查找元素符合，返回值 1return true;else if (tree-data data) / 查找元素比結(jié)點(diǎn)值小，從左孩子找 tree=tree-left_child;else / 查找元素比結(jié)點(diǎn)值大，從右孩子找tree=tree-right_child;/ 遞歸查找樹查找 ,平均查找查找長(zhǎng)度為 log2 (N+1 - 1 BSTreeNode*

9、search_binaryTree(BSTree tree, int data)if (tree = NULL) /樹空，返回空樹return NULL; coutdatadata = data) /輸出經(jīng)過的結(jié)點(diǎn)值結(jié)點(diǎn)值與查找元素符合，返回此子樹return tree;else if (tree-data data)/ 查找元素比結(jié)點(diǎn)值小，調(diào)用此函數(shù)繼續(xù)在左孩子 中查找return search_binaryTree(tree-left_child, data);else / 查找元素比結(jié)點(diǎn)值大，調(diào)用此函數(shù)繼續(xù)在右孩子中查找return search_binaryTree(tree-righ

10、t_child, data);三、闡述將遞歸算法改寫成迭代算法的一般方法 .遞歸Fun(x)If( 結(jié)束條件)Return;Else每步遞歸操作；Fun( 變量變化 )迭代For (開始狀態(tài)；結(jié)束狀態(tài)；變量變化)每步迭代操作。四、用C+語言闡述分治法遞歸與迭代實(shí)現(xiàn)抽象控制策略問題p,子問題p合并merge(),簡(jiǎn)單解決 ADHOc(P)，遞歸函數(shù)funl (p),迭 代函數(shù) 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初值;結(jié)束條件；變量變化)/變量由小變大Divide p into p0pk accoring to i