數(shù)據(jù)結(jié)構(gòu)-棧和隊(duì)列

第三章棧和隊(duì)列棧和隊(duì)列是兩種特殊的線性表，是操作受限的線性表，稱限定性DS3.1棧（stack）棧的定義和特點(diǎn)定義：限定僅在表尾進(jìn)行插入或刪除操作的線性表，表尾—棧頂，表頭—棧底，不含元素的空表稱空棧特點(diǎn)：先進(jìn)后出（FILO）或后進(jìn)先出（LIFO）ana1a2……...棧底棧頂...出棧進(jìn)棧棧s=(a1,a2,……,an)數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第1頁(yè)。棧的存儲(chǔ)結(jié)構(gòu)順序棧實(shí)現(xiàn)：一維數(shù)組s[M]top=0123450?？諚ｍ斨羔榯op,指向?qū)嶋H棧頂后的空位置，初值為0top123450進(jìn)棧Atop出棧棧滿BCDEF設(shè)數(shù)組維數(shù)為Mtop=0,?？?，此時(shí)出棧，則下溢（underflow)top=M,棧滿，此時(shí)入棧，則上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop?？諗?shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第2頁(yè)。入棧算法0M-1棧1底棧1頂棧2底棧2頂出棧算法在一個(gè)程序中同時(shí)使用兩個(gè)棧typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;順序棧的定義數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第3頁(yè)。鏈棧棧頂^…...topdatalink棧底結(jié)點(diǎn)定義入棧算法出棧算法typedefstructnode{intdata;structnode*link;}JD;^…...棧底toptopxptop^…...棧底topq數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第4頁(yè)。棧的應(yīng)用過程的嵌套調(diào)用r主程序srrrs子過程1rst子過程2rst子過程3數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第5頁(yè)。例遞歸的執(zhí)行情況分析遞歸過程及其實(shí)現(xiàn)遞歸：函數(shù)直接或間接的調(diào)用自身叫~實(shí)現(xiàn)：建立遞歸工作棧voidprint(intw){inti;if(w!=0){print(w-1);

for(i=1;i<=w;++i)printf(“%3d”,w);

printf("\n");}}Ch3_10.c運(yùn)行結(jié)果：1，2，2，3，3，3

