例题1：编写下列算法（假定下面所用的串均采用顺序存储方式，参数ch、ch1和ch2均为字符型）：

• 将串r中所有其值为ch1的字符换成ch2的字符。
• 将串r中所有字符按照相反的次序仍存放在r中。
• 从串r中删除其值等于ch的所有字符。
• 从串r1中第index个字符起求出首次与字符r2相同的子串的起始位置。
• 从串r中删除所有与串r3相同的子串（允许调用第（4）小题的函数和第（3）小题的删除子串的函数）。

解：（1）本小题的算法思想是：从头到尾扫描r串，对于值为ch1的元素直接替换成ch2即可。其函数如下：

orderstring *trans（r，ch1，ch2）

orderstring *r；

char ch1，ch2；

{

int i；

for（i=0；i<r->len; i++）

if（r->vec[ i ]==ch1）r->vec[ i ]=ch2;

return（r）；

}

（2）本小题的算法思想是：将第一个元素与最后一个元素交换，第二个元素与倒数第二个元素交换，如此下去，便将该串的所有字符反序了。其函数如下：

orderstring *invert（r）

orderstring *r；

{

int i；

char x；

for（i=0；i< ( r->len / 2 ); i++）

{

x= r->vec[ i ];

r->vec[ i ]= r->vec[r->len-i-1]；

r->vec[ r->len-i-1 ]=x;

}

return ( r );

}

（3）本小题的算法思想是：从头到尾扫描r串，对于其值为ch的元素采用移动的方式进行删除。其函数如下：

orderstring *delall（r，ch）

orderstring *r；

char ch；

{

int i，j；

for（i=0；i<r->len; i++）

if（r->vec[ i ]==ch）

{

for（j=i；j<r->len-1; j++）

r->vec[ j ]=r->vec[ j+1 ];

i--;

r->len--;

}

return（r）；

}

（4）本小题的算法思想是：从第index个元素开始扫描r1，当其元素值与r2的第一个元素的值相同时，判定它们之后的元素值是否依次相同，直到r2结束为止，若都相同则返回，否则继续上述过程直到r1扫描完为止。其函数如下：

int partposition（r2，r1，index）

orderstring *r2，*r1；

int index；

{

int i，j，k；

for（i=index；i<r2->len; i++）

for（j=i，k=0；r2->vec[ j ]== r1->vec[ k ]; j++, k++）

if（!r1->vec[ k+1 ]）

return（i）；

return（-1）；

}

（5）本小题的算法思想是：从位置1开始调用第（4）小题的函数partposition( )，若找到了一个相同子串，则调用delsubstring( )将其删除，再查找后面位置的相同子串，方法与以上相同。其函数如下：

orderstring *delstringall（r，r3）

orderstring *r，*r3；

{

int i=0，k；

while（i<r->len）/*当调用delsubstring( )进行删除操作时, r->len也减小了*/

{

if（（k=partposition（r, r3, i）!=-1））

r=delsubstring（r，k+1，r3->len）；

else

i++；

}

return r；

}

例题2：采用顺序存储方式存储串，编写一个函数将串s1中的第i个字符到第j个字符之间的字符（不包括第i个和第j个字符）用s2串替换，函数名为stuff（s1，i，j，s2）。例如：stuff（’abcd’, 1, 3, ’xyz’）返回’axyzcd’。

解：本题算法思想是：先提取s1的前i个字符str1，再取第j个字符及之后的所有字符str2，最后将str1，s2，str2连接起来便构成了结果串，其函数如下：

orderstring *stuff（s1，i，j，s2）

orderstring *s1，*s2；

int i，j；

{

orderstring *s；

int top，h；

s=（orderstring *）malloc（sizeof（orderstring））；

if（i<=j && i<s1->len && j<s1->len）

{

for（h=0；h<i；h++）s->vec[h]=s1->vec[h]；/*把s1的前i个字符赋给s*/

s->len=i；

h=0；

while（h<s2->len）

{

s->vec[s->len+h]=s2->vec[h]；

h++；

}

s->len=s->len+s2->len；

s->vec[s->len]=’\0’；

top=s->len；

for（top=s->len, h=j-1; h<s1->len; h++, top++）

s->vec[top]=s1->vec[h];/*连接s1的第i个字符及之后的字符*/

s->len=top;

s->vec[s->len]=’\0’;

}

return（s）；

}

例题3：建立三元组存储方法

解：输入一个稀疏矩阵A建立三元组存储方法的函数如下：

void crt_matrix（A，B）

int A[m][n]；

smatrik B；/*A是一个稀疏矩阵，B是产生的相对应的三元组*/

{

int i，j，k=1；

for（i=0；i<n；i++）/*按行优先顺序扫描A的元素，不为0者存入B中*/

for（j=0；j<m；j++）

if（A[ i ][ j ]！=0）

{

B[k][0]= i；

B[k][1]= j；

B[k][2]= A[ i ][ j ]；

k++；

}

B[0][0]= m；

B[0][1]= n；

B[0][2]= k-1；/*存入非0元素个数*/

}

例题4：假设稀疏矩阵A采用三元组表示，编写一个函数计算其转置矩阵B，要求B也采用三元组表示。

解：三元组表示中要求按行的顺序存放，所有转置过程不能直接将行下标和列下标转换，还必须使得列按顺序存放。因此在A中首先找出第一列中的所有元素，它们是转置矩阵第一行的非0元素，并把它们依次放在转置矩阵三元组数组B中；然后依次找出第二列中的所有元素，把它们依次放在数组B中；按照同样的方法逐列进行，直到找出第n列的所有元素，并把它们依次放在数组B中。实现本题功能的函数如下：

void transpose（A，B）

smatrik A，B； /*A是稀疏矩阵的三元组形式，B是存放A的转置矩阵的三元组数组*/

{

int m，n，p，q，t，col；

/*m为A中的行数； n为A中的列数； t为A中非0元素个数*/

/*q为B的下一项位置； p为A的当前项*/

m=A[0][0]；n=A[0][1]；t=A[0][2]；

B[0][0]=n；B[0][1]=m；B[0][2]=t；/*产生第0行的结果*/

If（t>0）/*非0 矩阵才做转置*/

{

q=1；

for（col=0；col<n；col++）/*按列转置*/

for（p=1；p<=t；p++）

if（A[p][1]==col）

{

B[q][0]=A[p][1]；

B[q][1]=A[p][0]；

B[q][2]=A[p][2]；

q++；

}

}

}

例题5：设二维数组A5*6的每个元素占4个字节，已知Loc（a00）=1000，A共占多少个字节？A的终端结点a45的起始地址为多少？按行和按列优先存储时，a25的起始地址分别为多少？

解：A共占的字节数为：5*6*4=120

a45的起始地址为：Loc（a00）+（4*6+5）*4 =1000+116=1116

按行优先存储时，a25的起始地址为：Loc（a00）+（2*6+5）*4=1000+68=1068

按列优先存储时，a25的起始地址为：Loc（a00）+（5*5+2）*4=1000+108=10108