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

DATA1065865姓名學(xué)號(hào)成績(jī)班級(jí)李紅976105995機(jī)97.6ABCDEFG數(shù)據(jù)結(jié)構(gòu)第二章

數(shù)據(jù)結(jié)構(gòu)與算法(續(xù))

2.3棧和隊(duì)列棧和隊(duì)列是兩種特殊的線性表，它們是運(yùn)算時(shí)要受到某些限制的線性表，故也稱為限定性的數(shù)據(jù)結(jié)構(gòu)。(續(xù))

隊(duì)列的主要運(yùn)算（1）設(shè)置一個(gè)空隊(duì)列；（2）插入一個(gè)新的隊(duì)尾元素，稱為進(jìn)隊(duì)；（3）刪除隊(duì)頭元素，稱為出隊(duì)；（4）讀取隊(duì)頭元素；2.3.2隊(duì)列2.3.2.1隊(duì)列的定義與運(yùn)算

定義：一種特殊的線性結(jié)構(gòu)，限定只能在表的一端進(jìn)行插入，在表的另一端進(jìn)行刪除的線性表。此種結(jié)構(gòu)稱為先進(jìn)先出（FIFO）表。

a1,

a2,

a3,

a4,…………

an-1,

an隊(duì)列示意圖隊(duì)頭隊(duì)尾2.隊(duì)列的存儲(chǔ)結(jié)構(gòu)（1）順序存儲(chǔ)結(jié)構(gòu)(a)線性隊(duì)列(b)循環(huán)隊(duì)列(a)線性隊(duì)列

3210(a)rear=front=-1(隊(duì)空）e3e4(c)e1,e2出隊(duì)，e4入隊(duì)

隊(duì)滿rear=4fronte1e2e3

(b)rearfront(b)e1,e2,e3入隊(duì)隊(duì)空時(shí)，令rear=front=-1，當(dāng)有新元素入隊(duì)時(shí)，尾指針加1，當(dāng)有元素出隊(duì)時(shí)，頭指針加1。故在非空隊(duì)列中，頭指針始終指向隊(duì)頭元素前一個(gè)位置，而尾指針始終指向隊(duì)尾元素的位置(b)

循環(huán)隊(duì)列

rearfront

0123(3)隊(duì)空隊(duì)滿條件：(Q.rear+1)%MAX=Q.front注：實(shí)際上為了避免與隊(duì)空標(biāo)志沖突，還留有一個(gè)空間。將頭尾連接成一個(gè)環(huán)，形成循環(huán)隊(duì)列。

rear(1)一般情況front0123e4e3

(2)

隊(duì)滿fronte3

e40123reare5循環(huán)隊(duì)列中加入一個(gè)元素的算法：

intEnQueue(intQ[],intx,int*pf,int*pr)Q[max]已有的循環(huán)隊(duì)列將插入的值已有隊(duì)列的頭指針已有隊(duì)列的尾指針循環(huán)隊(duì)列中加入一個(gè)元素的算法：

intEnQueue(intQ[],intx,int*pf,int*pr){intfront,rear;front=*pf;rear=*pr;if((rear+1)%MAX==front)return(0);else{rear=(rear+1)%MAX;Q[rear]=x;*pr=rear;return(1);}}

rearMax=4,Rear+1=4front0123e4e3

rear(Rear+1)%4=0front0123e4e3rear

rearfront0123e4e3x循環(huán)隊(duì)列中刪除一個(gè)元素的算法：intDeQueue(intQ[]，int*py，int*pf，int*pr)已有的循環(huán)隊(duì)列返回刪除的值的地址已有隊(duì)列的頭指針已有隊(duì)列的尾指針循環(huán)隊(duì)列中刪除一個(gè)元素的算法：intDeQueue(intQ[]，int*py，int*pf，int*pr){intfront,rear;front=*pf;rear=*pr;if(rear==front)return(0);else{front=(front+1)%MAX;*py=Q[front];*pf=front;return(1);}}ana2a1

ana3a2

Q.frontQ.rear刪除一個(gè)元素添加一個(gè)元素e^a1a2anQ.frontQ.rear

（2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)Q.frontQ.rear隊(duì)頭隊(duì)尾Q.rearQ.front2.4數(shù)組2.4.1二維數(shù)組的定義a1a11a12……..a1n

a2a21a22……..a2n

amam1am2……..amn

….ai=(ai1,

ai2,

……..

,

ain)(1<=i<=n)（1）

按行優(yōu)先順序存放（2）

按列優(yōu)先順序存放1、

特殊矩陣（1）

下三角陣（2）

三對(duì)角陣1、

稀疏矩陣（1）

順序存儲(chǔ)結(jié)構(gòu)——三元組表示法（2）

