数据结构课件 第四章串

《数据结构课件 第四章串》由会员分享，可在线阅读，更多相关《数据结构课件 第四章串（27页珍藏版）》请在金锄头文库上搜索。

1、第四章 串4.1 串类型的定义4.2 串的表示和实现4.2.1 定长顺序存储表示4.2.2 堆分配存储表示4.2.3 串的块链存储表示4.3 串的模式匹配算法4.4 串操作应用举例文本编辑Date1第四章 串4.1 串类型的定义基本概念串(String)是由零个或多个字符组成的有限序 列。一般记作S=a1a2a3an，其中S 是串 名，单引号括起来的字符序列是串值； ai(1in)可以是字母、数字或其它字符； 串中所包含的字符个数称为该串的长度。空串(Empty String)：长度为零的串。它不包 含任何字符。空格串(Blank String)： 由一个或多个空格 组成的串。 注意：空串和空

2、格串的不同。Date2第四章 串基本概念（续）子串：串中任意个连续字符组成的子序列。 主串：包含子串的串。通常将子串在主串中首 次出现时的该子串的首字符对应的主串中的 序号，定义为子串在主串中的序号（或位置 ）。例如，设A和B分别为A=“This is a string” B=“is”则B是A的子串，A为主串。B在A中出现了两次 ，其中首次出现所对应的主串位置是3。因此 ，称B在A中的序号（或位置）为3。特别地， 空串是任意串的子串，任意串是其自身的子 串。Date3第四章 串基本概念（续）通常在程序中使用的串可分为两种：串变量 和串常量。串常量和整常数、实常数一样， 在程序中只能被引用但不能

3、不能改变其值， 即只能读不能写。通常串常量是由直接量来 表示的，例如语句Error(“overflow”)中 “overflow”是直接量。但有的语言允许对 串常量命名，以使程序易读、易写。如C+中 ，可定义const char path=“dir/bin/appl”;这里path是一个串常量，对它只能读不能写 。串变量和其它类型的变量一样，其取值是 可以改变的。Date4第四章 串串的抽象数据类型定义串的抽象数据类型定义见教材P71串的基本操作(13个)：StrAssign, Strcopy, StrEmpty, StrCompare, StrLength, ClearString, Con

4、cat, SubString, Index, Replace, StrInsert, StrDelete, DestroyString许多高级语言均提供了串基本操作相应 的运算或标准库函数来实现。下面仅介绍几 种在C语言中常用的串运算，其它的串操作 见教材及参考书。Date5第四章 串串变量及基本操作：char s120=“dirtreeformat”,s220=“file.mem”;char s330,*p;int result;求串长(length)int strlen(char s); /求串的长度例如：couts2例如：result= strcompare (“baker”,”Bake

5、r”) result0result= strcompare (“12”,”12”); result=0result= strcompare (“Joe”,”Joseph”); result0Date8第四章 串基本操作（续）（5）字符定位(index)char strchr(char s,char c);该函数是找c在字符串中第一次出现的位置， 若找到则返回该位置，否则返回NULL。例如：p=strchr(s2,”.”); p 指向“file”之后的位置if(p) strcpy(p,”.cpp”); s2=“file.cpp” 最小操作子集：串赋值StrAssign、串比较 Strcompar

6、e、求串长StrLength、串联接concat 和求子串SubString。串的其余操作可由这些 基本操作组合而成。Date9第四章 串4.2 串的表示和实现因为串是特殊的线性表，故其存储结构与线性表 的存储结构类似。只不过由于组成串的结点是单个 字符。串有三种机内表示方法，下面分别介绍。 1 定长顺序存储表示定长顺序存储表示,也称为静态存储分配的顺序表 。它是用一组连续的存储单元来存放串中的字符序 列。所谓定长顺序存储结构，是直接使用定长的字 符数组来定义，数组的上界预先给出：#define maxstrlen 255typedef char sstringmaxstrlen+1;sstr

7、ing s; /s是一个可容纳255个字符的顺 序串。Date10第四章 串串的结束标记一般可使用一个不会出现在串中的特殊字符 在串值的尾部来表示串的结束。例如，C语言 中以字符0表示串值的终结，这就是为 什么在上述定义中，串空间最大值maxstrlen 为256，但最多只能存放255个字符的原因， 因为必须留一个字节来存放0字符。若 不设终结符，可用一个整数来表示串的长度 ，那么该长度减1的位置就是串值的最后一个 字符的位置。Date11第四章 串顺序串的类型定义顺序串的类型定义和顺序表类似：typedef structchar chmaxstrlen;int length;sstring;

8、 /其优点是涉及到串长操作 时速度快。Date12第四章 串顺序存储时串操作的实现串联接Concat(T,S1,S2)求子串SubString(sub,s,pos,len)注：串联接操作可能出现“截断” 现象Date13第四章 串2 堆分配存储表示这种存储表示的特点是，仍以一组地址连续 的存储单元存放串值字符序列，但它们的存 储空间是在程序执行过程中动态分配而得。 所以也称为动态存储分配的顺序表。在C语言 中，利用动态存储管理函数，来根据实际需 要动态分配和释放字符数组空间。typedef structchar *ch; /若是非空串，则按串长分配存储区，否则ch为 nullint lengt

