第04讲ch栈和队列

1、第三章 栈和队列栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性DS3.1 栈（stack）栈的定义和特点v定义：限定仅在表尾进行插入或删除操作的线性表，表尾栈顶，表头栈底，不含元素的空表称空栈v特点：先进后出（FILO）或后进先出（LIFO）ana1a2.栈底栈顶.出栈进栈栈s=(a1,a2,an) 线性表线性表 栈栈 队列队列Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1in+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1in栈的存储结构v顺序栈l实现：一维数组sMtop=012345

2、0栈空栈顶指针top,指向实际栈顶后的空位置，初值为0top123450进栈Atop出栈栈满BCDEF设数组维数为Mtop=0,栈空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈，则上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空base=0base=0base=0/- 栈的顺序存储表示栈的顺序存储表示 - #define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; typedef struct SElemType *base; SElemType *t

3、op; int stacksize; SqStack; 类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。l入栈算法0M-1栈1底栈1顶栈2底栈2顶l出栈算法l在一个程序中同时使用两个栈v链栈栈顶 .topdata next栈底l结点定义l入栈算法l出栈算法typedef struct node int data; struct node *next;JD; .栈底toptopxptop .栈底topq栈的应用v过程的嵌套调用r主程序主程序srrrs子过程子过程1rst子过程子过程2rst子过程子过程3例例 递归的执行情况分析递归的执行情况分析 v递归过程及其实现l递归：函数直接或间

4、接的调用自身叫l实现：建立递归工作栈 w=3;void print( int w) int i; if ( w!=0) print(w-1); for(i=1;i=w;+i) printf(“%3d,”,w); printf(“/n”); Ch3_10.c运行结果：1，2，2，3，3，3，递归调用执行情况如下：递归调用执行情况如下：主程序主程序(1)print(w) w=3; 3print(2);（1）w=3 top(2) 输出：输出：3, 3, 3w2print(1);（2）w=2 （1）w=3 top(3) 输出：输出：2, 2w1print(0);（3）w=1 （2）w=2 （1）w=3

