第04講ch棧和隊列

1、第三章 棧和隊列棧和隊列是兩種特殊的線性表，是操作受限的線性表，稱限定性DS3.1 棧（stack）棧的定義和特點v定義：限定僅在表尾進(jìn)行插入或刪除操作的線性表，表尾棧頂，表頭棧底，不含元素的空表稱空棧v特點：先進(jìn)后出（FILO）或后進(jìn)先出（LIFO）ana1a2.棧底棧頂.出棧進(jìn)棧棧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棧的存儲結(jié)構(gòu)v順序棧l實現(xiàn)：一維數(shù)組sMtop=012345

2、0棧空棧頂指針top,指向?qū)嶋H棧頂后的空位置，初值為0top123450進(jìn)棧Atop出棧棧滿BCDEF設(shè)數(shù)組維數(shù)為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; 類似于線性表的順序映象實現(xiàn)，指向表尾的指針可以作為棧頂指針。l入棧算法0M-1棧1底棧1頂棧2底棧2頂l出棧算法l在一個程序中同時使用兩個棧v鏈棧棧頂 .topdata next棧底l結(jié)點定義l入棧算法l出棧算法typedef struct node int data; struct node *next;JD; .棧底toptopxptop .棧底topq棧的應(yīng)用v過程的嵌套調(diào)用r主程序主程序srrrs子過程子過程1rst子過程子過程2rst子過程子過程3例例 遞歸的執(zhí)行情況分析遞歸的執(zhí)行情況分析 v遞歸過程及其實現(xiàn)l遞歸：函數(shù)直接或間

4、接的調(diào)用自身叫l(wèi)實現(xiàn)：建立遞歸工作棧 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運行結(jié)果：1，2，2，3，3，3，遞歸調(diào)用執(zhí)行情況如下：遞歸調(diào)用執(zhí)行情況如下：主程序主程序(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結(jié)束結(jié)束(1)l執(zhí)行情況：u遞歸工作棧保存內(nèi)容：形參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?？? A B C 02 B A C 8Hanoi.c D:fengyibkcpowerpower.cv回文游戲：順讀與逆讀字符串一樣（不含空格）dadtop1.讀入字符串2.去掉空格（原串）3.壓入棧4.原串字符與出棧字符依次比較 若不等，非回文 若直到?？斩枷嗟?，回文v多進(jìn)制輸出：字符串：“madam im adam”例 把十進(jìn)制數(shù)159轉(zhuǎn)換成八進(jìn)制數(shù)(159)10=(237)815981982802 3 7 余 7余 3余 2toptop7top73top732v表達(dá)式求值 中綴表達(dá)式 后綴表達(dá)式（RPN) a*b+c

11、ab*c+ a+b*c abc*+ a+(b*c+d)/e abc*d+e/+中綴表達(dá)式：操作數(shù)棧和運算符棧例 計算 2+4-3*6操作數(shù)運算符24+操作數(shù)運算符6-操作數(shù)運算符6-36*操作數(shù)運算符6-18操作數(shù)運算符12后綴表達(dá)式求值步驟：1、讀入表達(dá)式一個字符2、若是操作數(shù)，壓入棧，轉(zhuǎn)43、若是運算符，從棧中彈出2個數(shù)，將運算結(jié)果再壓入棧4、若表達(dá)式輸入完畢，棧頂即表達(dá)式值； 若表達(dá)式未輸入完，轉(zhuǎn)1top4top43top735top例 計算 4+3*5后綴表達(dá)式：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保存當(dāng)前簡單路保存當(dāng)前簡單路徑，只須存最后一個通徑，只須存最后一個通道塊。道塊?！跋乱粋€位置下一個位置”是是“當(dāng)當(dāng)前位置前位置”的四個方向上的四個方向上相鄰

