进栈溢出.ppt

《进栈溢出.ppt》由会员分享，可在线阅读，更多相关《进栈溢出.ppt（76页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、top空栈toptoptoptoptopa 进栈b 进栈aababcdee 进栈abcdef 进栈溢出abdee 退栈ctopc 退栈b 退栈abaa 退栈空空栈topabdd 退栈ctopabctoptop双栈共享一个栈空间双栈共享一个栈空间b0 t0 t1 b10 maxSize-1V栈的应用栈的应用栈在日常生活中和计算机程序设计中有着许多应用，下面仅介绍栈在计算机中的应用。1.算术表达式的求值算术表达式的求值算术表达式中包含了算术运算符和算术量(常量、变量、函数)，而运算符之间又存在着优先级，不能简单地进行从左到右运算，编译程序在求值时，不能简单从左到右运算，必须先算运算级别高的，再算运

2、算级别低的，同一级运算才从左到右(C+中有些从右到左)。因此，要实现表达式求值，必须设置两个栈，一个栈存放运算符，另一个栈存放操作数（算术量），在进行表达式求值时，编译程序从左到右扫描，遇到操作数，一律进入操作数栈，遇到运算符，则应与运算符栈的栈顶比较，若运算符优先级高于栈顶则进栈，否则退栈，退栈后，在操作数栈中退出两个元素(先退出在运算符右，后退出在运算符左)，然后用运算符栈中退出的栈顶元素进行运算，运算的结果存入操作数栈中，直到扫描完毕。这时运算符栈为空，操作数栈中只有一个元素，即为运算的结果。例求表达式1+2*3-4/2的值，栈的变化如下。步骤操作数栈运算符栈说明开始两栈均为空111进入

3、操作数栈+进入运算符栈2进入操作数栈*进入运算符栈3进入操作数栈退栈2*3进入操作数栈退栈1+6进入操作数栈234567891+12+12+1117+*236+*+步骤操作数栈运算符栈说明107-进入运算符栈4进入操作数栈/进入运算符栈2进入操作数栈退栈4/2进入操作数栈退栈7-2进入操作数栈1112131415161774-74-/742-/772-5当然，算术表达式除了简单求值外，还会涉及到算术表达式的两种表示方法，即中缀表示法和后缀表示法。刚才的例3-3中的表达式就是中缀表达式，中缀表达式求值较麻烦（须考虑运算符的优先级，甚至还要考虑圆括号），而后缀表达式求值较方便（无须考虑运算符的优先

4、级及圆括号）。下面将介绍算术表达式的中缀表示和后缀表示及它们的求值规律，例如，对于下列各中缀表达式：（1）3/5+8（2）18-9*(4+3)（3）(25+x)*(a*(a+b)+b)对应的后缀表达式为：(1)35/8+(2)18943+*-(3)25x+aab+*b+*2中缀表达式变成等价的后缀表达式中缀表达式变成等价的后缀表达式将中缀表达式变成等价的后缀表达式，表达式中操作数次序不变，运算符次序发生变化，同时去掉了圆括号。转换规则是：设立一个栈，存放运算符，首先栈为空，编译程序从左到右扫描中缀表达式，若遇到操作数，直接输出，并输出一个空格作为两个操作数的分隔符；若遇到运算符，则必须与栈顶比

