【精品數(shù)據(jù)結構】棧和隊列（續(xù)）

1、,DATA,10,65,865,姓名 學號 成績 班級 李紅 9761059 95 機97.6,數(shù)據(jù)結構,第二章數(shù)據(jù)結構與算法,(續(xù)),2.3 棧和隊列,棧和隊列是兩種特殊的線性表，它們是運算時要受到某些限制的線性表，故也稱為限定性的數(shù)據(jù)結構。,(續(xù)),隊列的主要運算,（1）設置一個空隊列； （2）插入一個新的隊尾元素，稱為進隊； （3）刪除隊頭元素，稱為出隊； （4）讀取隊頭元素；,2.3.2 隊列 2.3.2.1 隊列的定義與運算 定義：一種特殊的線性結構，限定只能在表的一端進行插入，在表的另一端進行刪除的線性表 。此種結構稱為先進先出（FIFO）表。,a1 , a2 , a3 , a4

2、, an-1 , an,隊 列 示 意 圖,隊頭,隊尾,2. 隊列的存儲結構,（1）順序存儲結構,(a) 線性隊列,(b) 循環(huán)隊列,(a)線性隊列,隊空時， 令rear=front=-1，當有新元素入隊時，尾指針加1，當有元素出隊時，頭指針加1。故在非空隊列中，頭指針始終指向隊頭元素前一個位置，而尾指針始終指向隊尾元素的位置,(b) 循環(huán)隊列,rear,隊滿條件： (Q.rear+1)%MAX=Q.front 注：實際上為了避免與隊空標志沖突，還留有一個空間。,將頭尾連接成一個環(huán)，形成循環(huán)隊列。,循環(huán)隊列中加入一個元素的算法： int EnQueue(int Q ,int x, int *p

3、f,int *pr),Qmax已有的循環(huán)隊列,將插入的值,已有隊列的頭指針,已有隊列的尾指針,循環(huán)隊列中加入一個元素的算法： int EnQueue(int Q ,int x, int *pf,int *pr) int front, rear; front=*pf; rear=*pr; if(rear+1)%MAX= =front) return(0); else rear=(rear+1)%MAX; Qrear=x; *pr=rear; return(1); ,rear,x,循環(huán)隊列中刪除一個元素的算法： int DeQueue(int Q ，int *py， int *pf，int *pr

4、),已有的循環(huán)隊列,返回刪除的值的地址,已有隊列的頭指針,已有隊列的尾指針,循環(huán)隊列中刪除一個元素的算法： int DeQueue(int Q ，int *py，int *pf，int *pr) int front, rear; front=*pf; rear=*pr; if(rear= =front) return(0); else front=(front+1)%MAX; *py=Qfront; *pf=front; return(1); ,刪 除,一個元素,添加 一個元素,e,（2） 鏈式存儲結構,Q.front,Q.rear,隊頭,隊尾,Q.rear,Q.front,2.4 數(shù) 組,2

5、.4.1 二維數(shù)組的定義,a1 a11 a12 . a1n,a2 a21 a22 . a2n,am am1 am2 . amn,.,ai=( ai1 , ai2 , . , ain ) ( 1=i=n ),（1）按行優(yōu)先順序存放 （2）按列優(yōu)先順序存放 1、 特殊矩陣 （1） 下三角陣 （2） 三對角陣 1、稀疏矩陣 （1） 順序存儲結構三元組表示法 （2） 順序存儲結構稀疏矩陣的轉置運算 （3）數(shù)組的鏈接存儲結構十字鏈表結構,242 數(shù)組的順序存儲結構,243 矩陣的壓縮存儲,（1）按行優(yōu)先順序存放 （2）按列優(yōu)先順序存放 1、 特殊矩陣 （1） 下三角陣 （2） 三對角陣 1、稀疏矩陣 （

6、1） 順序存儲結構三元組表示法 （2） 順序存儲結構稀疏矩陣的轉置運算 （3）數(shù)組的鏈接存儲結構十字鏈表結構,242 數(shù)組的順序存儲結構,243 矩陣的壓縮存儲,a11 a12 . a1n,a21 a22 . a2n,am1 am2 . amn,.,loc(aij)=loc(a11)+(i-1)n+(j-1)S,按行優(yōu)先順序存放,a11 a12 . a1n,a21 a22 . a2n,am1 am2 . amn,.,loc(aij)=loc(a11)+(j-1)m+(i-1)S,按列優(yōu)先順序存放,a11 0 0 . 0,a21 a22 0 . 0,an1 an2 an3. ann,. 0,A=

