数 据 结 构 刘家芬 Sept 2012.

Presentation on theme: "数 据 结 构 刘家芬 Sept 2012."— Presentation transcript:

1 数 据 结 构 刘家芬 Sept 2012

2 第四章 串 本章目标 在非数值处理、事务处理等问题常涉及到一系列的字符操作。字符串的处理比单纯数值处理复杂。 串的定义
例如：文字编辑系统、编译程序、图像、音乐处理、信息检索等。 本章目标 串的定义 串的存储结构和操作实现 *串的模式匹配算法

3 串的概念 串(字符串)：是零个或多个字符组成的有限序列。记作： S=‘a1a2a3…’。 S是串名，单引号括起来的字符序列是串值。
ai(1≦i≦n) 可以是单个字母、数字或其它字符 串长：串中所包含的字符个数称为该串的长度 空串(空的字符串)：长度为零的串称为空串，它不包含任何字符。 空格串(空白串)：构成串的所有字符都是空格的串称为空白串。 注意空串和空白串的不同，例如“ ”和“”分别表示长度为1的空白串和长度为0的空串。

4 子串的概念 串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。
通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为子串在主串中的序号（或位置）。 例如，设A和B分别为 A=“This is a string” B=“is” 则B是A的子串，A为主串。B在A中的序号是？ B在A中出现了两次，其中首次出现所对应的主串位置是3。称B在A中的序号（或位置）为3。 空串是任意串的子串，任意串是其自身的子串。

5 串相等 串相等：如果两个串的串值相等(相同)，称这两个串相等。只有当两个串的长度相等，且各个对应位置的字符都相同时才相等。
串值可用单引号或双引号括起来，但引号本身不属于串，用于区分串的边界而已。

6 串常量和串变量 通常在程序中使用的串可分为两种：串变量和串常量。
串常量在程序中只能被引用，不能改变其值，即只能读不能写。例如C语言中的printf("Succeed!") 串变量和其它类型的变量一样，其值可以改变。

