------------- 【解答】
5 写一个算法，判断依次读入的一个以@为结束符的字母序列，是否形如‘序列1&序列2’的字符序列。序列1和序列2中都不含‘&’，且序列2是序列1 的逆序列。例如，’a+b&b+a’是属于该模式的字符序列，而’1+3&3-1’则不是。 【解答】算法如下： int IsHuiWen() {
Stack *S; Char ch,temp; InitStack(&S);
Printf(“\\n请输入字符序列：”); Ch=getchar();
While( ch!=&) /*序列1入栈*/ { Push(&S,ch); ch=getchar(); }
do /*判断序列2是否是序列1的逆序列*/ { ch=getchar(); Pop(&S,&temp);
if(ch!= temp) /*序列2不是序列1的逆序列*/
{ return(FALSE); printf(“\\nNO”);} } while(ch!=@ && !IsEmpty(&S)) if(ch = = @ && IsEmpty(&S))
{ return(TRUE); printf(“\\nYES”);} /*序列2是序列1的逆序列*/ else {return(FALSE); printf(“\\nNO”);} }/*IsHuiWen()*/
8 要求循环队列不损失一个空间全部都能得到利用，设置一个标志tag,以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此相应的入队与出队算法。 【解答】入队算法：
int EnterQueue(SeqQueue *Q, QueueElementType x) { /*将元素x入队*/ -------------
-------------
if(Q->front==Q->front && tag==1) /*队满*/ return(FALSE);
if(Q->front==Q->front && tag==0) /*x入队前队空，x入队后重新设置标志*/ tag=1;
Q->elememt[Q->rear]=x;
Q->rear=(Q->rear+1)%MAXSIZE; /*设置队尾指针*/ Return(TRUE);
}
出队算法：
int DeleteQueue( SeqQueue *Q , QueueElementType *x) { /*删除队头元素，用x返回其值*/
if(Q->front==Q->rear && tag==0) /*队空*/ return(FALSE);
*x=Q->element[Q->front];
Q->front=(Q->front+1)%MAXSIZE; /*重新设置队头指针*/
if(Q->front==Q->rear) tag=0; /*队头元素出队后队列为空，重新设置标志域*/ Return(TUUE); }
第4章 串
第四章答案
1 设s=’I AM A STUDENT’，t=’GOOD’， q=’WORKER’。给出下列操作的结果： 【解答】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’。
2编写算法，实现串的基本操作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];
case >0: /*串T的长度大于串V的长度*/ for(i=pos+t.ien;i
-------------
S->len=S->len-T.len+V.len;
case <0: /*串T的长度小于串V的长度*/ if(S->len-T.len+V.len)<= MAXLEN /*插入后串长小于MAXLEN*/ { /*将S中子串T后的所有字符后移V.len-T.len个位置*/ for(i=S->len-T.len+V.len;i>=pos+T.len;i--) S->ch[i]=S->ch[i-T.len+V.len];
for(i=0;i<=V.len;i++) /*用V替换T*/ S->ch[pos+i]=V.ch[i]; S->len=S->len-T.len+V.len; } else
{ /*替换后串长>MAXLEN,但串V可以全部替换*/ if(pos+V.len<=MAXLEN)
{ for(i=MAXLEN-1;i>=pos+T.len; i--) S->ch[i]=s->ch[i-T.len+V.len]
for(i=0;i<=V.len;i++) /*用V替换T*/ S->ch[pos+i]=V.ch[i]; S->len=MAXLEN;}
else /*串V的部分字符要舍弃*/ { for(i=0;i
pos=StrIndex(S,pos+V.len,T); /*求S中下一个子串T的位置*/ }/*while()*/ return(1);
}/*StrReplace()*/
第五章 数组和广义表
第五章答案
1.假设有6行8列的二维数组A，每个元素占用6个字节，存储器按字节编址。已知A的基地址为1000，计算：
（1） 数组A共占用多少字节； （288）
（2） 数组A的最后一个元素的地址； （1282） （3） 按行存储时，元素A36的地址； （1126） （4） 按列存储时，元素A36的地址； （1192）
4.设有三对角矩阵An×n,将其三条对角线上的元素逐行的存于数组B[1..3n-2]中，使得B[k]=aij，求：（1）用i,j表示k的下标变换公式；（2）用k表示i、j的下标变换公式。 【解答】（1）k=2(i-1)+j
(2) i=[k/3]+1, j=[k/3]+k%3 （[ ]取整，%取余）
5.在稀疏矩阵的快速转置算法5.2中，将计算position[col]的方法稍加改动，使算法只占用一个辅助向量空间。 【解答】算法（一）
FastTransposeTSMatrix(TSMartrix A, TSMatrix *B)
{/*把矩阵A转置到B所指向的矩阵中去，矩阵用三元组表表示*/
int col,t,p,q;
int position[MAXSIZE];
B->len=A.len; B->n=A.m; B->m=A.n; if(B->len>0) { -------------
-------------
position[1]=1;
for(t=1;t<=A.len;t++)
position[A.data[t].col+1]++; /*position[col]存放第col-1列非零元素的个数,
即利用pos[col]来记录第col-1列中非零元素的个数*/
/*求col列中第一个非零元素在B.data[ ]的位置，存放在position[col]中*/ for(col=2;col<=A.n;col++)
position[col]=position[col]+position[col-1]; for(p=1;p col=A.data[p].col; q=position[col]; B->data[q].row=A.data[p].col; B->data[q].col=A.data[p].row; B->data[q].e=A.data[p].e; Position[col]++; } } } 算法(二) FastTransposeTSMatrix(TSMartrix A, TSMatrix *B) { int col,t,p,q; int position[MAXSIZE]; B->len=A.len; B->n=A.m; B->m=A.n; if(B->len>0) { for(col=1;col<=A.n;col++) position[col]=0; for(t=1;t<=A.len;t++) position[A.data[t].col]++; /*计算每一列的非零元素的个数*/ /*从最后一列起求每一列中第一个非零元素在B.data[]中的位置，存放在position[col]中*/ for(col=A.n,t=A.len;col>0;col--) { t=t-position[col]; position[col]=t+1; } for(p=1;p col=A.data[p].col; q=position[col]; B->data[q].row=A.data[p].col; B->data[q].col=A.data[p].row; B->data[q].e=A.data[p].e; Position[col]++; } } } 8.画出下面广义表的两种存储结构图示： ((((a), b)), ((( ), d), (e, f))) 【解答】 ------------- ------------- 第一种存储结构 第二种存储结构 9.求下列广义表运算的结果： （1） HEAD[((a,b),(c,d))]; (a,b) （2） TAIL[((a,b),(c,d))]; ((c,d)) （3） TAIL[HEAD[((a,b),(c,d))]]; (b) （4） HEAD[TAIL[HEAD[((a,b),(c,d))]]]; b （5） TAIL[HEAD[TAIL[((a,b),(c,d))]]]; (d) 第六章 第六章答案 6． 1分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 【解答】 -------------