數(shù)據(jù)結(jié)構(gòu)之隊列數(shù)組和表

1、1065865姓名姓名 學(xué)號學(xué)號 成績成績 班級班級 李紅李紅 9761059 95 機(jī)機(jī)97.6 ABCDEFG第二章第二章 數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法(續(xù)續(xù)) 2.3 2.3 棧和隊列棧和隊列棧和隊列棧和隊列是兩種特殊的線性表，它們是運(yùn)算時要受到某些限制的線性表，故也稱為限定性的數(shù)據(jù)限定性的數(shù)據(jù)結(jié)構(gòu)結(jié)構(gòu)。(續(xù)續(xù)) 隊列的主要運(yùn)算隊列的主要運(yùn)算（1）設(shè)置一個空隊列；）設(shè)置一個空隊列；（2）插入一個新的隊尾元素，稱為進(jìn)隊；）插入一個新的隊尾元素，稱為進(jìn)隊；（3）刪除隊頭元素，稱為出隊；）刪除隊頭元素，稱為出隊；（4）讀取隊頭元素；）讀取隊頭元素；2.3.2 隊列隊列2.3.2.1 隊列的定義

2、與運(yùn)算隊列的定義與運(yùn)算 定義：定義：一種特殊的線性結(jié)構(gòu)，限定只能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表 。此種結(jié)構(gòu)稱為先進(jìn)先出（先進(jìn)先出（FIFO）表表。 a1 , a2 , a3 , a4 , an-1 , an 隊 列 示 意 圖隊頭隊尾2. 隊列的存儲結(jié)構(gòu)隊列的存儲結(jié)構(gòu)（1）順序存儲結(jié)構(gòu)(a) 線性隊列 (b) 循環(huán)隊列(a)線性隊列線性隊列 3 2 1 0 (a)rear=front=-1(隊空）隊空） e3 e4 (c)e1,e2出隊，出隊，e4入隊入隊 隊隊 滿滿rear =4front e1 e2 e3 (b)rearfront(b)e1,e2,e3入隊入隊隊空時，隊空

3、時， 令令rear=front=-1，當(dāng)有當(dāng)有新元素入隊時，尾指針加新元素入隊時，尾指針加1，當(dāng)有元，當(dāng)有元素出隊時，頭指針加素出隊時，頭指針加1。故在非空隊。故在非空隊列中，列中，頭指針頭指針始終指向始終指向隊頭元素前一隊頭元素前一個位置個位置，而，而尾指針尾指針始終指向始終指向隊尾元素隊尾元素的位置的位置(b) 循環(huán)隊列循環(huán)隊列 rear front 0 1 2 3(3) 隊空隊空隊滿條件隊滿條件：(Q.rear+1)%MAX=Q.front注：實際上為了避免與隊空標(biāo)注：實際上為了避免與隊空標(biāo)志沖突，還留有一個空間。志沖突，還留有一個空間。將頭尾連接成一將頭尾連接成一個環(huán)，形成循環(huán)個環(huán)，形

4、成循環(huán)隊列。隊列。 rear(1)一般情況一般情況 front 0 1 2 3e4e3 (2) 隊滿隊滿 front e3 e4 0 1 2 3 reare5循環(huán)隊列中加入一個元素的算法：循環(huán)隊列中加入一個元素的算法： int EnQueue(int Q ,int x, int *pf,int *pr) QmaxQmax已已有的循環(huán)有的循環(huán)隊列隊列將插入將插入的值的值已有隊列已有隊列的頭指針的頭指針已有隊列已有隊列的尾指針的尾指針循環(huán)隊列中加入一個元素的算法：循環(huán)隊列中加入一個元素的算法： int EnQueue(int Q ,int x, int *pf,int *pr) int front

5、, rear; front=*pf; rear=*pr; if(rear+1)%MAX= =front) return(0); else rear=(rear+1)%MAX; Qrear=x; *pr=rear; return(1); rearMax=4,Rear+1=4 front 0 1 2 3e4e3 rear(Rear+1)%4=0 front 0 1 2 3e4e3rearrear rear front 0 1 2 3e4e3x x循環(huán)隊列中刪除一個元素的算法：循環(huán)隊列中刪除一個元素的算法：int DeQueue(int Q ，int *py， int *pf，int *pr) 已有