順序存儲(chǔ)結(jié)構(gòu)稀疏矩陣的轉(zhuǎn)置運(yùn)算（3）

數(shù)組的鏈接存儲(chǔ)結(jié)構(gòu)——十字鏈表結(jié)構(gòu)2．4．2數(shù)組的順序存儲(chǔ)結(jié)構(gòu)2．4．3矩陣的壓縮存儲(chǔ)（1）

按行優(yōu)先順序存放（2）

按列優(yōu)先順序存放1、

特殊矩陣（1）

下三角陣（2）

三對(duì)角陣1、

稀疏矩陣（1）

順序存儲(chǔ)結(jié)構(gòu)——三元組表示法（2）

順序存儲(chǔ)結(jié)構(gòu)稀疏矩陣的轉(zhuǎn)置運(yùn)算（3）

數(shù)組的鏈接存儲(chǔ)結(jié)構(gòu)——十字鏈表結(jié)構(gòu)2．4．2數(shù)組的順序存儲(chǔ)結(jié)構(gòu)2．4．3矩陣的壓縮存儲(chǔ)

amn……..

am2am1……….a2n……..

a22a21a1n

…….a12

a11

a11a12……..a1n

a21a22……..a2n

am1am2……..amn

….loc(aij)=loc(a11)+[(i-1)n+(j-1)]S

按行優(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)先順序存放

a11

0

0

……..0

a21a22

0

……..0

an1an2

an3……..ann

….0A=按行優(yōu)先存放{a11,

a21,

a22,

a31,

a32,…,

an1,

an2,…,

ann}

前i-1行非零元素個(gè)數(shù)∑R=i(i-1)2loc(aij)=loc(a11)+[(+(j-1)]S

i(i-1)2i-1R=1下三角陣

a11

a120

…………..0

a21a22

a23

0

………...00

0

……an-1,n-2an-1.n-1an-1,n………..A=

0

a21a22

a23

0

…..00

0

…………….an,n-1ann.按行優(yōu)先存放{a11,

a12,

a21,

a22,

a23,a32,a34,

…an,n-1,

ann}

loc(aij)=loc(a11)+[2(i-1)n+(j-1)]S

三對(duì)角陣

7000150

0-40000

-2000021000-100M=2164-214-143-4221551711列行值順序存儲(chǔ)結(jié)構(gòu)——三元組表示法

7000150

0-40000

-2000021000-1002164-143-4221551711-214

700-2

0-400

00-100000

15000

00021順序存儲(chǔ)結(jié)構(gòu)稀疏矩陣的轉(zhuǎn)置運(yùn)算

-134711-241-42215152146

求轉(zhuǎn)置矩陣的算法描述為：StatusTransposeSMatrix(TSMatrixM,TSMatrix&T){//采用三元組表存儲(chǔ)稀疏矩陣，求稀疏矩陣M的轉(zhuǎn)置矩陣TT.mu=M.nu;T.nu=M.mu;T.tu=M.tu;//互換行列數(shù)if(T.tu<>0){q=1;for(col=1;col<=M.nu;++col)//對(duì)稀疏矩陣的每一列分別處理

for(p=1;p<=M.tu;++p)//按行掃描三元組表

if(M.data[P].j==col{T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;++q}}returnOK;}//TransposeSMatrix

7000150

0-40000

-2000021

000-100M=2-4∧∧2515∧∧11-2∧4621∧∧41714-1∧∧3jerightdowni2．4數(shù)組（線性表的推廣）2．4．1二維數(shù)組的定義a1a11a12……..a1n

a2a21a22……..a2n

amam1am2……..amn

….ai=(ai1,

ai2,

……..

,

ain)(1<=i<=n)數(shù)組的運(yùn)算主要是存取元素、修改相應(yīng)的元素。（1）

按行優(yōu)先順序存放（2）

按列優(yōu)先順序存放2．4．3矩陣的壓縮存儲(chǔ)1、

特殊矩陣：值相同元素或非零元素的分布具有一定規(guī)律。（1）

下三角陣（2）

三對(duì)角陣2、

稀疏矩陣：元素分布無(wú)規(guī)律。（1）

順序存儲(chǔ)結(jié)構(gòu)——三元組表示法（2）

順序存儲(chǔ)結(jié)構(gòu)稀疏矩陣的轉(zhuǎn)置運(yùn)算（3）

數(shù)組的鏈接存儲(chǔ)結(jié)構(gòu)——十字鏈表結(jié)構(gòu)2．4．2數(shù)組的順序存儲(chǔ)結(jié)構(gòu)

a11a12…….a1n

a21

a22……..a2n……….am1

am2……..

amn

a11a12……..a1n

a21a22……..a2n

am1am2……..amn

….loc(aij)=loc(a11)+[(i-1)n+(j-1)]S

按行優(yōu)先順序存放

a11

a21…….

am1

a12

a22……..

am2……….

a1n

a2n……..

amn

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

a21a22

0

……..0

an1an2

an3……..ann

….0A=按行優(yōu)先存放{a11,

a21,

a22,

a31,

a32,…,

an1,

an2,…,

ann}

前i-1行非零元素個(gè)數(shù)∑R=i(i-1)2loc(aij)=loc(a11)+[(i(i-1)/2+(j-1)]S

i-1R=1下三角陣

a11

a120

…………..0

a21a22

a23

0

………...00

0

……an-1,n-2an-1.n-1an-1,n………..A=

0

a32a33

a34

0

…..00

0

…………….an,n-1an,n按行優(yōu)先存放{a11,

a12,

a21,

a22,

a23,a32,a33,

…an,n-1,

an,n}

loc(aij)=loc(a11)+2(i-1)+(j-1)

三對(duì)角陣

7000150

0-40000

-2000021000-100M=2164-214-143-4221551711列行值順序存儲(chǔ)結(jié)構(gòu)——三元組表示法

7000150

0-40000

-2000021000-1002164-143-4221551711-214

700-2

0-400150000000

00-10

00021順序存儲(chǔ)結(jié)構(gòu)稀疏矩陣的轉(zhuǎn)置運(yùn)算

-134711-241-42215152146

求轉(zhuǎn)置矩陣的算法描述為：StatusTransposeSMatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;//互換行列數(shù)if(T.tu!=0){q=1;for(col=1;col<=M.nu;++col)//對(duì)稀疏矩陣的每一列分別處理

for(p=1;p<=M.tu;++p)//按行掃描三元組表

if(M.data[P].j==col{T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;++q}}returnOK;}//TransposeSMatrix

7000150

0-40000

-2000021

000-100M=22-4∧∧1515∧∧41-2∧4621∧∧11734-1∧∧^ijedownright鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示第3列空

7000150

0-40000

-2000021

000-100M=22-4∧∧1515∧∧41-2∧4621∧∧11734-1∧∧^ijedownright鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)作業(yè)：P76第12、16題第18、19題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)T3=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)NSOST1DE+*T2T1A+;(e)NSOST2=D*ET2T3+;(f)T3=A-T1NSOST4=T2+T3(g)NSOST4；(h)優(yōu)先級(jí)相同時(shí)，應(yīng)先處理?xiàng)Ｖ袛?shù)據(jù)錯(cuò)在哪？P76#11

