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

第三章棧和隊列棧和隊列是兩種特殊的線性表，是操作受限的線性表，稱限定性DS3.1棧（stack）棧的定義和特點定義：限定僅在表尾進(jìn)行插入或刪除操作的線性表，表尾—棧頂，表頭—棧底，不含元素的空表稱空棧特點：先進(jìn)后出（FILO）或后進(jìn)先出（LIFO）ana1a2……...棧底棧頂...出棧進(jìn)棧棧s=(a1,a2,……,an)數(shù)據(jù)結(jié)構(gòu)—棧和隊列全文共48頁，當(dāng)前為第1頁。棧的存儲結(jié)構(gòu)順序棧實現(xiàn)：一維數(shù)組s[M]top=0123450?？諚ｍ斨羔榯op,指向?qū)嶋H棧頂后的空位置，初值為0top123450進(jìn)棧Atop出棧棧滿BCDEF設(shè)數(shù)組維數(shù)為Mtop=0,?？?，此時出棧，則下溢（underflow)top=M,棧滿，此時入棧，則上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop?？諗?shù)據(jù)結(jié)構(gòu)—棧和隊列全文共48頁，當(dāng)前為第2頁。入棧算法0M-1棧1底棧1頂棧2底棧2頂出棧算法在一個程序中同時使用兩個棧typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;順序棧的定義數(shù)據(jù)結(jié)構(gòu)—棧和隊列全文共48頁，當(dāng)前為第3頁。鏈棧棧頂^…...topdatalink棧底結(jié)點定義入棧算法出棧算法typedefstructnode{intdata;structnode*link;}JD;^…...棧底toptopxptop^…...棧底topq數(shù)據(jù)結(jié)構(gòu)—棧和隊列全文共48頁，當(dāng)前為第4頁。棧的應(yīng)用過程的嵌套調(diào)用r主程序srrrs子過程1rst子過程2rst子過程3數(shù)據(jù)結(jié)構(gòu)—棧和隊列全文共48頁，當(dāng)前為第5頁。例遞歸的執(zhí)行情況分析遞歸過程及其實現(xiàn)遞歸：函數(shù)直接或間接的調(diào)用自身叫~實現(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)—棧和隊列全文共48頁，當(dāng)前為第6頁。遞歸調(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)—棧和隊列全文共48頁，當(dāng)前為第7頁。TowerofHanoi問題問題描述：有A,B,C三個塔座，A上套有n個直徑不同的圓盤，按直徑從小到大疊放，形如寶塔,編號1,2,3……n。要求將n個圓盤從A移到C，疊放順序不變，移動過程中遵循下列原則：每次只能移一個圓盤圓盤可在三個塔座上任意移動任何時刻，每個塔座上不能將大盤壓到小盤上解決方法：n=1時，直接把圓盤從A移到Cn>1時，先把上面n-1個圓盤從A移到B,然后將n號盤從A移到C,再將n-1個盤從B移到C。即把求解n個圓盤的Hanoi問題轉(zhuǎn)化為求解n-1個圓盤的Hanoi問題，依次類推，直至轉(zhuǎn)化成只有一個圓盤的Hanoi問題算法：執(zhí)行情況：遞歸工作棧保存內(nèi)容：形參n,x,y,z和返回地址返回地址用行編號表示nxyz返回地址數(shù)據(jù)結(jié)構(gòu)—棧和隊列全文共48頁，當(dāng)前為第8頁。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)—棧和隊列全文共48頁，當(dāng)前為第9頁。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)—棧和隊列全文共48頁，當(dāng)前為第10頁。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)—棧和隊列全文共48頁，當(dāng)前為第11頁。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)—棧和隊列全文共48頁，當(dāng)前為第12頁?；匚挠螒颍喉樧x與逆讀字符串一樣（不含空格）dadtop1.讀入字符串2.去掉空格（原串）3.壓入棧4.原串字符與出棧字符依次比較若不等，非回文若直到?？斩枷嗟龋匚亩噙M(jìn)制輸出：字符串：“madamimadam”例把十進(jìn)制數(shù)159轉(zhuǎn)換成八進(jìn)制數(shù)(159)10=(237)81598198280237余7余3余2toptop7top73top732數(shù)據(jù)結(jié)構(gòu)—棧和隊列全文共48頁，當(dāng)前為第13頁。表達(dá)式求值

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

紫色

2#黃色3#

紅色4#

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

隊滿：(rear+1)%M==front數(shù)據(jù)結(jié)構(gòu)—棧和隊列全文共48頁，當(dāng)前為第23頁。入隊算法：出隊算法：數(shù)據(jù)結(jié)構(gòu)—棧和隊列全文共48頁，當(dāng)前為第24頁。隊列應(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ù)盡可能少例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)—棧和隊列全文共48頁，當(dāng)前為第25頁。算法思想：利用循環(huán)篩選。從第一個元素開始，凡與第一個元素?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)隊列cq[n]數(shù)組result[n]存放每個元素分組號工作數(shù)組newr[n]數(shù)據(jù)結(jié)構(gòu)—棧和隊列全文共48頁，當(dāng)前為第26頁。工作過程初始狀態(tài)：A中元素放于cq中，result和newr數(shù)組清零，組號group=1第一個元素出隊，將r矩陣中第一行“1”拷入newr中對應(yīng)位置，這樣，凡與第一個元素有沖突的元素在newr中對應(yīng)位置處均為“1”,下一個元素出隊若其在newr中對應(yīng)位置為“1”，有沖突，重新插入cq隊尾，參加下一次分組若其在newr中對應(yīng)位置為“0”,無沖突，可劃歸本組；再將r矩陣中該元素對應(yīng)行中的“1”拷入newr中如此反復(fù)，直到9個元素依次出隊，由newr中為“0”的單元對應(yīng)的元素構(gòu)成第1組,將組號group值“1”寫入result對應(yīng)單元中令group=2,newr清零，對cq中元素重復(fù)上述操作，直到cq中front==rear,即隊空，運(yùn)算結(jié)束數(shù)據(jù)結(jié)構(gòu)—棧和隊列全文共48頁，當(dāng)前為第27頁。算法描述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)—棧和隊列全文共48頁，當(dāng)前為第28頁。算法描述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)—棧和隊列全文共48頁，當(dāng)前為第29頁。算法描述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)—棧和隊列全文共48頁，當(dāng)前為第30頁。算法描述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)—棧和隊列全文共48頁，當(dāng)前為第31頁。算法描述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)—棧和隊列全文共48頁，當(dāng)前為第32頁。算法描述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)—棧和隊列全文共48頁，當(dāng)前為第33頁。算法描述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)—棧和隊列全文共48頁，當(dāng)前為第34頁。算法描述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)—棧和隊列全文共48頁，當(dāng)前為第35頁。算法描述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)—棧和隊列全文共48頁，當(dāng)前為第36頁。算法描述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)—棧和隊列全文共48頁，當(dāng)前為第37頁。算法描述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)—棧和隊列全文共48頁，當(dāng)前為第38頁。算法描述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)—棧和隊列全文共48頁，當(dāng)前為第39頁。算法描述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)—棧和隊列全文共48頁，當(dāng)前為第40頁。算法描述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)—棧和隊列全文共48頁，當(dāng)前為第41頁。算法描述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)—棧和隊列全文共48頁，當(dāng)前為第42頁。算法描述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)—棧和隊列全文共48頁，當(dāng)前為第43頁。算法描述010000000010110000000001100000010001010101101011010100001011000010000000100011011R=

96012345678cqfr010101

101012345678newr1

2

1

1

302

1001234567