}/*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 ∧ 1 ∧ 1 0 d 1 ∧ 1 ∧ 1 0 e 第一种存储结构（自底向上看） 1 1 ∧ 1 ∧ 0 f 7．求下列广义表运算的结果： （1） HEAD[((a,b),(c,d))]; （2） TAIL[((a,b),(c,d))]; （3） TAIL[HEAD[((a,b),(c,d))]];