6、的循環(huán)已有的循環(huán)隊列隊列返回刪返回刪除的值除的值的地址的地址已有隊列已有隊列的頭指針的頭指針已有隊列已有隊列的尾指針的尾指針循環(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); an a2 a1 an a3 a2 Q.frontQ.rear 刪刪 除除

7、一個元素一個元素 添加添加 一個元素一個元素e a1 a2 anQ.frontQ.rear （2） 鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)Q.frontQ.rear隊頭隊尾Q.rearQ.front2.4 數(shù)數(shù) 組組2.4.1 二維數(shù)組的定義二維數(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)置運(yùn)算（

8、3） 數(shù)組的鏈接存儲結(jié)構(gòu)十字鏈表結(jié)構(gòu)242 數(shù)組的順序存儲結(jié)構(gòu)數(shù)組的順序存儲結(jié)構(gòu) 243 矩陣的壓縮存儲矩陣的壓縮存儲（1） 按行優(yōu)先順序存放（2） 按列優(yōu)先順序存放1、 特殊矩陣（1） 下三角陣（2） 三對角陣1、 稀疏矩陣（1） 順序存儲結(jié)構(gòu)三元組表示法（2） 順序存儲結(jié)構(gòu)稀疏矩陣的轉(zhuǎn)置運(yùn)算（3） 數(shù)組的鏈接存儲結(jié)構(gòu)十字鏈表結(jié)構(gòu)242 數(shù)組的順序存儲結(jié)構(gòu)數(shù)組的順序存儲結(jié)構(gòu) 243 矩陣的壓縮存儲矩陣的壓縮存儲 amn . am2 am1 . a2n . a22 a21 a1n . a12 a11 a11 a12 . a1n a21 a22 . a2n am1 am2 . amn .loc(

9、aij)=loc(a11)+(i-1)n+(j-1)S 按行優(yōu)先順序存放按行優(yōu)先順序存放 amn . a2n a1n . am2 . a22 a12 am1 . a21 a11 a11 a12 . a1n a21 a22 . a2n am1 am2 . amn .loc(aij)=loc(a11)+(j-1)m+(i-1)S 按列優(yōu)先順序存放按列優(yōu)先順序存放 a11 0 0 . 0 a21 a22 0 . 0 an1 an2 an3. ann . 0A=按行優(yōu)先存放按行優(yōu)先存放a11 , a21 , a22 , a31 , a32 , , an1 , an2 , , ann 前前i-1行非零元

10、素個數(shù)行非零元素個數(shù) R= i(i-1)2loc(aij)=loc(a11)+( +(j-1)S i(i-1)2i-1R=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)先存放按行優(yōu)先存放a11 , a12 , a21 , a22 , a23 , a32 , a34 , an,n-1 , ann loc(aij)=loc(a11)+2(i-1)n+(j-1)S 三對角陣三對角陣 7 0 0 0 15 0 0 -4 0

11、 0 0 0 -2 0 0 0 0 21 0 0 0 -1 0 0M= 21 6 4 -2 1 4 -1 4 3 -4 2 2 15 5 1 7 1 1列列行行值值順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)三元組表示法三元組表示法 7 0 0 0 15 0 0 -4 0 0 0 0 -2 0 0 0 0 21 0 0 0 -1 0 0 21 6 4 -1 4 3 -4 2 2 15 5 1 7 1 1 -2 1 4 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)置運(yùn)算順序存儲結(jié)構(gòu)稀疏矩陣的轉(zhuǎn)置運(yùn)算 -1 3 4 7 1 1 -2

12、4 1 -4 2 2 15 1 5 21 4 6 求轉(zhuǎn)置矩陣的算法描述為：求轉(zhuǎn)置矩陣的算法描述為：Status TransposeSMatrix(TSMatrix M, TSMatrix &T)/采用三元組表存儲稀疏矩陣，求稀疏矩陣采用三元組表存儲稀疏矩陣，求稀疏矩陣M的轉(zhuǎn)置矩陣的轉(zhuǎn)置矩陣TT.mu=M.nu; T.nu=M.mu; T.tu=M.tu; / 互換行列數(shù)互換行列數(shù)if (T.tu0) q=1;for(col=1;col=M.nu; +col) / 對稀疏矩陣的每一列分別處理對稀疏矩陣的每一列分別處理 for(p=1; p=M.tu; +p) / 按行掃描三元組表按行掃描三元組表

