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

棧和隊列棧和隊列是兩種特殊的線性表，是操作受限的線性表，稱限定性DS3.1棧（stack）棧的定義和特點定義：限定僅在表尾進行插入或刪除操作的線性表，表尾—棧頂，表頭—棧底，不含元素的空表稱空棧特點：先進后出（FILO）或后進先出（LIFO）ana1a2……...棧底棧頂...出棧進棧棧s=(a1,a2,……,an)棧的存儲結(jié)構(gòu)順序棧實現(xiàn)：一維數(shù)組s[M]top=0123450?？諚ｍ斨羔榯op,指向?qū)嶋H棧頂后的空位置，初值為0top123450進棧Atop出棧棧滿BCDEF設(shè)數(shù)組維數(shù)為Mtop=0,?？?，此時出棧，則下溢（underflow)top=M,棧滿，此時入棧，則上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop?？談?chuàng)建棧判斷棧空0M-1棧1底棧1頂棧2底棧2頂入棧算法出棧算法在一個程序中同時使用兩個棧定義順序棧鏈棧棧頂^…...topdatalink棧底結(jié)點定義入棧算法出棧算法typedef

structnode{intdata;

structnode*link;}JD;^…...棧底toptopxptop^…...棧底topq棧的應(yīng)用過程的嵌套調(diào)用r主程序srrrs子過程1rst子過程2rst子過程3實現(xiàn)遞歸將所有的實在參數(shù)、返回地址等信息傳遞給被調(diào)用函數(shù)保存；為被調(diào)用函數(shù)的局部變量分配存儲區(qū)；將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口。當在一個函數(shù)的運行期間調(diào)用另一個函數(shù)時，在運行該被調(diào)用函數(shù)之前，

需先完成三項任務(wù)：保存被調(diào)函數(shù)的計算結(jié)果；釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū)；依照被調(diào)函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù)。從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，應(yīng)該完成下列三項任務(wù)：例遞歸的執(zhí)行情況分析voidprint(intw){inti;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í)行情況如下：主程序(1)print(w)w=3;3print(2);（1）w=3topw2print(1);（2）w=2（1）w=3topw1print(0);（3）w=1（2）w=2（1）w=3topw0（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)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問題算法：3.2隊列隊列的定義及特點定義：隊列是限定只能在表的一端進行插入，在表的另一端進行刪除的線性表隊尾(rear)——允許插入的一端隊頭(front)——允許刪除的一端隊列特點：先進先出(FIFO)a1a2a3…….an入隊出隊frontrear隊列Q=(a1,a2,……,an)雙端隊列a1a2a3…….an端1端2入隊出隊入隊出隊鏈隊列結(jié)點定義typedef

structnode{intdata;

structnode*link;}JD;頭結(jié)點^…...front隊頭隊尾rear設(shè)隊首、隊尾指針front和rear,front指向頭結(jié)點，rear指向隊尾frontrearx入隊^xfrontreary入隊x^yfrontrearx出隊x^yfrontrear空隊^frontreary出隊^入隊算法出隊算法隊列的順序存儲結(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è)數(shù)組維數(shù)為M，則：當front=-1,rear=M-1時，再有元素入隊發(fā)生溢出——真溢出當front-1,rear=M-1時，再有元素入隊發(fā)生溢出——假溢出解決方案隊首固定，每次出隊剩余元素向下移動——浪費時間循環(huán)隊列基本思想：把隊列設(shè)想成環(huán)形，讓sq[0]接在sq[M-1]之后，若rear+1==M,則令rear=0;0M-11frontrear…...…...實現(xiàn)：利用“?！边\算入隊：rear=(rear+1)%M;sq[rear]=x;出隊：front=(front+1)%M;x=sq[front];隊滿、隊空判定條件012345rearfrontJ4J5J6012345rearfrontJ9J8J7J4J5J6012345rearfront初始狀態(tài)J4,J5,J6出隊J7,J8,J9入隊隊空：front==rear隊滿：front==rear解決方案：1.另外設(shè)一個標志以區(qū)別隊空、隊滿2.少用一個元素空間：隊空：front==rear

隊滿：(rear+1)%M==front入循環(huán)隊算法出循環(huán)隊算法：潘對空判對瞞隊列應(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}算法思想：利用循環(huán)篩選。從第一個元素開始，凡與第一個元素?zé)o沖突的元素劃歸一組；再將剩下的元素重新找出互不沖突的劃歸第二組；直到所有元素進組所用數(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]工作過程初始狀態(tài)：A中元素放于cq中，result和newr數(shù)組清零，組號group=1第一個元素出隊，將r矩陣中第一行“1”拷入newr中對應(yīng)位置，這樣，凡與第一個元素有沖突的元素在newr中對應(yīng)位置處均為“1”,下一個元素出隊若其在newr中對應(yīng)位置為“1