《chap3 栈和队列.ppt》由会员分享，可在线阅读，更多相关《chap3 栈和队列.ppt（108页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三章第三章栈和队列栈和队列栈栈和和队队列列是两种特殊的线性表，它们是运算时要受到某些限制的线性表，故也称为限限定定性性的的数数据据结构结构。3.1 3.1 栈栈3.1.13.1.1栈的定义栈的定义栈：栈：限定只能在表的一端进行插入和删除的特殊的线性表限定只能在表的一端进行插入和删除的特殊的线性表 设栈设栈s=s=（a a1 1，a a2 2，.,.,a ai i，.，a an n），其中其中a a1 1是栈底元素，是栈底元素，a an n是栈顶元素。是栈顶元素。a1a2.an进栈进栈出栈出栈栈顶栈顶栈底栈底3.1 3.1 栈栈3.1.13.1.1栈的定义栈的定义栈：栈：限定只能在表的一端进行
2、插入和删除的特殊的线性表限定只能在表的一端进行插入和删除的特殊的线性表 设栈设栈s=s=（a a1 1，a a2 2，.,.,a ai i，.，a an n），其中其中a a1 1是栈底元素，是栈底元素，a an n是栈顶元素。是栈顶元素。栈顶（栈顶（top)top)：允许插入和删除的一端；允许插入和删除的一端；约定约定toptop始终指向新数据元素将存放的位置。始终指向新数据元素将存放的位置。栈底（栈底（bottom):bottom):不允许插入和删除的一端。不允许插入和删除的一端。a1a2.an进栈进栈出栈出栈栈顶栈顶栈底栈底栈的习题入栈出栈的次序判断栈的特性3.1.2栈的存储结构栈的存储
3、结构顺序栈、链栈顺序栈、链栈a2a1a1a2top(1)顺序栈：顺序栈：(2)用顺序存储结构表示的栈。用顺序存储结构表示的栈。(3)顺顺序序栈栈用用一一组组连连续续的的存存储储单单元元存存放放自自栈栈底底到到栈栈顶顶的的数数据据元元素素，一一般般用用一一维维数数组组表表示示，设设置置一一个个简简单单变变量量top指指示示栈栈顶顶位位置置，称称为为栈栈顶顶指指针针，它它始始终终指指向向待待插插入入元元素的位置。素的位置。栈中的运算：栈中的运算：1.设置空栈设置空栈；2.插入一个新的栈顶元素插入一个新的栈顶元素3.删除栈顶元素；删除栈顶元素；4.读取栈顶元素读取栈顶元素。设数组设数组S是一个顺序栈
4、，栈的最大容量是一个顺序栈，栈的最大容量stacksize=4，初始状态初始状态top=0 10S42310basestop=xtop=top+1top 10 25 30S42310topbasetop=top-1x=stop栈空栈空10进栈进栈30出栈出栈S42310Top=0top栈满栈满top=stacksize 10 25 30 40S42310top=4base进栈算法进栈算法#definestatcksize100intpush(ints,intx,int*ptop)inttop;top=*ptop;if(top=stacksize)printf(“overflow”);retur
5、n(0);elsestop=x;*ptop=+top;/*实实际际栈栈顶顶指指针针加加1*/return(1);通过地址传递，用通过地址传递，用ptop带回实际栈顶指带回实际栈顶指针针a2a3a4987654321a10top出栈算法：出栈算法：intpop(ints,int*ptop,int*py)inttop;top=*ptop;if(top=0)printf(“stackempty”);return(0);else-top;*py=stop;/*返回出栈元素返回出栈元素*/*ptop=top;return(1);通过地址传递，用通过地址传递，用ptop带回实际栈顶指带回实际栈顶指针针通过
6、指针变量通过指针变量py带回带回出栈元素出栈元素栈栈sa2a3a4987654321a10topxtop栈底栈底（2）链栈）链栈用用指指针针来来实实现现的的栈栈叫叫链链栈栈。栈栈的的容容量量事事先先不不能能估计时采用这种存储结构。估计时采用这种存储结构。链栈的类型说明如下：链栈的类型说明如下：Typedefstructlnodeintdata；structlnode next；lnode，Lstack；进栈算法进栈算法intlpush(Lstacks,inte)p=(Lstack)malloc(sizeof(lnode);p-data=e;p-next=s;s=p;return(1);base
7、S栈栈s进栈元素进栈元素e进栈算法进栈算法intlpush(Lstacks,inte)p=(Lstack)malloc(sizeof(lnode);p-data=e;p-next=s;s=p;return(1);PbaseS进栈算法进栈算法intlpush(Lstacks,inte)p=(Lstack)malloc(sizeof(lnode);p-data=e;p-next=s;s=p;return(1);PbaseSe进栈算法进栈算法intlpush(Lstacks,inte)p=(Lstack)malloc(sizeof(lnode);p-data=e;p-next=s;s=p;retur
8、n(1);PbaseSe进栈算法进栈算法intlpush(Lstacks,inte)p=(Lstack)malloc(sizeof(lnode);p-data=e;p-next=s;s=p;return(1);PbaseSSer主主程程序序srrrs子子程程序序1rst子子程程序序2rst子子程程序序33.1.3栈的应用栈的应用(1)过过程程的的嵌嵌套套(2)递递归归算算法：法：1(n=0,1)n!=n(n-1)！(n1)函数的递归调用函数的递归调用1.定义：定义：在调用一个函数的过程中直接或间接地调用该函数本身。直接调用直接调用intf(x)intx;inty,z;.z=f(x);retur
9、n(2*z);f 函数调用 f函数intf1(x)intx;inty,z;.z=f2(y);return(2*z);intf2(t)intt;inta,c;.c=f1(a);return(3+c);间接调用间接调用特点特点 是无终止的递归调用，因此，应该给定一个限制递应该给定一个限制递归次数的条件。归次数的条件。f 1函数调用 f2函数f 2函数调用 f1函数 float fac(int n)float f;if(n0)printf(“n0,data error!n”);else if(n=0|n=1)f=1;else f=fac(n-1)*n;return f;例如：写一函数求例如：写一函数
10、求n!以求4的阶乘为例：fac(4)=4*fac(3)fac(3)=3*fac(2)fac(2)=2*fac(1)fac(1)=1fac(4)=4*3*2*1fac(2)=2*1fac(3)=3*2*1下下推推回回代代利用栈实现递归调用利用栈实现递归调用主程序主程序(1)输出输出f(4);4f(4);（1）n=4top(2)s=4*f(3)n3f(3);（2）n=3（1）n=4top(3)s=3*f(2)n2f(2);（3）n=2（2）n=3（1）n=4top(4)s=2*f(1)n1（4）n=1（3）n=2（2）n=3（1）n=4topss=3*2*1;(2)3(1)4tops=2*1(3)
11、2(2)3(1)4tops=4*3*2*1(1)4top返回返回(3)2(2)3(1)4top(4)1结束结束输出输出24运算符：运算符：*/*+-（）界限符：界限符：；以表达式以表达式A*B+CD为例说明利用栈的为例说明利用栈的求值过程。求值过程。优先级：优先级：43322110（3）表达式的计算）表达式的计算操作数变量：操作数变量：ABCDA*B+C/D;top2top1初态;(a)OSNSBA*;(b)NSOST1;(c)T1=A*BNSOSDCT1/+;(d)NSOS(g)NSOST2=C/DT2T1+;(e)NSOST3;(f)T3=T2+T1NSOS思思想想：从从左左到到右右扫扫描
12、描表表达达式式，若若当当前前读读入入的的是是操操作作数数，则则进进操操作数（作数（NS）栈，若读入的符号是运算符，应进行判断：栈，若读入的符号是运算符，应进行判断：1.若若是是“（”，进进运运算算符符栈栈；若若是是“）”，当当运运算算符符栈栈顶顶是是“（”，则则弹弹出出栈栈顶顶元元素素，继继续续扫扫描描下下一一符符号号。否否则则当当前前读读入入符符号号暂暂不不处处理理，从从操操作作数数栈栈弹弹出出两两个个操操作作数数，从从运运算算符符栈栈弹弹出出一一个个运运算算符符，生生成成运运算算指指令令，结结果果送送入入操操作作数数栈栈，继继续续处处理当前读入符号。理当前读入符号。2.2.若若读读入入的的
13、运运算算符符的的优优先先级级大大于于运运算算符符栈栈顶顶的的优优先先级级，则则进进运运算算符符栈栈，继继续续扫扫描描下下一一符符号号；否否则则从从操操作作数数栈栈顶顶弹弹出出两两个个操操作作数数，从从运运算算符符栈栈弹弹出出一一个个运运算算符符，生生成成运运算算指指令令，把把结结果送入操作数栈。继续处理刚才读入的符号。果送入操作数栈。继续处理刚才读入的符号。3.3.若若读读入入的的是是“；”，且且运运算算符符栈栈顶顶的的符符号号也也是是“；”时时，则表达式处理结束。从操作数栈弹出表达式结果。则表达式处理结束。从操作数栈弹出表达式结果。4、地图四染色问题地图四染色问题“四染色四染色”定理是计算机
14、科学中著名的定理之一。定理是计算机科学中著名的定理之一。使使地地图图中中相相邻邻的的国国家家或或行行政政区区域域不不重重色色，最最少少可可用用四四种种颜色对地图着色。颜色对地图着色。证明此定理的结论，利用栈采用回溯法对地图着色。证明此定理的结论，利用栈采用回溯法对地图着色。思想：对每个行政区编号：思想：对每个行政区编号：1-71-7 对颜色编号；对颜色编号；a a、b b、c c、d d；从从第第一一号号行行政政区区开开始始逐逐一一染染色色，每每一一个个区区域域逐逐次次用用四四种种颜颜色色进进行行试试探探，若若所所取取颜颜色色与与周周围围不不重重，则则用用栈栈记记下下来来该该区区域域的的色色数
15、数，否否则则依依次次用用下下一一色色数数进进行行试试探探。若若出出现现a-da-d均均与与周周围围发发生生重重色色，则则需需退退栈栈回回溯溯，修修改改当当前前栈栈顶顶的色数。的色数。011 11 10100001010011001010110101101011011000000000R1:7,1:712345671234567Voidmapcolor(intR,intn,ints)s1=1;/1号区域染号区域染1色色I=2;J=1;/I为区域号，为区域号，J为染色号为染色号while(I=n)while(J=4)&(I=n)k=1;/k表示已经着色的区域号表示已经着色的区域号while(KI)
16、&(sK RI,K!=J)K=K+1;/若不相邻，或若相邻且不重色，对下一个区域判断。若不相邻，或若相邻且不重色，对下一个区域判断。IF(K4)THENI=I-1;J=sI+1(1)(2)(4)(5)(6)(7)(3)1#粉色粉色2#黄色黄色3#红色红色4#绿色绿色123212312243123243123241232431122341234567S1:7Voidmapcolor(intR,intn,ints)s1=1;/1号区域染号区域染1色色I=2;J=1;/I为区域号，为区域号，J为染色号为染色号while(I=n)while(J=4)&(I=n)k=1;/k表示已经着色的区域号表示已经
17、着色的区域号while(kI)&(sk RI,k!=J)k=k+1;/若不相邻，或若相邻且不重色，对下一个区域判断若不相邻，或若相邻且不重色，对下一个区域判断。IF(K4)THENI=I-1;J=sI+100000000011011010110101101010011001010000101111101234567123456711234567Voidmapcolor(intR,intn,ints)s1=1;/1号区域染号区域染1色色I=2;J=1;/I为区域号，为区域号，J为染色号为染色号while(I=n)while(J=4)&(I=n)k=1;/k表示已经着色的区域号表示已经着色的区域号
18、while(kI)&(sk RI,k!=J)k=k+1;/若不相邻，或若相邻且不重色，对下一个区域判断若不相邻，或若相邻且不重色，对下一个区域判断。IF(K4)THENI=I-1;J=sI+1011 11 101000010100110010101101011010110110000000001234567123456711234567I=2,J=1I=2,J=1k=1k=1Voidmapcolor(intR,intn,ints)s1=1;/1号区域染号区域染1色色I=2;J=1;/I为区域号，为区域号，J为染色号为染色号while(I=n)while(J=4)&(I=n)k=1;/k表示已经
19、着色的区域号表示已经着色的区域号while(kI)&(sk RI,k!=J)k=k+1;/若不相邻，或若相邻且不重色，对下一个区域判断。若不相邻，或若相邻且不重色，对下一个区域判断。IF(K4)THENI=I-1;J=sI+1011 11 101000010100110010101101011010110110000000001234567123456711234567I=2,J=2I=2,J=2k=1k=1Voidmapcolor(intR,intn,ints)s1=1;/1号区域染号区域染1色色I=2;J=1;/I为区域号，为区域号，J为染色号为染色号while(I=n)while(J=4
20、)&(I=n)k=1;/k表示已经着色的区域号表示已经着色的区域号while(kI)&(sk RI,k!=J)k=k+1=2;/若不相邻，或若相邻且不重色，对下一个区域判断。若不相邻，或若相邻且不重色，对下一个区域判断。IF(K4)THENI=I-1;J=sI+1011 11 1010000101001100101011010110101101100000000012345671234567112345671I=2,J=2I=2,J=2k=2k=2Voidmapcolor(intR,intn,ints)s1=1;/1号区域染号区域染1色色I=2;J=1;/I为区域号，为区域号，J为染色号为染色
21、号while(I=n)while(J=4)&(I=n)k=1;/k表示已经着色的区域号表示已经着色的区域号while(kI)&(sk RI,k!=J)k=k+1=2;/若不相邻，或若相邻且不重色，对下一个区域判断。若不相邻，或若相邻且不重色，对下一个区域判断。IF(K4)THENI=I-1;J=sI+1000000000110110101101011010100110010100001011111012345671234567112345671I=3,J=1I=3,J=1k=2k=22 2Voidmapcolor(intR,intn,ints)I=2;J=1;/I为区域号，为区域号，J为染色号
22、为染色号while(I=n)while(J=4)&(I=n)k=1;/k表示已经着色的区域号表示已经着色的区域号while(kI)&(sk RI,k!=J)k=k+1;/若不相邻，或若相邻且不重色，对下一个区域判断。若不相邻，或若相邻且不重色，对下一个区域判断。IF(K4)THENI=I-1;J=sI+1011 11 1010000101001100101011010110101101100000000012345671234567122341234567I=6,J=1I=6,J=1k=1k=1Voidmapcolor(intR,intn,ints)I=6;J=1;/I为区域号，为区域号，J为
23、染色号为染色号while(I=n)while(J=4)&(I=n)k=1;/k表示已经着色的区域号表示已经着色的区域号while(kI)&(sk RI,k!=J)k=k+1;/若不相邻，或若相邻且不重色，对下一个区域判断。若不相邻，或若相邻且不重色，对下一个区域判断。IF(K4)THENI=I-1;J=sI+1000000000110110101101011010100110010100001011111012345671234567432211234567I=6,J=2I=6,J=2k=1k=1Voidmapcolor(intR,intn,ints)I=6;J=1;/I为区域号，为区域号，J
24、为染色号为染色号while(I=n)while(J=4)&(I=n)k=1;/k表示已经着色的区域号表示已经着色的区域号while(kI)&(sk RI,k!=J)k=k+1;=2/若不相邻，或若相邻且不重色，对下一个区域判断。若不相邻，或若相邻且不重色，对下一个区域判断。IF(K4)THENI=I-1;J=sI+1011 11 1010000101001100101011010110101101100000000012345671234567122341234567I=6,J=2I=6,J=2k=2k=2Voidmapcolor(intR,intn,ints)I=6;J=1;/I为区域号，为
25、区域号，J为染色号为染色号while(I=n)while(J=4)&(I=n)k=1;/k表示已经着色的区域号表示已经着色的区域号while(kI)&(sk RI,k!=J)k=k+1;=2/若若不不相相邻邻，或或若若相相邻邻且且不不重重色色，对对下下一一个个区区域域判判断。断。IF(K4)THENI=I-1;J=sI+1000000000110110101101011010100110010100001011111012345671234567432211234567I=6,J=3I=6,J=3k=2k=2Voidmapcolor(intR,intn,ints)I=6;J=1;/I为区域号，
26、为区域号，J为染色号为染色号while(I=n)while(J=4)&(I=n)k=1;/k表示已经着色的区域号表示已经着色的区域号while(kI)&(sk RI,k!=J)k=k+1;/若不相邻，或若相邻且不重色，对下一个区域判断。若不相邻，或若相邻且不重色，对下一个区域判断。IF(K4)THENI=I-1;J=sI+1011 11 1010000101001100101011010110101101100000000012345671234567122341234567I=6,J=3I=6,J=3k=1k=1Voidmapcolor(intR,intn,ints)I=6;J=1;/I为区
27、域号，为区域号，J为染色号为染色号while(I=n)while(J=4)&(I=n)k=1;/k表示已经着色的区域号表示已经着色的区域号while(kI)&(sk RI,k!=J)k=k+1;=2/若若不不相相邻邻，或或若若相相邻邻且且不不重重色色，对对下下一一个个区区域域判判断。断。IF(K4)THENI=I-1;J=sI+1000000000110110101101011010100110010100001011111012345671234567432211234567I=6,J=3I=6,J=3k=2k=2Voidmapcolor(intR,intn,ints)I=6;J=1;/I为
28、区域号，为区域号，J为染色号为染色号while(I=n)while(J=4)&(I=n)k=1;/k表示已经着色的区域号表示已经着色的区域号while(kI)&(sk RI,k!=J)k=k+1;=3/若若不不相相邻邻，或或若若相相邻邻且且不不重重色色，对对下下一一个个区区域域判判断。断。IF(K4)THENI=I-1;J=sI+1000000000110110101101011010100110010100001011111012345671234567432211234567I=6,J=3I=6,J=3k=3k=3Voidmapcolor(intR,intn,ints)I=6;J=1;/I
29、为区域号，为区域号，J为染色号为染色号while(I=n)while(J=4)&(I=n)k=1;/k表示已经着色的区域号表示已经着色的区域号while(kI)&(sk RI,k!=J)k=k+1;=4/若若不不相相邻邻，或或若若相相邻邻且且不不重重色色，对对下下一一个个区区域域判判断。断。IF(K4)THENI=I-1;J=sI+1000000000110110101101011010100110010100001011111012345671234567432211234567I=6,J=3I=6,J=3k=4k=4Voidmapcolor(intR,intn,ints)I=6;J=1;/
30、I为区域号，为区域号，J为染色号为染色号while(I=n)while(J=4)&(I=n)k=1;/k表示已经着色的区域号表示已经着色的区域号while(kI)&(sk RI,k!=J)k=k+1;/若不相邻，或若相邻且不重色，对下一个区域判断。若不相邻，或若相邻且不重色，对下一个区域判断。IF(K4)THENI=I-1;J=sI+1000000000110110101101011010100110010100001011111012345671234567432211234567I=6,J=4I=6,J=4k=1k=1Voidmapcolor(intR,intn,ints)I=6;J=1;
31、/I为区域号，为区域号，J为染色号为染色号while(I=n)while(J=4)&(I=n)k=1;/k表示已经着色的区域号表示已经着色的区域号while(kI)&(sk RI,k!=J)k=k+1;=2/若若不不相相邻邻，或或若若相相邻邻且且不不重重色色，对对下下一一个个区区域域判判断。断。IF(K4)THENI=I-1;J=sI+1000000000110110101101011010100110010100001011111012345671234567432211234567I=6,J=4I=6,J=4k=2k=2Voidmapcolor(intR,intn,ints)I=6;J=1
32、;/I为区域号，为区域号，J为染色号为染色号while(I=n)while(J=4)&(I=n)k=1;/k表示已经着色的区域号表示已经着色的区域号while(kI)&(sk RI,k!=J)k=k+1;=3/若若不不相相邻邻，或或若若相相邻邻且且不不重重色色，对对下下一一个个区区域域判判断。断。IF(K4)THENI=I-1;J=sI+1000000000110110101101011010100110010100001011111012345671234567432211234567I=6,J=4I=6,J=4k=3k=3Voidmapcolor(intR,intn,ints)I=6;J=
33、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)THENI=I-1;J=sI+1000000000110110101101011010100110010100001011111012345671234567432211234567I=6,J=4I=6,J=4k=4k=4Voidmapcolor(intR,intn,ints)I=6;J
34、=1;/I为区域号，为区域号，J为染色号为染色号while(I=n)while(J=4)&(I=n)k=1;/k表示已经着色的区域号表示已经着色的区域号while(kI)&(sk RI,k!=J)k=k+1;=5/若若不不相相邻邻，或或若若相相邻邻且且不不重重色色，对对下下一一个个区区域域判判断。断。IF(K4)THENI=I-1;J=sI+1000000000110110101101011010100110010100001011111012345671234567432211234567I=6,J=4I=6,J=4k=5k=5Voidmapcolor(intR,intn,ints)I=6;
35、J=1;/I为区域号，为区域号，J为染色号为染色号while(I=n)while(J=4)&(I=n)k=1;/k表示已经着色的区域号表示已经着色的区域号while(kI)&(sk RI,k!=J)k=k+1;/若不相邻，或若相邻且不重色，对下一个区域判断。若不相邻，或若相邻且不重色，对下一个区域判断。IF(K4)THENI=I-1;J=sI+1000000000110110101101011010100110010100001011111012345671234567432211234567I=6,J=5I=6,J=5k=4k=4Voidmapcolor(intR,intn,ints)I=6
36、;J=1;/I为区域号，为区域号，J为染色号为染色号while(I=n)while(J=4)&(I=n)k=1;/k表示已经着色的区域号表示已经着色的区域号while(kI)&(sk RI,k!=J)k=k+1;/若不相邻，或若相邻且不重色，对下一个区域判断。若不相邻，或若相邻且不重色，对下一个区域判断。IF(K4)THENI=I-1;J=sI+1000000000110110101101011010100110010100001011111012345671234567432211234567I=5,J=5I=5,J=5k=4k=4Voidmapcolor(intR,intn,ints)I=
37、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;/若不相邻，或若相邻且不重色，对下一个区域判断。若不相邻，或若相邻且不重色，对下一个区域判断。IF(K4)THENI=I-1;J=sI+1000000000110110101101011010100110010100001011111012345671234567442211234567I=5,J=4I=5,J=4k=4k=4Voidmapcolor(intR,intn,ints)I
38、=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;/若不相邻，或若相邻且不重色，对下一个区域判断。若不相邻，或若相邻且不重色，对下一个区域判断。IF(K4)THENI=I-1;J=sI+1000000000110110101101011010100110010100001011111012345671234567432211234567I=5,J=4I=5,J=4k=1k=1Voidmapcolor(intR,intn,ints)
39、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;=2/若若不不相相邻邻，或或若若相相邻邻且且不不重重色色，对对下下一一个个区区域域判判断。断。IF(K4)THENI=I-1;J=sI+1000000000110110101101011010100110010100001011111012345671234567432211234567I=5,J=4I=5,J=4k=2k=2Voidmapcolor(intR,intn,ints
40、)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;=3/若若不不相相邻邻，或或若若相相邻邻且且不不重重色色，对对下下一一个个区区域域判判断。断。IF(K4)THENI=I-1;J=sI+1000000000110110101101011010100110010100001011111012345671234567432211234567I=5,J=4I=5,J=4k=3k=3Voidmapcolor(intR,intn,int
41、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)THENI=I-1;J=sI+1000000000110110101101011010100110010100001011111012345671234567432211234567I=5,J=4I=5,J=4k=4k=4Voidmapcolor(intR,intn,in
42、ts)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;=5/若若不不相相邻邻，或或若若相相邻邻且且不不重重色色，对对下下一一个个区区域域判判断。断。IF(K4)THENI=I-1;J=sI+1000000000110110101101011010100110010100001011111012345671234567432211234567I=5,J=4I=5,J=4k=5k=5Voidmapcolor(intR,intn,i
43、nts)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;=5/若若不不相相邻邻，或或若若相相邻邻且且不不重重色色，对对下下一一个个区区域域判判断。断。IF(K4)THENI=I-1;J=sI+1000000000110110101101011010100110010100001011111012345671234567432211234567I=4,J=4I=4,J=4k=5k=5Voidmapcolor(intR,intn,
44、ints)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;=5/若若不不相相邻邻，或或若若相相邻邻且且不不重重色色，对对下下一一个个区区域域判判断。断。IF(K4)THENI=I-1;J=sI+1000000000110110101101011010100110010100001011111012345671234567432211234567I=4,J=4I=4,J=4k=5k=5Voidmapcolor(intR,intn
45、,ints)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;/若不相邻，或若相邻且不重色，对下一个区域判断。若不相邻，或若相邻且不重色，对下一个区域判断。IF(K4)THENI=I-1;J=sI+1000000000110110101101011010100110010100001011111012345671234567432211234567I=4,J=4I=4,J=4k=1k=1Voidmapcolor(intR,int
46、n,ints)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;=2/若若不不相相邻邻，或或若若相相邻邻且且不不重重色色，对对下下一一个个区区域域判判断。断。IF(K4)THENI=I-1;J=sI+1000000000110110101101011010100110010100001011111012345671234567432211234567I=4,J=4I=4,J=4k=2k=2Voidmapcolor(intR,in
47、tn,ints)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;=3/若若不不相相邻邻，或或若若相相邻邻且且不不重重色色，对对下下一一个个区区域域判判断。断。IF(K4)THENI=I-1;J=sI+1000000000110110101101011010100110010100001011111012345671234567432211234567I=4,J=4I=4,J=4k=3k=3Voidmapcolor(intR,i
48、ntn,ints)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)THENI=I-1;J=sI+1000000000110110101101011010100110010100001011111012345671234567432211234567I=4,J=4I=4,J=4k=4k=4Voidmapcolor(intR,
49、intn,ints)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)THENI=I-1;J=sI+1000000000110110101101011010100110010100001011111012345671234567442211234567I=4,J=4I=4,J=4k=4k=4Voidmapcolor(intR
50、,intn,ints)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)THENI=I-1;J=sI+1000000000110110101101011010100110010100001011111012345671234567442211234567I=5,J=1I=5,J=1k=4k=4Voidmapcolor(int