9、h; /串长度hsring;Date14第四章 串3 串的链式存储结构顺序串上的插入和删除操作不方便，需要移动大 量的字符。因此，我们可用单链表方式来存储串值 ，串的这种链式存储结构简称为链串。typedef struct nodechar data;struct node *next;lstring;一个链串由头指针唯一确定。这种结构便于进行插入和删除运算，但存储空间利 用率太低。Date15第四章 串结点的大小由于串结构的特殊性，可使每个结点存 放多个字符。通常将结点数据域存放的字符 个数定义为结点的大小，显然，当结点大小 大于 1时，串的长度不一定正好是结点的整 数倍，因此要用特殊字符来

10、填充最后一个结 点，以表示串的终结。headABCIB C DE F G HI # # #headADate16第四章 串块链结构（设头、尾指针）对于结点大小不为1的链串，其类型定义只需对 上述的结点类型做简单的修改即可。#define nodesize 80typedef struct nodechar datanodesize;struct node *next; node;typedef struct lstringnode *head,*tail;int curlen; lstring;Date17第四章 串存储密度的概念存储密度小，运算处理方便，存储 占用量大；存储密度大，情况则相反

11、。串的链式存储结构队某些串操作（ 如联接等）有一定的方便，但总的说来 不如另外两种存储结构灵活。存储密度 =串值所占的存储位实际分配的存储位Date18第四章 串4.3 串的模式匹配算法子串定位运算又称为模式匹配(Pattern Matching)或串匹配(String Matching) ，此运算的应用非常广泛。 在文本编辑程序中，我们经常要查找某 一特定单词在文本中出现的位置。显然 ，解此问题的有效算法能极大地提高文 本编辑程序的响应性能。 在串匹配中，一般将主串称为目标串， 子串称之为模式串。Date19第四章 串模式匹配（续）设S为目标串，T为模式串，且不妨设 ：S=“s0s1s2sn

12、-1” T=“t0t1tm-1” 串的匹配实际上是对于合法的位置 0in-m依次将目标串中的子串 sii+m-1和模式串t0m-1进行比 较，若sii+m-1=t0m-1，则称 从位置i开始的匹配成功，亦称模式t在 目标s中出现.Date20第四章 串模式匹配（续）若sii+m-1 t0m-1，则称从位 置i开始的匹配失败。上述的位置i又称 为位移，当sii+m-1=t0m-1时 ，i称为有效位移；当sii+m-1 t0m-1时，i称为无效位移。这样 ，串匹配问题可简化为是找出某给定模 式T在一给定目标T中首次出现的有效位 移。Date21第四章 串模式匹配算法串匹配的算法很多，这里我们只讨论

13、一种 最简单的称为朴素的串匹配算法。其基 本思想是用一个循环来依次检查n-m+1 个合法的位移i(0I n-m)是否为有 效位移，其算法段为：for(i=0;i=n-m;i+)if(Sii+m-1=T0m-1)return i; Date22第四章 串模式匹配算法匹配过程设目标串为a b a b c a b c a c b a b，模式串为a b c a c 第一趟 a b a b c a b c a c b a ba b c第二趟 a b a b c a b c a c b a ba第三趟 a b a b c a b c a c b a ba b c a c第四趟 a b a b c a b

14、 c a c b a ba第五趟 a b a b c a b c a c b a ba第六趟 a b a b c a b c a c b a ba b c a cDate23第四章 串KMP算法模式匹配的改进算法算法是由D.E.Knuth、V.R.Pratt和J.H.Morris同 时发现，因而得名。 改进在于：利用已经得到的部分匹配结果将 模式向右“滑动”尽可能远的一段距离。算法 可以在O(n+m)的时间数量级上完成。 第一趟 a b a b c a b c a c b a ba b c 第二趟 a b a b c a b c a c b a ba b c a c 第三趟 a b a b c

15、 a b c a c b a ba b c a cDate24第四章 串线性结构复习线性表n个数据元素的有限序列 抽象数据类型定义（12个基本操作） 存储结构：顺序存储顺序表；链式存储线性 链表，循环链表和双向链表；其它。 栈和队列操作受限的线性表 抽象数据类型定义（分别为9个操作） 存储结构：顺序存储顺序栈和循环队列；链式 存储链栈和链队列 串由零个或多个字符组成的有限序列 抽象数据类型定义（13个基本操作） 存储结构：定长顺序存储；堆分配存储和块链存 储Date25第四章 串作业题1 (P27 4.3)设s=I AM A STUDENT, t=GOOD, q=WORKER. 求： strlenth(s),strlength(t), substring(s,8,7), substring(t,2,1), index(s,A), index(s,t), concat(substring(s,6,2),concat(t,substring( s,7,7). 2 (P29 4.12)编写一个实现串的置换操作 replace(&S,T,V)的算法. 注：操作replace的意义见串的类型定义 P72Date26第四章 串思考题1. 了解C+中的字符串函数 2. 用BP算法求解具体问题 3. 全面复习线性结构(二、三、四 章)， 包括基本概念和算法。Date27第四章 串