发布时间 : 2024/5/10 23:48:09 星期五 文章《数据结构——C语言描述》习题及答案-耿国华-2更新完毕开始阅读

{

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;ilen;i--) /*将S中子串T后的所有字符 S->ch[i-t.len+v.len]=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;

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;ich[i+pos]=V.ch[i]; S->len=MAXLEN;} }/*switch()*/

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 && jnext; 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)