第三章数据结构栈.ppt

1、第三章 栈和队列,第三章 栈和队列,3.1 栈 3.2 队列,栈和队列 是两种特殊的线性表，它们是运算时要受到某些限制的线性表，故也称为限定性的数据结构。,栈和队列,栈和队列是两种特殊的线性表，它们是运算时要受到某些限制的线性表，故也称为限定性的数据结构。,3.1.1 栈的概念,进栈,出栈,栈顶,栈底,栈：限定只能在表的一端进行插入和删除的特殊的线性表,设栈s=（a1，a2，. . . ,ai，. . . ，an）， 其中a1是栈底元素， an是栈顶元素。,一、什么是栈？,栈顶（top)：允许插入和删除的一端； 约定top始终指向新数据元素将存放的位置。 栈底（bottom):不允许插入和删除

2、的一端。,栈的示意图,出栈,进栈,栈的特点 后进先出,第一个进栈的元素在栈底，最后一个进栈的元素在栈顶， 第一个出栈的元素为栈顶元素， 最后一个出栈的元素为栈底元素,1）构造一个空栈S； 2） 进栈操作Push3）出栈操作Pop4) 取栈顶元素top,二 栈的基本操作,设数组S是一个顺序栈，栈的最大容量stacksize=4 ，初始状态top=0,10,S4,2,3,1,0,base,top=top+1 stop=x,top,10,25,30,S4,2,3,1,0,top,base,x=stop top=top-1,栈空,10进栈,30出栈,top,栈满,top=stacksize-1,10,

3、25,30,40,S4,2,3,1,0,top=3,base,3.1.2 栈的存储结构,top,一 顺序栈： 用顺序存储结构表示的栈。,顺序栈 链栈,1 栈的顺序存储结构,因素 :,空间：- data ,当前栈顶位置-top,提示：s.top s.data s.top 空栈：s.top = -1 栈满：s.top = maxsize-1;,class Seq_Stack /顺序栈的容量 private int maxsize; /数组，用于存储顺序栈中的数据元素 private T data; /指示顺序栈的栈顶 private int top;,构建空栈算法,public Seq_Stack