13、 if(M.dataP.j= =col T.dataq.i=M.datap.j; T.dataq.j=M.datap.i; T.dataq.e=M.datap.e; +q return OK;/TransposeSMatrix 7 0 0 0 15 0 0 -4 0 0 0 0 -2 0 0 0 0 21 0 0 0 -1 0 0M=2-42515 11-2 4621 41714-1 3 j e rightdown i24 數(shù)數(shù) 組組 （ 線性表的推廣）線性表的推廣）241 二維數(shù)組的定義二維數(shù)組的定義 a1 a11 a12 . a1n a2 a21 a22 . a2n am am1 am2

14、. amn .ai=( ai1 , ai2 , . , ain ) ( 1=i=n )數(shù)組的運(yùn)算主要是存取元素、修改相應(yīng)的元素。數(shù)組的運(yùn)算主要是存取元素、修改相應(yīng)的元素。（1） 按行優(yōu)先順序存放按行優(yōu)先順序存放（2） 按列優(yōu)先順序存放按列優(yōu)先順序存放243 矩陣的壓縮存儲矩陣的壓縮存儲1、 特殊矩陣：值相同元素或非零元素的分布具有一定規(guī)律。特殊矩陣：值相同元素或非零元素的分布具有一定規(guī)律。（1） 下三角陣下三角陣（2） 三對角陣三對角陣2、 稀疏矩陣稀疏矩陣 ：元素分布無規(guī)律。：元素分布無規(guī)律。（1） 順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)三元組表示法三元組表示法（2） 順序存儲結(jié)構(gòu)稀疏矩陣的轉(zhuǎn)置運(yùn)算順序存

15、儲結(jié)構(gòu)稀疏矩陣的轉(zhuǎn)置運(yùn)算（3） 數(shù)組的鏈接存儲結(jié)構(gòu)數(shù)組的鏈接存儲結(jié)構(gòu)十字鏈表結(jié)構(gòu)十字鏈表結(jié)構(gòu)242 數(shù)組的順序存儲結(jié)構(gòu)數(shù)組的順序存儲結(jié)構(gòu) a11 a12 . a1n a21 a22 . a2n . am1 am2 . amn a11 a12 . a1n a21 a22 . a2n am1 am2 . amn .loc(aij)=loc(a11)+(i-1)n+(j-1)S 按行優(yōu)先順序存放按行優(yōu)先順序存放 a11 a21 . am1 a12 a22 . am2 . a1n a2n . amn a11 a12 . a1n a21 a22 . a2n am1 am2 . amn .loc(aij)

16、=loc(a11)+(j-1)m+(i-1)S 按列優(yōu)先順序存放按列優(yōu)先順序存放 a11 0 0 . 0 a21 a22 0 . 0 an1 an2 an3. ann . 0A=按行優(yōu)先存放按行優(yōu)先存放a11 , a21 , a22 , a31 , a32 , , an1 , an2 , , ann 前前i-1行非零元素個數(shù)行非零元素個數(shù) R= i(i-1)2loc(aij)=loc(a11)+(i(i-1)/2 +(j-1)S i-1R=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 a

17、32 a33 a34 0 . 0 0 0 .an,n-1 an,n按行優(yōu)先存放按行優(yōu)先存放a11 , a12 , a21 , a22 , a23 , a32 , a33 , an,n-1 , an,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 0M= 21 6 4 -2 1 4 -1 4 3 -4 2 2 15 5 1 7 1 1列列行行值值順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)三元組表示法三元組表示法 7 0 0 0 15 0 0 -4 0 0 0 0 -2 0 0

18、0 0 21 0 0 0 -1 0 0 21 6 4 -1 4 3 -4 2 2 15 5 1 7 1 1 -2 1 4 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)置運(yùn)算順序存儲結(jié)構(gòu)稀疏矩陣的轉(zhuǎn)置運(yùn)算 -1 3 4 7 1 1 -2 4 1 -4 2 2 15 1 5 21 4 6 求轉(zhuǎn)置矩陣的算法描述為：求轉(zhuǎn)置矩陣的算法描述為：Status TransposeSMatrix(TSMatrix M, TSMatrix &T)T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; / 互換行列數(shù)互換行

