数据结构(第二版)习题答案第4章
第
4章字符串、数组和特殊矩阵
4.1稀疏矩阵常用的压缩存储方法有（三元组顺序存储）和（十字链表）两种。
4.2设有一个10 × 10的对称矩阵 A采用压缩方式进行存储，存储时以按行优先的顺序存
储其下三角阵，假设其起始元素 a00的地址为 1，每个数据元素占 2个字节，则 a65的地址为
（ 53 ）。
4.3若串S =“software”，其子串的数目为（ 36 ）。
4.4常对数组进行的两种基本操作为（访问数据元素）和（修改数组元素）。
4.5 要计算一个数组所占空间的大小，必须已知（数组各维数）和（每个元素占用的空
间）。
4.6对于半带宽为 b的带状矩阵，它的特点是：对于矩阵元素 aij，若它满足（|i-j|>b），
则 aij = 0。
4.7字符串是一种特殊的线性表，其特殊性体现在（该线性表的元素类型为字符）。
4.8试编写一个函数，实现在顺序存储方式下字符串的 strcompare （S1，S2）运算。
【答】：
#include <stdio.h>
#include <string.h>
#define MAXSIZE 100
typedef struct{
char str[MAXSIZE];
int length;
}seqstring;
/* 函数 strcompare()的功能是：当 s1>s2时返回 1，当 s1==s2时返回 0，当 s1<s2时返回-1*/
int strcompare(seqstring s1,seqstring s2)
{ int i,m=0,len;
len=s1.length<s2.length ?s1.length:s2.length;
for(i=0;i<=len;i++)
if(s1.str[i]>s2.str[i])
{m=1;break;}
else if(s1.str[i]<s2.str[i])
{m=-1;break;}
return m;
}
int main()
字符串长度17模式串长度{ seqstring s1,s2;
int i,m;
printf("input char to s1:\n");
gets(s1.str);
s1.length=strlen(s1.str);
printf("input char to s2:\n");
gets(s2.str);
s2.length=strlen(s2.str);
m=strcompare(s1,s2);
if(m==1) printf("s1>s2\n");
else if(m==-1) printf("s2>s1\n");
else if(m==0) printf("s1=s2\n");
}
4.9试编写一个函数，实现在顺序存储方式下字符串的
replace（S，T1，T2）运算。
【参考程序
1】：
/*本程序用来在顺序存储下用快速匹配模式实现在字符串
S中用
T2替换所有
T1出现的可
能*/
#include<malloc.h>
#include<string.h>
#include<stdio.h>
# define maxsize 100
typedef struct{
char str[maxsize];
int length ;
} seqstring;
//求
next[]函数
void getnext(seqstring*p,int next[])
{int i,j;
next[0]=-1;
i=0;j=-1;
while(i<p->length)
{
if(j==-1||p->str[i]==p->str[j])
{++i;++j;next[i]=j;}
else
j=next[j];
}
}
//快速模式匹配算法
int kmp(seqstring*t,seqstring*p,int next[],int temppos) {int i,j;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。