假設(shè)一個(gè)算術(shù)表達(dá)式中包含圓括弧、方括弧和花括弧三種類型的括弧,編寫一個(gè)判別表達(dá)式中括弧是否正確配對(duì)的函數(shù).P76#11

假設(shè)一個(gè)算術(shù)表達(dá)式中包含圓括弧、方括弧和花括弧三種類型的括弧,編寫一個(gè)判別表達(dá)式中括弧是否正確配對(duì)的函數(shù).voidmain(){intlen,tag;charexp[size]=“dsgdsg(wetewt{eewtwrwer)etewtewt[wetwet]etwet}";len=strlen(exp);tag=Correct(exp,len);if(tag==1)

printf("right\n");else

printf("wrong\n");}輸出結(jié)果：wrongP76#12

設(shè)棧S為空，隊(duì)Q的狀態(tài)是abcd，其中a為隊(duì)首元素，d為隊(duì)尾元素，經(jīng)過下面兩個(gè)操作后，隊(duì)Q的狀態(tài)是（）。（1）刪除隊(duì)Q中的元素，將刪除的元素插入棧S，直到隊(duì)Q為空。（2）依次將棧S中的元素插入隊(duì)Q，直到棧S為空。(a)abcd(b)acbd(c)dcba(d)bacddcbafrontreartop隊(duì)Q棧Sfrontreardcbatop隊(duì)Q棧Sabcdfrontreartop隊(duì)Q棧ScP76#13

若進(jìn)棧序列為3，5，7，9，進(jìn)棧過程中可以出棧，則不可能的一個(gè)出棧次序是（）。(a)7,5,3,9(b)

9,7,5,3(c)7,5,9,3(d)

9,5,7,3P76#13

若進(jìn)棧序列為3，5，7，9，進(jìn)棧過程中可以出棧，則不可能的一個(gè)出棧次序是（）。(a)7,5,3,9(b)

9,7,5,3(c)7,5,9,3(d)

9,5,7,3dA[n]A[T+1]A[T]….A[1]A[T]是棧頂元素T103040baseP76#14….T=T+1P76#15用一維數(shù)組設(shè)計(jì)棧，初態(tài)是?？?，top=0?，F(xiàn)有輸入序列是a、b、c、d，經(jīng)過push、push、pop、push、pop、push操作后，輸出序列是（），棧頂指針是（