19、列數(shù)if (T.tu !=0) q=1;for(col=1;col=M.nu; +col) / 對稀疏矩陣的每一列分別處理對稀疏矩陣的每一列分別處理 for(p=1; p=M.tu; +p) / 按行掃描三元組表按行掃描三元組表 if(M.dataP.j= =col T.dataq.i=M.datap.j; T.dataq.j=M.datap.i; T.dataq.e=M.datap.e; +q return OK;/TransposeSMatrix 7 0 0 0 15 0 0 -4 0 0 0 0 -2 0 0 0 0 21 0 0 0 -1 0 0M=22-41515 41-2 4621

20、 11734-1 i j edown right鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)表示第表示第3 3列空列空 7 0 0 0 15 0 0 -4 0 0 0 0 -2 0 0 0 0 21 0 0 0 -1 0 0M=22-41515 41-2 4621 11734-1 i j edown right鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)作業(yè)：作業(yè)：P76 P76 第第1212、1616題題 第第1818、1919題題A+B*C-D/E；top1初態(tài);(a)top2OSNSBA+;(b)OS*C NST1=B*CA+;(c)NSOST1T2;(d)NSOST2=A+T1EDT2/-;(e)NSOST3T2-;(f)T

21、3=D/ENSOS(g)NSOST4；T4=T2-T3(h)A-B/C+D*E；top2初態(tài);(a)OSNSBA;(b)OS/C NSA;(c)NSOST1T1=B/CA;(d)NSOST1 DE+*T2T1A+;(e)NSOST2=D*ET2T3+;(f)T3=A-T1NSOST4=T2+T3(g)NSOST4；(h)優(yōu)先級相同時，應(yīng)先處理棧中數(shù)據(jù)錯在哪？錯在哪？ 假設(shè)一個算術(shù)表達(dá)式中包含圓括弧、方括弧和花括弧三種類型的假設(shè)一個算術(shù)表達(dá)式中包含圓括弧、方括弧和花括弧三種類型的括弧括弧,編寫一個判別表達(dá)式中括弧是否正確配對的函數(shù)編寫一個判別表達(dá)式中括弧是否正確配對的函數(shù).#define siz

22、e 100int Correct(char expsize , int len) char ssize; int top=0, i=0,tag=1;while(i0) tag=0; return tag; 假設(shè)一個算術(shù)表達(dá)式中包含圓括弧、方括弧和花括弧三種類型的假設(shè)一個算術(shù)表達(dá)式中包含圓括弧、方括弧和花括弧三種類型的括弧括弧,編寫一個判別表達(dá)式中括弧是否正確配對的函數(shù)編寫一個判別表達(dá)式中括弧是否正確配對的函數(shù).void main()int len, tag;char expsize=“dsgdsg(wetewteewtwrwer)etewtewtwetwetetwet;len=strlen(e

23、xp);tag=Correct(exp, len);if (tag=1) printf(rightn);else printf(wrongn);輸出結(jié)果：wrong 設(shè)棧S為空，隊Q的狀態(tài)是abcd，其中a為隊首元素，d為隊尾元素，經(jīng)過下面兩個操作后，隊Q的狀態(tài)是（ ）。（1）刪除隊Q中的元素，將刪除的元素插入棧S，直到隊Q為空。（2）依次將棧S中的元素插入隊Q，直到棧S為空。 (a) abcd (b) acbd (c) dcba (d) bacddcbafrontreartop隊Q棧Sfrontreardcbatop隊Q棧Sabcdfrontreartop隊Q棧Sc 若進(jìn)棧序列為若進(jìn)棧序列為

24、3，5，7，9，進(jìn)棧過程中可以出棧，則不可能的進(jìn)棧過程中可以出棧，則不可能的一個出棧次序是（一個出棧次序是（ ）。）。 (a) 7,5,3,9 (b) 9,7,5,3 (c) 7,5,9,3 (d) 9,5,7,3 若進(jìn)棧序列為若進(jìn)棧序列為3，5，7，9，進(jìn)棧過程中可以出棧，則不可能的進(jìn)棧過程中可以出棧，則不可能的一個出棧次序是（一個出棧次序是（ ）。）。 (a) 7,5,3,9 (b) 9,7,5,3 (c) 7,5,9,3 (d) 9,5,7,3dAnAT+1AT.A1AT是棧頂元素是棧頂元素T1030 40base.T=T+1 用一維數(shù)組設(shè)計棧，初態(tài)是棧用一維數(shù)組設(shè)計棧，初態(tài)是?？?，空，top=0?，F(xiàn)有輸入序列是。現(xiàn)有輸入序列是 a、b、c、d，經(jīng)過經(jīng)過 push、push、pop、push、pop、push操作后，輸出序列是（操作后，輸出序列是（ ），），棧頂指針是（棧頂指針是（ ）bc2P76#16.