




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、,DATA,10,65,865,姓名 學(xué)號 成績 班級 李紅 9761059 95 機97.6,數(shù)據(jù)結(jié)構(gòu),第二章數(shù)據(jù)結(jié)構(gòu)與算法,(續(xù)),2.3 棧和隊列,棧和隊列是兩種特殊的線性表,它們是運算時要受到某些限制的線性表,故也稱為限定性的數(shù)據(jù)結(jié)構(gòu)。,(續(xù)),隊列的主要運算,(1)設(shè)置一個空隊列; (2)插入一個新的隊尾元素,稱為進隊; (3)刪除隊頭元素,稱為出隊; (4)讀取隊頭元素;,2.3.2 隊列 2.3.2.1 隊列的定義與運算 定義:一種特殊的線性結(jié)構(gòu),限定只能在表的一端進行插入,在表的另一端進行刪除的線性表 。此種結(jié)構(gòu)稱為先進先出(FIFO)表。,a1 , a2 , a3 , a4
2、, an-1 , an,隊 列 示 意 圖,隊頭,隊尾,2. 隊列的存儲結(jié)構(gòu),(1)順序存儲結(jié)構(gòu),(a) 線性隊列,(b) 循環(huán)隊列,(a)線性隊列,隊空時, 令rear=front=-1,當(dāng)有新元素入隊時,尾指針加1,當(dāng)有元素出隊時,頭指針加1。故在非空隊列中,頭指針始終指向隊頭元素前一個位置,而尾指針始終指向隊尾元素的位置,(b) 循環(huán)隊列,rear,隊滿條件: (Q.rear+1)%MAX=Q.front 注:實際上為了避免與隊空標(biāo)志沖突,還留有一個空間。,將頭尾連接成一個環(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) 鏈?zhǔn)酱鎯Y(jié)構(gòu),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) 順序存儲結(jié)構(gòu)三元組表示法 (2) 順序存儲結(jié)構(gòu)稀疏矩陣的轉(zhuǎn)置運算 (3)數(shù)組的鏈接存儲結(jié)構(gòu)十字鏈表結(jié)構(gòu),242 數(shù)組的順序存儲結(jié)構(gòu),243 矩陣的壓縮存儲,(1)按行優(yōu)先順序存放 (2)按列優(yōu)先順序存放 1、 特殊矩陣 (1) 下三角陣 (2) 三對角陣 1、稀疏矩陣 (
6、1) 順序存儲結(jié)構(gòu)三元組表示法 (2) 順序存儲結(jié)構(gòu)稀疏矩陣的轉(zhuǎn)置運算 (3)數(shù)組的鏈接存儲結(jié)構(gòu)十字鏈表結(jié)構(gòu),242 數(shù)組的順序存儲結(jié)構(gòu),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,列,行,值,順序存儲結(jié)構(gòu)三元組表示法,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,順序存儲結(jié)構(gòu)稀疏矩陣的轉(zhuǎn)置運算,求轉(zhuǎn)置矩陣的算法描述為: 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ù)組的運算主要是存取元素、修改相應(yīng)的元素。,(1)按行優(yōu)先順序存放 (2)按列優(yōu)先順序存放 243 矩陣的壓縮存儲 1、 特殊矩陣:值相同元素或非零元素的分布具有一定規(guī)律。 (1) 下三角陣 (2) 三對角
10、陣 2、稀疏矩陣 :元素分布無規(guī)律。 (1) 順序存儲結(jié)構(gòu)三元組表示法 (2) 順序存儲結(jié)構(gòu)稀疏矩陣的轉(zhuǎn)置運算 (3)數(shù)組的鏈接存儲結(jié)構(gòu)十字鏈表結(jié)構(gòu),242 數(shù)組的順序存儲結(jié)構(gòu),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,列,行,值,順序存儲結(jié)構(gòu)三元組表示法,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,順序存儲結(jié)構(gòu)稀疏矩陣的轉(zhuǎn)置運算,求轉(zhuǎn)置矩陣的算法描述為: 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=,鏈?zhǔn)酱鎯Y(jié)構(gòu),表示第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=,鏈?zhǔn)酱鎯Y(jié)構(gòu),作業(yè):,P76 第12、16題 第18、19題,A+B*C-D/E;,A-B/C+D*E;,優(yōu)先級相同時,應(yīng)先處理棧中數(shù)據(jù),錯在哪?,P76#11 假設(shè)一個算術(shù)表達式中包含圓括弧、方括弧和花括弧三種類型的括弧,編寫一個判別表達式中括弧是否正確配對的函數(shù).,P76#11 假設(shè)一個
14、算術(shù)表達式中包含圓括弧、方括弧和花括弧三種類型的括弧,編寫一個判別表達式中括弧是否正確配對的函數(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); ,輸出結(jié)果:wrong,P76#12 設(shè)棧S為空,隊Q的狀態(tài)是abcd,其中a為隊首元素,d為隊尾元素,經(jīng)過下面兩個操作后,隊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、組設(shè)計棧,初態(tài)是???,top=0?,F(xiàn)有輸入序列是 a、b、c、d,經(jīng)過 push、push、pop、push、pop、push操作后,輸出序列是( ),棧頂指針是( ),bc,2,P76#16. 假役某單位每天要有一批工人向調(diào)度員報到,并等待分配工作。當(dāng)有工作需要分配時,調(diào)度員就從等待分配的工人中派一名去做該項工作;當(dāng)某個工人完成了分配給他的任務(wù)后,就又回到調(diào)度室等待再次分配工作。 調(diào)度員的調(diào)度原則是在保證人人有工作的前提下,鼓勵勤快和熟練的工人。請問對應(yīng)這種分配原則所采用的數(shù)據(jù)結(jié)構(gòu)是什么?調(diào)度員都需要做哪些工作?,采用隊列數(shù)據(jù)結(jié)構(gòu)。 調(diào)度員 要做的工作:開辟一個隊列結(jié)構(gòu)的線性表;設(shè)置一個隊頭
17、指針和一個隊尾指針;有報到的或完成任務(wù)的,就排在隊尾,需要工人做工時,從隊頭選派工人。,P76#17 對于下面的程序調(diào)用過程,請問入棧序列是( ), 出棧次序是( )。,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
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 人事調(diào)令模板
- 四川巴中圖書館招聘試題帶答案分析2024年
- 2024“安全生產(chǎn)事故隱患排查”知識競賽試卷附答案詳解
- 2024年云南經(jīng)濟管理學(xué)院附屬高級中學(xué)招聘教師考試真題
- 聚氯乙烯生產(chǎn)流程的質(zhì)量控制與提升方法
- 建筑公司市政工程井蓋安裝高度差控制制度
- 4.1 整式-課時2 多項式及整式【勤徑學(xué)升】2025-2026學(xué)年數(shù)學(xué)七年級上冊
- 普通班三年級漢語教案第一課
- 建筑公司勞保用品穿戴檢查監(jiān)督管理辦法
- 2024年黔南州龍里縣招聘教師真題
- 【課件】第五單元化學(xué)反應(yīng)的定量關(guān)系新版教材單元分析九年級化學(xué)人教版(2024)上冊
- 十堰房縣國有企業(yè)招聘筆試題庫2024
- 滬教版小學(xué)六年級語文上學(xué)期考前練習(xí)試卷-含答案
- 04S519小型排水構(gòu)筑物(含隔油池)圖集
- 外研版(2024)七年級上冊英語全冊教案教學(xué)設(shè)計
- 研討報告的格式范文模板
- 山東省青島市2023-2024學(xué)年五年級下學(xué)期6月期末科學(xué)試題
- GB/T 44130.1-2024電動汽車充換電服務(wù)信息交換第1部分:總則
- 中考重慶作文滿分范文英語
- 傷口造口進修匯報護理
- GB/T 43635-2024法庭科學(xué)DNA實驗室檢驗規(guī)范
評論
0/150
提交評論