数据结构（本）课程辅导与练习-第4章 第4章串 一、相关术语 串，空串，空格串、串的长度、串的顺序存储结构、串的链式存储结构 二、串的基本概念 1,串 串(Sr1以)又移字符串，是零个或多个字符组成的有限序列。一般记为 S="aa." 其中 ①5是串名 ②双引号括起的字符序列是串值： 将串值括起米的双引号本身不属于串，它的作用是避免串与常数减与标识符混清。 【例】”123”是数字字符串，它不月于鉴常数123 【例】”x1“是长度为2的字符串，而x1通常表示一个标识符。 ③a.(1多in)可以是字母、数字或其它字符 ①串中所包含的字符个数称为该串的长度。 2。空申和空白中 长度为零的串称为空中(E即y String),它不包含任何字符。 仅由一个或多个空格组成的串称为空白串(Blank Str1n暖)： 注意： 空串和空白串的不月。 【例】·”和””分别表示长度为1的空白串和长度为0的空串。 3。子申和主申 串中任意个连续字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。 通常将子串在主串中首次出现时，该子申首字符对应的主串中的序号定义为子半在主 串中的序号（或位置）。 【例】设A和B分别为 A="This is a string B-"is" 则B是A的子串，B在A中出现了两次。其中首次出现对应的主申位置是3。因此称 B在A中的序号（或位置）是3。 注意： ①空串是任意串的子串 ②任意串是其自身的子串。 4.中变量和中君量 通常在程序中使用的串可分为：串变量和串常量。 1
1 数据结构(本)课程辅导与练习-第 4 章 第 4 章 串 一、相关术语 串、空串、空格串、串的长度、串的顺序存储结构、串的链式存储结构 二、串的基本概念 1．串 串（String）又称字符串，是零个或多个字符组成的有限序列。一般记为 S="a1a2……an" 其中 ①S 是串名 ②双引号括起的字符序列是串值； 将串值括起来的双引号本身不属于串,它的作用是避免串与常数或与标识符混淆。 【例】"123"是数字字符串，它不同于整常数 123 【例】"xl"是长度为 2 的字符串，而 xl 通常表示一个标识符。 ③ai（1≤i≤n）可以是字母、数字或其它字符； ④串中所包含的字符个数称为该串的长度。 2．空串和空白串 长度为零的串称为空串（Empty String），它不包含任何字符。 仅由一个或多个空格组成的串称为空白串（Blank String）。 注意： 空串和空白串的不同。 【例】″ ″和″″分别表示长度为 1 的空白串和长度为 0 的空串。 3．子串和主串 串中任意个连续字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。 通常将子串在主串中首次出现时，该子串首字符对应的主串中的序号定义为子串在主 串中的序号（或位置）。 【例】设 A 和 B 分别为 A="This is a string" B="is" 则 B 是 A 的子串，B 在 A 中出现了两次。其中首次出现对应的主串位置是 3。因此称 B 在 A 中的序号（或位置）是 3。 注意： ①空串是任意串的子串 ②任意串是其自身的子串。 4．串变量和串常量 通常在程序中使用的串可分为：串变量和串常量
(1)串变量 串变量和其它类型的变量一样，其取值是可以改变的。 (2)串常量 串常量和整常数、实常数一样，在程序中贝能被引用但不能改变其值。即贝能读不 能写， ①申常量由直接量来表示的： 【例】Error(”overf1ow”)中"overf1ow”是直接量： ②串常量命名 有的语言允许对串常量命名，以使程序易读、易写。 【例】C中，可定义串常量阳th comst char path[]='dir/bin/appl": 三、串的基本运算 对于串的基本运算，很多高级语言均提供了相应的运算符或标准的岸函量来实现。 为述方便，先定文几个相关的变量： char s1[20]="dir/bin/appl",s2[20]="file.asm',s3[30],*p: int result: 下面以C语言中串运算介绍串的基本运算 1.求中长 1nt8 trlen(char*s)/*求串s的长度/ 【例】printf(°，strlen(s1):/◆输出sl的串长12/ 2,事复制 char estrcp时(char *to,foa):/将from申复制到to串中，并返回to开始处指 针/ 【例】strepy3,sl): /体s3'dir/bin/apl”,sl串不变/ 3.违接 char *streat(car*ta,char *from):/体将foa串复制到to串的术尾，并返日to 串开始处的指针*/ 【例】strcat(s3."/门：/es3-dir/hin/appl/广/ strcat (s3.s2):/*s3-"dir/bin/appl/file.asn'/ 4.申比较 1 nt stre即(char*sl,char*2):/*比较s1和s2的大小，当s1s2和s1=s2 时，分别返回小于0、大于0和等于0的值/ 【例】res知lt=stremp("Joe”,”joseph7/体resul1=一1/ result=strcmp("Visual","Baker"):/result=I*/ result=stremp("12","12"): /*灯esult=0体/ 5.字符定位 char *strehr《char 4s,char e):/找e在字符串8中第一次出现的位置，若找到
2 （1）串变量 串变量和其它类型的变量一样，其取值是可以改变的。 （2）串常量 串常量和整常数、实常数一样，在程序中只能被引用但不能改变其值。即只能读不 能写。 ①串常量由直接量来表示的： 【例】Error（"overflow"）中"overflow"是直接量。 ②串常量命名 有的语言允许对串常量命名，以使程序易读、易写。 【例】C 中，可定义串常量 path const char path[]="dir/bin/appl"; 三、串的基本运算 对于串的基本运算，很多高级语言均提供了相应的运算符或标准的库函数来实现。 为叙述方便，先定义几个相关的变量： char s1[20]="dir/bin/appl",s2[20]="file.asm",s3[30],*p; int result; 下面以 C 语言中串运算介绍串的基本运算 1．求串长 int strlen(char *s);/*求串 s 的长度*/ 【例】printf("%d",strlen(s1)); /*输出 s1 的串长 12*/ 2．串复制 char *strcpy(char *to,*from)；/*将 from 串复制到 to 串中，并返回 to 开始处指 针*/ 【例】strcpy(s3,s1); /*s3="dir/bin/appl",s1 串不变*/ 3.连接 char *strcat(char *to,char *from);/*将 from 串复制到 to 串的末尾，并返回 to 串开始处的指针*/ 【例】strcat(s3,"/"); /*s3="dir/bin/appl/"*/ strcat(s3,s2); /*s3="dir/bin/appl/file.asm"*/ 4.串比较 int strcmp(char *s1,char *s2);/*比较 s1 和 s2 的大小，当 s1s2 和 s1=s2 时，分别返回小于 0、大于 0 和等于 0 的值*/ 【例】result=strcmp("Joe","joseph") /*result＝－1*/ result=strcmp("Visual","Baker"); /*result＝1*/ result=strcmp("12","12"); /*result=0*/ 5.字符定位 char *strchr(char *s,char c);/*找 c 在字符串 s 中第一次出现的位置， 若找到
则运目该位置，否则返回M儿L*/ 【例】p=strchr(s2,'.'):/p指向°i1e”之后的位置*/ if(p)strepy(p,.cpp:/体s2=file,cpo”4/ 注意： ①上述操作是最基本的，其中后4个操作还有变种形式。 ②其它的串操作见C的(stg.h>,在不同的高级语言中。对串运算的种类及符号 露不尽相同， ③其余的串操作一般可由这些基本操作组合而成。 四、串的顺序存储 1,顺序申 串的顺序存储结构简称为顺序串。 与顺序表类似。顺序串是用一组地址莲续的存储单元来存储串中的字符序列。因此 可用高级语言的字符数组来实现，按其存储分配的不同可将顺序串分为如下两类： (1》静态存储分配的顺序申 (2》动态存储分配的顺序串 2,静态存储分配的顺序串 (1)直接使用定长的字符数组来定义 该种方法顺序串的具体搞述： adefine MaxStrSize 256 /该值依赖于用。由用户定义*/ typedef char SeqString[MaxStrSize]: /eSeg5 tring是顺序串类型/ SegStrinz S: /5是一个可容纳255个字符的顺序 串制 注意： ①串值空间的大小在编译时刻就己确定，是静态的。难以适应括入，链接等操作 ②直接使用定长的字符数组存故串内容外，一般可使用一个不会出现在串中的特殊 字符放在串值的末尾来表示串的结束。所以串空间最大值为：5S12e时，最多只能放 ax5 trSixe-】个字符. 【例】C语言中以字符'0'表示串值的终结. 0 1234567891011 字符表示： s t r n g 3 \h 1o 01234567891011 A3CII码表示： 8311611410311010311546100 (2)类似顺序表的定复 直接使用定长的字符数组存放串内容外，可用一个整数来表示串的长度。此时顺序 串的类型定文完全和顺序表类以 typedef struct char ch[aStr5ize]:/体可容纳256个字符，并候次存储在ch[0.,n中 /
3 则返回该位置，否则返回 NULL*/ 【例】p=strchr(s2,'.'); /*p 指向"file"之后的位置*/ if(p) strcpy(p,".cpp"); /*s2="file.cpp" */ 注意： ①上述操作是最基本的，其中后 4 个操作还有变种形式。 ②其它的串操作见 C 的。在不同的高级语言中，对串运算的种类及符号 都不尽相同。 ③其余的串操作一般可由这些基本操作组合而成。 四、串的顺序存储 1．顺序串 串的顺序存储结构简称为顺序串。 与顺序表类似，顺序串是用一组地址连续的存储单元来存储串中的字符序列。因此 可用高级语言的字符数组来实现，按其存储分配的不同可将顺序串分为如下两类： （1）静态存储分配的顺序串 （2）动态存储分配的顺序串 2．静态存储分配的顺序串 （1）直接使用定长的字符数组来定义 该种方法顺序串的具体描述： #define MaxStrSize 256 /*该值依赖于应用，由用户定义*/ typedef char SeqString[MaxStrSize]; /*SeqString 是顺序串类型*/ SeqString S; /*S 是一个可容纳 255 个字符的顺序 串*/ 注意： ①串值空间的大小在编译时刻就已确定，是静态的。难以适应插入、链接等操作 ②直接使用定长的字符数组存放串内容外，一般可使用一个不会出现在串中的特殊 字符放在串值的末尾来表示串的结束。所以串空间最大值为 MaxStrSize 时，最多只能放 MaxStrSize-1 个字符。 【例】C 语言中以字符'\0'表示串值的终结。 （2）类似顺序表的定义 直接使用定长的字符数组存放串内容外，可用一个整数来表示串的长度。此时顺序 串的类型定义完全和顺序表类似： typedef struct{ char ch[MaxStrSize]; /*可容纳 256 个字符，并依次存储在 ch[0..n]中 */
int length: ]SeqString: 注意 ①串的长度减1的位置就是串值的最后一个字符的位置. ②这种表示的优点是涉及串长的操作速度快。 3,动态存储分配的顺序串 黑序串的字符数组空间可使用C语言的a11oC和T0e等动老存储管理函数，来根 据实标需要动态地分配和释放。 这样定义的顺序串类型亦有两种形式。 (1)较简单的定义 typedef char *string:/C中的串库(strg.h>相当于使用此类型定义串/ (2)复柔足义 typedef struct char *ch:/,若串妻空，则按实际的串长分配存储区，否则ch为山*/ int length: )String: 五、串的蛙式存储 1.统中 用单蛙表方式存储串值，串的这种链式存储结构简称为链串， sm□b□cGd□eGG&囚 ()结点大小为1的链串S S Z a b c d c f g \O A )结点大小为4的链非s 2.链申的结构类型定义 typedef struct node char data; struct node ext: LinkStrNode: /结点类型*/ typedef LinkStrNode礼inkString:/inkString为链串类里*/ LinkString S: /5是链串的头指针*/ 注意： ①链串和单蛙表的差异仅在于其结点数据域为单个字符： ②一个链串由头蛋针唯一确定。 3.链串的结点大小 通常，将结点数据域存傲的字符个数定文为结点的大小。结点的大小的值越大，存 储密度越高。 4
4 int length; }SeqString; 注意： ①串的长度减 1 的位置就是串值的最后一个字符的位置。 ②这种表示的优点是涉及串长的操作速度快。 3.动态存储分配的顺序串 顺序串的字符数组空间可使用 C 语言的 malloc 和 free 等动态存储管理函数，来根 据实际需要动态地分配和释放。 这样定义的顺序串类型亦有两种形式。 （1）较简单的定义 typedef char *string; /*C 中的串库相当于使用此类型定义串*/ （2）复杂定义 typedef struct{ char *ch;/* 若串非空，则按实际的串长分配存储区，否则 ch 为 NULL*/ int length; }HString; 五、串的链式存储 1.链串 用单链表方式存储串值，串的这种链式存储结构简称为链串。 2.链串的结构类型定义 typedef struct node{ char data; struct node *next; }LinkStrNode; /*结点类型*/ typedef LinkStrNode *LinkString; /*LinkString 为链串类型*/ LinkString S; /*S 是链串的头指针*/ 注意： ①链串和单链表的差异仅在于其结点数据域为单个字符： ②一个链串由头指针唯一确定。 3.链串的结点大小 通常，将结点数据域存放的字符个数定义为结点的大小。结点的大小的值越大，存 储密度越高
(1)结点大小为1的歧申 【例】串值为”abede的结点大小为1的歧串S如下图所示， sm□bGc□deG☒ 这种结构便于进行插入和副除运算，但存储空间利用率太低： 《2)结点大小)1的情串 【例】串值为”abede广的结点大小为4的链串s如下图所示。 S Z a b c d e f g \OA 注意： ①为了提高存销密度，可使每个结点存放多个字符。 ②当结点大小大于1时，串的长度不一定正好是结点大小的整数倍，因此要用特 殊字符来填充最后一个结点，以表示串的终结， 图虽然提高结点的大小使得存结密度增大，但是做插入、制除运算时，可能会引 起大量字符的移动，给运算带米不便， 六、串的运算 串是特殊的线性表，故顺序串和随串上实现的运算分别与顺序表和单链表上进行的操 作类似， 串的运算在数材4.2节讲的常清楚，我们下面讨论在序串和链串上实现的子 串定位运算 1,于串定位运算 子串定位运算类似于串的基本运算中的字符定位运算。只不过是找子串而不是找字 符在主串中首次出现的位置。此运算的应用非常广泛。 【例】在文本编辑中，我们经常要查找某一特定单司在文本中出现的位置，解此月题的 有效算法能极大地提高文本编辑程序的响应性能。 子串定位运算又称审的慎式匹配或审匹配. 2,目标（串）和机式（串） 在串匹配中，一舰将主串称为目标（申），子串称为模式（申）。 假设T为目标串，P为模式串，且不妨设： T="tetitg"trt" P-"ppp"(0<a≤n 3.串匹配 串匹配就是对于合法的位置（又称合法的位移）0运1多重，依次将目标串中的子串 ”ttt”和模式串"ppp"进行比较： ①若”t4t-”="pw”,则称从位置i开始的匹配成功，或称i为有效位移。 ②若”tttm”≠A”,则称从位置i开始的匹配失败，或称i为无效位移。 因此，串匹配问题可简化为找出某给定模式串P在给定目标串T中首次出现的有效位移。 七、裤习题 单项选释墨
5 （1）结点大小为 1 的链串 【例】串值为"abcdef"的结点大小为 1 的链串 S 如下图所示。 这种结构便于进行插入和删除运算，但存储空间利用率太低。 （2）结点大小>1 的链串 【例】串值为"abcdef"的结点大小为 4 的链串 S 如下图所示。 注意： ①为了提高存储密度，可使每个结点存放多个字符。 ②当结点大小大于 1 时，串的长度不一定正好是结点大小的整数倍，因此要用特 殊字符来填充最后一个结点，以表示串的终结。 ③虽然提高结点的大小使得存储密度增大，但是做插入、删除运算时，可能会引 起大量字符的移动，给运算带来不便。 六、串的运算 串是特殊的线性表，故顺序串和链串上实现的运算分别与顺序表和单链表上进行的操 作类似。 串的运算在教材 4.2 节讲的非常清楚，我们下面讨论在顺序串和链串上实现的子 串定位运算。 1．子串定位运算 子串定位运算类似于串的基本运算中的字符定位运算。只不过是找子串而不是找字 符在主串中首次出现的位置。此运算的应用非常广泛。 【例】在文本编辑中，我们经常要查找某一特定单词在文本中出现的位置。解此问题的 有效算法能极大地提高文本编辑程序的响应性能。 子串定位运算又称串的模式匹配或串匹配。 2．目标（串）和模式（串） 在串匹配中，一般将主串称为目标（串），子串称为模式（串）。 假设 T 为目标串，P 为模式串，且不妨设： T="t0t1t2…tn-1" P="p0p1p2…pm-1"(0＜m≤n) 3．串匹配 串匹配就是对于合法的位置（又称合法的位移）0≤i≤n-m，依次将目标串中的子串 "titi+1…ti+m-1"和模式串"p0p1p2…pm-1"进行比较： ①若"titi+1…ti+m-1"＝"p0p1p2…pm-1"，则称从位置 i 开始的匹配成功，或称 i 为有效位移。 ②若"titi+1…ti+m-1"≠"p0p1p2…pm-1"，则称从位置 i 开始的匹配失败，或称 i 为无效位移。 因此，串匹配问题可简化为找出某给定模式串P在给定目标串T中首次出现的有效位移。 七、练习题 单项选择题
1.以下陈述中正确的是《)。 A。串是一种特殊的线性表 B。串的长度必须大于零 C。串中元素只能是字母 D.空串就是空白申 2.设有两个串p和q:其中q是p的子串，q在p中首次出现的位置的算法称为()。 A.求子审 B.连接 C,匹配 D,求串长 3.串是()。 A。不少于一个字母的序列 B。任意个字母的序列 C,不少于一个字符的序列 D,有限个字符的序列 4。串的长度是指( A.串中所含不同字母的个数 B串中所含字符的个划 C.串中所含不同字符的个数 D.串中所含非空格字将的个影 5.若串S=“Egis由”，其子串的个数是( A.9 B.16 C,36 D.28 6.下面关于串的叙述中，不正确的是( A.串是字符的有限序列 B。空串是由空格构成的串 C.模式元配是申的一种重要运算 D.串即可以采用顺序存储，也可以采用链式存储 7。串与普通的线性表相比较，它的特妹性体暖在( A.顺序的存储结构 B。链接的存储结构 C,数据元素是一个字符 D,数据元素可以任意 8.空串与空格串〔 A。相同 B.不相同 C。可能相同D。无法确定 9,两个字符串相等的条件是( A。两串的长度相等 R。两事色含的字符相同 C。两串的长度相等，并且两串包含的字符相同 D。两申的长度相等，并且对应位置上的字符相同 10。在实际应用中，要输入多个字符申，且长度无法预定。则应该采用()存储比 较合逅( A.随式 B.顺序 C。堆结构 D。无法确定 练习题答案 单项透择题 1.A2.C3.D4.B5.D6.B7.C8.B9.D10.A
6 1.以下陈述中正确的是（ ）。 A．串是一种特殊的线性表 B．串的长度必须大于零 C．串中元素只能是字母 D．空串就是空白串 2．设有两个串 p 和 q，其中 q 是 p 的子串，q 在 p 中首次出现的位置的算法称为（ ）。 A．求子串 B．连接 C．匹配 D．求串长 3．串是（ ）。 A．不少于一个字母的序列 B．任意个字母的序列 C．不少于一个字符的序列 D．有限个字符的序列 4．串的长度是指（ ）。 A．串中所含不同字母的个数 B．串中所含字符的个数 C．串中所含不同字符的个数 D．串中所含非空格字符的个数 5. 若串 S==“English”，其子串的个数是（ ）。 A．9 B．16 C． 36 D．28 6．下面关于串的叙述中，不正确的是（ ）。 A．串是字符的有限序列 B．空串是由空格构成的串 C．模式匹配是串的一种重要运算 D．串即可以采用顺序存储，也可以采用链式存储 7．串与普通的线性表相比较，它的特殊性体现在（ ）。 A．顺序的存储结构 B．链接的存储结构 C．数据元素是一个字符 D．数据元素可以任意 8．空串与空格串（ ）。 A．相同 B．不相同 C．可能相同 D．无法确定 9．两个字符串相等的条件是（ ）。 A．两串的长度相等 B．两串包含的字符相同 C．两串的长度相等，并且两串包含的字符相同 D．两串的长度相等，并且对应位置上的字符相同 10．在实际应用中，要输入多个字符串，且长度无法预定。则应该采用（ ）存储比 较合适（ ）。 A．链式 B． 顺序 C．堆结构 D．无法确定 练习题答案 单项选择题 1．A 2．C 3．D 4．B 5．D 6．B 7．C 8．B 9．D 10．A