数据结构习题集（李冬梅 第2版）C语言版源程序习题集-算法8-6.docx

《数据结构习题集（李冬梅 第2版）C语言版源程序习题集-算法8-6.docx》由会员分享，可在线阅读，更多相关《数据结构习题集（李冬梅 第2版）C语言版源程序习题集-算法8-6.docx（2页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、/分别指向表的下界和上界 分别指向新的子表的下界和上界 分别记录A1和A2中元素的和 标记划分是否成功 /记录表的中间位置 循环进行划分选择枢轴从两端交替地向中间扫描/从最右侧位置依次向左搜索将比枢轴记录小的记录移到低端/从最左侧位置依次向右搜索将比枢轴记录大的记录移到高端枢轴记录到位枢轴的位置是n/2的前一位置，flag-0; else/划分成功，下次循环将退出划分继续划分#include using namespace std;int Partition(int a ,int n)/将正整数构成的集合划分为两个不相交的子集A1和A2int low=0,high=n-l;int low0=0

2、,highO=n-l;int sl=0,s2=0;int flag=l;int k=n/2;while(flag)(int pivotkey=alow； while(lowhigh) while(lowpivotkey)-high;if(low!high)alow=ahigh;while(lowhigh & alowpivotkey) +low;if(low!=high) ahigh=alow;)alow=pivotkey;if (low=k-l)/满足条件,if (lowk-l)lowO=+low； high=highO;)else/满足条件，枢轴low及之前的所有元素均屈于Al继续对low

3、之后的元素进行划分继续对low之前的元素进行划分满足条件，枢轴low及之后的所有元素均屈于A2highO=-high; low=lowO;)cout”Al中的元素：； for(int i-0;ik;i+) (couta isl+=ai;/求解了集Al中元素的和 coutendl;coutA2中的元素：”; for(int i=k;in;i+) (coutais2+=ai;求解子集A2中元素的和) coutendl;cout| S1-S2 | 的值为：-s2-slendl; return s2-sl;int main。(int n;coutn;int an;cout”请输入数组元素：，for(int i=0;in;i+) cina i;Partition(a,n);return 0;输出结果请输入数组长度：5请输入数组元素：6 12 8 4A1中的元素：1 2A2中的元素：4 6 8IS1-S2I 的值为：15