7 串的抽象数据类型定义 ADT String{ 数据对象：D = { ai|ai∈CharacterSet, i=1,2,…,n, n ≥0 } 数据关系：R = {<ai-1, ai>| ai-1, ai∈D, i=2,3,…,n } 基本操作： // 13种 StrAssign(&T, chars) // 串赋值 StrCompare(S,T) // 串比较 StrLength(S) // 求串长 Concat(&T, S1, S2) // 串连接 SubString(&Sub, S, pos, len) // 求子串 …… Index(S, T, pos) // 返回子串位置 Replace(&S, T,V) // 替换子串 }ADT Sting

8 串的基本操作 这些基本操作同样需要由设计人员根据需求和存储方式自行实现。 在基本操作的基础上可以实现更为复杂的操作。
前五种构成最小操作子集。即这些操作不能利用其它操作来实现，而其它操作可由最小操作子集实现。

9 基本操作子集

10 定位函数的实现 例如定位函数Index(S,T,pos)可由求子串和串比较操作配合实现。查看母串S中是否存在和T匹配的子串,若存在返回它在主串S中第一次出现的位置，否则返回0。 假设S=‘abcaabda’ ,T=‘abda’, 如何实现？ 思想：从母串S中的第一个字符开始的Length（T）个字符与子串T比较，若相等，则返回1；否则再从S中第二个字符开始的Length（T）个字符与子串T比较，如此反复，直到匹配成功或主串S中的字符已被取尽。

11 串定位

12 串的存储表示和实现 串是一种特殊的线性表，其存储表示和线性表类似，但又不完全相同。 串在计算机中有3种表示方式：
定长顺序存储表示：将串定义成字符数组，利用串名可以直接访问串值。用这种表示方式，串的存储空间在编译时确定，其大小不能改变。 堆分配存储方式：仍然用一组地址连续的存储单元来依次存储串中的字符序列，但串的存储空间是在程序运行时根据串的实际长度动态分配的。 块链存储方式：是一种链式存储结构表示。

13 串的定长顺序存储表示 又称为串的顺序存储结构，用一组连续的存储单元来存放串中的字符序列。所谓定长顺序存储结构，是直接使用定长的字符数组来定义，数组的大小预先确定。 串的实际长度在255以内，超过部分将被舍去，称为“截断”。 串长的两种表示： 用下标为0的数组元素存放串的长度，如PASCAL语言 用一个特殊符号例如\0表示串结束，该符号不计入串长度，如C语言

14 定长顺序存储下的基本操作 串链接Concat(&T,S1,S2)的实现非常直观，执行串复制操作即可。但要注意根据串的长度进行截断操作。

15 定长顺序存储下的基本操作 串链接Concat(&T,S1,S2)的实现非常直观，执行串复制操作即可。但要注意根据串的长度进行截断操作。

16 定长顺序存储下的基本操作 串链接Concat(&T,S1,S2)的实现非常直观，执行串复制操作即可。但要注意根据串的长度进行截断操作。

17

18 求子串

19 串的堆分配存储表示 这种存储表示的特点是：仍然以一组地址连续的存储空间来存储字符串值，但其所需的存储空间是在程序执行过程中动态分配的。
实现方法：系统提供一个空间足够大且地址连续的存储空间(称为“堆”)， 并由C语言的动态存储分配函数malloc()和free()来管理。 用malloc()为每个串分配一块实际串长所需的存储空间，并返回一个指向起始地址的指针作为基址。为了方便，串长也作为串结构的一部分。

20 堆分配存储表示下基本操作的实现

21 堆分配存储表示下基本操作的实现

22 堆分配存储表示下基本操作的实现

23 堆分配存储表示下基本操作的实现

24 堆分配存储表示下基本操作的实现

25 串的链式存储 串的链式存储结构和线性表的串的链式存储结构类似，采用单链表来存储串，结点的构成是
data域：存放字符，data域可存放的字符个数称为结点的大小； next域：存放指向下一结点的指针。 若每个结点仅存放一个字符，则结点的指针域就非常多，造成系统空间浪费，为节省存储空间，考虑串结构的特殊性，使每个结点存放若干个字符，这种结构称为块链结构。

26 串的块链结构 当结点大小大于1时，串长不一定是结点大小的整数倍，块链的最后一个结点不一定占满，可用#或其他特殊字符填充。

27 串的块链存储 为了便于实现串的联接等操作，用链表存储串时，除了头指针用于指示链表的开头，又附设一个尾指针指示链表的最后一个结点。

28 串的模式匹配算法 模式匹配：子串在主串中的定位，也叫字符串匹配。模式匹配成功是指在主串S中能够找到模式串T，否则，称模式串T在主串S中不存在。 模式匹配的应用在非常广泛。例如，在文本编辑程序中，我们经常要查找某一特定单词在文本中出现的位置。 模式匹配算法的研究能极大地提高文本编辑程序的响应性能。

29 串的模式匹配算法BF

30 串的模式匹配算法BF 该算法的关键点： 当t和s碰上第一个不匹配的字符时：主串要退回到i-j+2的位置，而模式串也要退回到第一个字符（即j=1的位置）。

31 串的模式匹配算法KMP 考虑s=“00000000000000000000000001” t=“0000001”
每当一趟匹配过程出现字符不相等时，主串指示器不用回溯，而是利用已经得到的“部分匹配”结果，将模式串的指示器向右“滑动”尽可能远的一段距离后继续进行比较。

32 串的模式匹配算法KMP

33 串的模式匹配算法KMP 模式串t的前k-1个字符必须满足下式，而且不可能存在k’>k满足该式。 而已经得到的 “部分匹配”的结果为：
设主串s=“s1s2…sn” ，模式串t=“t1t2 …tm” 。当si≠tj (1≦i≦n-m，1≦j<m)时，主串s的指针i不必回溯，模式串t的指针j回溯到第k(k<j)个字符继续比较。 模式串t的前k-1个字符必须满足下式，而且不可能存在k’>k满足该式。 t1t2…tk-1= si-(k-1) si-(k-2) … si-2 si (4-1) 而已经得到的 “部分匹配”的结果为： tj-(k-1) tj-k… tj-1=si-(k-1) si-(k-2) … si-2 si (4-2) 由式(4-1)和式(4-2)得： t1t2…tk-1=tj-(k-1) tj-k… tj (4-3)

34 Max{k|1<k<j∧t1t2…tk-1=tj-(k-1) tj-k… tj-1 } 该集合不空时
串的模式匹配算法KMP 当j=1时 Max{k|1<k<j∧t1t2…tk-1=tj-(k-1) tj-k… tj-1 } 该集合不空时 其它情况 next[j]= 定义next[j]函数为

35 KMP函数思想 求得next[j]值之后，KMP算法的思想：
目标串(主串)为s，模式串为t ，并设i指针和j指针分别指示目标串和模式串中正待比较的字符，设i和j的初值均为1。 若有si=tj，则i和j分别加1。 否则，i不变，j退回到j=next[j]的位置，再比较si和tj 若相等，则i和j分别加1 否则，i不变，j再次退回到j=next[j]的位置。 依此类推。

36 KMP函数思想 直到下列两种可能： （1）j退回到某个下一个[j]值时字符比较相等，则指针各自加1继续进行匹配。
（2）退回到j=0，将i和j分别加1，即从主串的下一个字符si+1模式串的t1重新开始匹配。

37 KMP算法示例

38 KMP的实现

39 Have FUN !