数据结构之队列数组和表

DATA1065865姓名学号成绩班级李红976105995机97.6ABCDEFG数据结构第二章

数据结构与算法(续)

2.3栈和队列栈和队列是两种特殊的线性表，它们是运算时要受到某些限制的线性表，故也称为限定性的数据结构。(续)

队列的主要运算（1）设置一个空队列；（2）插入一个新的队尾元素，称为进队；（3）删除队头元素，称为出队；（4）读取队头元素；2.3.2队列2.3.2.1队列的定义与运算

定义：一种特殊的线性结构，限定只能在表的一端进行插入，在表的另一端进行删除的线性表。此种结构称为先进先出（FIFO）表。

a1,

a2,

a3,

a4,…………

an-1,

an队列示意图队头队尾2.队列的存储结构（1）顺序存储结构(a)线性队列(b)循环队列(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)

循环队列

rearfront

0123(3)队空队满条件：(Q.rear+1)%MAX=Q.front注：实际上为了避免与队空标志冲突，还留有一个空间。将头尾连接成一个环，形成循环队列。

rear(1)一般情况front0123e4e3

(2)

队满fronte3

e40123reare5循环队列中加入一个元素的算法：

intEnQueue(intQ[],intx,int*pf,int*pr)Q[max]已有的循环队列将插入的值已有队列的头指针已有队列的尾指针循环队列中加入一个元素的算法：

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循环队列中删除一个元素的算法：intDeQueue(intQ[]，int*py，int*pf，int*pr)已有的循环队列返回删除的值的地址已有队列的头指针已有队列的尾指针循环队列中删除一个元素的算法：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）链式存储结构Q.frontQ.rear队头队尾Q.rearQ.front2.4数组2.4.1二维数组的定义a1a11a12……..a1n

a2a21a22……..a2n

amam1am2……..amn

….ai=(ai1,

ai2,

……..

,

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

按行优先顺序存放（2）

按列优先顺序存放1、

特殊矩阵（1）

下三角阵（2）

三对角阵1、

稀疏矩阵（1）

顺序存储结构——三元组表示法（2）

顺序存储结构稀疏矩阵的转置运算（3）

数组的链接存储结构——十字链表结构2．4．2数组的顺序存储结构2．4．3矩阵的压缩存储（1）

按行优先顺序存放（2）

按列优先顺序存放1、

特殊矩阵（1）

下三角阵（2）

三对角阵1、

稀疏矩阵（1）

顺序存储结构——三元组表示法（2）

顺序存储结构稀疏矩阵的转置运算（3）

数组的链接存储结构——十字链表结构2．4．2数组的顺序存储结构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

按行优先顺序存放

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

按列优先顺序存放

a11

0

0

……..0

a21a22

0

……..0

an1an2

an3……..ann

….0A=按行优先存放{a11,

a21,

a22,

a31,

a32,…,

an1,

an2,…,

ann}

前i-1行非零元素个数∑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.按行优先存放{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列行值顺序存储结构——三元组表示法

7000150

0-40000

-2000021000-1002164-143-4221551711-214

700-2

0-400

00-100000

15000

00021顺序存储结构稀疏矩阵的转置运算

-134711-241-42215152146

求转置矩阵的算法描述为：StatusTransposeSMatrix(TSMatrixM,TSMatrix&T){//采用三元组表存储稀疏矩阵，求稀疏矩阵M的转置矩阵TT.mu=M.nu;T.nu=M.mu;T.tu=M.tu;//互换行列数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数组（线性表的推广）2．4．1二维数组的定义a1a11a12……..a1n

a2a21a22……..a2n

amam1am2……..amn

….ai=(ai1,

ai2,

……..

,

ain)(1<=i<=n)数组的运算主要是存取元素、修改相应的元素。（1）

按行优先顺序存放（2）

按列优先顺序存放2．4．3矩阵的压缩存储1、

特殊矩阵：值相同元素或非零元素的分布具有一定规律。（1）

下三角阵（2）

三对角阵2、

稀疏矩阵：元素分布无规律。（1）

顺序存储结构——三元组表示法（2）

顺序存储结构稀疏矩阵的转置运算（3）

数组的链接存储结构——十字链表结构2．4．2数组的顺序存储结构

a11a12…….a1n

a21

a22……..a2n……….am1

am2……..

amn

a11a12……..a1n

a21a22……..a2n

am1am2……..amn

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

按行优先顺序存放

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

按列优先顺序存放

a11

0

0

……..0

a21a22

0

……..0

an1an2

an3……..ann

….0A=按行优先存放{a11,

a21,

a22,

a31,

a32,…,

an1,

an2,…,

ann}

前i-1行非零元素个数∑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按行优先存放{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列行值顺序存储结构——三元组表示法

7000150

0-40000

-2000021000-1002164-143-4221551711-214

700-2

0-400150000000

00-10

00021顺序存储结构稀疏矩阵的转置运算

-134711-241-42215152146

求转置矩阵的算法描述为：StatusTransposeSMatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;//互换行列数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链式存储结构表示第3列空

7000150

0-40000

-2000021

000-100M=22-4∧∧1515∧∧41-2∧4621∧∧11734-1∧∧^ijedownright链式存储结构作业：P76第12、16题第18、19题A+B*C-D/E；top1初态;(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初态;(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)优先级相同时，应先处理栈中数据错在哪？P76#11

假设一个算术表达式中包含圆括弧、方括弧和花括弧三种类型的括弧,编写一个判别表达式中括弧是否正确配对的函数.P76#11

假设一个算术表达式中包含圆括弧、方括弧和花括弧三种类型的括弧,编写一个判别表达式中括弧是否正确配对的函数.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");}输出结果：wrongP76#12

设栈S为空，队Q的状态是abcd，其中a为队首元素，d为队尾元素，经过下面两个操作后，队Q的状态是（）。（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用一维数组设计栈，初态是栈空，top=0。现有输入序列是a、b、c、d，经过push、push、pop、push、pop、push操作后，输出序列是（），栈顶指针是（