第4章 串

数据结构（C语言版）（第2版）

课后习题答案

李冬梅 2015.3II

目录

第 1 章 绪论 ................................................................ 1

第 2 章 线性表 .............................................................. 5

第 3 章 栈和队列 ............................................................ 13

第 4 章 串、数组和广义表 .................................................... 26

第 5 章 树和二叉树 .......................................................... 33

第 6 章 图 ................................................................. 43

第 7 章 查找 ................................................................ 54

第 8 章 排序 ............................................................... 651 第1章绪论

1 •简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结 构、抽象数据类型。

答案：

数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的 总称。如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、 图像、声音、动画等通过特殊编码定义后的数据。

第四、五章串、数组和广义表练习题答案

一．填空题 1. 不包含任何字符（长度为0）的串 称为空串； 由一个或多个空格（仅由空格符）

组成的串 称为空白串。 2. 设S=“A;/document/Mary.doc”，则strlen(s)= 20 , “/”的字符定位的位置为

3 。

3. 子串的定位运算称为串的模式匹配； 被匹配的主串 称为目标串， 子串 称为模式。 4. 设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第 6 次匹配成功。

5. 若n为主串长，m为子串长，则串的古典（朴素）匹配算法最坏的情况下需要比较字符

的总次数为 (n-m+1)*m 。 6. 假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为 288 B ；末尾元素A57的第一个字节地址为 1282 ；若按行存储时，元素A14的第一个字节地址为 (8+4)

×6+1000=1072 ；若按列存储时，元素A47的第一个字节地址为 (6×7＋4)×6＋1000）

＝1276 。 (注：数组是从0行0列还是从1行1列计算起呢？由末单元为A57可知，是从0行0列开始！) 7. 〖00年计算机系考研题〗设数组a[1„60, 1„70]的基地址为2048，每个元素占2个存储

单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为 8950 。 答：不考虑0行0列，利用列优先公式： LOC(aij)=LOC(ac1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L

得：LOC(a32,58)=2048+[(58-1)*(60-1+1)+32-1]]*2＝8950

8. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别

表示该元素 的 行下标 、 列下标 和 元素值 。 9.求下列广义表操作的结果：

数据结构(第二版)习题答案第4章

00

第

00

4章字符串、数组和特殊矩阵

00

4.1稀疏矩阵常用的压缩存储方法有（ 三元组顺序存储 ）和（十字

链表 ）两种。

00

4.2设有一个 10 × 10的对称矩阵 A采用压缩方式进行存储，存储

时以按行优先的顺序存

00

储其下三角阵，假设其起始元素 a00的地址为 1，每个数据元素占 2

个字节，则 a65的地址为

00

（ 53 ）。

00

4.3若串 S =“software”，其子串的数目为（ 36 ）。

00

4.4常对数组进行的两种基本操作为（ 访问数据元素 ）和（ 修改

数组元素 ）。

00

4.5 要计算一个数组所占空间的大小，必须已知（数组各维数）和（每

个元素占用的空

00

间）。

00

4.6对于半带宽为 b的带状矩阵，它的特点是：对于矩阵元素 aij，

若它满足（|i-j|>b），

00

则 aij = 0。

00

4.7字符串是一种特殊的线性表，其特殊性体现在（ 该线性表的元

素类型为字符 ）。

00

4.8试编写一个函数，实现在顺序存储方式下字符串的 strcompare

（S1，S2）运算。

00

【答】：

00

#include

00

#include

00

#define MAXSIZE 100

00

typedef struct{

00

char str[MAXSIZE];

00

int length;

00

}seqstring;

00

/* 函数 strcompare()的功能是：当 s1>s2时返回 1，当 s1==s2时

返回 0，当 s1

00

int strcompare(seqstring s1,seqstring s2)

00

{ int i,m=0,len;

00

len=s1.length

00

for(i=0;i<=len;i++)

00

if(s1.str[i]>s2.str[i])

00

{m=1;break;}

00

第4章 串

1 习题4

1.名词解释：串、空串、空格串、子串。

解：串是有限的字符序列，从数据结构角度讲，串属于线性结构。与线性表的不同之处在于串的元素是字符。

空串是不含任何字符的串，其长度为0。

空格是一个字符，其ASCII码值是32。空格串是由空格组成的串，其长度等于空格的个数。

串中任意连续的若干字符组成的子序列称为该串的子串。

2.已知三个字符串分别为”“aabcaabcbcaabS，”“caabS'，”“bcbS"。利用串的基本运算得到结果串为”“aacacaabcbcaS'"，要求写出得到结果串3S所用的函数及执行算法。

解：串'"S可看作由以下两部分组成：”“acaabcbca和”“aca，设这两部分分别叫串s1和s2，要设法从S、'S、"S中得到这两部分，然后使用连接操作连接s1和s2得到'"S。

i=index();//

s1=substr(S,i,length(S)-i+1);//取出串s1

j=index(S,"S);//求串"S在串S中的起始位置，S串中”“bcb后是”“aca

s2=substr(S,j+3,length(S)-j-2);//形成串s2

'"S=concat(s1,s2);

3.已知字符串1S中存放一段英文，写出算法),3,2,1(nSSSformat，将其按给定的长度n格式化成两端对齐的字符串2S，其多余的字符存入3S。

解：题目要求将字符串S1拆分成字符串S2和S3，要求字符串S2“按给定长度n格式化为两端对齐的字符串”，即长度为n且首尾字符不能为空格字符。算法从左到右扫描字符串S1，找到第一个非空格字符，计数到n，第n个拷入字符串S2的字符不能为空格，然后将余下字符复制到字符串S3中。

void format(char *S1,char *S2,char *S3,int n){

char *p=S1,*q=S2;

int i=0;