《数据结构》课件(C语言) 第04章

《《数据结构》课件(C语言) 第04章》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第四章串《数据结构》主要内容串的逻辑结构串的基本操作串的链式存储结构串的堆存出结构串的顺序存储结构静态结构存储串时的操作2主要内容•静态结构存储串时的操作（Index函数）•朴素的模式匹配算法（BF算法）•改进的模式匹配算法（KMP算法）•求模式串next函数值的算法•求模式串next函数值的修正算法•next函数的性质•示例与模式匹配7.模式匹配（重点）3第四章串串（又称字符串）是一种特殊的线性表，它的每个结点仅由一个字符组成。本章将讨论串的有关概念、结构、存储方法和串的基本运算及其实现。4定义：串（String）是零个或多个字符组成的有限序列。一般记为：S=‘a1a

2、2···an’(n≥0).术语1）串名：S.2）串值：'a1a2···an'，ai(1≤i≤n).3）串的长度：串中所包含的字符个数，如串'abcde'的长度为5.串的逻辑结构54）空串：长度为0(n=0)的串，它不包含任何字符，记作S=''(或S=φ).5）空格串：由空格符(ASCII值32)组成的串，如S=‘’.注意S=''与S=''不同，前者是长度为1的非空串，它含有一个空格字符，而后者是长度为0的空串。6）子串：串中任意个连续的字符组成的子序列。比如'abcde'中的'bcd'.串的逻辑结构6用二元组的形式来定义串：串是一个二元组,string=(

3、D,R)其中D={ai

4、ai∈字符集,i=1,2,···,n,n≥0}R={N}有序偶的集合N={

5、ai-1,ai∈D,i=2,3,···n}故串的逻辑结构和线性表极为相似。区别仅在D的定义上。线性表的数据对象可以是任意数据类型，而串的数据对象是字符集。串是几种最简单的数据结构之一。串的逻辑结构7串虽然是一种特殊的线性表，但由于存储结构有所不同，故其基本操作也不同。1、基本操作子集不同，比如串包含有联接、求子串等操作2、操作对象不同，线性表的操作通常以数据元素或结点为操作对象，而串的操作主要以串的整体为操作对象。1）赋值操作Assign(s,t)s为

6、串名，t为字符串变量。Create(s,ss)s为串名，ss为字符序列。2）判等函数Equal(s,t)返回布尔值true或false.s,t可为非空串或空串。3）求串长函数Length(s)返回串s字符的个数。4）联接函数Concat(s,t)返回由串s,t相联接而成的新串。联接运算不满足交换律，但满足结合律。串的基本操作85）求子串函数Substr(S,start,len)返回从串S中第start个字符起，长度为len的字符序列。要求1≤start≤Length(s)+1,0≤len≤Length(s)-start+1.6）定位函数Index(s,t)返回串t在串

7、s中第一次出现时的串首位置，若未出现，则返回值0，要求t不能是空串。7）置换操作Replace(s,t,v)以串v替换所有在串s中出现的和非空串t相等的子串。串的基本操作9串的基本操作8）插入（前插）操作Insert(s,pos,t)在串s的第pos个字符之前插入串t.要求1≤pos≤Length(s)+1。注.Insert(S,Length(s)+1,t)与Concat(s,t)功能相同，即当pos=Length(s)+1时，t将插入至s的尾部之后。9）删除操作Delete(s,pos,len)从串s中删去从第pos个字符起，长度为len的子串。要求1≤pos≤L

8、ength(s)，且1≤len≤Length(s)-pos+1。说明：可将1)至5)定义为串的基本操作，6)至9)可由基本操作加以实现。10示例1用串的基本操作(1)至(5)实现定位函数Index(s,t)。intIndex(strings,stringt)/*若串s中存在和t相等的子串，则返回第一个子串在主串中的位置，否则返回零*/{n=Length(s);m=Length(t);i=1;//m不等于0while(i≤n-m+1)if(Equal(Substr(s,i,m),t))returni;elsei++;return0;}//index串的基本操作11C中预

9、定义字符串标准函数和标准过程字符串标准函数函数名意义结果类型strcat连接字符串序列char*strcpy复制一个字符串char*strlen返回串的动态长度int还有：strcmp,strcmpi,strrchr,……参见：String.h串的基本操作12用线性链表的方式存储串值结点大小问题串的链式存储结构DATAS^head1）结点大小等于1，即一个结点存放一个字符优点：便于实现插入、删除等操作缺点：浪费存储空间，存储利用率最多1/2DATASTRUCTURES^head2）结点大小等于4，即一个结点存放4个字符优点：存储效率较