《算法数据结构幻灯片》由会员分享，可在线阅读，更多相关《算法数据结构幻灯片（50页珍藏版）》请在金锄头文库上搜索。
1、第4章 串,字符串一般简称串,【学习目标】 1. 理解“串”类型定义中各基本操作的特点，并能正确利用它们进行串的其它操作。 2. 理解串类型的各种存储表示方法。 3. 理解串匹配的各种算法。 【重点和难点】 相对于其它各个知识点而言，本章非整个课程的重点，鉴于串已是多数高级语言中已经实现的数据类型，因此本章重点仅在于了解串类型定义中各基本操作的定义以及串的实现方法，并学会利用这些基本操作来实现串的其它操作。本章的难点是理解实现串匹配的KMP算法的思想，但它不属本章学习的基本要求，更不是重点学习内容。,为何要单独讨论“串”类型？ 1） 程序设计中，处理对象很多都是串类型。 2） 字符串操作比其他
2、数据类型更复杂（如拷贝、连接操作）。,4.1 串类型的定义,4.2 串的表示和实现,4.3 串的模式匹配算法,4.1 串类型的定义,4.1 串类型定义,串(string):即字符串，是由零个或多个字符 组成的有限序列。 是数据元素为单个字符的特殊线性表。,记为： s = a1 a2 an (n0 ),ai( 0i n)可以是字母、数字或其它字符；,4.1 串类型定义,长度：串中字符数目 n 称为串的长度。 空串：长度为 0 的字符称为空串(Null string)， 我们用表示“空串”。 空格串：由一个或多个空格组成的串 称为空格串(black string)。,问：空串和空格串有无区别？,答
3、：有区别。 空串(Null String)是指长度为零的串； 而空格串(Blank String),是指包含一个或多个空格字 符 (空格键)的字符串。它的长度为空格字符的个数,空串是任意串的子串；任意串S都是自身的子串， 除S本身外，S的其它子串称为“真子串”,4.1 串类型定义,子串：串 S 中任意个连续的字符组成的子序列叫 S 的子串; 主串：包含子串的串 S 叫主串。 字符位置：字符在串中的序号。 子串位置：子串的第一个字符在主串中的序号。 串相等：串长度相等，且对应位置上字符相等。,例1：现有以下4个字符串： a =BEI b =JING c = BEIJING d = BEI JIN
4、G,问： 他们各自的长度？ a是哪个串的子串？在主串中的位置是多少？ 空串是哪个串的子串？ a是不是自己的子串？,a =3，b =4，c = 7，d=8,a是c和d的子串，在c和d中的位置都是1,C语言中已有类似串运算函数,串的抽象数据类型定义 ADT String 数据对象： D ai |aiCharacterSet, i=1,2,.,n, n0 数据关系： R1 | ai-1, ai D, i=2,.,n 基本操作: （教材p71给出13种基本操作） StrAssign(&T, chars) / 串赋值，生成值为chars的串T StrCompare(S,T) / 串比较，若ST，返回值大
5、于0 StrLength(S) / 求串长，即返回S的元素个数 Concat(&T, S1, S2) / 串连接，用T返回S1S2的新串 SubString(&Sub, S, pos, len) / 求S中pos起长度为len的子串 Index(S, T, pos) / 返回子串T在pos之后的位置 Replace(&S, T,V) / 用子串V替换子串T ,4.1 串类型定义,注：Concat操作concatenation，把多个短字符串合并为长字符串,复习：C语言中常用的串运算,4.1 串类型定义,注：用C处理字符串时，要调用标准库函数 #include,串比较：int strcmp(ch
6、ar *s1,char *s2); / StrCompare(S,T) 求串长：int strlen(char *s); /StrLength(S) 串连接：char strcat(char *to,char *from) / Concat( / Index(S, T, pos) ,4.1 串类型定义,可利用串比较、求串长和求子串等操作实现定位函数实现Index(S，T，pos),算法的基本思想为：,StrCompare(SubString(S, i, StrLength(T), T ),S 串,T 串,T 串,i,pos,n-m+1,n= StrLength(S) m= StrLength(
7、T),4.1 串类型定义,算法描述： int Index (String S, String T, int pos) / T为非空串。若主串S中第pos个字符之后存在与T相等的子串， / 则返回第一个这样的子串在S中的 位置，否则返回0 if (pos 0) n = StrLength(S); m = StrLength(T); i = pos; while ( i = n-m+1) SubString (sub, S, i, m); if (StrCompare(sub,T) != 0) +i ; else return i ; / while / if return 0; / S中不存在与
8、T相等的子串 / Index,Index(S, T, pos) / 返回子串T在主串S中第pos之后第一次出现的位置,例1：设 s=I AM A STUDENT,t=GOOD,q=WORKER。求： StrLength(s) StrLength(t) SubString(&sub, s, 8, 7)= SubString(&sub, t, 2, 1)= Index(s, A)= Index(s, t)= Replace( &s, STUDENT, q )=,4.1 串类型定义,14,4,STUDENT,O,3,0,I AM A WORKER,思考：SubString(&sub, q, 5, 0
9、)=,长度为 0 的子串为“合法”串,4.1 串类型定义,例2：设 s =I AM A STUDENT, t =GOOD,求： Concat( SubString(s,6,2), Concat( t,SubString(s,7,8) ) ) ？,解：因为 SubString(s,6,2)A ； SubString(s,7,8) STUDENT Concat(t,SubString(s,7,8)GOOD STUDENT 所以： Concat(SubString(s,6,2), Concat(t,SubString(s,7,8) A GOOD STUDENT,4.2 串的表示和实现,4.2 串的表
10、示和实现,串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。 串的基本操作和线性表有很大差别。 在线性表的基本操作中，大多以“单个元素”作为操作对象； 在串的基本操作中，通常以“串的整体”作为操作对象。例如查找某子串，在主串某位置上插入一个子串等。,4.2 串的表示和实现,定长顺序存储表示 用一组地址连续的存储单元存储串值的字符序列 堆分配存储表示 用一组地址连续的存储单元存储串值的字符序列,但存储空间是在程序执行过程中动态分配而得。 串的块链存储 链式方式存储,串有三种机内表示方法：,顺序存储,链式存储,4.2.1 定长顺序存储表示 用一组地址连续的存储单元来存放串值的字符序
11、列。 为每个定义的变量分配固定长度存储区 #define MAXSTRLEN 255 / 用户可在255以内定义最大串长 typedef unsigned char Sstring MAXSTRLEN + 1; / 0号单元存放串的长度,4.2 串的表示和实现,串的实际长度可在这个予定义长度的范围内随意设定，超过 予定义长度的串值则被舍去，称之为“截断”,4.2.1 定长顺序存储表示 1.串联接Concat(&T,s1,s2),4.2 串的表示和实现,串的联接算法中需分三种情况处理 S10+S20MAXSTRLEN S10 MAXSTRLEN, S10+ S20MAXSTRLEN S10= M
12、AXSTRLEN,S1 sm s1 s2 S2 tn t1 t2 T sm+tn s1 s2 t1 t2 ,T1S10 = S11S10; TS10+1MAXSTRLEN = S21MAXSTRLENS10; T0 = MAXSTRLEN; uncut = FALSE; ,4.2 串的表示和实现,Status Concat(SString S1, SString S2, SString / Concat,T1S10 = S11S10; TS10+1S10+S20 = S21S20; T0 = S10+S20; uncut = TRUE; ,if (S10+S20 = MAXSTRLEN) /
13、未截断,else if (S10 MAXSTRSIZE) / 截断,else / 截断(仅取S1),T0MAXSTRLEN = S10MAXSTRLEN; / T0 = S10 = MAXSTRLEN uncut = FALSE; ,4.2.1 定长顺序存储表示 2.求子串SubString(&Sub,S,pos,len),4.2 串的表示和实现,将串S中从第pos个字符开始、长度为len的字符序列复制到串Sub中(注：串Sub的预留长度与S一样),s = a1 a2 an,pos,len,Sub ,讨论：在操作中出现串值序列长度超过上界MAXSIZE时，约定截尾法处理。若想存放超长字符串怎么
14、办？ 改用动态分配的一维数组堆,4.2.1 定长顺序存储表示 2.求子串SubString( /,4.2 串的表示和实现,子串长度,4.2 串的表示和实现,4.2.2 堆分配存储表示 仍用一组连续的存储单元来存放串，但存储空间是在程 序执行过程中动态分配而得。,通常，C语言中存在一个称之为“堆”的自由存储空间。提供的串类型就是以这种存储方式实现的。系统利用函数malloc( )和free( )进行串值空间的动态管理。,/=串的堆分配存储表示= typedef struct char *ch; / 若是非空串,则按串实际长度分 /配存储区;否则 ch为NULL int length; / 串长度
15、 HString;,4.2 串的表示和实现,4.2.2 堆分配存储表示 串插入操作： void StrInsert (HString / StrInsert _HSq,C是指针变量，可以自增！意即每次后移一个数据单元。,4.2 串的表示和实现,4.2.2 堆分配存储表示 Status StrAssign(HString /StrAssign,此处T.ch0没有用来装串长，因为另有T.length 分量,其它基本操作的算法描述见教材P77,4.2 串的表示和实现,4.2.3 串的块链存储表示 由于串结构的特殊性结构中的每个数据元素是一 个字符，则采用链表时，存在一个结点大小问题。,法1：链表结点（数据域）大小取1,法2：链表结点（数据域）大小取n(例如n=4),最后结点未占满，补“#”或其它非串值字符,4.2 串的表示和实现,4.2.3 串的块链存储表示,存储密度 =,数据元素所占存储位,实际分配的存储位,
