中南大学：数据结构：第二章-2-4

10 65
865
9761059 95 97.6
()
()
1
2
3
4
2.3.2
2.3.2.1
FIFO
a1,a2,a3,a4,………… an-1,an
2,
1
(a)
(b)
(a)
3
2
1
0
(a)
rear=front=-1(
e3
e4
(c)
(c) e1,e2e4
rear =4
front
e1
e2
e3
(b)
rear
front
(b)e1,e2,e3
rear=front=-111
(b)
rear front
0
1
2
3
(3)
(Q.rear+1)%MAX=Q.front
e4
e3
(2)
front
e3
e4
0
1
2
3
rear
e5
int EnQueue(int Q[ ],int x,int *pf,int *pr)
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;
Q[rear]=x;
*pr=rear;
return(1);}
}
e4
e3
int DeQueue(int Q[ ]int *py int *pfint *pr)
int DeQueue(int Q[ ]int *pyint *pfint *pr)
{ int front,rear;
front=*pf; rear=*pr;
if(rear= =front) return(0);
else
{ front=(front+1)%MAX;
*py=Q[front];
*pf=front;
return(1);}
}
an
a2
a1
an
a3
a2
Q.front
Q.rear
e ^a1 a2 anQ.front
Q.rear
2
Q.front
Q.rear
Q.rear
Q.front
24
241
a1 a11 a12 …….,a 1n
a2 a21 a22 …….,a 2n
am am1 am2 …….,a mn
………………….
ai=( ai1,ai2,……..,ain ) ( 1<=i<=n )
1
2
243
1
1
2
2
1 ——
2
3 ——
242
a11
a12
…….
a1n
a21
a22
…….,
a2n
……….
am1
am2
…….,
amn
a11 a12 …….,a 1n
a21 a22 …….,a 2n
am1 am2 …….,a mn
………………….
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
a21 a22 0…….,0
an1 an2 an3…….,ann
…………………,0
A=
{a11,a21,a22,a31,a32,…,an1,an2,…,ann}
i-1 ∑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
{a11,a12,a21,a22,a23,a32,a33,…a n,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=
2164
-214
-143
-422
1551
711
——
7 0 0 0 15 0
0 -4 0 0 0 0
-2 0 0 0 0 21
0 0 0 -1 0 0
2164
-143
-422
1551
711
-214
7 0 0 -20 -4 0 0
15 0 0 0
0 0 0 0
0 0 -1 0
0 0 0 21
-134
711
-241
-422
1515
2146
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=
2 2 -4
1 5 15
4 1 -2 4 6 21
1 1 7
3 4 -1
^
i j e
down right
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=
2 2 -4
1 5 15
4 1 -2 4 6 21
1 1 7
3 4 -1
^
i j e
down right
A+B*C-D/E
top1 ;
(a)
top2
OSNS
B
A
+;
(b)
OS
*C
NS
T1=B*C
A
+;
(c)
NS OS
T1
T2 ;
(d)
NS OS
T2=A+T1
E
D
T2
/
-;
(e)
NS OS
T3
T2
-;
(f)
T3=D/E
NS OS
(g)
NS OS
T4
T4=T2-T3
(h)
A-B/C+D*E
top2;
(a)
OSNS
B
A ;
(b)
OS
/C
NS
A ;
(c)
NS OS
T1
T1=B/C
A ;
(d)
NS OS
T1
D
E
+* T2
T1
A
+;
(e)
NS OS
T2=D*E
T2
T3
+;
(f)
T3=A-T1
NS OS
T4=T2+T3
(g)
NS OS
T4
(h)
P76#11,.
# de f in e s iz e 1 0 0
i n t C o rre ct( ch a r ex p [ siz e],i n t l en )
{ cha r s[ siz e]; i n t t o p =0,i =0,t a g =1;
w h i l e(i< l en && ta g ! =0)
{ i f ( ex p [ i ] ==? (? | | e x p [ i ] ==? [?
| | e x p [ i ] ==? {? )
{ to p ++ ;
s[ t o p ] =e x p [ i ] ; }
i f ( ex p [ i ] ==? )? ) { i f ( s[ t o p ] ==? (? ) top -- ;
el se tag =0;}
i f ( ex p [ i ] ==? ]? ) { i f ( s[ t o p ] ==? [? ) top -- ;
el se tag =0;}
i f ( ex p [ i ] ==? }? ) { i f ( s[ t o p ] ==? {? ) t o p -- ;
el se tag =0;}
i ++ ; } i f ( t o p >0) t a g = 0 ; retu rn t a g ; }
void main()
{
int len,tag;
char exp[size]=“dsgdsg(wetewt{eewtwrwer)etewtewt[wetwet]etwet}";
len=strlen(exp);
tag=Correct(exp,len);
if (tag==1)
printf("right\n");
else
printf("wrong\n");
}
wrong
P76#12 S Q abcd a
d Q
1 Q S Q
2 S Q S
(a) abcd (b) acbd (c) dcba (d) bacd
d
c
b
afront
rear
top
Q S
front
rear d
c
b
a
top
Q S
a
b
c
dfront
rear
top
Q S
c
P76#13 3579
(a) 7,5,3,9
(b) 9,7,5,3
(c) 7,5,9,3
(d) 9,5,7,3
P76#13 3579
(a) 7,5,3,9
(b) 9,7,5,3
(c) 7,5,9,3
(d) 9,5,7,3
d
A[n]
A[T+1]
A[T] ….
A[1]
A[T]
T
10
30
40
base
P76#14
….
T=T+1
P76#15 top=0 abcd pushpushpoppush
poppush
bc
2
P76#16.
P76#17
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++) q[ii,jj]=0;
if ( (a.tu * b.tu) !=0 )
{for (int row=1; row<=b.mu; row++) num[row]=0;
for (int t=1; t<=b.tu; t++) num[b.data[t].i ]+=1;
pos[1]=1;
for (row=2; row<=b.mu+1; row++)
pos[row]=pos[row-1]+num[row-1];
for ( int p=1; p<=a.tu; p++) {row=a.data[p].j; int u=a.data[p].i; }
for (int g=pos[row]; g<=pos[row+1]-1; g++)
{int w=b.data[g].j; q[u,w]+=a.data[p].v*b.data[g].v; } }
P76#19
aij i>=j
B 1… n(n+1)/2] aij
B i *( i -1 ) / 2 + j