例,地图四染色问题
,四染色,定理是计算机科学中著名的定理之一 。
使地图中相邻的国家或行政区域不重色,最少可用四种颜色对地图着色 。
思想,对每个行政区编号,1-7
对颜色编号； a,b,c,d；
从第一号行政区开始逐一染色,每一个区域逐次用四种颜色进行 试探,若所取颜色与周围不重,则 用栈记下来该区域的色数,否则依次用下一色数进行试探 。 若出现
a-d均与周围发生重色,则需 退栈回溯,修改当前栈顶的色数 。
思想,对每个行政区编号,1-7
对颜色编号； a,b,c,d；
a 粉色 b 黄色
c 红色 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 0
R [ 1,7,1,7 ]
1 2 3 4 5 6 7
1
2
3
4
5
6
7
Void mapcolor(int R[][],int n,int s[])
{
s[1]=1; // 1号区域染 1色
I=2; J=1; // I为区域号,J为染色号
while ( I<=n)
{ while(( J<=4)&&(I<=n))
{ k=1; // k表示已经着色的区域号
while(( K<I)&&(s[K]?R[I,K]!=J))
K=K+1; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I)
THEN J=J+1
ELSE{ s[I]=J; I=I+1; J=1; }
}
IF (J>4) THEN { I=I-1; J=s[I]+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 4
1 2 3 4 5 6 7
S [ 1,7 ]
Void mapcolor(int R[][],int n,int s[])
{ s[1]=1; // 1号区域染 1色
I=2; J=1; // I为区域号,J为染色号
while ( I<=n)
{ while(( J<=4)&&(I<=n))
{ k=1; // k表示已经着色的区域号
while(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
1
1 2 3 4 5 6 7
Void mapcolor(int R[][],int n,int s[])
{ s[1]=1; // 1号区域染 1色
I=2; J=1; // I为区域号,J为染色号
while ( I<=n)
{ while(( J<=4)&&(I<=n))
{ k=1; // k表示已经着色的区域号
while(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
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 0
1 2 3 4 5 6 7
1
2
3
4
5
6
7
1
1 2 3 4 5 6 7
I=2,J=1k=1
Void mapcolor(int R[][],int n,int s[])
{ s[1]=1; // 1号区域染 1色
I=2; J=1; // I为区域号,J为染色号
while ( I<=n)
{ while(( J<=4)&&(I<=n))
{ k=1; // k表示已经着色的区域号
while(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=2
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
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 0
1 2 3 4 5 6 7
1
2
3
4
5
6
7
1
1 2 3 4 5 6 7
I=2,J=2k=1
Void mapcolor(int R[][],int n,int s[])
{ s[1]=1; // 1号区域染 1色
I=2; J=1; // I为区域号,J为染色号
while ( I<=n)
{ while(( J<=4)&&(I<=n))
{ k=1; // k表示已经着色的区域号
while(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1=2; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=2
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
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 0
1 2 3 4 5 6 7
1
2
3
4
5
6
7
1
1 2 3 4 5 6 7
I=2,J=2
k=2
Void mapcolor(int R[][],int n,int s[])
{ s[1]=1; // 1号区域染 1色
I=2; J=1; // I为区域号,J为染色号
while ( I<=n)
{ while(( J<=4)&&(I<=n))
{ k=1; // k表示已经着色的区域号
while(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1=2; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=2
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
1
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 ( I<=n)
{ while(( J<=4)&&(I<=n))
{ k=1; // k表示已经着色的区域号
while(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
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 0
1 2 3 4 5 6 7
1
2
3
4
5
6
7
1 2 2 3 4
1 2 3 4 5 6 7
I=6,J=1k=1
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1;// 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=2
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
1 2 3 4 5 6 7
I=6,J=2k=1
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1;=2 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=2
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
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 0
1 2 3 4 5 6 7
1
2
3
4
5
6
7
1 2 2 3 4
1 2 3 4 5 6 7
I=6,J=2k=2
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1;=2 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=3
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
1 2 3 4 5 6 7
I=6,J=3k=2
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=3
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
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 0
1 2 3 4 5 6 7
1
2
3
4
5
6
7
1 2 2 3 4
1 2 3 4 5 6 7
I=6,J=3k=1
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1;=2 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=3
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
1 2 3 4 5 6 7
I=6,J=3k=2
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1;=3 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=3
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
1 2 3 4 5 6 7
I=6,J=3k=3
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1;=4 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=3
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
1 2 3 4 5 6 7
I=6,J=3k=4
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
1 2 3 4 5 6 7
I=6,J=4k=1
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1;=2 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
1 2 3 4 5 6 7
I=6,J=4k=2
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1;=3 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
1 2 3 4 5 6 7
I=6,J=4k=3
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1;=4 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
1 2 3 4 5 6 7
I=6,J=4k=4
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1;=5 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
1 2 3 4 5 6 7
I=6,J=4k=5
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=5
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
1 2 3 4 5 6 7
I=6,J=5k=4
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=5
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
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 ( I<=n)
{ while(( J<=4)&&(I<=n))
{ k=1; // k表示已经着色的区域号
while(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
44221
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 ( I<=n)
{ while(( J<=4)&&(I<=n))
{ k=1; // k表示已经着色的区域号
while(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
1 2 3 4 5 6 7
I=5,J=4k=1
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =2 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
1 2 3 4 5 6 7
I=5,J=4k=2
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =3 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
1 2 3 4 5 6 7
I=5,J=4k=3
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =4 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
1 2 3 4 5 6 7
I=5,J=4k=4
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =5 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=5
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
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 ( I<=n)
{ while(( J<=4)&&(I<=n))
{ k=1; // k表示已经着色的区域号
while(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =5 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=5
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
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 ( I<=n)
{ while(( J<=4)&&(I<=n))
{ k=1; // k表示已经着色的区域号
while(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =5 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
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 ( I<=n)
{ while(( J<=4)&&(I<=n))
{ k=1; // k表示已经着色的区域号
while(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
1 2 3 4 5 6 7
I=4,J=4k=1
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =2 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
1 2 3 4 5 6 7
I=4,J=4k=2
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =3 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
1 2 3 4 5 6 7
I=4,J=4k=3
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =4 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
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 ( I<=n)
{ while(( J<=4)&&(I<=n))
{ k=1; // k表示已经着色的区域号
while(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =4 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
44221
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 ( I<=n)
{ while(( J<=4)&&(I<=n))
{ k=1; // k表示已经着色的区域号
while(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =4 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
44221
1 2 3 4 5 6 7
I=5,J=1
k=4
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=1
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
44221
1 2 3 4 5 6 7
I=5,J=1k=1
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=2
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
44221
1 2 3 4 5 6 7
I=5,J=2k=1
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =2 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=2
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
44221
1 2 3 4 5 6 7
I=5,J=2k=2
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =3 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=2
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
44221
1 2 3 4 5 6 7
I=5,J=2k=3
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =3 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=3
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
44221
1 2 3 4 5 6 7
I=5,J=3k=3
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=3
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
44221
1 2 3 4 5 6 7
I=5,J=3k=1
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =2 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=3
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
44221
1 2 3 4 5 6 7
I=5,J=3k=2
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =3 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=3
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
44221
1 2 3 4 5 6 7
I=5,J=3k=3
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =4 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=3
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
44221
1 2 3 4 5 6 7
I=5,J=3k=4
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =5 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=3
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
44221
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 ( I<=n)
{ while(( J<=4)&&(I<=n))
{ k=1; // k表示已经着色的区域号
while(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =5 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=3
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
34221
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 ( I<=n)
{ while(( J<=4)&&(I<=n))
{ k=1; // k表示已经着色的区域号
while(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =5 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=3
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
34221
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 ( I<=n)
{ while(( J<=4)&&(I<=n))
{ k=1; // k表示已经着色的区域号
while(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
34221
1 2 3 4 5 6 7
I=6,J=1k=1
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1 =2
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
34221
1 2 3 4 5 6 7
I=6,J=2k=1
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =2 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1 =2
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
34221
1 2 3 4 5 6 7
I=6,J=2k=2
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1 =3
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
34221
1 2 3 4 5 6 7
I=6,J=3k=1
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =2 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1 =3
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
34221
1 2 3 4 5 6 7
I=6,J=3k=2
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =3 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1 =3
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
34221
1 2 3 4 5 6 7
I=6,J=3k=3
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =4 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1 =3
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
34221
1 2 3 4 5 6 7
I=6,J=3k=4
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =5 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1 =3
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
34221
1 2 3 4 5 6 7
I=6,J=3k=5
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =5 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1 =4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
34221
1 2 3 4 5 6 7
I=6,J=4k=5
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1 =4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
34221
1 2 3 4 5 6 7
I=6,J=4k=1
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =2 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1 =4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
34221
1 2 3 4 5 6 7
I=6,J=4k=2
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =3 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1 =4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
34221
1 2 3 4 5 6 7
I=6,J=4k=3
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =4 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1 =4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
34221
1 2 3 4 5 6 7
I=6,J=4k=4
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =4 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1 =5
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
34221
1 2 3 4 5 6 7
I=6,J=5k=4
a b c b
a b c
a b b d c
a b c b d c
a b c b d
a b c b d c a
a b b c d
S [ 1,7 ]
1 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)
(5)
(6) (1)(2)
(4)
(7)
(3)
(5)
(6)
作业 1,某百货公司仓库中，有一批电视机,按其价格由高到低的顺序存储在计算机中,经常发生的操作是入库和出库 。
现在又新到 m 台价格为 h 元的电视机需入库，请你为仓库管理系统 设计一种数据结构,并画出逻辑示意图。用框图的形式给出增加电视机到数据结构中（插入操作）的思想。注意：
数据元素是（数量，价格），数据元素之间的价格不同。
因为经常进行入库、出库操作，即插入、删除，故使用线性链表。
结点数据结构示意图为,价格 Pi 数量 Ni 指针域 link
数据域 data
价格由高到底的顺序存储,P1 > … > Pi-1 > Pi >… > P k
P1 N1?Pi-1 Ni-1 Pi Ni Pk Nk ^?
若,Pi-1 > h > Pi
h m
L
S
2 8375 ^
P R
(1) L=P->link;
2 8375 ^
P R S
L
L
作业 2,对以下单链表分别执行下列各程序段,并画出结果示意图,
L
S
2 8375 ^
P R
(2) R->data=P->data;
2 8575 ^
P R S
(3) R->data=P->link->data;
2 8775 ^
P R S
L
S
2 8375 ^
P R
(4) P->link->link->link->data=P->data;
2 5375 ^
P R S
L
S
2 8375 ^
P R
(5) T=P;
while(T!=NULL)
{ T->data=(T->data)*2;
T=T->link; }
L
S
2 ^
P R
10 14 6 16
L
S
2 8375 ^
P R
(6) T=P;
while(T->link!=NULL)
{ T->data=(T->data)*2;
T=T->link; }
L
S
2 ^
P R
10 14 6 8
L
S
2 8375 ^
P R
(7) P=(JD*)malloc(sizeof(JD));
P->data=10;
R->link=P;
P->link=S;
L
S
2 8375 ^
P R
(7) P=(JD*)malloc(sizeof(JD));
P->data=10;
R->link=P;
P->link=S;
P
L
S
2 8375 ^
P R
L
S
2 8375 ^
P R
(7) P=(JD*)malloc(sizeof(JD));
P->data=10;
R->link=P;
P->link=S;
P 10
L
S
2 8375 ^
P R
L
S
2 8375 ^
P R
(7) P=(JD*)malloc(sizeof(JD));
P->data=10;
R->link=P;
P->link=S;
L
S
2 8375 ^
R
P 10
L
S
2 8375 ^
P R
(7) P=(JD*)malloc(sizeof(JD));
P->data=10;
R->link=P;
P->link=S;
L
S
2 8375 ^
R
P 10
L
S
2 8375 ^
P R
(8) T=L;
T->link=P->link;
free(P);
L
S
2 837 ^
P
RT
5
L
S
2 8375 ^
P R
(9) S->link=L;
L
S
2 8375
P R
如果 S->link= =L 则 S所指向的结点为尾结点,
L
S
2 8375 ^
P R
例 若进栈序列为 3,5,7,9，
进栈过程中可以出栈，则不可能的一个出栈次序是
（ ）。
(a) 7,5,3,9
(b) 9,7,5,3
(c) 7,5,9,3
(d) 9,5,7,3
d
例 用一维数组设计栈，初态是 栈空,top=0。
现有输入序列是 a,b,c,d，经过 push,push
,pop,push,pop,push操作后，输出序列是
（ ），栈 顶指针是（ ）b,c 2
例对于下面的程序调用过程,请问入栈序列是 （ ）,
出栈次序是 （ ） 。
1,2,3
2,1,3
例,设栈 S为空，队 Q的状态是 abcd，其中 a为队首元素,d
为队尾元素，经过下面两个操作后，队 Q的状态是（ ）。
（ 1）删除队 Q中的元素，将删除的元素插入栈 S，直到队 Q为空。
（ 2）依次将栈 S中的元素插入队 Q，直到栈 S为空。
(a) abcd (b) acbd (c) dcba (d) bacd
d
c
b
afront
rear
top
队 Q 栈 S
front
rear d
c
b
a
top
队 Q 栈 Sa
b
c
dfront
rear
top
队 Q 栈 S
c
例：假役某单位每天要有一批工人向调度员报到，并等待分配工作。当有工作需要分 配时，调度员就从等待分配的工人中派一名去做该项工作；当某个工人完成了分配给他的任务后，就又回到调度室等待再次分配工作。
调度员的调度原则是在保证人人有工作的前提下，
鼓励勤快和熟练的工人。请问对应这种分配原则所采用的数据结构是什么？调度员都需要做哪些工作？
采用队列数据结构。
调度员 要做的工作：开辟一个队列结构的线性表；
设置一个队头指针和一个队尾指针；有报到的或完成任务的，就排在队尾，需要工人做工时，从队头选派工人。
例：
设下三角阵如下图：
如果按行序为主序将下三角元素 aij（ i>=j）存储在 一个一维数组 B「 1… n(n+1)/2] 中，对任意下三角元素 aij，
它在数组 B中的下标为（ ）i *( i -1 ) / 2 + j
应用举例 — 电话号码查询问题
设计一个查询某个城市或单位的私人电话号码的数据结构。
要求对任意给出的一个姓名，若该人有电话号码，则迅速找到其电话号码；否则指出该人没有电话号码。
问题描述：
设有 n个人围坐在一个圆桌周围,现从第 s个人开始报数,数到第 m的人出列,然后从出列的下一个人重新开始报数,数到第 m的人又出列,…,如此反复直到所有的人全部出列为止 。
Josephus问题是：对于任意给定的 n,s和 m,求出按出列次序得到的 n个人员的序列 。
现以 n=8,s=1,m=4为例，
应用举例 — Josephus问题
n1
n2
n3
n4
n5
n6
n7
n8
S=1; m=4;
n4 n8 n5 n2 n1 n3 n7 n6
Josephus问题用顺序表结构和循环单链表结构求解 Josephus问题的一般步骤为：
1）首先利用线性表的一些运算如创建空线性表、插入元素等构造 Josephus表；
2）从 Josephus表中的第 s个结点开始寻找、输出和删除表中的第 m个结点，然后再从该结点后的下一结点开始寻找、输出和删除表中的第 m个结点，重复此过程，直到 Josephus表中的所有元素都删除。
应用举例 — 田径赛的时间安排问题
设六个项目的比赛：跳高、跳远、标枪、铅球,100米和 200米
规定每个选手至多参加三个项目的比赛。
现有五名选手报名比赛，选手所选择的项目如参赛选手比赛项目表所示。
要求设计一个竞赛日程安排表，使得在尽可以短的时间内安排完比赛。
（ 1）为了能较好地解决这个问题，首先应该选择一个合适的数据结构来表示它。
（ 2）抽象为对无向图进行“着色”操作：每种颜色表示一个比赛时间，着同一种颜色的顶点是可以安排在同一时间内竞赛的项目。
由此可得：只要安排 4个不同的时间竞赛即可。时间 1内可以比赛跳高（ A）和标枪（ C），时间 2内可以比赛跳远（ B）和铅球
（ D），时间 3和时间 4内分别比赛 100米（ E）和 200米（ F）。
（顶点代表竞赛项目，在所有的两个不能同时进行比赛的项目之间连上一条边）
,四染色,定理是计算机科学中著名的定理之一 。
使地图中相邻的国家或行政区域不重色,最少可用四种颜色对地图着色 。
思想,对每个行政区编号,1-7
对颜色编号； a,b,c,d；
从第一号行政区开始逐一染色,每一个区域逐次用四种颜色进行 试探,若所取颜色与周围不重,则 用栈记下来该区域的色数,否则依次用下一色数进行试探 。 若出现
a-d均与周围发生重色,则需 退栈回溯,修改当前栈顶的色数 。
思想,对每个行政区编号,1-7
对颜色编号； a,b,c,d；
a 粉色 b 黄色
c 红色 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 0
R [ 1,7,1,7 ]
1 2 3 4 5 6 7
1
2
3
4
5
6
7
Void mapcolor(int R[][],int n,int s[])
{
s[1]=1; // 1号区域染 1色
I=2; J=1; // I为区域号,J为染色号
while ( I<=n)
{ while(( J<=4)&&(I<=n))
{ k=1; // k表示已经着色的区域号
while(( K<I)&&(s[K]?R[I,K]!=J))
K=K+1; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I)
THEN J=J+1
ELSE{ s[I]=J; I=I+1; J=1; }
}
IF (J>4) THEN { I=I-1; J=s[I]+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 4
1 2 3 4 5 6 7
S [ 1,7 ]
Void mapcolor(int R[][],int n,int s[])
{ s[1]=1; // 1号区域染 1色
I=2; J=1; // I为区域号,J为染色号
while ( I<=n)
{ while(( J<=4)&&(I<=n))
{ k=1; // k表示已经着色的区域号
while(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
1
1 2 3 4 5 6 7
Void mapcolor(int R[][],int n,int s[])
{ s[1]=1; // 1号区域染 1色
I=2; J=1; // I为区域号,J为染色号
while ( I<=n)
{ while(( J<=4)&&(I<=n))
{ k=1; // k表示已经着色的区域号
while(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
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 0
1 2 3 4 5 6 7
1
2
3
4
5
6
7
1
1 2 3 4 5 6 7
I=2,J=1k=1
Void mapcolor(int R[][],int n,int s[])
{ s[1]=1; // 1号区域染 1色
I=2; J=1; // I为区域号,J为染色号
while ( I<=n)
{ while(( J<=4)&&(I<=n))
{ k=1; // k表示已经着色的区域号
while(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=2
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
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 0
1 2 3 4 5 6 7
1
2
3
4
5
6
7
1
1 2 3 4 5 6 7
I=2,J=2k=1
Void mapcolor(int R[][],int n,int s[])
{ s[1]=1; // 1号区域染 1色
I=2; J=1; // I为区域号,J为染色号
while ( I<=n)
{ while(( J<=4)&&(I<=n))
{ k=1; // k表示已经着色的区域号
while(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1=2; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=2
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
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 0
1 2 3 4 5 6 7
1
2
3
4
5
6
7
1
1 2 3 4 5 6 7
I=2,J=2
k=2
Void mapcolor(int R[][],int n,int s[])
{ s[1]=1; // 1号区域染 1色
I=2; J=1; // I为区域号,J为染色号
while ( I<=n)
{ while(( J<=4)&&(I<=n))
{ k=1; // k表示已经着色的区域号
while(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1=2; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=2
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
1
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 ( I<=n)
{ while(( J<=4)&&(I<=n))
{ k=1; // k表示已经着色的区域号
while(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
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 0
1 2 3 4 5 6 7
1
2
3
4
5
6
7
1 2 2 3 4
1 2 3 4 5 6 7
I=6,J=1k=1
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1;// 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=2
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
1 2 3 4 5 6 7
I=6,J=2k=1
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1;=2 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=2
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
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 0
1 2 3 4 5 6 7
1
2
3
4
5
6
7
1 2 2 3 4
1 2 3 4 5 6 7
I=6,J=2k=2
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1;=2 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=3
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
1 2 3 4 5 6 7
I=6,J=3k=2
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=3
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
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 0
1 2 3 4 5 6 7
1
2
3
4
5
6
7
1 2 2 3 4
1 2 3 4 5 6 7
I=6,J=3k=1
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1;=2 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=3
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
1 2 3 4 5 6 7
I=6,J=3k=2
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1;=3 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=3
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
1 2 3 4 5 6 7
I=6,J=3k=3
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1;=4 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=3
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
1 2 3 4 5 6 7
I=6,J=3k=4
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
1 2 3 4 5 6 7
I=6,J=4k=1
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1;=2 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
1 2 3 4 5 6 7
I=6,J=4k=2
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1;=3 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
1 2 3 4 5 6 7
I=6,J=4k=3
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1;=4 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
1 2 3 4 5 6 7
I=6,J=4k=4
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1;=5 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
1 2 3 4 5 6 7
I=6,J=4k=5
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=5
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
1 2 3 4 5 6 7
I=6,J=5k=4
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=5
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
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 ( I<=n)
{ while(( J<=4)&&(I<=n))
{ k=1; // k表示已经着色的区域号
while(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
44221
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 ( I<=n)
{ while(( J<=4)&&(I<=n))
{ k=1; // k表示已经着色的区域号
while(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
1 2 3 4 5 6 7
I=5,J=4k=1
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =2 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
1 2 3 4 5 6 7
I=5,J=4k=2
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =3 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
1 2 3 4 5 6 7
I=5,J=4k=3
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =4 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
1 2 3 4 5 6 7
I=5,J=4k=4
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =5 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=5
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
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 ( I<=n)
{ while(( J<=4)&&(I<=n))
{ k=1; // k表示已经着色的区域号
while(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =5 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=5
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
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 ( I<=n)
{ while(( J<=4)&&(I<=n))
{ k=1; // k表示已经着色的区域号
while(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =5 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
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 ( I<=n)
{ while(( J<=4)&&(I<=n))
{ k=1; // k表示已经着色的区域号
while(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
1 2 3 4 5 6 7
I=4,J=4k=1
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =2 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
1 2 3 4 5 6 7
I=4,J=4k=2
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =3 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
1 2 3 4 5 6 7
I=4,J=4k=3
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =4 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
43221
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 ( I<=n)
{ while(( J<=4)&&(I<=n))
{ k=1; // k表示已经着色的区域号
while(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =4 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
44221
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 ( I<=n)
{ while(( J<=4)&&(I<=n))
{ k=1; // k表示已经着色的区域号
while(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =4 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
44221
1 2 3 4 5 6 7
I=5,J=1
k=4
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=1
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
44221
1 2 3 4 5 6 7
I=5,J=1k=1
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=2
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
44221
1 2 3 4 5 6 7
I=5,J=2k=1
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =2 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=2
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
44221
1 2 3 4 5 6 7
I=5,J=2k=2
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =3 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=2
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
44221
1 2 3 4 5 6 7
I=5,J=2k=3
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =3 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=3
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
44221
1 2 3 4 5 6 7
I=5,J=3k=3
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=3
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
44221
1 2 3 4 5 6 7
I=5,J=3k=1
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =2 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=3
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
44221
1 2 3 4 5 6 7
I=5,J=3k=2
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =3 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=3
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
44221
1 2 3 4 5 6 7
I=5,J=3k=3
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =4 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=3
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
44221
1 2 3 4 5 6 7
I=5,J=3k=4
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =5 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=3
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
44221
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 ( I<=n)
{ while(( J<=4)&&(I<=n))
{ k=1; // k表示已经着色的区域号
while(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =5 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=3
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
34221
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 ( I<=n)
{ while(( J<=4)&&(I<=n))
{ k=1; // k表示已经着色的区域号
while(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =5 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1=3
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
34221
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 ( I<=n)
{ while(( J<=4)&&(I<=n))
{ k=1; // k表示已经着色的区域号
while(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
34221
1 2 3 4 5 6 7
I=6,J=1k=1
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1 =2
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
34221
1 2 3 4 5 6 7
I=6,J=2k=1
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =2 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1 =2
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
34221
1 2 3 4 5 6 7
I=6,J=2k=2
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1 =3
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
34221
1 2 3 4 5 6 7
I=6,J=3k=1
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =2 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1 =3
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
34221
1 2 3 4 5 6 7
I=6,J=3k=2
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =3 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1 =3
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
34221
1 2 3 4 5 6 7
I=6,J=3k=3
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =4 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1 =3
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
34221
1 2 3 4 5 6 7
I=6,J=3k=4
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =5 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1 =3
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
34221
1 2 3 4 5 6 7
I=6,J=3k=5
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =5 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1 =4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
34221
1 2 3 4 5 6 7
I=6,J=4k=5
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1 =4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
34221
1 2 3 4 5 6 7
I=6,J=4k=1
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =2 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1 =4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
34221
1 2 3 4 5 6 7
I=6,J=4k=2
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =3 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1 =4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
34221
1 2 3 4 5 6 7
I=6,J=4k=3
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =4 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1 =4
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
34221
1 2 3 4 5 6 7
I=6,J=4k=4
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(( k<I)&&(s[k]?R[I,k]!=J))
k=k+1; =4 // 若不相邻,或若相邻且不重色,对下一个区域判断 。
IF (K<I) //相邻且重色
THEN J=J+1 =5
ELSE{ s[I]=J; I=I+1; J=1; }//相邻且不重色
}
IF (J>4) THEN { I=I-1; J=s[I]+1 }}
}
0000000
0011011
0101101
0110101
0011001
0100001
011 11 10
1 2 3 4 5 6 7
1
2
3
4
5
6
7
34221
1 2 3 4 5 6 7
I=6,J=5k=4
a b c b
a b c
a b b d c
a b c b d c
a b c b d
a b c b d c a
a b b c d
S [ 1,7 ]
1 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)
(5)
(6) (1)(2)
(4)
(7)
(3)
(5)
(6)
作业 1,某百货公司仓库中，有一批电视机,按其价格由高到低的顺序存储在计算机中,经常发生的操作是入库和出库 。
现在又新到 m 台价格为 h 元的电视机需入库，请你为仓库管理系统 设计一种数据结构,并画出逻辑示意图。用框图的形式给出增加电视机到数据结构中（插入操作）的思想。注意：
数据元素是（数量，价格），数据元素之间的价格不同。
因为经常进行入库、出库操作，即插入、删除，故使用线性链表。
结点数据结构示意图为,价格 Pi 数量 Ni 指针域 link
数据域 data
价格由高到底的顺序存储,P1 > … > Pi-1 > Pi >… > P k
P1 N1?Pi-1 Ni-1 Pi Ni Pk Nk ^?
若,Pi-1 > h > Pi
h m
L
S
2 8375 ^
P R
(1) L=P->link;
2 8375 ^
P R S
L
L
作业 2,对以下单链表分别执行下列各程序段,并画出结果示意图,
L
S
2 8375 ^
P R
(2) R->data=P->data;
2 8575 ^
P R S
(3) R->data=P->link->data;
2 8775 ^
P R S
L
S
2 8375 ^
P R
(4) P->link->link->link->data=P->data;
2 5375 ^
P R S
L
S
2 8375 ^
P R
(5) T=P;
while(T!=NULL)
{ T->data=(T->data)*2;
T=T->link; }
L
S
2 ^
P R
10 14 6 16
L
S
2 8375 ^
P R
(6) T=P;
while(T->link!=NULL)
{ T->data=(T->data)*2;
T=T->link; }
L
S
2 ^
P R
10 14 6 8
L
S
2 8375 ^
P R
(7) P=(JD*)malloc(sizeof(JD));
P->data=10;
R->link=P;
P->link=S;
L
S
2 8375 ^
P R
(7) P=(JD*)malloc(sizeof(JD));
P->data=10;
R->link=P;
P->link=S;
P
L
S
2 8375 ^
P R
L
S
2 8375 ^
P R
(7) P=(JD*)malloc(sizeof(JD));
P->data=10;
R->link=P;
P->link=S;
P 10
L
S
2 8375 ^
P R
L
S
2 8375 ^
P R
(7) P=(JD*)malloc(sizeof(JD));
P->data=10;
R->link=P;
P->link=S;
L
S
2 8375 ^
R
P 10
L
S
2 8375 ^
P R
(7) P=(JD*)malloc(sizeof(JD));
P->data=10;
R->link=P;
P->link=S;
L
S
2 8375 ^
R
P 10
L
S
2 8375 ^
P R
(8) T=L;
T->link=P->link;
free(P);
L
S
2 837 ^
P
RT
5
L
S
2 8375 ^
P R
(9) S->link=L;
L
S
2 8375
P R
如果 S->link= =L 则 S所指向的结点为尾结点,
L
S
2 8375 ^
P R
例 若进栈序列为 3,5,7,9，
进栈过程中可以出栈，则不可能的一个出栈次序是
（ ）。
(a) 7,5,3,9
(b) 9,7,5,3
(c) 7,5,9,3
(d) 9,5,7,3
d
例 用一维数组设计栈，初态是 栈空,top=0。
现有输入序列是 a,b,c,d，经过 push,push
,pop,push,pop,push操作后，输出序列是
（ ），栈 顶指针是（ ）b,c 2
例对于下面的程序调用过程,请问入栈序列是 （ ）,
出栈次序是 （ ） 。
1,2,3
2,1,3
例,设栈 S为空，队 Q的状态是 abcd，其中 a为队首元素,d
为队尾元素，经过下面两个操作后，队 Q的状态是（ ）。
（ 1）删除队 Q中的元素，将删除的元素插入栈 S，直到队 Q为空。
（ 2）依次将栈 S中的元素插入队 Q，直到栈 S为空。
(a) abcd (b) acbd (c) dcba (d) bacd
d
c
b
afront
rear
top
队 Q 栈 S
front
rear d
c
b
a
top
队 Q 栈 Sa
b
c
dfront
rear
top
队 Q 栈 S
c
例：假役某单位每天要有一批工人向调度员报到，并等待分配工作。当有工作需要分 配时，调度员就从等待分配的工人中派一名去做该项工作；当某个工人完成了分配给他的任务后，就又回到调度室等待再次分配工作。
调度员的调度原则是在保证人人有工作的前提下，
鼓励勤快和熟练的工人。请问对应这种分配原则所采用的数据结构是什么？调度员都需要做哪些工作？
采用队列数据结构。
调度员 要做的工作：开辟一个队列结构的线性表；
设置一个队头指针和一个队尾指针；有报到的或完成任务的，就排在队尾，需要工人做工时，从队头选派工人。
例：
设下三角阵如下图：
如果按行序为主序将下三角元素 aij（ i>=j）存储在 一个一维数组 B「 1… n(n+1)/2] 中，对任意下三角元素 aij，
它在数组 B中的下标为（ ）i *( i -1 ) / 2 + j
应用举例 — 电话号码查询问题
设计一个查询某个城市或单位的私人电话号码的数据结构。
要求对任意给出的一个姓名，若该人有电话号码，则迅速找到其电话号码；否则指出该人没有电话号码。
问题描述：
设有 n个人围坐在一个圆桌周围,现从第 s个人开始报数,数到第 m的人出列,然后从出列的下一个人重新开始报数,数到第 m的人又出列,…,如此反复直到所有的人全部出列为止 。
Josephus问题是：对于任意给定的 n,s和 m,求出按出列次序得到的 n个人员的序列 。
现以 n=8,s=1,m=4为例，
应用举例 — Josephus问题
n1
n2
n3
n4
n5
n6
n7
n8
S=1; m=4;
n4 n8 n5 n2 n1 n3 n7 n6
Josephus问题用顺序表结构和循环单链表结构求解 Josephus问题的一般步骤为：
1）首先利用线性表的一些运算如创建空线性表、插入元素等构造 Josephus表；
2）从 Josephus表中的第 s个结点开始寻找、输出和删除表中的第 m个结点，然后再从该结点后的下一结点开始寻找、输出和删除表中的第 m个结点，重复此过程，直到 Josephus表中的所有元素都删除。
应用举例 — 田径赛的时间安排问题
设六个项目的比赛：跳高、跳远、标枪、铅球,100米和 200米
规定每个选手至多参加三个项目的比赛。
现有五名选手报名比赛，选手所选择的项目如参赛选手比赛项目表所示。
要求设计一个竞赛日程安排表，使得在尽可以短的时间内安排完比赛。
（ 1）为了能较好地解决这个问题，首先应该选择一个合适的数据结构来表示它。
（ 2）抽象为对无向图进行“着色”操作：每种颜色表示一个比赛时间，着同一种颜色的顶点是可以安排在同一时间内竞赛的项目。
由此可得：只要安排 4个不同的时间竞赛即可。时间 1内可以比赛跳高（ A）和标枪（ C），时间 2内可以比赛跳远（ B）和铅球
（ D），时间 3和时间 4内分别比赛 100米（ E）和 200米（ F）。
（顶点代表竞赛项目，在所有的两个不能同时进行比赛的项目之间连上一条边）