5、 top(4)输出：输出：1w0（4）w=0 （3）w=1 （2）w=2 （1）w=3 topw(3) 输出：输出：2, 2(2) 2(1) 3top(4)输出：输出：1(3) 1(2) 2(1) 3top(2) 输出：输出：3, 3, 3 (1 ) 3top返回返回(3) 1(2) 2(1) 3top(4) 0结束结束(1)l执行情况：u递归工作栈保存内容：形参n,x,y,z和返回地址u返回地址用行编号表示n x y z 返回地址 main() int m; printf(Input number of disks”); scanf(%d,&m); printf(”Steps : %3d d

6、isks”,m); hanoi(m,A,B,C);(0) void hanoi(int n,char x,char y,char z)(1) (2) if(n=1)(3) move(1,x,z);(4) else(5) hanoi(n-1,x,z,y);(6) move(n,x,z);(7) hanoi(n-1,y,x,z);(8) (9) ABC1233 A B C 03 A B C 02 A C B 63 A B C 02 A C B 61 A B C 6ABC3 A B C 02 A C B 6 main() int m; printf(Input the number of disks

7、 scanf(%d,&m); printf(The steps to moving %3d hanoi(m,A,B,C);(0) void hanoi(int n,char x,char y,char z)(1) (2) if(n=1)(3) move(1,x,z);(4) else(5) hanoi(n-1,x,z,y);(6) move(n,x,z);(7) hanoi(n-1,y,x,z);(8) (9) ABC3 A B C 02 A C B 61 C A B 8ABC3 A B C 02 A C B 63 A B C 03 A B C 02 A C B 6 main() int m;

8、 printf(Input the number of disks scanf(%d,&m); printf(The steps to moving %3d hanoi(m,A,B,C);(0) void hanoi(int n,char x,char y,char z)(1) (2) if(n=1)(3) move(1,x,z);(4) else(5) hanoi(n-1,x,z,y);(6) move(n,x,z);(7) hanoi(n-1,y,x,z);(8) (9) ABC3 A B C 02 B A C 83 A B C 02 B A C 81 B C A 6ABC3 A B C

9、02 B A C 83 A B C 0 main() int m; printf(Input the number of disks scanf(%d,&m); printf(The steps to moving %3d hanoi(m,A,B,C);(0) void hanoi(int n,char x,char y,char z)(1) (2) if(n=1)(3) move(1,x,z);(4) else(5) hanoi(n-1,x,z,y);(6) move(n,x,z);(7) hanoi(n-1,y,x,z);(8) (9) ABC3 A B C 02 B A C 81 A B

10、 C 8ABC3 A B C 02 B A C 83 A B C 0栈空3 A B C 02 B A C 8Hanoi.c D:fengyibkcpowerpower.cv回文游戏：顺读与逆读字符串一样（不含空格）dadtop1.读入字符串2.去掉空格（原串）3.压入栈4.原串字符与出栈字符依次比较 若不等，非回文 若直到栈空都相等，回文v多进制输出：字符串：“madam im adam”例 把十进制数159转换成八进制数(159)10=(237)815981982802 3 7 余 7余 3余 2toptop7top73top732v表达式求值 中缀表达式 后缀表达式（RPN) a*b+c

11、ab*c+ a+b*c abc*+ a+(b*c+d)/e abc*d+e/+中缀表达式：操作数栈和运算符栈例 计算 2+4-3*6操作数运算符24+操作数运算符6-操作数运算符6-36*操作数运算符6-18操作数运算符12后缀表达式求值步骤：1、读入表达式一个字符2、若是操作数，压入栈，转43、若是运算符，从栈中弹出2个数，将运算结果再压入栈4、若表达式输入完毕，栈顶即表达式值； 若表达式未输入完，转1top4top43top735top例 计算 4+3*5后缀表达式：435*+top415top19(1)(2)(4)(5)(6)(7)(3)v地图四染色问题R 7 7 1 2 3 4 5 6

12、 71 2 3 4 5 6 7 1 0 0 0 0 1 00 1 1 1 1 1 01 0 1 0 1 1 01 0 1 1 0 1 01 1 0 1 1 0 01 0 0 1 1 0 00 0 0 0 0 0 01 2 3 4 5 6 7 122 3414334231# 紫色紫色 2# 黄色黄色3# 红色红色4# 绿色绿色20/500 1 2 3 4 5 6 7 8 90123456789入入口口出口出口1东东2南南3西西4北北用栈用栈S保存当前简单路保存当前简单路径，只须存最后一个通径，只须存最后一个通道块。道块。“下一个位置下一个位置”是是“当当前位置前位置”的四个方向上的四个方向上相邻

13、的方块。相邻的方块。“纳入路径纳入路径”即即“当前当前位置位置”入栈。入栈。“退回一步退回一步”即即“出栈出栈” 。3.2 队列队列的定义及特点v定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表l队尾(rear)允许插入的一端l队头(front)允许删除的一端v队列特点：先进先出(FIFO)a1 a2 a3.an 入队出队frontrear队列Q=(a1,a2,an)v双端队列a1 a2 a3.an 端1端2入队出队入队出队链队列v结点定义typedef struct node int data; struct node *next;JD;头结点 .front队头队尾rea

14、r设队首、队尾指针front和rear,front指向头结点，rear指向队尾frontrearx入队xfrontreary入队xyfrontrearx出队xyfront rear空队front reary出队v入队算法v出队算法队列的顺序存储结构v实现：用一维数组实现sqMfront=0rear=0123450队空123450frontJ1,J1,J3入队J1J2J3rearrear123450J4,J5,J6入队J4J5J6front设两个指针front,rear,约定：rear指示队尾元素；front指示队头元素空队列条件：front=rear入队列：sq+rear=x;出队列：x=sq

15、+front;rearrearfrontrear123450J1,J2,J3出队J1J2J3frontfrontfrontv存在问题设数组维数为M，则：l当front=-1,rear=M-1时，再有元素入队发生溢出真溢出l当front-1,rear=M-1时，再有元素入队发生溢出假溢出v解决方案l队首固定，每次出队剩余元素向下移动浪费时间l循环队列u基本思想：把队列设想成环形，让sq0接在sqM-1之后，若rear+1=M,则令rear=0;0M-11frontrear.u实现：利用“模”运算u入队： rear=(rear+1)%M; sqrear=x;u出队： front=(front+1)

16、%M; x=sqfront;u队满、队空判定条件012345rearfrontJ4J5J6012345rearfrontJ9J8J7J4J5J6012345rearfront初始状态J4,J5,J6出队J7,J8,J9入队队空：front=rear队满：front=rear解决方案：1.另外设一个标志以区别队空、队满2.少用一个元素空间： 队空：front=rear 队满：(rear+1)%M=frontu入队算法：u出队算法：队列应用举例 划分子集问题v问题描述：已知集合A=a1,a2,an，及集合上的关系R= (ai,aj) | ai,ajA, ij，其中(ai,aj)表示ai与aj间存在

17、冲突关系。要求将A划分成互不相交的子集A1,A2,Ak,(kn)，使任何子集中的元素均无冲突关系，同时要求分子集个数尽可能少例 A=1,2,3,4,5,6,7,8,9 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) 可行的子集划分为： A1= 1,3,4,8 A2= 2,7 A3= 5 A4= 6,9 v算法思想：利用循环筛选。从第一个元素开始，凡与第一个元素无冲突的元素划归一组；再将剩下的元素重新找出互不冲突的划归第二组；直到所有元素进组v所用数据结构l冲

18、突关系矩阵urij=1, i,j有冲突urij=0, i,j无冲突l循环队列cqnl数组resultn存放每个元素分组号l工作数组newrnv工作过程l初始状态：A中元素放于cq中，result和newr数组清零，组号group=1l第一个元素出队，将r矩阵中第一行“1”拷入newr中对应位置，这样，凡与第一个元素有冲突的元素在newr中对应位置处均为“1”,下一个元素出队u若其在newr中对应位置为“1”，有冲突，重新插入cq队尾，参加下一次分组u若其在newr中对应位置为“0”, 无冲突，可划归本组；再将r矩阵中该元素对应行中的“1”拷入newr中l如此反复，直到9个元素依次出队，由new

19、r中为“0”的单元对应的元素构成第1组,将组号group值“1”写入result对应单元中l令group=2,newr清零，对cq中元素重复上述操作，直到cq中front=rear,即队空，运算结束v算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R=1 2 3 4 5 6 7 8 90 1 2 3 4 5 6 7 8 cqf r0

20、 0 0 0 0 0 0 0 00 1 2 3 4 5 6 7 8 newr0 0 0 0 0 0 0 0 00 1 2 3 4 5 6 7 8 result初始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) v算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00

21、1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R= 2 3 4 5 6 7 8 90 1 2 3 4 5 6 7 8 cqfr0 1 0 0 0 0 0 0 00 1 2 3 4 5 6 7 8 newr1 0 0 0 0 0 0 0 00 1 2 3 4 5 6 7 8 resultR= (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) v算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0

22、00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R= 2 3 4 5 6 7 8 90 1 2 3 4 5 6 7 8 cqfr0 1 0 0 0 0 0 0 00 1 2 3 4 5 6 7 8 newr1 0 0 0 0 0 0 0 00 1 2 3 4 5 6 7 8 resultR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7,6

23、), (3,7), (6,3) v算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R= 2 4 5 6 7 8 90 1 2 3 4 5 6 7 8 cqfr0 1 0 0 0 1 1 0 00 1 2 3 4 5 6 7 8 newr1 0 1 0 0 0 0 0 00 1 2 3 4 5 6 7 8 resultR= (2,8)

24、, (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7,6), (3,7), (6,3) v算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R= 2 5 6 7 8 90 1 2 3 4 5 6 7 8 cqfr0 1 0 0 1 1 1 0 10 1

25、2 3 4 5 6 7 8 newr1 0 1 1 0 0 0 0 00 1 2 3 4 5 6 7 8 resultR= (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) v算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0

26、 1 1 0 1 1R= 2 5 6 7 8 90 1 2 3 4 5 6 7 8 cqfr0 1 0 0 1 1 1 0 10 1 2 3 4 5 6 7 8 newr1 0 1 1 0 0 0 0 00 1 2 3 4 5 6 7 8 resultR= (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) v算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1

27、0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R= 2 5 6 7 8 90 1 2 3 4 5 6 7 8 cqfr0 1 0 0 1 1 1 0 10 1 2 3 4 5 6 7 8 newr1 0 1 1 0 0 0 0 00 1 2 3 4 5 6 7 8 resultR= (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) v算法描述0 1 0 0 0

28、 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R= 2 5 6 7 8 90 1 2 3 4 5 6 7 8 cqfr0 1 0 0 1 1 1 0 10 1 2 3 4 5 6 7 8 newr1 0 1 1 0 0 0 0 00 1 2 3 4 5 6 7 8 resultR= (2,8), (9,4), (2,9), (2,1), (2,5), (6

29、,2), (5,9), (5,6), (5,4), (7,5), (7,6), (3,7), (6,3) v算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R= 2 5 6 7 90 1 2 3 4 5 6 7 8 cqfr0 1 0 0 1 1 1 0 10 1 2 3 4 5 6 7 8 newr1 0 1 1 0 0 0 1

30、00 1 2 3 4 5 6 7 8 resultR= (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) v算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R= 2 5 6 7 90 1 2 3 4 5

31、6 7 8 cqfr0 1 0 0 1 1 1 0 10 1 2 3 4 5 6 7 8 newr1 0 1 1 0 0 0 1 00 1 2 3 4 5 6 7 8 resultR= (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) v算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1

32、1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R= 5 6 7 90 1 2 3 4 5 6 7 8 cqfr1 0 0 0 1 1 0 1 10 1 2 3 4 5 6 7 8 newr1 2 1 1 0 0 0 1 00 1 2 3 4 5 6 7 8 resultR= (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) v算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0

33、 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R= 6 7 9 50 1 2 3 4 5 6 7 8 cqfr1 0 0 0 1 1 0 1 10 1 2 3 4 5 6 7 8 newr1 2 1 1 0 0 0 1 00 1 2 3 4 5 6 7 8 resultR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7,6), (3,7

34、), (6,3) v算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R= 7 9 5 60 1 2 3 4 5 6 7 8 cqfr1 0 0 0 1 1 0 1 10 1 2 3 4 5 6 7 8 newr1 2 1 1 0 0 0 1 00 1 2 3 4 5 6 7 8 resultR= (2,8), (9,4), (2,9

35、), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7,6), (3,7), (6,3) v算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R= 9 5 60 1 2 3 4 5 6 7 8 cqfr1 0 1 0 1 1 0 1 10 1 2 3 4 5 6 7 8 newr1

