《《数据结构——用C语言描述（第二版）》-宁正元-电子教案 第4章 串》由会员分享，可在线阅读，更多相关《《数据结构——用C语言描述（第二版）》-宁正元-电子教案 第4章 串（49页珍藏版）》请在金锄头文库上搜索。
1、4.1 串的基本概念 4.2 串的存储实现 4.3 串的模式匹配算法 4.4 汉字串,第4章 串,串又称字符串，是一种特殊的线性表，是数据元素类型为字符的线性表，其应用非常广泛，是许多软件系统（如字符编辑、情报检索、词法分析、符号处里、自然语言翻译等系统）的操作对象。 本章介绍串的概念和各种存储结构，并讨论串的联接、求子串、串的插入、删除和置换以及串的模式匹配等运算。,第4章 串,串是由n个(n 0 )字符组成的有限序列，一般记作： S=“a1a2an” 其中，S是串名，用成对的双引号括起来的字符序列是串的值，ai可以是字母，数字或其它字符；n为串中字符的个数，称为串的长度，长度为零的串称为空
2、串。需要注意的是，成对的双引号本身仅作为标记，不属于串。 例如，串“Beijing”和“Bei jing”的长度分别是7和8。空串和空格串是两个不同的情况，例如，S1=“”即为空串，它的长度为0，空串内无任何字符，而S2=“ ”为空格串，即由一个或多个空格组成，其长度为串中空格的个数，空格符可以出现在字符序列的任意部位。 串中任意个连续的字符组成的子序列称为子串，一个串可以包含若干个子串，相应地，包含子串的串称为主串。字符在串中的序号称作该字符在串中的位置。当两个串长度相等且对应字符都相同时相等。,4.1 串的基本概念,串的逻辑结构与线性表的区别仅在于串的数据对象约束为字符集。 串结构的形式化
3、定义为： String=(D，R) 其中，D= aiaicharacter，i=1，2n，n0，R=a i-1，aiD，i=1，2，n 串的基本运算有： （1）初始化ClearString（s）：初始化串s。 （2）StrAssign（s，ch）：串赋值。 （3）StrCopy(s，t)：串复制。 （4）StrConcat（t，s1，s2）：串联接。 （5）求串长StrLen（s）：返回s串的元素个数，即s串的长度。 （6）串比较StrCom（s，t） （7）求子串SubStr（t，s，pos，len）：返回s串的第pos个字符起始的长度为len的子串。 （8）插入运算StrInsert（s，
4、pos，t）：把串t的值插入到串s的第pos个字符之后。 （9）删除运算StrDel（s，pos，len）：将串s中从第pos字符起始的长度为len的子串删除。,（10）子串定位StrIndex（s，t，pos）：从主串s的第pos个字符起定位串s中是否存在和串t值相等的子串，若存在，则返回子串t在主串s中第一次出现的位置，否则，返回函数值0。 例如， StrIndex（“Beijing”，“jin”，1）=4； StrIndex（“Beijing”，“jng”，2）=0 （11）置换运算StrReplace（s，pos，len,t）：用t串置换s串中第pos字符开始的连续的len个字符。 例
5、如，s=“Thatisabag！”，则 StrReplace（s，3，2，“is”）“Thisisabag！” 有时用另一种置换运算StrReplace（s，t，v）表示用v串置换所有在s串中出现的与t串相等的子串。 例如，s=“if（jn） j；”，t=“j”，v=“i”，则 StrReplace（s，t，v）=“if（in） i；” 以上介绍的是有关串的一些基本运算，利用它们可以处理关于串的各种操作，在使用高级程序设计语言中的串类型时，对于串的基本运算可以有不同的定义方法。,4.2.1 串的定长顺序存储及运算实现 1.串的定长顺序存储 串的顺序存储结构简称顺序串，是把串中的字符依次存放在一
6、组地址连续的存储单元中。 有时将为字符串分配一个固定长度的一组地址连续的存储单元的存储分配方法称之为定长顺序存储分配。定长顺序存储分配的实现，要结合具体的计算机编址方式进行，通常有三种实现方式： （1）紧缩方式 紧缩方式将串长显式地直接存储，字符依次顺序放在连续的几个单元中，这种存储方式的优点是充分地利用了空间，然而运算不太方便。 假定计算机按字编址，若串S为“DataStructure”， 表示空格字符，则S串有14个字符，存储S串的长度14和每个字符，一共需占用4个存储单元，如图4.1所示。,4.2 串的存储实现,（2）非紧缩方式 非紧缩方式是每个单元只存放一个字符，串的长度不显式存储，由
7、串中字符占存储单元的数目来隐式确定。如图4.2给出了上述串的非紧缩存储。显然，非紧缩存储方式对于串运算比较方便，但存储空间没有得到有效的利用。 （3）单字节存储方式 计算机按字节编址，每个字节存放一个字符，这时的串长度由串占用的字节数隐式确定，如图4.3所示。这种存储方式既不浪费空间，又使串中每个字符与唯一的地址对应，方便了运算，对于按字节编址的计算机而言是非常合适的。,在C语言中，按字节寻址。C语言中的串有字符串常量和字符串变量两种。用双引号括起来的字符序列为字符串常量，可以用宏定义#define来定义字符串常量的标识符。 例如， #define CITY Beijing 对字符串变量而言，
8、C语言将其类型说明为字符型一维数组。 例如，char ch100； 其中，数组ch是一个一维数组，这里的字符串的最大长度是由其变量说明时决定并且固定不变。通常，在字符串的最后一个字符的后面存放一个结束标志0。 为了更好地讨论字符串的运算，可将顺序串类型定义如下： #define MAXLEN 81 typedef struct string char chMAXLEN； int len； SeqString；,2.定长顺序串的基本运算实现 （1）求串长 int StrLen (SeqString *s) return(*s).len); （2）串的联接 两个串的联接就是将一个串紧接着存放在另一
9、个串的后面而得到一个新串。,void StrConcat (SeqString *t ， SeqString *s1， SeqString *s2) int i，j; if (*s1).len+(*s2).len=MAXLEN) for(i=0；i (*s1).len ；i+) (*t).chi=(*s1).chi; for(j=0；j (*s2).len ；j+) (*t).ch(*s1).len +j=(*s2).chj; (*t).len=(*s1).len+(*s2).len; else if (*s1).len MAXLEN) for(i=0；i (*s1).len ；i+) (*t
10、).chi=(*s1).chi; for(j=0；j MAXLEN- (*s1).len；j+) (*t).ch(*s1).len +j=(*s2).chj; (*t).len= MAXLEN； else printf (“overflow！n”); ,（3）求子串 void SubString（t，s，pos，len） /* 用t返回主串s中第pos个字符起，长度为len的子串 */ SeqString *t，*s； int pos，len； int i； if (pos(*s).len) | (len(*s).len-pos+1) printf(“pos或len超界n”); else fo
11、r(i=0；i len；i+) (*t).chi=(*s).chpos-1+i (*t).len=len; ,（4）子串的插入 void StrInsert (SeqString *s， int pos， SeqString *t) /* 在串s中的pos位置插入子串t */ int i； if (pos (*s).len+1) printf(“Insertion position incorrect!n”)； else if (*s).len+(*t).len=pos；i-) (*s).chi+(*t).len=(*s).chi; for (i=0；i(*t).len；i+) (*s).ch
12、i+pos=(*t).chi; (*s).len=(*s).len+(*t).len； else printf(“overflow！”)； ,（5）子串的删除 void StrDel (s，pos，len) /*从串s中删除第pos字符起始的长度为len的子串*/ SeqString *s； int pos，len; int i，j，k； char *p，*q； if (pos (*s).len) printf(“Deleted position incorrect!n”)； else if (pos= =len) (*s).len=0；/*删除整个串*/ else,if (pos+len-1
13、0）/*将被删除位置后的字符向前移动*/ *q=*p； +p； +q； k-； *q=*p; (*s).len=(*s).len-len； else printf(“no characteds deleted!n”)；/*没有len个字符可删除*/ ,（6）串的置换 void StrReplace (s，t，v) /*用v串替代s串中所有的t子串*/ SeqString *s，*t，*v； int start，pos，m，n，q； n=(*s).len；m=(*t).len；q=(*v).len； pos=1； do start=StrIndex(s，t，pos)；/*定位函数*/ if (s
14、tart!=0) StrDel (s，start，m)； StrInsert(s，v，start)； pos= start+q； (*s).len=(*s).len+q-m； n=(*s).len； while (pos=n-m+1) & (start !=0)； /*StrReplace*/ 其中，函数StrIndex( ) 用于从主串s的第pos个字符起定位串s中是否存在和串t值相等的子串，若存在，则返回子串t在主串s中第一次出现的位置，否则，返回函数值0，,4.2.2 串的堆式动态存储及运算实现 在许多实际应用的串处理系统中采用堆式动态存储分配策略。 例如，可以用一维数组heap char heapMAXLEN 表示堆空间，如图4.4所示。每当产生一个串时，应用程序就在执行过程中动态地从free指示的位置为新串值分配一个长度与串长相同的存储空间，并相应修改free的值，同时建立该串的一个描述（称为符号表），指示串的长度和该串在heap中的第一个字符位置，借助它们在堆结构的串名与串值之间建立起一个对应关系，称作串名的存储映像。所有的串名存储映像就构成了一个为系统中所有串名和串值之间建立一一对
