DATA1065865姓名學號成績班級李紅976105995機97.6ABCDEFG數(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,…………

an-1,

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

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

隊滿rear=4fronte1e2e3

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

循環(huán)隊列

rearfront

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

rear(1)一般情況front0123e4e3

(2)

隊滿fronte3

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

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

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)隊列中刪除一個元素的算法：intDeQueue(intQ[]，int*py，int*pf，int*pr)已有的循環(huán)隊列返回刪除的值的地址已有隊列的頭指針已有隊列的尾指針循環(huán)隊列中刪除一個元素的算法：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刪除一個元素添加一個元素e^a1a2anQ.frontQ.rear

（2）鏈式存儲結(jié)構(gòu)Q.frontQ.rear隊頭隊尾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）

三對角陣1、

稀疏矩陣（1）

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

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

數(shù)組的鏈接存儲結(jié)構(gòu)——十字鏈表結(jié)構(gòu)2．4．2數(shù)組的順序存儲結(jié)構(gòu)2．4．3矩陣的壓縮存儲（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)2．4．2數(shù)組的順序存儲結(jié)構(gòu)2．4．3矩陣的壓縮存儲

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行非零元素個數(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

三對角陣

7000150

0-40000

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

7000150

0-40000

-2000021000-1002164-143-4221551711-214

700-2

0-400

00-100000

15000

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

-134711-241-42215152146

求轉(zhuǎn)置矩陣的算法描述為：StatusTransposeSMatrix(TSMatrixM,TSMatrix&T){//采用三元組表存儲稀疏矩陣，求稀疏矩陣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)//對稀疏矩陣的每一列分別處理

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ù)組的運算主要是存取元素、修改相應的元素。（1）

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

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

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

下三角陣（2）

三對角陣2、

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

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

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

數(shù)組的鏈接存儲結(jié)構(gòu)——十字鏈表結(jié)構(gòu)2．4．2數(shù)組的順序存儲結(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行非零元素個數(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)

三對角陣

7000150

0-40000

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

7000150

0-40000

-2000021000-1002164-143-4221551711-214

700-2

0-400150000000

00-10

00021順序存儲結(jié)構(gòu)稀疏矩陣的轉(zhuǎ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)//對稀疏矩陣的每一列分別處理

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鏈式存儲結(jié)構(gòu)表示第3列空

7000150

0-40000

-2000021

000-100M=22-4∧∧1515∧∧41-2∧4621∧∧11734-1∧∧^ijedownright鏈式存儲結(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)先級相同時，應先處理棧中數(shù)據(jù)錯在哪？P76#11

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

假設(shè)一個算術(shù)表達式中包含圓括弧、方括弧和花括弧三種類型的括弧,編寫一個判別表達式中括弧是否正確配對的函數(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為空，隊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棧ScP76#13

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

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

9,5,7,3P76#13

若進棧序列為3，5，7，9，進棧過程中可以出棧，則不可能的一個出棧次序是（）。(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è)計棧，初態(tài)是棧空，top=0。現(xiàn)有輸入序列是a、b、c、d，經(jīng)過push、push、pop、push、pop、push操作后，輸出序列是（），棧頂指針是（