4、(int size) data = new Tsize; maxsize = size; top = -1; , 进栈算法 public void Push(T x), if (IsFull() Console.WriteLine(Stack is full); return; data+top = x; /push,a1,a2,a3,9,8,7,6,5,4,3,2,1,a0,0,top,e,top,出栈算法： public T Pop(), T x = default(T); if (IsEmpty() Console.WriteLine(Stack is empty); Return x;

5、 x = datatop; -top; Return x; ,top,top,top,栈底,二 链栈 用指针来实现的栈叫链栈。栈的容量事先不能估计时采用这种存储结构。,public class LinkStack /栈顶指示器 private StackNode top; /栈中结点的个数 private int size; /初始化链栈 public LinkStack() top = null; size = 0; ,/入栈操作 public void Push(T item) StackNode q = new StackNode(item); if (top = null) top =

6、 q; else q.next = top; top = q; +size; ,base,top,进栈元素,进栈算法 public void Push(T item) StackNode q = new StackNode(item); if (top = null) top = q; else q.next = top; top = q; +size; ,base,top,进栈算法 public void Push(T item) StackNode q = new StackNode(item); if (top = null) top = q; else q.next = top; to

7、p = q; +size; ,top,进栈算法 public void Push(T item) StackNode q = new StackNode(item); if (top = null) top = q; else q.next = top; top = q; +size; ,base,Top,item, 问题提出 ： 上溢-方法-,分配足够大的空间；多栈；浪费惊人且无法估计,共享， 动态利用其他的栈,两栈共享:,bottom1 top1 top2 bottom2,定义：,ElemType data ; int Top 2 ;,空栈： top1=bottom1=0 top2 = b

8、ottom 2 =maxstack 栈满： top1 = top2,n 个栈 （每个栈maxstack / n ）,bot1 bot2 botn,top1 top2 topn, 第i栈上溢 ： topi = bot i+1 方法 ： 找离 i 最近的还未满的栈 - 之间的元素统统左（右）移, 问题提出 ： 上溢-方法-,分配足够大的空间；多栈；浪费惊人且无法估计,共享， 动态利用其他的栈,r,主程序,3.1.4 栈的应用 (1) 过程的嵌套,(2) 递归算法：,1 (n=0,1) n! = n(n-1)！ (n1),函数的递归调用,1. 定义： 在调用一个函数的过程中直接或间接地调用该函数本身

9、。 直接调用 int f(x) int x; int y,z; . z=f(x); return (2*z); ,f 函数,调用 f函数,int f1(x) int x; int y,z; . z=f2( y); return (2*z); ,int f2(t) int t; int a,c; . c=f1(a); return (3+c); ,间接调用,特点 是无终止的递归调用，因此，应该给定一个限制递归次数的条件。,float fac ( int n) float f; if(n0) printf(“n0,data error!n”); else if(n= =0|n= =1) f=1;

10、else f=fac(n-1)* n ; return f; ,例如：写一函数求n!,以求4的阶乘为例：,fac(4)=4*fac(3),fac(3)=3*fac( 2),fac(2)=2*fac( 1),fac(1)=1,fac(4)=4*3*2*1,fac(2)=2*1,fac(3)=3*2*1,下 推,回 代,利用栈实现递归调用,汉诺塔 问题,汉诺塔 问题 是印度的一个古老的传说。 开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为

11、帮助，但每次只能搬一个，而且大的不能放在小的上面。解答结果请自己运行计算，程序见尾部。面对庞大的数字(移动圆片的次数)18446744073709551615，看来，众僧们耗尽毕生精力也不可能完成金片的移动。,逆向推理： 1.假如一个和尚能把上面63个盘子先搬到B座，第二个和尚再把最大的那个移到C，第三个和尚再把63个盘子移到C座；至此整个工作就完成的。 2.问题是怎么才能把63个盘子移到B座，按照同样的方法，先把62个盘子选移到C座，再把第63个盘子移到B座，最后再将62个盘子移到B座。 3如此类推; 4.从上面分析可以看出：只有等后面那个和尚搬完盘子，前面的和尚才能够去完成任。让我们来栈的

12、数据结构：数据的处理只在一端处理，且是先进后出。所以用递归的方法去处理是正确的。,算法思路： 1.如果只有一个金片，则把该金片从源移动到目标棒，结束。 2.如果有n个金片，则把前n-1个金片移动到辅助的棒，然后把自己移动到目标棒，最后再把前n-1个移动到目标棒. 3.单纯对于有N个金片要挪动的步数求出, 可以使用递推方法,满足递推方程f(i) = f(i - 1) * 2 + 1.,usingSystem; usingSystem.Collections.Generic; usingSystem.Text; namespaceHanoiProgram classProgram staticin

13、tcount=0;/计数，总共搬动盘子的次数； staticvoidPrintMove(charx,chary) Console.WriteLine(0-1,x,y) staticvoidHanoi(intn,charone,chartwo,charthree) if(n=1) +count; PrintMove(one,three); else +count; /借助中间塔把第N个盘上面(n-1)个盘子的搬移到另一个盘； Hanoi(n-1,one,three,two); /打印第N个盘移到目标塔的步骤； PrintMove(one,three); /借助中间塔把原来第N个盘子上面的（n-1

14、）个盘子搬到现在第N个盘子所在的塔上; Hanoi(n-1,two,one,three); ,staticvoidMain(stringargs) Console.WriteLine(开始搬64个盘子 .); Hanoi(64,A,B,C); Console.WriteLine(搬迁结速；一共进行了0次的搬迁。,count); Console.Read(); ,3、栈的应用举例,例 表达式求值 1）问题的提出 设计一个小计算器: 对键入的表达式进行求值。,高级语言中的赋值语句：变量=表达式；,2） 表达式的构成 操作数+运算符+界符（如括号） 3） 表达式的求值： 例 5+6 (1+2)- 4

15、 按照四则运算法则，上述表达式的计算过程为： 5+6 (1+2)- 4=5+6 3- 4 = 5+18-4= 23-4=19,栈的应用举例,1,2,3,4,4） 算符优先关系表 表达式中任何相邻运算符c1、c2的优先关系有： c1c2：c1的优先级高于c2,算符间的优先关系表,注： c1 c2是相邻算符， c1在左， c2在右,算符的优先级设置,栈的应用举例,5 算符优先算法,从左向右扫描表达式： 遇操作数保存； 遇运算符号cj与前面的刚扫描过的运算符ci比较 若cicj 则说明ci是已扫描的运算符中优先级最高者，可进行运算； 若ci = cj 则ci为（，cj 为 ），说明括号内的式子已计算

16、完，需要消去括号；,5 + 4 (1 + 2) - 6,后面也许有优先级更高的算符,+,+,(,后保存的算符有优先级高,用两个栈分别保存扫描过程中遇到的操作数和运算符,问题,判断是运算符还是数据？,- 设OP 为操作符集合 - 判断W是操作符函数：In(w,OP),判断运算符的优先级？,- Precede(c1,c2),运算？,- Operate(a, op, b),算符比较算法,Char Precede( char c1, char c2) int c_temp1, c_temp2; switch(c1) case * : case / : c_temp1=4; break; case +

17、: case - : c_temp1=2; break; . . . . . . switch(c2) case * : case / : c_temp2=3; break; case + : case - : c_temp2=1; break; . . . . . . ,c1是栈内；c2是栈外,确定c1,c2 的优先级 - c_temp,续,if (c_temp1c_temp2) return( ); ,确定优先级比较结果,表达式求值示意图：5+6(1+2)-4,#,5,+,6,(,1,+,2,3,18,23,-,4,19,5,读入表达式过程：,+,6,(,1,+,2,),-,4,#,=19

18、,1+2=3,63=18,5+18=23,23-4=19,栈的应用举例,在算符优先算法中，建立了两个工作栈。一个是OPTR栈，用以保存运算符一个是OPND栈，用以保存操作数或运算结果。int express ( ) /运算数栈，OP为运算符集合。 InitStack(OPTR); Push (OPTR, # ); InitStack(OPND); w=getchar( ); While(w!= # | GetTop(OPTR)!=#) if(! In(w,OP)Push(OPND,w);w=getchar(); /不是运算符则进栈 else / In(w, OP)判断c是否 是运算符的函数,3

19、.2 栈的应用举例,续 switch (Precede(GetTop(OPTR), w) ) case : /新输入的算符c优先级低，即栈顶算符优先权高， /出栈并将运算结果入栈OPND op=Pop(OPTR); b=Pop(OPND); a= Pop(OPND); Push(OPND, Operate(a, op, b); break; return GetTop(OPND); ,小 结 1 栈是限定仅能在表尾一端进行插入、 删除操作的线性表； 2 栈的元素具有后进先出的特点； 3 栈顶元素的位置由一个称为栈顶指针的 变量指示， 进栈、出栈操作要修改栈顶指针；,3.1 栈,A*B + C/

20、D;,top2,思想：从左到右扫描表达式，若当前读入的是操作数，则进操作数（NS）栈，若读入的符号是运算符，应进行判断： 若是“（”，进运算符栈；若是“）”，当运算符栈顶是“（”，则弹出栈顶元素，继续扫描下一符号。否则当前读入符号暂不处理，从操作数栈弹出两个操作数，从运算符栈弹出一个运算符，生成运算指令，结果送入操作数栈，继续处理当前读入符号。 2.若读入的运算符的优先级大于运算符栈顶的优先级，则进运算符栈，继续扫描下一符号；否则从操作数栈顶弹出两个操作数，从运算符栈弹出一个运算符，生成运算指令，把结果送入操作数栈。继续处理刚才读入的符号。 3. 若读入的是“；”，且运算符栈顶的符号也是“；”

21、时，则表达式处理结束。从操作数栈弹出表达式结果。,输入：表达式符号序列,表达式求值算法：,输出：表达式值 y,初始化栈 NS、OS,Push (OS, “;” , top2)； t=0; /表示扫描下一个符号 while (t 2) IF t=0 THEN read W;,IF W 为操作数 THEN Push( NS, W, top1),ELSE p=OStop2; /读运算符栈栈顶元素，存入p .,IF (Wp)or(W=“(“) THEN,Push (OS, W, top2); t=0;,ELSE IF (p=“;” ）and (W=“ ;”) THEN, Pop (NS, y,top1

22、); t=2; /处理过程结束,ELSE IF (p=“(“ )and (w=“）”）THEN,ELSE Pop(NS,x,top1);,Pop(NS,z,top1);,Pop(OS,p,top2）；,x=z x;,Push(NS ,x ,top1);,t=1; /t=1,当前的符号下次重新考虑,输出 y; return;, Pop(OS ,p,top2); t=0; ,4、 地图四染色问题 “四染色”定理是计算机科学中著名的定理之一。 使地图中相邻的国家或行政区域不重色，最少可用四种颜色对地图着色。 证明此定理的结论，利用栈采用回溯法对地图着色。 思想：对每个行政区编号：1-7 对颜色编号；

23、a、b、c、d； 从第一号行政区开始逐一染色，每一个区域逐次用四种颜色进行试探，若所取颜色与周围不重，则用栈记下来该区域的色数，否则依次用下一色数进行试探。若出现a-d均与周围发生重色，则需退栈回溯，修改当前栈顶的色数。,1 2 3 4 5 6 7,1 2 3 4 5 6 7,(1),(2),(4),(5),(6),(7),(3),1# 粉色 2# 黄色 3# 红色 4# 绿色,1 2 3 4 5 6 7,S 1 : 7 ,说明：,i-区号 si-第i区颜色号 j-颜色号 Rmn- m区n区相邻,初始化：第1区=1号颜色,准备： 区号=2 色号=1,当没填完,当色号没试完 并且 区也没填完,依

24、次和已填的区比较是否冲突,如果冲突,换下个颜色试,该区设为该色号 准备下一个,如果颜色都试过,需重改上一区的颜色,s1=1;,I=2; J=1;,i=n,J=4 i=n,冲突含义 已填完：1ki 相邻：rik=1 且 重色：sk=j,Ki,J+1,Si=j i+1 J=1,J4,i=i-1 J=si+1,Void mapcolor(int R,int n,int s) s1=1; / 1号区域染1色 I=2; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,

25、Void mapcolor(int R,int n,int s) s1=1; / 1号区域染1色 I=2; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=2,J=1,k=1,Void mapcolor(int R,int n,int s) s1=1; / 1号区域染1色 I=2; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4

26、5 6 7,I=2,J=2,k=1,Void mapcolor(int R,int n,int s) s1=1; / 1号区域染1色 I=2; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=2,J=2,k=2,Void mapcolor(int R,int n,int s) s1=1; / 1号区域染1色 I=2; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2

27、3 4 5 6 7,1 2 3 4 5 6 7,I=3,J=1,k=2,2,Void mapcolor(int R,int n,int s) I=2; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=6,J=1,k=1,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1

28、2 3 4 5 6 7,I=6,J=2,k=1,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=6,J=2,k=2,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=

29、6,J=3,k=2,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=6,J=3,k=1,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=6,J=3,k=2,Void

30、 mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=6,J=3,k=3,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=6,J=3,k=4,Void mapcolor(int

31、R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=6,J=4,k=1,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=6,J=4,k=2,Void mapcolor(int R,int n,int s)

32、 I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=6,J=4,k=3,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=6,J=4,k=4,Void mapcolor(int R,int n,int s) I=6; J=1; / I

33、为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=6,J=4,k=5,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=6,J=5,k=4,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 whi

34、le ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=5,J=5,k=4,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=5,J=4,k=4,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN

35、I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=5,J=4,k=1,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=5,J=4,k=2,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1

36、,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=5,J=4,k=3,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=5,J=4,k=4,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7

37、,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=5,J=4,k=5,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=4,J=4,k=5,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7

38、,1 2 3 4 5 6 7,I=4,J=4,k=5,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=4,J=4,k=1,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7

39、,I=4,J=4,k=2,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=4,J=4,k=3,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=4,J=4,k=4,V

40、oid mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=4,J=4,k=4,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=5,J=1,k=4,Void mapcolor(i

41、nt R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=5,J=1,k=1,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=5,J=2,k=1,Void mapcolor(int R,int n,int

42、 s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=5,J=2,k=2,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=5,J=2,k=3,Void mapcolor(int R,int n,int s) I=6; J=1;

43、/ I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=5,J=3,k=3,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=5,J=3,k=1,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号

44、while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=5,J=3,k=2,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=5,J=3,k=3,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) TH

45、EN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=5,J=3,k=4,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=5,J=3,k=5,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI

46、+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=5,J=3,k=5,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=6,J=1,k=5,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5

47、6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=6,J=1,k=1,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=6,J=2,k=1,Void mapcolor(int R,int n,int s) I=6; J=1; / I为区域号，J为染色号 while ( I4) THEN I=I-1; J=sI+1 ,1 2 3 4 5 6 7,1 2 3 4 5 6 7,1 2 3 4 5 6 7,I=6,J=2,k=2,Void mapcolor(int R,int n,int s) I=6; J=1;