36、 2 1 1 0 0 2 1 00 1 2 3 4 5 6 7 8 resultR= (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) v算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R= 5 6 90

37、 1 2 3 4 5 6 7 8 cqfr1 0 1 0 1 1 0 1 10 1 2 3 4 5 6 7 8 newr1 2 1 1 0 0 2 1 00 1 2 3 4 5 6 7 8 resultR= (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) v算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0

38、00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R= 6 90 1 2 3 4 5 6 7 8 cqfr0 1 0 1 0 1 1 0 10 1 2 3 4 5 6 7 8 newr1 2 1 1 3 0 2 1 00 1 2 3 4 5 6 7 8 resultR= (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) v算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0

39、0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R= 9 60 1 2 3 4 5 6 7 8 cqfr0 1 0 1 0 1 1 0 10 1 2 3 4 5 6 7 8 newr1 2 1 1 3 0 2 1 00 1 2 3 4 5 6 7 8 resultR= (2,8), (9,4), (2,9), (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7,6), (

40、3,7), (6,3) v算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R= 9 60 1 2 3 4 5 6 7 8 cqfr0 1 0 1 0 1 1 0 10 1 2 3 4 5 6 7 8 newr1 2 1 1 3 0 2 1 00 1 2 3 4 5 6 7 8 resultR= (2,8), (9,4), (2,9)

