第5章_减治法(完).ppt

下载文档 降价啦

58
0
约1.79万字
约 80页
2017-06-28 发布于湖北
举报
版权申诉
保障服务

第5章_减治法(完).ppt

1、本文档共80页，可阅读全部内容。
2、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击这里二次下载。
4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。

第5章_减治法(完)

int SearchMid(int A[ ], int B[ ], int n) { int s1 = 0, e1 = n - 1, s2 = 0, e2 = n-1; //初始化两个序列的上下界 int mid1, mid2; while (s1 e1 s2 e2) //循环直到区间只有一个元素 { mid1= (s1 + e1)/2; //序列A的中位数的下标 mid2 = (s2 + e2)/2; //序列B的中位数的下标 if (A[mid1] == B[mid2]) return A[mid1]; //第①种情况 if (A[mid1] B[mid2]) //第②种情况 { if ((s1 + e1) % 2 == 0) s1 = mid1; else s1 = mid1 + 1; e2 = mid2; } else { if ((s2 + e2) % 2 == 0) s2 = mid2; else s2 = mid2 + 1; e1 = mid1; } } if (A[s1] B[s2]) return A[s1]; //较小者为所求 else return B[s2]; } BiNode *insertBST(BiNode *root, int data) { if(root == NULL) { root = new BiNode; root-data = data; root-lchild = NULL; root-rchild = NULL; return root; } if(data = root-data) root-lchild = insertBST(root-lchild, data); else root-rchild = insertBST(root-rchild, data); return root; } BiNode *createBST(int a[], int n) { BiNode *T = NULL; for (int i=0; i n; i++) T = insertBST(T, a[i]); return T; } int Partition(int r[ ], int low, int high) //划分 { int i = low, j=high; //初始化待划分区间 while (i j) { while (i j r[i] = r[j]) j--; //右侧扫描 if (i j) { int temp = r[i]; r[i] = r[j]; r[j] = temp; //将较小记录交换到前面 i++; } while (i j r[i] = r[j]) i++; //左侧扫描 if (i j) { int temp = r[i]; r[i] = r[j]; r[j] = temp; //将较大记录交换到后面 j--; } } return i; // 返回轴值记录的位置 } int MinK(int r[ ],int low,int high,int k) //k为第k小元素 { int s; //s为轴值位置 s = Partition(r, low, high); if (s == k) return r[s]; if(s k) return MinK(r, low, s-1, k); else return MinK(r, s+1, high, k); } void HeapSort(int r[ ], int n) { int i, temp; for (i = (n-1)/2; i = 0; i--) //初始建堆，从最后一个分支结点至根结点 SiftHeap(r, i, n) ; for (i = 1; i = n-1; i++) //重复执行移走堆顶及重建堆的操作 { t