数据结构 用C语言描述 课后答案(7)

C.DATA[PC].E=A.DATA[PA].E; PA++;PC++;} ELSE

IF A.DATA[PA].I>B.DATA[PB].I {

C.DATA[PC].I=B.DATA[PB].I; C.DATA[PC].J=B.DATA[PB].J; C.DATA[PC].E=B.DATA[PB].E; PB++;PC++;} ELSE

IF A.DATA[PA].J

ELSE IF A.DATA[PA].J>B.DATA[PB].J {C.DATA[PC].I=B.DATA[PB].I; C.DATA[PC].J=B.DATA[PB].J; C.DATA[PC].E=B.DATA[PB].E; PB++;PC++;} ELSE

{IF A.DATA[PA].E+B.DATA[PB].E {C.DATA[PC].I=A.DATA[PA].I; C.DATA[PC].J=A.DATA[PA].J;

C.DATA[PC].E=A.DATA[PA].E+B.DATA[PB].E; }

PA++;PB++;PC++; }

}

WHILE(PA<=A.TU)

{C.DATA[PC].I=A.DATA[PA].I; C.DATA[PC].J=A.DATA[PA].J; C.DATA[PC].E=A.DATA[PA].E; PA++;PC++;} WHILE(PB<=B.TU)

{C.DATA[PC].I=B.DATA[PB].I; C.DATA[PC].J=B.DATA[PB].J; C.DATA[PC].E=B.DATA[PB].E; PB++;PC++;}

}

6、试编写算法，将数组A（0：N-1）中的元素循环右移K位，并要求只用一个元素大小的附加存储空间，元素移动或交换的次数为O（N）。 【解答】 MAIN()

{INT I,J,K,DIRECT,TOP,BUTTOM,N,TEMP; INT A[10]={0,1,2,3,4,5,6,7,8,9}; N=10;

PRINTF(\ SCANF(\ IF(K<0)

PRINTF(\ ELSE

{IF(K>=N) K=K%N; TOP=0;BUTTOM=N-1; DIRECT=1; WHILE(K!=0)

{IF(DIRECT==1)

{WHILE(BUTTOM-TOP+1-2*K>=0)

{FOR(J=BUTTOM;J>=BUTTOM-K+1;J--) {TEMP=A[J-K]; A[J-K]=A[J]; A[J]=TEMP; }

BUTTOM=J; }

IF(BUTTOM==(K-1+TOP)) K=0; ELSE

{DIRECT=0;

K=(BUTTOM-TOP+1)%K; } }

IF(DIRECT==0)

{WHILE(TOP+2*K-1<=BUTTOM) {FOR(J=TOP;J<=TOP+K-1;J++) {TEMP=A[J+K]; A[J+K]=A[J]; A[J]=TEMP; }

TOP=J; }

IF(TOP==(BUTTOM-K+1)) K=0; ELSE

{DIRECT=1;

K=(BUTTOM-TOP+1)%K; } } } }

FOR(I=0;I

PRINTF(\ }

GETCH(); }

7、若矩阵A M*N中的某个元素A[I，J]是第I行中的最小值，同时又是第J列中的最大值，则称其为该矩阵中的马鞍点，假设以二维数组存储矩阵，试编写求矩阵中的所有马鞍点。 【解答】略

8、三元组表的一种变型是：以三元组表中去掉行下标域得到二元组表，另设一个行起始向量，其每个分量是二元组表的一个下标值，用于指示一行中非零元素的起点，试编写算法，由矩阵元素的下标值I，J求矩阵元素。 【解答】

#DEFINE MAXSIZE 12500 #DEFINE MAXI 500 TYPEDEF STRUCT

{ELEMTYPE E; INT J; }2TRIPLE; TYPEDEF STRUCT

{2TRIPLE DATA[MAXSIZE+1]; INT RPOS[MAXI+1]; INT MU,NU,TU; }TSMATRIX;

ELEMTYPE INDEX(TSMATRIX A,INT I,INT J) {

IF(I>A.MU||J>A.NU) RETURN ERROR; POS=A.RPOS[I];

WHILE(POS<=A.TU&&POS

{IF A.DATA[POS].J=J RETURN(A.DATA[POS].E); IF A.DATA[POS].J>J RETURN(0); POS++; }

RETURN(0); }

9、三元组表的另一种变型是：不存矩阵元素的行、列下标，而存非零元在矩阵中以行为主序时排列的顺序号，试写一算法，由矩阵元素的下标值I，J求元素的值。 【解答】

#DEFINE MAXSIZE 12500 TYPEDEF STRUCT {INT INDEX; DATATYPE E; }2TRIPLE; TYPEDEF STRUCT

{2TRIPLE DATA[MAXSIZE+1]; INT MU,NU,TU;} TXMATRIX;

DATATYPE INDEX(TSMATRIX A,INT I,INT J) {

IF(I>A.MU||J>A.NU) RETURN ERROR; POS=(I-1)*NU+J; K=1;

WHILE(K<=A.TU)

{IF A.DATA[K].INDEX=POS RETURN(A.DATA[K].E; IF A.DATA[K].INDEX>POS RETURN(0); K++; }

RETURN(0); }

10、画出下列广义表的图形表示和它们的存储表示： (1) D(A(c), B(e), C(a, L(b, c, d))) (2) J1(J2(J1, a, J3(J1)), J3(J1))

【解答】(1) D(A(c), B(e), C(a, L(b, c, d))) (2) J1(J2(J1, a, J3(J1)), J3(J1))

11、广义表A=（（X，（A，B）），（X，（A，B），Y）），则运算 HEAD（HEAD（TAIL（A）））是（ X ）。

课后练习

一、设s=’I AM A STUDENT’, t=’GOOD’, q=’WORKER’。给出下列操作的结果：

StrLength(s); SubString(sub1,s,1,7); SubString(sub2,s,7,1); StrIndex(s,’A’,4); StrReplace(s,’STUDENT’,q); StrCat(StrCat(sub1,t), StrCat(sub2,q)); 【解答】StrLength(s)=14;

SubString(sub1,s,1,7) sub1=’I AM A ’; SubString(sub2,s,7,1) sub2=’ ’; StrIndex(s,4,’A’)=6;

StrReplace(s,’STUDENT’,q); s=’I AM A WORKER’;

StrCat(StrCat(sub1,t),StrCat(sub2,q)) sub1=’I AM A GOOD WORKER’。 二、编写算法，实现串的基本操作StrReplace(S,T,V)。 【解答】算法如下：

int strReplace(SString S,SString T, SString V) {/*用串V替换S中的所有子串T */ int pos,i;

pos=strIndex(S,1,T); /*求S中子串T第一次出现的位置*/ if(pos = = 0) return(0);

while(pos!=0) /*用串V替换S中的所有子串T */ {

switch(T.len-V.len) {

case 0: /*串T的长度等于串V的长度*/ for(i=0;i<=V.len;i++) /*用V替换T*/ S->ch[pos+i]=V.ch[i];

…… 此处隐藏：1297字，全部文档内容请下载后查看。喜欢就下载吧 ……