数据结构第四讲

《数据结构与算法》第四章 串

知识点及例题精选

串（即字符串）是一种特殊的线性表，它的数据元素仅由一个字符组成。

4.1 串及其基本运算

4.1.1 串的基本概念

１．串的定义

串是由零个或多个任意字符组成的字符序列。一般记作：

s=＂s1 s2 … sn＂＂

其中s 是串名；在本书中，用双引号作为串的定界符，引号引起来的字符序列为串值，引号本身不属于串的内容；ai(1<=i<=n)是一个任意字符，它称为串的元素，是构成串的基本单位，i是它在整个串中的序号; n为串的长度，表示串中所包含的字符个数，当n=0时，称为空串，通常记为Ф。

２．几个术语

子串与主串：串中任意连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。

子串的位置：子串的第一个字符在主串中的序号称为子串的位置。

串相等：称两个串是相等的，是指两个串的长度相等且对应字符都相等。

4.2 串的定长顺序存储及基本运算

因为串是数据元素类型为字符型的线性表，所以线性表的存储方式仍适用于串，也因为字符的特殊性和字符串经常作为一个整体来处理的特点，串在存储时还有一些与一般线性表不同之处。

4.2.1 串的定长顺序存储

类似于顺序表，用一组地址连续的存储单元存储串值中的字符序列，所谓定长是指按预定义的大小，为每一个串变量分配一个固定长度的存储区，如：

#define MAXSIZE 256

char s[MAXSIZE];

则串的最大长度不能超过256。

如何标识实际长度？

1. 类似顺序表，用一个指针来指向最后一个字符，这样表示的串描述如下：

typedef struct

{ char data[MAXSIZE];

int curlen;

} SeqString;

定义一个串变量：SeqString s;

这种存储方式可以直接得到串的长度：s.curlen+1。如图4.1所示。

0 1 2 3 4 5 6 7 8 9 10 ... MAXSIZE-1

数据结构教案(总32页)

-CAL-FENGHAI.-(YICAI)-Company One1

-CAL-本页仅作为文档封面，使用请直接删除

2015 至2016 学年第二学期

数 据 结 构 课程

教

案

课程编码： 1261D03

总学时／周学时： 80 / 5

开课时间： 2016年2 月 24日第 1 周至第 16

周

授课年级、专业、班级： 15级网工程2班

使用教材 严蔚敏. 数据结构（C语言版）[M] 北京：清华大学出版社，2011.

系别/教研室： 信息工程学院 / 物联网工程

授课教师： 刘波 教学目标：

《数据结构》是物联网工程专业的一门专业必修课。用计算机解决任何问题都需要进行数据表示和数据处理，而数据表示和数据处理正是《数据结构》要研究的内容。主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。

通过本课程教学，使学生了解数据结构的基本概念，理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，掌握算法描述及算法的评价标准，熟悉在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会，旨在培养学生基本的、良好的程序设计技能，编制高效可靠的程序，并为学生日后学习操作系统和数据库等后续课程奠定基础。

教学要求:

本课程主要是以抽象数据类型的观点来组织和讲解线性表、栈、队列、树、二叉树、图等各种主要的数学模型并定义为相应的抽象数据类型，给出各种物理表示法和有关算法，关于数据处理技术介绍几种主要的排序和查找算法。

学生通过学习该课程后主要应掌握以下内容：

1．了解数据结构及有关的基本概念；

习题

一、单项选择题

1. 空串与空格字符组成的串的区别在于（ ）。

A.没有区别 B.两串的长度不相等

C.两串的长度相等 D.两串包含的字符不相同

2. 一个子串在包含它的主串中的位置是指（ ）。

A.子串的最后那个字符在主串中的位置

B.子串的最后那个字符在主串中首次出现的位置

C.子串的第一个字符在主串中的位置

D.子串的第一个字符在主串中首次出现的位置

3. 下面的说法中，只有（ ）是正确的。

A.字符串的长度是指串中包含的字母的个数

B.字符串的长度是指串中包含的不同字符的个数

C.若T包含在S中，则T一定是S的一个子串

D.一个字符串不能说是其自身的一个子串

4. 两个字符串相等的条件是（ ）。

A.两串的长度相等

B.两串包含的字符相同

C.两串的长度相等，并且两串包含的字符相同

D.两串的长度相等，并且对应位置上的字符相同

5. 若SUBSTR（S，i，k）表示求S中从第i个字符开始的连续k个字符组成的子串的操作，则对于S=“Beijing＆Nanjing”，SUBSTR（S，4，5）=（ ）。

A. “ijing” B. “jing＆”

C. “ingNa” D. “ing＆N”

6. 若INDEX（S，T）表示求T在S中的位置的操作，则对于S=“Beijing＆Nanjing”，T=“jing”，INDEX（S，T）=（ ）。

A.2 B.3 C.4 D.5

7. 若REPLACE（S，S1，S2）表示用字符串S2替换字符串S中的子串S1的操作，则对于S=“Beijing＆Nanjing”，S1=“Beijing”，S2=“Shanghai”，REPLACE（S，S1，S2）=（ ）。

1. 设S=“A;/document/Mary.doc”，则strlen(s)= 20 , “/”的字符定位的位置为

3 。

2. 子串的定位运算称为串的模式匹配； 被匹配的主串 称为目标串， 子串 称为模式。

3 设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第 6 次匹配成功。

4 若n为主串长，m为子串长，则串的古典（朴素）匹配算法最坏的情况下需要比较字符的总次数为 (n-m+1)*m 。

5 设有两个串p和q，求q在p中首次出现的位置的运算称作：

Ａ．连接 Ｂ．模式匹配 Ｃ．求子串 Ｄ．求串长

6 设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x和y串的连接串，subs(s, i,

j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,

2, len(s2)), subs(s1, len(s2), 2))的结果串是：

Ａ．BCDEF Ｂ．BCDEFG Ｃ．BCPQRST Ｄ．BCDEFEF

7函数void insert(char *s, char *t, int pos)将字符串t插入到字符串s中，插入位置为pos。请用c语言实现该函数。假设分配给字符串s的空间足够让字符串t插入。（说明：不得使用任何库函数）

[题目分析]本题是字符串的插入问题，要求在字符串s中的pos位置，插入字符串t。首先应查找字符串s的pos位置，将第pos个字符到字符串s尾的子串向后移动字符串t的长度，然后将字符串t复制到字符串s的第pos位置后。

对插入位置pos要验证其合法性，小于1或大于串s的长度均为非法，因题目假设给字符串s的空间足够大，故对插入不必判溢出。

void insert(char *s, char *t, int pos)