41、, (2,1), (2,5), (6,2), (5,9), (5,6), (5,4), (7,5), (7,6), (3,7), (6,3) v算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R= 90 1 2 3 4 5 6 7 8 cqfr0 1 1 0 1 0 1 0 00 1 2 3 4 5 6 7 8 newr1 2 1

42、1 3 4 2 1 00 1 2 3 4 5 6 7 8 resultR= (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) v算法描述0 1 0 0 0 0 0 0 00 1 0 1 1 0 0 0 00 0 0 0 0 1 1 0 00 0 0 0 1 0 0 0 10 1 0 1 0 1 1 0 10 1 1 0 1 0 1 0 00 0 1 0 1 1 0 0 00 1 0 0 0 0 0 0 01 0 0 0 1 1 0 1 1R= 1 2 3 4 5 6

43、 7 8 9 cqfr0 1 1 1 1 0 1 0 01 2 3 4 5 6 7 8 9 newr1 2 1 1 3 4 2 1 41 2 3 4 5 6 7 8 9resultR= (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) Ch3_9.c可行的子集划分为： A1= 1,3,4,8 A2= 2,7 A3= 5 A4= 6,9 v优先级队列v离散时间模拟v图的广度优先遍历v基数排序53/58 1）解决计算机主机与外设不匹配的问题；）解决计算机主机与外设不匹配

44、的问题； 2）解决由于多用户引起的资源竞争问题；）解决由于多用户引起的资源竞争问题； 3）离散事件的模拟）离散事件的模拟-模拟实际应用中的各种模拟实际应用中的各种排队现象；排队现象； 4）用于处理程序中具有先进先出特征的过程；）用于处理程序中具有先进先出特征的过程； 54/58 到医院看病的过程是，患者先排队等候到医院看病的过程是，患者先排队等候，排队过程中主要重复两件事情：，排队过程中主要重复两件事情： 1）病人到达诊室时，将病历交给护士，）病人到达诊室时，将病历交给护士，到等候队列中候诊。到等候队列中候诊。 2）护士从等候队列中取出下一个患者的）护士从等候队列中取出下一个患者的病历，该患者进入诊室就诊。病历，该患者进入诊室就诊。例例7-3.c55/58例例7-3.cvoid SeeDoctor( ) SqQueue *Q=NULL; char ch; int n;InitQueue(Q