《算法设计与分析书中程序(第05章)》由会员分享，可在线阅读，更多相关《算法设计与分析书中程序(第05章)（6页珍藏版）》请在金锄头文库上搜索。
1、73【程序 5-1】 分治法SolutionType DandC(ProblemType P)ProblemType P1，P2，Pk;if (Small(P) return S(P);/子问题 P 足够小，用 S(P)直接求解else Divide(P，P1，P2，Pk);/将问题 P 分解成子问题 P1, P2, , PkReturn Combine(DandC(P1)，DandC(P2)，DandC(Pk);/求解子问题，并合并解 【程序 5-2】 一分为二的分治法SolutionType DandC(int left，int right)if (Small(left，right) re
2、turn S(left，right);else int m=Divide(left，right);/以 m 为界将问题分解成两个子问题Return Combine(DandC(left，m)，DandC(m+1，right); /分别求解子问题，并合并解【程序 5-3】 可排序表类template struct E /可排序表中元素的类型operator K()const return key;/重载类型转换运算符K key;/关键字可以比较大小D data;/其他数据;template class SortableList /可排序表类public:SortableList(int mSiz
3、e)/构造函数 maxSize=mSize;l=new TmaxSize;n=0;SortableList()delete l;/析构函数74private:T *l ;/动态生成一维数组int maxSize;/线性表的最大表长int n;/线性表的实际长度;【程序 5-4】 求最大最小元template void SortableList:MaxMin(Tmax=min=l0; for (int i=1; imax) max=li; if(livoid SortableList:MaxMin(int i, int j, Tif (i=j) max=min=li;/表中只有一个元素时else
4、 if (i=j-1)/表中有两个元素时if (limin1) min=min1;/两子表最小元的小者为原表最小元 75【程序 5-6】 二分搜索算法框架template int SortableList:BSearch(const Telse return m;/搜索成功return -1;/搜索失败 【程序 5-7】 对半搜索递归算法template int SortableList:BSearch(const T/搜索右半子表else return m;/搜索成功return-1;/搜索失败【程序 5-8】 对半搜索的迭代算法template int SortableList:BSear
5、ch1(const Twhile (leftlm) left=m+1;else return m;/搜索成功return-1;/搜索失败76【程序 5-9】 Merge 函数template void SortableList:Merge(int left, int mid, int right) T* temp=new Tright-left+1;int i=left, j=mid+1, k=0;while ( ivoid SortableList:MergeSort()MergeSort(0, n-1);template void SortableList:MergeSort(int le
6、ft, int right)if (leftint SortableList:Partition(int left, int right) /前置条件：leftrightint i=left, j=right+1;do do i+; while (lilleft);77if (ivoid SortableList:QuickSort()QuickSort(0, n-1);template void SortableList:QuickSort(int left, int right)if(leftResultCode SortableList:Select1(Tif (n=r) /若问题足够小
7、，使用直接插入排序，取其中的第 k 小元素，其下标为 left+k1InsertSort(left, right); return left+k-1;for (int i=1; i=n/r; i+)InsertSort(left+(i-1)*r, left+i*r-1);/二次取中规则求每组的中间值Swap(left+i-1, left+(i-1)*r+Ceil(r, 2) -1);/将每组的中间值集中存放在子表前部int j=Select(Ceil(n/r, 2), left, left+(n/r) -1, r );/求二次中间值，其下标为 jSwap(left, j);/二次中间值为主元，并换至 left 处j=Partition(left, right);/对表（子表）进行分划操作if (k=j-left+1) return j;/返回第 k 小元素下标else if (kj-left+1) return Select(k, left, j-1, r);/在左子表求第 k 小元素else return Select(k- (j-left+1), j+1, right, r);/在右子表求第 k- (j-left+1)小元素