，數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第6頁(yè)。遞歸調(diào)用執(zhí)行情況如下：主程序(1)print(w)w=3;3print(2);（1）w=3top(2)輸出：3,3,3w2print(1);（2）w=2（1）w=3top(3)輸出：2,2w1print(0);（3）w=1（2）w=2（1）w=3top(4)輸出：1w0（4）w=0（3）w=1（2）w=2（1）w=3topw(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é)束(1)數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第7頁(yè)。TowerofHanoi問題問題描述：有A,B,C三個(gè)塔座，A上套有n個(gè)直徑不同的圓盤，按直徑從小到大疊放，形如寶塔,編號(hào)1,2,3……n。要求將n個(gè)圓盤從A移到C，疊放順序不變，移動(dòng)過程中遵循下列原則：每次只能移一個(gè)圓盤圓盤可在三個(gè)塔座上任意移動(dòng)任何時(shí)刻，每個(gè)塔座上不能將大盤壓到小盤上解決方法：n=1時(shí)，直接把圓盤從A移到Cn>1時(shí)，先把上面n-1個(gè)圓盤從A移到B,然后將n號(hào)盤從A移到C,再將n-1個(gè)盤從B移到C。即把求解n個(gè)圓盤的Hanoi問題轉(zhuǎn)化為求解n-1個(gè)圓盤的Hanoi問題，依次類推，直至轉(zhuǎn)化成只有一個(gè)圓盤的Hanoi問題算法：執(zhí)行情況：遞歸工作棧保存內(nèi)容：形參n,x,y,z和返回地址返回地址用行編號(hào)表示nxyz返回地址數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第8頁(yè)。main(){intm;printf("Inputnumberofdisks”);scanf("%d",&m);printf(”Steps:%3ddisks”,m);hanoi(m,'A','B','C');(0)}voidhanoi(intn,charx,chary,charz)(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)}ABC1233ABC03ABC02ACB63ABC02ACB61ABC6ABC3ABC02ACB6數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第9頁(yè)。main(){intm;printf("Inputthenumberofdisksscanf("%d",&m);printf("Thestepstomoving%3dhanoi(m,'A','B','C');(0)}voidhanoi(intn,charx,chary,charz)(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)}ABC3ABC02ACB61CAB8ABC3ABC02ACB63ABC03ABC02ACB6數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第10頁(yè)。main(){intm;printf("Inputthenumberofdisksscanf("%d",&m);printf("Thestepstomoving%3dhanoi(m,'A','B','C');(0)}voidhanoi(intn,charx,chary,charz)(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)}ABC3ABC02BAC83ABC02BAC81BCA6ABC3ABC02BAC83ABC0數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第11頁(yè)。main(){intm;printf("Inputthenumberofdisksscanf("%d",&m);printf("Thestepstomoving%3dhanoi(m,'A','B','C');(0)}voidhanoi(intn,charx,chary,charz)(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)}ABC3ABC02BAC81ABC8ABC3ABC02BAC83ABC0?？?ABC02BAC8Hanoi.cD:\fengyi\bkc\power\power.c數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第12頁(yè)?；匚挠螒颍喉樧x與逆讀字符串一樣（不含空格）dadtop1.讀入字符串2.去掉空格（原串）3.壓入棧4.原串字符與出棧字符依次比較若不等，非回文若直到棧空都相等，回文多進(jìn)制輸出：字符串：“madamimadam”例把十進(jìn)制數(shù)159轉(zhuǎn)換成八進(jìn)制數(shù)(159)10=(237)81598198280237余7余3余2toptop7top73top732數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第13頁(yè)。表達(dá)式求值

中綴表達(dá)式后綴表達(dá)式（RPN)a*b+cab*c+a+b*cabc*+a+(b*c+d)/eabc*d+e/+中綴表達(dá)式：操作數(shù)棧和運(yùn)算符棧例計(jì)算2+4-3*6操作數(shù)運(yùn)算符24+操作數(shù)運(yùn)算符6-操作數(shù)運(yùn)算符6-36*操作數(shù)運(yùn)算符6-18操作數(shù)運(yùn)算符12數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第14頁(yè)。后綴表達(dá)式求值步驟：1、讀入表達(dá)式一個(gè)字符2、若是操作數(shù)，壓入棧，轉(zhuǎn)43、若是運(yùn)算符，從棧中彈出2個(gè)數(shù)，將運(yùn)算結(jié)果再壓入棧4、若表達(dá)式輸入完畢，棧頂即表達(dá)式值；若表達(dá)式未輸入完，轉(zhuǎn)1top4top43top735top例計(jì)算4+3*5后綴表達(dá)式：435*+top415top19數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第15頁(yè)。(1)(2)(4)(5)(6)(7)(3)地圖四染色問題R[7][7]12345671234567100001001111101010110101101011011001001100000000012345671223414334231#

紫色

2#黃色3#

紅色4#

綠色數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第16頁(yè)。3.2隊(duì)列隊(duì)列的定義及特點(diǎn)定義：隊(duì)列是限定只能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表隊(duì)尾(rear)——允許插入的一端隊(duì)頭(front)——允許刪除的一端隊(duì)列特點(diǎn)：先進(jìn)先出(FIFO)a1a2a3…….an入隊(duì)出隊(duì)frontrear隊(duì)列Q=(a1,a2,……,an)雙端隊(duì)列a1a2a3…….an端1端2入隊(duì)出隊(duì)入隊(duì)出隊(duì)數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第17頁(yè)。鏈隊(duì)列結(jié)點(diǎn)定義typedefstructnode{intdata;structnode*link;}JD;頭結(jié)點(diǎn)^…...front隊(duì)頭隊(duì)尾rear設(shè)隊(duì)首、隊(duì)尾指針front和rear,front指向頭結(jié)點(diǎn)，rear指向隊(duì)尾數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第18頁(yè)。frontrearx入隊(duì)^xfrontreary入隊(duì)x^yfrontrearx出隊(duì)x^yfrontrear空隊(duì)^frontreary出隊(duì)^數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第19頁(yè)。入隊(duì)算法出隊(duì)算法數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第20頁(yè)。隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)：用一維數(shù)組實(shí)現(xiàn)sq[M]front=-1rear=-1123450隊(duì)空123450frontJ1,J1,J3入隊(duì)J1J2J3rearrear123450J4,J5,J6入隊(duì)J4J5J6front設(shè)兩個(gè)指針front,rear,約定：rear指示隊(duì)尾元素；front指示隊(duì)頭元素前一位置初值front=rear=-1空隊(duì)列條件：front==rear入隊(duì)列：sq[++rear]=x;出隊(duì)列：x=sq[++front];rearrearfrontrear123450J1,J2,J3出隊(duì)J1J2J3frontfrontfront數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第21頁(yè)。存在問題設(shè)數(shù)組維數(shù)為M，則：當(dāng)front=-1,rear=M-1時(shí)，再有元素入隊(duì)發(fā)生溢出——真溢出當(dāng)front-1,rear=M-1時(shí)，再有元素入隊(duì)發(fā)生溢出——假溢出解決方案隊(duì)首固定，每次出隊(duì)剩余元素向下移動(dòng)——浪費(fèi)時(shí)間循環(huán)隊(duì)列基本思想：把隊(duì)列設(shè)想成環(huán)形，讓sq[0]接在sq[M-1]之后，若rear+1==M,則令rear=0;0M-11frontrear…...…...實(shí)現(xiàn)：利用“模”運(yùn)算入隊(duì)：rear=(rear+1)%M;sq[rear]=x;出隊(duì)：front=(front+1)%M;x=sq[front];隊(duì)滿、隊(duì)空判定條件數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第22頁(yè)。012345rearfrontJ4J5J6012345rearfrontJ9J8J7J4J5J6012345rearfront初始狀態(tài)J4,J5,J6出隊(duì)J7,J8,J9入隊(duì)隊(duì)空：front==rear隊(duì)滿：front==rear解決方案：1.另外設(shè)一個(gè)標(biāo)志以區(qū)別隊(duì)空、隊(duì)滿2.少用一個(gè)元素空間：隊(duì)空：front==rear

隊(duì)滿：(rear+1)%M==front數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第23頁(yè)。入隊(duì)算法：出隊(duì)算法：數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第24頁(yè)。隊(duì)列應(yīng)用舉例劃分子集問題問題描述：已知集合A={a1,a2,……an}，及集合上的關(guān)系R={(ai,aj)|ai,ajA,ij}，其中(ai,aj)表示ai與aj間存在沖突關(guān)系。要求將A劃分成互不相交的子集A1,A2,……Ak,(kn)，使任何子集中的元素均無沖突關(guān)系，同時(shí)要求分子集個(gè)數(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}數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第25頁(yè)。算法思想：利用循環(huán)篩選。從第一個(gè)元素開始，凡與第一個(gè)元素?zé)o沖突的元素劃歸一組；再將剩下的元素重新找出互不沖突的劃歸第二組；直到所有元素進(jìn)組所用數(shù)據(jù)結(jié)構(gòu)沖突關(guān)系矩陣r[i][j]=1,i,j有沖突r[i][j]=0,i,j無沖突循環(huán)隊(duì)列cq[n]數(shù)組result[n]存放每個(gè)元素分組號(hào)工作數(shù)組newr[n]數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第26頁(yè)。工作過程初始狀態(tài)：A中元素放于cq中，result和newr數(shù)組清零，組號(hào)group=1第一個(gè)元素出隊(duì)，將r矩陣中第一行“1”拷入newr中對(duì)應(yīng)位置，這樣，凡與第一個(gè)元素有沖突的元素在newr中對(duì)應(yīng)位置處均為“1”,下一個(gè)元素出隊(duì)若其在newr中對(duì)應(yīng)位置為“1”，有沖突，重新插入cq隊(duì)尾，參加下一次分組若其在newr中對(duì)應(yīng)位置為“0”,無沖突，可劃歸本組；再將r矩陣中該元素對(duì)應(yīng)行中的“1”拷入newr中如此反復(fù)，直到9個(gè)元素依次出隊(duì)，由newr中為“0”的單元對(duì)應(yīng)的元素構(gòu)成第1組,將組號(hào)group值“1”寫入result對(duì)應(yīng)單元中令group=2,newr清零，對(duì)cq中元素重復(fù)上述操作，直到cq中front==rear,即隊(duì)空，運(yùn)算結(jié)束數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第27頁(yè)。算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=123456789012345678cqfr000000000012345678newr000000000012345678result初始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)}數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第28頁(yè)。算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=23456789012345678cqfr010000000012345678newr100000000012345678resultR={(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)}數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第29頁(yè)。算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