13、的方塊。相鄰的方塊?！凹{入路徑納入路徑”即即“當(dāng)前當(dāng)前位置位置”入棧。入棧?！巴嘶匾徊酵嘶匾徊健奔醇础俺鰲３鰲！?。3.2 隊列隊列的定義及特點v定義：隊列是限定只能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表l隊尾(rear)允許插入的一端l隊頭(front)允許刪除的一端v隊列特點：先進(jìn)先出(FIFO)a1 a2 a3.an 入隊出隊frontrear隊列Q=(a1,a2,an)v雙端隊列a1 a2 a3.an 端1端2入隊出隊入隊出隊鏈隊列v結(jié)點定義typedef struct node int data; struct node *next;JD;頭結(jié)點 .front隊頭隊尾rea

14、r設(shè)隊首、隊尾指針front和rear,front指向頭結(jié)點，rear指向隊尾frontrearx入隊xfrontreary入隊xyfrontrearx出隊xyfront rear空隊front reary出隊v入隊算法v出隊算法隊列的順序存儲結(jié)構(gòu)v實現(xiàn)：用一維數(shù)組實現(xiàn)sqMfront=0rear=0123450隊空123450frontJ1,J1,J3入隊J1J2J3rearrear123450J4,J5,J6入隊J4J5J6front設(shè)兩個指針front,rear,約定：rear指示隊尾元素；front指示隊頭元素空隊列條件：front=rear入隊列：sq+rear=x;出隊列：x=sq

15、+front;rearrearfrontrear123450J1,J2,J3出隊J1J2J3frontfrontfrontv存在問題設(shè)數(shù)組維數(shù)為M，則：l當(dāng)front=-1,rear=M-1時，再有元素入隊發(fā)生溢出真溢出l當(dāng)front-1,rear=M-1時，再有元素入隊發(fā)生溢出假溢出v解決方案l隊首固定，每次出隊剩余元素向下移動浪費時間l循環(huán)隊列u基本思想：把隊列設(shè)想成環(huán)形，讓sq0接在sqM-1之后，若rear+1=M,則令rear=0;0M-11frontrear.u實現(xiàn)：利用“?！边\算u入隊： rear=(rear+1)%M; sqrear=x;u出隊： front=(front+1)

16、%M; x=sqfront;u隊滿、隊空判定條件012345rearfrontJ4J5J6012345rearfrontJ9J8J7J4J5J6012345rearfront初始狀態(tài)J4,J5,J6出隊J7,J8,J9入隊隊空：front=rear隊滿：front=rear解決方案：1.另外設(shè)一個標(biāo)志以區(qū)別隊空、隊滿2.少用一個元素空間： 隊空：front=rear 隊滿：(rear+1)%M=frontu入隊算法：u出隊算法：隊列應(yīng)用舉例 劃分子集問題v問題描述：已知集合A=a1,a2,an，及集合上的關(guān)系R= (ai,aj) | ai,ajA, ij，其中(ai,aj)表示ai與aj間存在

17、沖突關(guān)系。要求將A劃分成互不相交的子集A1,A2,Ak,(kn)，使任何子集中的元素均無沖突關(guān)系，同時要求分子集個數(shù)盡可能少例 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算法思想：利用循環(huán)篩選。從第一個元素開始，凡與第一個元素?zé)o沖突的元素劃歸一組；再將剩下的元素重新找出互不沖突的劃歸第二組；直到所有元素進(jìn)組v所用數(shù)據(jù)結(jié)構(gòu)l沖

18、突關(guān)系矩陣urij=1, i,j有沖突urij=0, i,j無沖突l循環(huán)隊列cqnl數(shù)組resultn存放每個元素分組號l工作數(shù)組newrnv工作過程l初始狀態(tài)：A中元素放于cq中，result和newr數(shù)組清零，組號group=1l第一個元素出隊，將r矩陣中第一行“1”拷入newr中對應(yīng)位置，這樣，凡與第一個元素有沖突的元素在newr中對應(yīng)位置處均為“1”,下一個元素出隊u若其在newr中對應(yīng)位置為“1”，有沖突，重新插入cq隊尾，參加下一次分組u若其在newr中對應(yīng)位置為“0”, 無沖突，可劃歸本組；再將r矩陣中該元素對應(yīng)行中的“1”拷入newr中l(wèi)如此反復(fù)，直到9個元素依次出隊，由new

19、r中為“0”的單元對應(yīng)的元素構(gòu)成第1組,將組號group值“1”寫入result對應(yīng)單元中l(wèi)令group=2,newr清零，對cq中元素重復(fù)上述操作，直到cq中front=rear,即隊空，運算結(jié)束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優(yōu)先級隊列v離散時間模擬v圖的廣度優(yōu)先遍歷v基數(shù)排序53/58 1）解決計算機主機與外設(shè)不匹配的問題；）解決計算機主機與外設(shè)不匹配

44、的問題； 2）解決由于多用戶引起的資源競爭問題；）解決由于多用戶引起的資源競爭問題； 3）離散事件的模擬）離散事件的模擬-模擬實際應(yīng)用中的各種模擬實際應(yīng)用中的各種排隊現(xiàn)象；排隊現(xiàn)象； 4）用于處理程序中具有先進(jìn)先出特征的過程；）用于處理程序中具有先進(jìn)先出特征的過程； 54/58 到醫(yī)院看病的過程是，患者先排隊等候到醫(yī)院看病的過程是，患者先排隊等候，排隊過程中主要重復(fù)兩件事情：，排隊過程中主要重復(fù)兩件事情： 1）病人到達(dá)診室時，將病歷交給護士，）病人到達(dá)診室時，將病歷交給護士，到等候隊列中候診。到等候隊列中候診。 2）護士從等候隊列中取出下一個患者的）護士從等候隊列中取出下一個患者的病歷，該患者進(jìn)入診室就診。病歷，該患者進(jìn)入診室就診。例例7-3.c55/58例例7-3.cvoid SeeDoctor( ) SqQueue *Q=NULL; char ch; int n;InitQueue(Q