文档介绍：第6章串计算机上的非数值处理对象基本上是字符串数据。在开发 C语言程序的过程中,源程序和目标程序都是字符串数据。字符串一般简称为串,它也是一种重要的线性结构。在进销存等事物处理中,顾客的姓名和地址、货物的名称、产地和规格都是字符串数据。在信息管理系统、信息检索系统、问答系统、自然语言翻译程序等都是以字符串数据作为处理对象的。本章重点和难点: 1、串的顺序存储表示与实现 2、串的堆分配存储表示与实现 3、串的链式表示与实现 4、串的模式匹配算法 串串是仅由字符组成的一种特殊的线性表。 什么是串串( string )(或字符串)是由零个或多个字符组成的有限序列,一般记作: S= ”a 1a 2…a n”。其中, S是串名,用双引号括起来的字符序列是串的值, a i (1 ≤i≤ n) 可以是字母、数字或其它字符, n是串的长度。当 n=0 时,串称为空串( null string )。 串串中任意个连续的字符组成的子序列称为该串的子串。相应地, 包含子串的串称为主串。通常将字符在串中的序号称为该字符在串中的位置。子串在主串中的位置以子串的第一个字符在主串中的位置来表示。例如, a、b、c、d是4个串: a= ” northwest ”, b= ” university ”, c= ” northwestuniversity ”, d= ” northwest university ”它们的长度分别为 9、 10 、 19 、 20 ,a和b都是 c和d的子串, a在c 和d的位置都为 1,b在c的位置是 10 ,b在d的位置是 11 。两个串是相等的,当且仅当两个串的值是相等的。也就是说,只有当两个串的长度相等,且串中各个对应位置的字符均相等,两个串才是相等的。 串 串的抽象数据类型 {a 1,a 2,…,a n},每个元素的类型均为字符。串是一种特殊的线性表,区别仅仅在于串的数据对象为字符集合。串具有线性表的特征:除了第一个元素 a 1外,每一个元素有且只有一个直接前驱元素,除了最后一个元素 a n外,每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。 串 ,往往是一连串的字符作为操作对象。例如,在串中查找某个子串,将一个串连接在另一个串的末尾等。为了说明的方便,定义以下几个串: S= ” e from Jiaozuo ” T= ” e from Zhengzhou ” R= ” Jiaozuo ” V= ” Beijing ” 串串的基本操作主要有: (1) StrAssign(&S,cstr ):串的赋值操作。(2) StrEmpty(S ):判断串是否为空。(3) StrLength(S ):求串的长度。例如, StrLength(S )=19 , StrLength(T )=21 , StrLength(R )=7 , StrLength(V )=7 。(4) StrCopy(&T,S ):串的复制。(5) pare(S,T ):串的比较。比较串 S和T的每个字符的 ASCII 值的大小,如果 S的值大于 T,则返回 1;如果 S的值等于 T,则返回 0;如果 S的值小于 T,则返回-1 。例如, pare(S,T )=-1 ,因为串 S和串 T比较到第 13 个字符时,字符’J’的 ASCII 值小于字符’Z’的 ASCII 值,所以返回-1 。 串(6) StrInsert(&S,pos,T ):串的插入操作。在串 S的 pos 个位置插入串 T,如果插入成功,返回 1;否则返回 0。(7) StrDelete(&S,pos,len ):串的删除操作。如果在串 S中删除第 pos 个字符开始,长度为 len 的字符串。如果找到并删除成功,返回 1;否则,返回 0。例如,如果在串 S中的第 13 个位置删除长度为 7的字符串后,即 StrDelete(S,13,7) ,则 S= ” e from ”。(8) StrConcat(&T,S ):串的连接。将串 S连接在串 T的后面。连接成功, 返回 1;否则,返回 0。例如,如果将串 S连接在串 T的后面,即 StrCat(T,S ),则 T= ” e from ZhengzhouI come from Jiaozuo ”。 串(9) SubString(&Sub,S,pos,len ):截取子串。截取串 S中从第 pos 个字符开始,长度为 len 的连续字符,并赋值给 Sub 。截取成功返