{
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
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()*/
附加题：用链式结构实现定位函数。 【解答】
typedef struct Node { char data;
struct Node *next; }Node,*Lstring;
int strIndex(Lstring S, int pos, Lstring T)
/*从串S的pos序号起，串T第一次出现的位置 */ {
Node *p, *q, *Ppos; int i=0，,j=0;
if(T->next= =NULL || S->next = =NULL) return(0); p=S->next; q=T->next;
while(p!=NULL && j
if(j!=pos) return(0); while(p!=NULL && q!=NULL) {
Ppos=p; /*Ppos指向当前匹配的起始字符*/ if(p->data = = q->data)
{p=p->next; q=q->next;}
else /*从Ppos指向字符的下一个字符起从新匹配*/
{p=Ppos->next; q=T->head->next; i++;} }
if(q= =NULL) return(pos+i); /*匹配成功*/ else return(0); /*失败*/ }
第五章 数组和广义表
参考题 实习题
习 题
1．
假设有6行8列的二维数组A，每个元素占用6个字节，存
储器按字节编址。已知A的基地址为1000，计算： （1） 数组A共占用多少字节； （288） （2） 数组A的最后一个元素的地址； （1282） （3） 按行存储时，元素A36的地址； （1126） （4） 按列存储时，元素A36的地址； （1192） [注意]：本章自定义数组的下标从1开始。
2． 设有三对角矩阵（aij）n×n ,将其三条对角线上的元素逐行地存于
数组B(1:3n-2)中，使得B[k]= aij ，求： （1） 用i,j表示k的下标变换公式； （2） 用k表示i,j的下标变换公式。
i = k/3 + 1, j = k%3 + i - 1 = k%3 + k/3 或：
i = k/3 + 1, j = k - 2×( k/3 )
2．
假设稀疏矩阵A和B均以三元组表作为存储结构。试写出矩
阵相加的算法，另设三元组表C存放结果矩阵。 [提示]：参考P.28例、P.47例。
4．在稀疏矩阵的快速转置算法5.2中，将计算position[col]的方法稍加改动，使算法
只占用一个辅助向量空间。 [提示]：
（1） position[ k ] 中为第k列非零元素个数，k = 1, 2, …, n （2） position[ 0 ] = 1; （第1列中第一个非零元素的正确位置） （3） position[ k ] = position[ k – 1 ] + position[ k ] , k = 1,
2, …, n
（4） position[ k ] = position[ k – 1 ] , k = n, n – 1 , … ,1
5．写一个在十字链表中删除非零元素aij的算法。
[提示]：“删除”两次，释放一次。 6．画出下面广义表的两种存储结构图示： ((((a), b)), ((( ), d), (e, f)))
0 a 1 1 1 ∧ ∧
0 b 1 ∧ 0 d 1 ∧ 1 1 1 ∧ 1 1 1 0 e ∧ ∧ 1 0 f ∧
第一种存储结构（自底向上看）
7．求下列广义表运算的结果： （1） HEAD[((a,b),(c,d))]; （2） TAIL[((a,b),(c,d))]; （3） TAIL[HEAD[((a,b),(c,d))]];
（4） HEAD[TAIL[HEAD[((a,b),(c,d))]]]; b （5） TAIL[HEAD[TAIL[((a,b),(c,d))]]]; (d)