7、,按行優(yōu)先存放a11 , a21 , a22 , a31 , a32 , , an1 , an2 , , ann,前i-1行非零元素個數(shù) R=,i(i-1),2,loc(aij)=loc(a11)+( +(j-1)S,i(i-1),2,i-1,R=1,下三角陣,a11 a12 0 . 0,a21 a22 a23 0 . 0,0 0 an-1,n-2 an-1.n-1 an-1,n,.,A=,0 a21 a22 a23 0 . 0,0 0 .an,n-1 ann.,按行優(yōu)先存放a11 , a12 , a21 , a22 , a23 , a32 , a34 , an,n-1 , ann,loc(a

8、ij)=loc(a11)+2(i-1)n+(j-1)S,三對角陣,7 0 0 0 15 0,0 -4 0 0 0 0,-2 0 0 0 0 21,0 0 0 -1 0 0,M=,21,6,4,-2,1,4,-1,4,3,-4,2,2,15,5,1,7,1,1,列,行,值,順序存儲結構三元組表示法,21,6,4,-1,4,3,-4,2,2,15,5,1,7 0 0 -2,0 -4 0 0,0 0 -1 0,0 0 0 0,15 0 0 0,0 0 0 21,順序存儲結構稀疏矩陣的轉置運算,求轉置矩陣的算法描述為： Status TransposeSMatrix(TSMatrix M, TSMat

9、rix /TransposeSMatrix,7 0 0 0 15 0,0 -4 0 0 0 0,-2 0 0 0 0 21,0 0 0 -1 0 0,M=,24 數(shù) 組 （ 線性表的推廣）,241 二維數(shù)組的定義,a1 a11 a12 . a1n,a2 a21 a22 . a2n,am am1 am2 . amn,.,ai=( ai1 , ai2 , . , ain ) ( 1=i=n ),數(shù)組的運算主要是存取元素、修改相應的元素。,（1）按行優(yōu)先順序存放 （2）按列優(yōu)先順序存放 243 矩陣的壓縮存儲 1、 特殊矩陣：值相同元素或非零元素的分布具有一定規(guī)律。 （1） 下三角陣 （2） 三對角

10、陣 2、稀疏矩陣 ：元素分布無規(guī)律。 （1） 順序存儲結構三元組表示法 （2） 順序存儲結構稀疏矩陣的轉置運算 （3）數(shù)組的鏈接存儲結構十字鏈表結構,242 數(shù)組的順序存儲結構,a11 a12 . a1n,a21 a22 . a2n,am1 am2 . amn,.,loc(aij)=loc(a11)+(i-1)n+(j-1)S,按行優(yōu)先順序存放,a11 a12 . a1n,a21 a22 . a2n,am1 am2 . amn,.,loc(aij)=loc(a11)+(j-1)m+(i-1)S,按列優(yōu)先順序存放,a11 0 0 . 0,a21 a22 0 . 0,an1 an2 an3. an

11、n,. 0,A=,按行優(yōu)先存放a11 , a21 , a22 , a31 , a32 , , an1 , an2 , , ann,前i-1行非零元素個數(shù) R=,i(i-1),2,loc(aij)=loc(a11)+(i(i-1)/2 +(j-1)S,i-1,R=1,下三角陣,a11 a12 0 . 0,a21 a22 a23 0 . 0,0 0 an-1,n-2 an-1.n-1 an-1,n,.,A=,0 a32 a33 a34 0 . 0,0 0 .an,n-1 an,n,按行優(yōu)先存放a11 , a12 , a21 , a22 , a23 , a32 , a33 , an,n-1 , an

12、,n,loc(aij)=loc(a11)+2(i-1)+(j-1),三對角陣,7 0 0 0 15 0,0 -4 0 0 0 0,-2 0 0 0 0 21,0 0 0 -1 0 0,M=,21,6,4,-2,1,4,-1,4,3,-4,2,2,15,5,1,7,1,1,列,行,值,順序存儲結構三元組表示法,21,6,4,-1,4,3,-4,2,2,15,5,1,7 0 0 -2,0 -4 0 0,15 0 0 0,0 0 0 0,0 0 -1 0,0 0 0 21,順序存儲結構稀疏矩陣的轉置運算,求轉置矩陣的算法描述為： Status TransposeSMatrix(TSMatrix M,

13、 TSMatrix /TransposeSMatrix,7 0 0 0 15 0,0 -4 0 0 0 0,-2 0 0 0 0 21,0 0 0 -1 0 0,M=,鏈式存儲結構,表示第3列空,7 0 0 0 15 0,0 -4 0 0 0 0,-2 0 0 0 0 21,0 0 0 -1 0 0,M=,鏈式存儲結構,作業(yè)：,P76 第12、16題 第18、19題,A+B*C-D/E；,A-B/C+D*E；,優(yōu)先級相同時，應先處理棧中數(shù)據(jù),錯在哪？,P76#11 假設一個算術表達式中包含圓括弧、方括弧和花括弧三種類型的括弧,編寫一個判別表達式中括弧是否正確配對的函數(shù).,P76#11 假設一個

14、算術表達式中包含圓括弧、方括弧和花括弧三種類型的括弧,編寫一個判別表達式中括弧是否正確配對的函數(shù).,void main() int len, tag; char expsize=“dsgdsg(wetewteewtwrwer)etewtewtwetwetetwet; len=strlen(exp); tag=Correct(exp, len); if (tag=1) printf(rightn); else printf(wrongn); ,輸出結果：wrong,P76#12 設棧S為空，隊Q的狀態(tài)是abcd，其中a為隊首元素，d為隊尾元素，經過下面兩個操作后，隊Q的狀態(tài)是（ ）。 （1）刪除

15、隊Q中的元素，將刪除的元素插入棧S，直到隊Q為空。 （2）依次將棧S中的元素插入隊Q，直到棧S為空。 (a) abcd (b) acbd (c) dcba (d) bacd,c,P76#13 若進棧序列為3，5，7，9，進棧過程中可以出棧，則不可能的一個出棧次序是（ ）。 (a) 7,5,3,9 (b) 9,7,5,3 (c) 7,5,9,3 (d) 9,5,7,3,P76#13 若進棧序列為3，5，7，9，進棧過程中可以出棧，則不可能的一個出棧次序是（ ）。 (a) 7,5,3,9 (b) 9,7,5,3 (c) 7,5,9,3 (d) 9,5,7,3,d,T=T+1,P76#15 用一維數(shù)

16、組設計棧，初態(tài)是棧空，top=0。現(xiàn)有輸入序列是 a、b、c、d，經過 push、push、pop、push、pop、push操作后，輸出序列是（ ），棧頂指針是（ ）,bc,2,P76#16. 假役某單位每天要有一批工人向調度員報到，并等待分配工作。當有工作需要分配時，調度員就從等待分配的工人中派一名去做該項工作；當某個工人完成了分配給他的任務后，就又回到調度室等待再次分配工作。 調度員的調度原則是在保證人人有工作的前提下，鼓勵勤快和熟練的工人。請問對應這種分配原則所采用的數(shù)據(jù)結構是什么？調度員都需要做哪些工作？,采用隊列數(shù)據(jù)結構。 調度員 要做的工作：開辟一個隊列結構的線性表；設置一個隊頭

17、指針和一個隊尾指針；有報到的或完成任務的，就排在隊尾，需要工人做工時，從隊頭選派工人。,P76#17 對于下面的程序調用過程，請問入棧序列是（ ）， 出棧次序是（ ）。,1、2、 3,2、1、3,P76#18 試寫出兩個稀疏矩陣相乘的算法。本程序有待修改,稀疏矩陣： void mmult ( TSMatrix a, TSMatrix b, int q) if (a.nu != b.mu) printf(“Incompatible Matrices”); else for (int ii=1; ii=a.mu; ii+) for (int jj=1; jj=b.nu; jj+) qii, jj=0; if ( (a.tu * b.tu) !=0 ) for (int row=1; row=b.mu; row+) numrow=0; for (int t=1; t=b.tu; t+) numb.datat.i +=1; pos1=1; for (row=2; row=b.mu+1; row+) po