数据结构课件串.ppt

《数据结构课件串.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构——第4章串目标理解串的定义；理解串的存储方式；掌握模式匹配算法。本章内容4.1串及其基本运算4.2串的存储结构及基本运算4.3模式匹配算法4.1串及其基本运算什么是串？串(String)是零个或多个字符组成的有限序列。一般记作S＝'a1a2a3…an'。相关术语串名串值串长空串空格串子串主串子串的位置串相等4.1串及其基本运算串的抽象数据类型定义：ADTString//P71{数据对象D：由零个或多个字符型的数据元素构成的有限集合；数据关系R：{

2、其中ai,ai+1D,i=1,2,……n-1}基本操作：（1

3、）StrAssign(&T,S)（2）StrCopy(&T,S)（3）Strempty(S)（4）StrCompare(S,T)（5）StrLength(S)（6）ClearString(&S)（7）StrConcat(&S,T)（8）Substring(&Sub,S,pos,len)（9）Index(P,T)（10）StrInsert(S,pos,T)（11）StrDelete(&S,pos,len)（12）Replace(&S,T,V)（13）StrDestroy(&S)}ADTString串的主要操作：1、字符串处理函数2、子串定位

4、StrIndex(s,t)本章内容4.1串及其基本运算4.2串的存储结构及基本运算4.3模式匹配算法4.2串的存储结构及基本运算4.2.1串的定长顺序存储结构4.2.2串的堆存储结构4.2.3串的链式存储结构4.2.1串的定长顺序存储结构定长顺序存储结构的实现：用一组地址连续的存储单元存储串值中的字符序列。定长是指按预定义的大小，为每一个串变量分配一个固定长度的存储区。通常用数组实现。#defineMAXSTRLEN255typedefunsignedcharSString[MAXSTRLEN+1];如何标识字符串的实际长度？4.2.1串

5、的定长顺序存储标识实际长度的方法1.类似顺序表，用一个指针来指向最后一个字符，串描述如下：typedefstruct{unsignedcharelem[MAXSTRLEN+1];intcurlen;//下标}SqString;例：SqStrings;串的长度=s.curlen+14.2.1串的定长顺序存储标识实际长度的方法2.在串尾存储一个不会在串中出现的特殊字符作为终结符，常用’’。4.2.1串的定长顺序存储标识实际长度的方法3.在数组的0号单元存储串长度，串第一个字符从数组的1单元开始存放。字符的序号和存储位置将一致。例：type

6、defunsingedcharSString[MAXSIZE+1];s[0]存放串的实际长度串值存放在s[1]～s[MAXSIZE]4.2串的存储结构及基本运算4.2.1串的定长顺序存储结构4.2.2串的堆存储结构4.2.3串的链式存储结构4.2.2串的堆存储结构堆结构堆空间：在内存中开辟的能存储足够多的串、并且地址连续的存储空间称为堆空间。空间管理：C语言使用动态分配函数malloc（）和free（）来管理空间。4.2.2串的堆存储结构堆结构类型定义串的索引项结点类型：typedefstruct{char*stradr;/*起始地址*/

7、intlength;/*串长*/}HString;4.2串的存储结构及基本运算4.2.1串的定长顺序存储结构4.2.2串的堆存储结构4.2.3串的链式存储结构4.2.3串的链式存储结构链式存储实现：链串与一般的链表类似，链串中的一个结点可以存储一个或多个字符。链串结点大小的选择将直接影响到串处理的效率。存储密度=串所占存储容量/实际存储容量例子：结点大小为4的，结点为大小为1的。(P78图4.2)4.2.3串的链式存储结构链式存储示意#defienSIZE80typedefstructChunk{charch[SIZE];structCh

8、unk*next;}Chunk;typedefstruct{Chunk*head,*tail;intcurlen;}LString;本章内容4.1串及其基本运算4.2串的存储结构及基本运算4.3模式匹配算法4.3模式匹配算法4.3.1模式匹配概述4.3.2简单模式匹配算法4.3.3KMP算法4.3.1模式匹配概述串的模式匹配也称为子串定位。设s和t是给定的两个串，在主串s中查找子串t的过程称为模式匹配，如果在s中找到等于t的子串，则称匹配成功，返回t在s中的首次出现的存储位置(或序号)，否则匹配失败，返回0。s称为主串，t称为模式串。为了

9、运算方便，设字符串采用定长存储，且串的长度存放在0号单元。4.3模式匹配算法4.3.1模式匹配概述4.3.2简单模式匹配算法4.3.3KMP算法算法思想：用t中的每个字符去与s中的字符一一比较