5、较，运算符级别比栈顶级别高则进栈，否则退出栈顶元素并输出，然后输出一个空格作分隔符；若遇到左括号，进栈；若遇到右括号，则一直退栈输出，直到退到左括号止。当栈变成空时，输出的结果即为后缀表达式。将中缀表达式(1+2)*(8-2)/(7-4)变成等价的后缀表达式。现在用栈来实现该运算，栈的变化及输出结果如下步骤栈中元素输出结果说明1(（进栈2(1输出13(+1+进栈4(+12输出2512+退栈输出，退栈到（止6*12+*进栈7*(12+（进栈8*(12+（进栈9*(12+8输出810*(-12+8-进栈11*(-12+82输出212*(12+82-退栈输出，退栈到（止13*(/12+82-/进栈1

6、4*(/(12+82-（进栈15*(/(12+82-7输出716*(/(-12+82-7-进栈17*(/(-12+82-74输出418*(/12+82-74-退栈输出，退栈到（止19*12+82-74-/退栈输出，退栈到（止2012+82-74-/*退栈并输出步骤栈中元素输出结果说明3后缀表达式的求值后缀表达式的求值将中缀表达式转换成等价的后缀表达式后，求值时，不需要再考虑运算符的优先级，只需从左到右扫描一遍后缀表达式即可。具体求值步骤为：设置一个栈，开始时，栈为空，然后从左到右扫描后缀表达式，若遇操作数，则进栈；若遇运算符，则从栈中退出两个元素，先退出的放到运算符的右边，后退出的放到运算符左

7、边，运算后的结果再进栈，直到后缀表达式扫描完毕。此时，栈中仅有一个元素，即为运算的结果。例，求后缀表达式：12+82-74-/*的值，栈的变化情如下：步骤栈中元素说明111进栈2122进栈3遇+号退栈2和1431+2=3的结果3进栈5388进栈63822进栈73遇-号退栈2和88368-2=6的结果6进栈93677进栈1036744进栈步骤栈中元素说明1136遇-号退栈4和7123637-4=3的结果3进栈133遇/号退栈3和614326/3=2的结果2进栈15遇*号退栈2和31663*2=6进栈176扫描完毕，运算结束从上可知，最后求得的后缀表达式之值为6，与用中缀表达式求得的结果一致，但后

8、缀式求值要简单得多。4函数的嵌套调用函数的嵌套调用在函数嵌套调用中，一个函数的执行没有结束，又开始另一个函数的执行，因此必须用栈来保存函数中中断的地址，以便调用返回时能从断点继续往下执行。例设有一个主程序，它调用函数a，函数a又调用函数b，函数b又调用函数c，（见下页），其中r，s，t分别表示中断地址，我们可以用一个栈来描述调用情况（见下页）。主程序调用函数a，留下一个断点地址r进栈，然后主函数处于挂起状态，进入函数a中执行，函数a中再调用函数b，留下一个断点地址s进栈，然后函数a处于挂起状态，进入函数b中执行，函数b中调用函数c，留下一个断点地址t进栈，然后函数b处于挂起状态，进入函数c中执

9、行，函数c执行完后，要返回断点处继续执行，但返回到那一个断点呢?根据栈顶元素来决定。返回时，执行退栈操作，先退出t，故返回t断点继续执行，接着退栈退出s，故返回s断点继续执行，接着退栈退出r，返回r断点继续执行，最后栈为空，算法结束。迷宫问题小型迷宫小型迷宫路口路口 动作动作结果结果1 1(入口入口)正向走 进到 2 22 2左拐弯 进到 3 33 3右拐弯 进到 4 44 4(堵死)回溯 退到 3 33 3(堵死)回溯 退到 2 22 2正向走 进到 5 55 5(堵死)回溯 退到 2 22 2右拐弯 进到 6 66 6左拐弯 进到7 7(出口出口)43521766左左 0 直直 2 右右

10、0行行 3 行行 5 行行 6 0 0 4 0 0 0 0 0 0 7 0 0 7小小型型迷迷宫宫的的数数据据迷宫的类定义迷宫的类定义#include#include#includeclass Maze private:intMazeSize;intEXIT;Intersection*intsec;public:Maze(char*filename);intTraverseMaze(intCurrentPos);Maze:Maze(char*filename)/构造函数：从文件filename 中读取各路口/和出口的数据ifstreamfin;fin.open(filename,ios:in|

11、ios:nocreate);/为输入打开文件,文件不存在则打开失败 if(!fin)cout“迷宫数据文件”filename “打不开”MazeSize;/输入迷宫路口数 intsec=new IntersectionMazeSize+1;/创建迷宫路口数组创建迷宫路口数组for(inti=1;iintseci.left intseci.forward intseci.right;fin EXIT;/输入迷宫出口输入迷宫出口fin.close();迷宫漫游与求解算法迷宫漫游与求解算法intMaze:TraverseMaze(intCurrentPos)if(CurrentPos 0)/路口从路

12、口从 1 开始开始 if(CurrentPos=EXIT)/出口处理出口处理 cout CurrentPos ;return1;else /递归递归向左向左搜寻可行搜寻可行 if(TraverseMaze(intsecCurrentPos.left)cout CurrentPos “”;return1;else /递归递归向前向前搜寻可行搜寻可行 if(TraverseMaze(intsecCurrentPos.forward)cout CurrentPos “”;return1;else /递归递归向右向右搜寻可行搜寻可行 if(TraverseMaze(intsecCurrentPos.r

13、ight)cout CurrentPos ;return1;return 0;递归与回溯递归与回溯 常用于搜索过程常用于搜索过程n皇后问题皇后问题 在在 n 行行 n 列的列的国际象棋棋盘上，国际象棋棋盘上，若两个皇后位于同一行、同一列、若两个皇后位于同一行、同一列、同一对角线上，则称为它们为互相同一对角线上，则称为它们为互相攻击。攻击。n皇后问题是指皇后问题是指找到这找到这 n 个个皇后的互不攻击的布局皇后的互不攻击的布局。1#主对角线主对角线3#主对角线主对角线5#主对角线主对角线0#次对角线次对角线2#次对角线次对角线4#次对角线次对角线6#次对角线次对角线1#次对角线次对角线3#次对角

14、线次对角线5#次对角线次对角线0#主对角线主对角线2#主对角线主对角线4#主对角线主对角线6#主对角线主对角线0 1 2 3 0123k=i+jk=n+i-j-1解题思路解题思路n n安放第安放第 i 行行皇后时，需要在列的方向从皇后时，需要在列的方向从 0 到到 n-1 试探试探(j=0,n-1)n n在第在第 j 列安放一个皇后：列安放一个皇后：uu如果在列、主对角线、次对角线方向如果在列、主对角线、次对角线方向有其它皇后，则出现攻击，撤消在第有其它皇后，则出现攻击，撤消在第 j 列安放的皇后。列安放的皇后。uu如果没有出现攻击，在第如果没有出现攻击，在第 j 列安放的列安放的皇后不动，递

15、归安放第皇后不动，递归安放第 i+1行皇后。行皇后。n n设置设置 4 个数组个数组u col n：coli 标识第标识第 i 列是否安放列是否安放了皇后了皇后u md2n-1:mdk 标识第标识第 k 条主对条主对角线是否安放了皇后角线是否安放了皇后u sd2n-1:sdk 标识第标识第 k 条次对角条次对角线是否安放了皇后线是否安放了皇后u qn:qi 记录第记录第 i 行皇后在第几列行皇后在第几列void Queen(int i)for(int j=0;jn;j+)if(第第 i 行第行第 j 列没有攻击列没有攻击)在在第第 i 行第行第 j 列安放皇后列安放皇后；if(i=n-1)输出

16、一个布局输出一个布局；else Queen(i+1);撤消撤消第第 i 行第行第 j 列的皇后列的皇后；算法求精算法求精void Queen(int i)for(int j=0;jn;j+)if(!colj&!mdn+i-j-1&!sdi+j)/*第第 i 行第行第 j 列没有攻击列没有攻击*/colj=mdn+i-j-1=sdi+j=1;qi=j;/*在在第第 i 行第行第 j 列安放皇后列安放皇后*/if(i=n-1)/*输出一个布局输出一个布局*/for(intk=0;kn;k+)cout qk ,;cout endl;else Queen(i+1);colj=mdn+i-j-1=sdi

17、+j=0;qi=0;/*撤消撤消第第 i 行第行第 j 列的皇后列的皇后*/地图四染色问题地图四染色问题使使地地图图中中相相邻邻的的国国家家或或行行政政区区域域不不重重色色，最最少少可可用用四四种种颜色对地图着色。颜色对地图着色。说明此结论，利用栈采用回溯法对地图着色。说明此结论，利用栈采用回溯法对地图着色。思想：对每个行政区编号：思想：对每个行政区编号：1-71-7 对颜色编号；对颜色编号；a a、b b、c c、d d；从从第第一一号号行行政政区区开开始始逐逐一一染染色色，每每一一个个区区域域逐逐次次用用四四种种颜颜色色进进行行试试探探，若若所所取取颜颜色色与与周周围围不不重重，则则用用栈

18、栈记记下下来来该该区区域域的的色色数数，否否则则依依次次用用下下一一色色数数进进行行试试探探。若若出出现现a-da-d均均与与周周围围发发生生重重色色，则则需需退退栈栈回回溯溯，修修改改当当前前栈栈顶顶的色数。的色数。0 1 1 1 1 1 0 1 0 0 0 0 1 0 1 0 0 1 1 0 0 1 0 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0R 1:7,1:7 1 2 3 4 5 6 71 2 3 4 5 6 7 Void mapcolor(int R,int n,int s)s1=1;/1号区域染号区域染1色色I=2;J=1

19、;/I为区域号，为区域号，J为染色号为染色号while(I=n)while(J=4)&(I=n)k=1;/k表示已经着色的区域号表示已经着色的区域号while(KI)&(sK RI,K!=J)K=K+1;/若不相邻，或若相邻且不重色，对下一个区域判断。若不相邻，或若相邻且不重色，对下一个区域判断。IF(K4)THEN I=I-1;J=sI+1 (1)(2)(4)(5)(6)(7)(3)1#粉色粉色2#黄色黄色3#红色红色4#绿色绿色 1 2 3 2 1 2 3 1 2 2 4 3 1 2 3 2 4 3 1 2 3 2 4 1 2 3 2 4 3 1 1 2 2 3 41 2 3 4 5 6

20、7 S 1:7 Void mapcolor(int R,int n,int s)I=6;J=1;/I为区域号，为区域号，J为染色号为染色号 while(I=n)while(J=4)&(I=n)k=1;/k表示已经着色的区域号表示已经着色的区域号 while(kI)&(sk RI,k!=J)k=k+1;=4/若不相邻，或若相邻且不重色，对下一个区域判断。若不相邻，或若相邻且不重色，对下一个区域判断。IF(K4)THEN I=I-1;J=sI+1 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 0 1 0 0 1 1 0 0 1 0 1 0

21、0 0 0 1 0 1 1 1 1 1 01 2 3 4 5 6 71 2 3 4 5 6 7 3 4 2 2 11 2 3 4 5 6 7 I=6,J=5I=6,J=5k=4k=4 a b c b a b c a b b d c a b cb d c a b cb d a b c b d caa b b c dS1:71 2 3 4 5 6 7 a 粉色粉色 b 黄色黄色c 红色红色 d 绿色绿色(1)(2)(4)(7)(3)(5)(6)(1)(2)(4)(7)(3)(5)(6)(1)(2)(4)(7)(3)(5)(6)(1)(2)(4)(7)(3)(5)(6)(1)(2)(4)(7)(3)

22、(5)(6)(1)(2)(4)(7)(3)(5)(6)(1)(2)(4)(7)(3)(5)(6)队列的进队和出队队列的进队和出队 front rear空队列front rearA进队Afront rearB进队A Bfront rearC,D进队A B C Dfront rearA退队B C Dfront rearB退队C Dfront rearE,F,G进进队C D E F GC D E F Gfront rearH进进队,溢出01234567front01234567front01234567frontrearAABCrearrear空队列空队列A进进队队B,C进进队队0123456701

23、234567A退退队队B退退队队01234567D,E,F,G,H进进队队frontBCrearAfrontBCrearfrontCrearDEF GH优先级队列(PriorityQueue)F优先级队列优先级队列 是不同于先进先出队是不同于先进先出队列的另一种队列。每次从队列中取列的另一种队列。每次从队列中取出的是具有最高优先权的元素出的是具有最高优先权的元素F例如下表：任务的优先权及执行顺例如下表：任务的优先权及执行顺序的关系序的关系数字越小，优先权越高数字越小，优先权越高 优先队列的类定义优先队列的类定义#include#include$include const intmaxPQSiz

24、e=50;/缺省元素个数缺省元素个数template classPQueuepublic:PQueue();PQueue()deletepqelements;void PQInsert(const Type&item);TypePQRemove();void makeEmpty()count=-1;intIsEmpty()const return count=-1;int IsFull()const return count=maxPQSize;intLength()const return count;private:Type*pqelements;/存放数组存放数组intcount;/队列

25、元素计数队列元素计数 优先队列部分成员函数的实现优先队列部分成员函数的实现 template PQueue:PQueue():count(-1)pqelements=new TypemaxPQSize;assert(pqelements!=0);/分配断言分配断言template voidPQueue:PQInsert(const Type&item)assert(!IsFull();/判队满断言判队满断言count+；pqelementscount=item;template Type PQueue:PQRemove()assert(!IsEmpty();/判队空断言判队空断言Typemin

26、=pqelements0;intminindex=0;for(inti=1;icount;i+)/寻找最小元素寻找最小元素 if(pqelementsimin)/存于存于minmin=pqelementsi;minindex=i;pqelementsminindex=pqelementscount-1;count-;/删除删除returnmin;除了栈和队列之外，还有一种限定性数据结构，它们是双端队列（double-endedqueue）。端1端2插入删除图双端队列的示意图a1a2aia0an-1删除插入双端队列是限定插入和删除操作在线性表的两端进行，我们可以将它看成是栈底连在一起的两个栈，但

27、它与两个栈共享存储空间是不同的。共享存储空间中的两个栈的栈顶指针是向两端扩展的，因而每个栈只需一个指针；而双端队列允许两端进行插入和删除元素，因而每个端点必须设立两个指针，如图3-13所示。在实际使用中，还有输出受限的双端队列（即一个端点允许插入和删除，另一个端点只允许插入）；输入受限的双端队列（即一个端点允许插入和删除，另一个端点只允许删除）。如果限定双端队列从某个端点插入的元素只能从该端点删除，则双端队列就蜕变为两个栈底相邻接的栈了。尽管双端队列看起来比栈和队列更灵活，但实际中并不比栈和队列实用，故在此不再深入讨论。队列的应用队列在日常生活中和计算机程序设计中，有着非常重要的作用，在此，仅

28、举出若干例子来说明。第一个例子就是CPU资源的竞争问题。在具有多个终端的计算机系统中，有多个用户需要使用CPU各自运行自己的程序，它们分别通过各自终端向操作系统提出使用CPU的请求，操作系统按照每个请求在时间上的先后顺序，将其排成一个队列，每次把CPU分配给队头用户使用，当相应的程序运行结束，则令其出队，再把CPU分配给新的队头用户，直到所有用户任务处理完毕。第二个例子就是主机与外部设备之间速度不匹配的问题。以主机和打印机为例来说明，主机输出数据给打印机打印，主机输出数据的速度比打印机打印的速度要快得多，若直接把输出的数据送给打印机打印，由于速度不匹配，显然是不行的。所以解决的方法是设置一个打

29、印数据缓冲区，主机把要打印输出的数据依此写如到这个缓冲区中，写满后就暂停输出，继而去做其它的事情，打印机就从缓冲区中按照先进先出的原则依次取出数据并打印，打印完后再向主机发出请求，主机接到请求后再向缓冲区写入打印数据，这样利用队列既保证了打印数据的正确，又使主机提高了效率。逐行打印二项展开式逐行打印二项展开式(a+b)i 的系数的系数杨辉三角形杨辉三角形 (Pascals triangle)分析第分析第 i 行元素与第行元素与第 i+1行元素的关系行元素的关系目的是从前一行的数据可以计算下一行的数据目的是从前一行的数据可以计算下一行的数据从第从第 i 行数据计算并存放第行数据计算并存放第 i+

30、1 行数据行数据利用队列打印二项展开式系数的程序利用队列打印二项展开式系数的程序#include#include#includequeue.hvoidYANGVI(intn)Queue q;/队列初始化队列初始化 q.MakeEmpty();q.EnQueue(1);q.EnQueue(1);ints=0;for(int i=1;i=n;i+)/逐行计算逐行计算coutendl;q.EnQueue(0);for(int j=1;j=i+2;j+)/下一行下一行intt=q.DeQueue();q.EnQueue(s+t);s=t;if(j!=i+2)cout s ;划分子集问题u问题描述：已知

31、集合A=a1,a2,an，及集合上的关系R=(ai,aj)|ai,ajA,ij，其中(ai,aj)表示ai与aj间存在冲突关系。要求将A划分成互不相交的子集A1,A2,Ak,(kn)，使任何子集中的元素均无冲突关系，同时要求分子集个数尽可能少例A=1,2,3,4,5,6,7,8,9R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)可行的子集划分为：A1=1,3,4,8A2=2,7A3=5A4=6,9u算法思想：利用循环筛选。从第一个元素开始，凡与第一个元素无冲突的元素划归一组；再将剩下的

32、元素重新找出互不冲突的划归第二组；直到所有元素进组u所用数据结构冲突关系矩阵rij=1,i,j有冲突rij=0,i,j无冲突循环队列cqn数组resultn存放每个元素分组号工作数组newrnu工作过程初始状态：A中元素放于cq中，result和newr数组清零，组号group=1第一个元素出队，将r矩阵中第一行“1”拷入newr中对应位置，这样，凡与第一个元素有冲突的元素在newr中对应位置处均为“1”,下一个元素出队若其在newr中对应位置为“1”，有冲突，重新插入cq队尾，参加下一次分组若其在newr中对应位置为“0”,无冲突，可划归本组；再将r矩阵中该元素对应行中的“1”拷入newr中

33、如此反复，直到9个元素依次出队，由newr中为“0”的单元对应的元素构成第1组,将组号group值“1”写入result对应单元中令group=2,newr清零，对cq中元素重复上述操作，直到cq中front=rear,即队空，运算结束u算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=123456789012345678cqf r000000000012345678newr000000000012345678result初始R=(2,8),(9,4),(2,9),(2,

34、1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)u算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=23456789012345678cqfr010000000012345678newr100000000012345678resultR=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)u算法描述01000

35、0000010110000000001100000010001010101101011010100001011000010000000100011011R=23456789012345678cqfr010000000012345678newr100000000012345678resultR=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)u算法描述01000000001011000000000110000001000101010110101101010000101100001000000

36、0100011011R=2456789012345678cqfr010001100012345678newr101000000012345678resultR=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)u算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=256789012345678cqfr010011101012345678newr10110000001234

37、5678resultR=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)u算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=256789012345678cqfr010011101012345678newr101100000012345678resultR=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7

38、,5),(7,6),(3,7),(6,3)u算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=256789012345678cqfr010011101012345678newr101100000012345678resultR=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)u算法描述010000000010110000000001100000010001010101

39、101011010100001011000010000000100011011R=256789012345678cqfr010011101012345678newr101100000012345678resultR=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)u算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=25679012345678cqfr010011101

40、012345678newr101100010012345678resultR=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)u算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=25679012345678cqfr010011101012345678newr101100010012345678resultR=(2,8),(9,4),(2,9),(2,1),(2,5),

41、(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)u算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=5679012345678cqfr100011011012345678newr121100010012345678resultR=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)u算法描述010000000010110000

42、000001100000010001010101101011010100001011000010000000100011011R=6795012345678cqfr100011011012345678newr121100010012345678resultR=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)u算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=79560

43、12345678cqfr100011011012345678newr121100010012345678resultR=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)u算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=956012345678cqfr101011011012345678newr121100210012345678resultR=(2,8),(9,4)

44、,(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)u算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=569012345678cqfr101011011012345678newr121100210012345678resultR=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)u算法描述

45、010000000010110000000001100000010001010101101011010100001011000010000000100011011R=69012345678cqfr010101101012345678newr121130210012345678resultR=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)u算法描述010000000010110000000001100000010001010101101011010100001011000010000000

46、100011011R=96012345678cqfr010101101012345678newr121130210012345678resultR=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)u算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=96012345678cqfr010101101012345678newr121130210012345678result

47、R=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)u算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=9012345678cqfr011010100012345678newr121134210012345678resultR=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7)

48、,(6,3)u算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=012345678cqfr011110100012345678newr121134214012345678resultR=(2,8),(9,4),(2,9),(2,1),(2,5),(6,2),(5,9),(5,6),(5,4),(7,5),(7,6),(3,7),(6,3)可行的子集划分为：A1=1,3,4,8A2=2,7A3=5A4=6,9group+;resulti-1=group;for(k=0;kn

49、;k+)newrk=ri-1k;elseif(newri-1!=0)rear=(rear+1)%n;cqrear=i;elseresulti-1=group;for(k=0;kn;k+)newrk=newrk+ri-1k;pre=i;while(rear!=front);voiddivision(intrN,intn,intcq,intnewr,intresult)intk,i,pre,group;for(k=0;kn;k+)cqk=k+1;front=n-1;rear=n-1;for(k=0;kn;k+)newrk=0;group=1;pre=0;dofront=(front+1)%n;i=

50、cqfront;if(ipre)group+;resulti-1=group;for(k=0;kn;k+)newrk=ri-1k;elseif(newri-1!=0)rear=(rear+1)%n;cqrear=i;elseresulti-1=group;for(k=0;kn;k+)newrk=newrk+ri-1k;pre=i;while(rear!=front);voiddivision(intrN,intn,intcq,intnewr,intresult)intk,i,pre,group;for(k=0;kn;k+)cqk=k+1;front=n-1;rear=n-1;for(k=0;k