23456789012345678cqfr010000000012345678newr100000000012345678resultR={(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)}數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第30頁(yè)。算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

2456789012345678cqfr010001

100012345678newr101000000012345678resultR={(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)}數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第31頁(yè)。算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

256789012345678cqfr01001

1

101012345678newr101

100000012345678resultR={(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)}數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第32頁(yè)。算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

2

56789012345678cqfr01001

1

101012345678newr101

100000012345678resultR={(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)}數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第33頁(yè)。算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

2

5

6789012345678cqfr01001

1

101012345678newr101

100000012345678resultR={(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)}數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第34頁(yè)。算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

2

5

6

789012345678cqfr01001

1

101012345678newr101

100000012345678resultR={(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)}數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第35頁(yè)。算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

2

5

6

79012345678cqfr01001

1

101012345678newr101

100010012345678resultR={(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)}數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第36頁(yè)。算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

2

5

6

7

9012345678cqfr01001

1

101012345678newr101

100010012345678resultR={(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)}數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第37頁(yè)。算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=5

6

7

9012345678cqfr10001

101

1012345678newr1

2

1

100010012345678resultR={(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)}數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第38頁(yè)。算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=6

7

95012345678cqfr10001

101

1012345678newr1

2

1

100010012345678resultR={(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)}數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第39頁(yè)。算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

7

956012345678cqfr10001

101

1012345678newr1

2

1

100010012345678resultR={(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)}數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第40頁(yè)。算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

956012345678cqfr10101

101

1012345678newr1

2

1

1002

10012345678resultR={(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)}數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第41頁(yè)。算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

569012345678cqfr10101

101

1012345678newr1

2

1

1002

10012345678resultR={(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)}數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第42頁(yè)。算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

69012345678cqfr010101

101012345678newr1

2

1

1

302

10012345678resultR={(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)}數(shù)據(jù)結(jié)構(gòu)—棧和隊(duì)列全文共48頁(yè)，當(dāng)前為第43頁(yè)。算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

96012345678cqfr010101

101012345678newr1

2

1

1

302

1001234567