华师本科生数据结构课件 第5章 串和数组.PPT
《华师本科生数据结构课件 第5章 串和数组.PPT》由会员分享,可在线阅读,更多相关《华师本科生数据结构课件 第5章 串和数组.PPT(102页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、【课前思考】,为什么顺序表以及其它线性结构的顺序存储结构都可以用一维数组来描述?,因为在高级编程语言中实现的一维数组正是用的这种顺序存储的映象方式。,从数据结构的观点来说,串是一种特殊的线性表;但就数据类型而言,串不是线性表。,串就是线性表的结论是否正确?,第4章 串和数组,5.1 串类型的定义 5.2 串的表示和实现 5.3 串的模式匹配算法 5.4 串操作应用举例 5.5 数组的定义 5.6 数组顺序存储的表示和实现 5.7 矩阵的压缩存储,【学习目标】,理解串类型定义中各基本操作的特点,并能正确利用它们进行串的其它操作。理解串类型的各种存储表示方法。理解串匹配的各种算法。 理解数组类型的
2、特点及其在高级编程语言中的存储表示和实现方法,并掌握数组在以行为主的存储表示中的地址计算方法; 掌握特殊矩阵的存储压缩表示方法; 理解稀疏矩阵的两类存储压缩方法的特点及其适用范围,掌握以三元组表示稀疏矩阵时进行矩阵运算所采用的处理方法;,【重点和难点】,重点 了解串类型定义以及串的实现方法串的匹配, 学会利用这些基本操作来实现串的其它操作; 掌握随机稀疏矩阵的压缩存储表示方法和运算实现,串、串的匹配、数组、特殊矩阵、稀疏矩阵、三元组、十字链表。,【知识点】,课后练习题:5.1,5.2,5.3,5.4,5.6,5.11,5.12,记为: s = “a0 a1 . an-1” (n0 ),串中字符
3、个数(n0),n=0时称为空串 。 由一个或多个空格符组成的串。 串s中任意个连续的字符序列叫s的子串; S叫主串。 子串的第一个字符的序号。 字符在串中的序号。 串长度相等,且对应位置上字符相等。,串即字符串,是由零个或多个字符组成的有限序列,是数据元素为单个字符的特殊线性表。,若干术语: 串长: 空白串: 子串: 子串位置: 字符位置: 串相等:,隐含结束符/0 ,即ASCII码NUL,5.1 串的定义和操作,串(string):由0个或多个字符组成的有限序列,也称字符串。记为:s=“a0a1a2an-1” (n0), 其中s是串的名,a0a1a2an-1是串的值,ai(0in-1)可以是
4、字母、数字或其它字符。 串长度:串中字符的数目n。 空串:不含任何字符的串,串长度=0 空格串:仅由一个或多个空格组成的串 子串:由串中任意个连续的字符组成的子序列 主串:包含子串的串。,串相等的条件:当两个串的长度相等且各个对应位置的字符都相等时才相等。 注意:(1) 串值必须用一对单引号括起来 (2) 串值大小是按词典次序进行比较的 StrCompare(data,Stru)0显然,只有在两个串的长度相等且每个字符一一对等的情况下称两个串相等。,练1:串是由 字符组成的序列,一般记为 。,练2:现有以下4个字符串: a =BEI b =JING c = BEIJING d = BEI JI
5、NG,问: 他们各自的长度? a是哪个串的子串?在主串中的位置是多少?,a =3,b =4,c = 7,d=8,a是c和d的子串,在c和d中的位置都是1,练3:空串和空白串有无区别? 答:有区别。空串(Null String)是指长度为零的串;而空 白串(Blank String),是指包含一个或多个空白字符 (空格键)的字符串。,0个或多个,S=a1a2an,串的数据对象约束为字符集。 线性表的基本操作大多以“单个元素”为操作对象,而串的基本操作通常以“串的整体”作为操作对象。,串的逻辑结构和线性表的区别:,补充:C语言中常用的串运算,串比较, int strcmp(chars1,char
6、s2); /StrCompare(S,T) 求串长, int strlen(char s); /StrLength(S) 串连接, char strcat(char *to,char *from) /Concat( /Index(S,T,pos) ,注:用C处理字符串时,要调用标准库函数 #include,gets( char *s ) 输入一个串; puts( char *s ) 输出一个串; strcat(char *s1, char *s2 ) 串联接函数; strcpy( char *s1, char *s2 ) 串复制函数; strcmp( char *s1, char *s2 )
7、串比较函数; strlen( char *s ) 求串长函数;, 表示空串,空串的长度为零。,StrAssign ( 若S T,则返回值 0; 若S T,则返回值 0.,StrLength (S) 初始条件:串S存在。 操作结果:返回S的元素个数,称为串的长度.,Concat (,SubString( sub, commander , 1, 9 ),SubString( sub, commander , 9, 1 ),求得 sub = r ,求得 sub = commander ,SubString( sub, commander, 4, 7 ) sub = ?,SubString( sub,
8、 beijing, 7, 2 ) = ? sub = ?,SubString( student, 5, 0 ) = ,起始位置和子串长度之间存在约束关系,长度为 0 的子串为“合法”串,Index( S, T, pos )初始条件:串S和T存在,T是非空串,1posStrLength(S)。操作结果:若主串 S 中存在和串 T 值相同的子串, 则返回它在主串 S 中第pos个字符之后第一次出现的位置; 否则函数值为0。,假设 S = abcaabcaaabc , T = bca ,Index(S, T, 1) = 2;,Index(S, T, 3) = 6;,Index(S, T, 8) =
9、0;,“子串在主串中的位置”意指子串中的第一个字符在主串中的位序。,Replace ( /S中不存在与T相等的子串 ,n = StrLength(S); m = StrLength(T); i = pos;,while ( i = n-m+1) / while,SubString (sub, S, i, m); if (StrCompare(sub,T) != 0) +i ; else return i ;,串的置换函数:,S串,T串,V串,V串,pos,pos,sub,i,news 串,sub,= i+m,pos,n-pos+1,void replace(String / 剩余串 Conca
10、t( S, news, sub );,n=StrLength(S); m=StrLength(T); pos = 1; StrAssign(news, NullStr); i=1;,串的逻辑结构和线性表极为相似,区别仅在于串的数据对象约束为字符集。,串的基本操作和线性表有很大差别。 在线性表的基本操作中,大多以单个元素作为操作对象; 在串的基本操作中,通常以串的整体作为操作对象。,串的整体操作 赋值 StrAssign(S, “Data Structure”) 复制 StrCopy(T, S) / T=S, T为“Data Structure” 比较 StrCompare(S, T) 连接 C
11、oncat(T, “Data”, “Structure”) /T为“DataStructure” 取子串 SubString(sub, S, 2, 5) / sub为“ata S” 子串在主串中的定位 Index(S, “a”, 3) / 4 子串置换 Replace(S, “a”, “b”) / S为“Dbtb Structure” 子串插入 StrInsert(S, 3, “aha”) / “Daahata Structure” 子串删除 StrDelete(S, 3, 5) / “Daructure”,设 s =I AM A STUDENT, t =GOOD, q=WORKER。求:,练
12、习:,StrLength(s) StrLength(t) SubString(s, 8, 7)= SubString(t, 2, 1)= Index(s, A)= Index(s, t)= Replace(s, STUDENT,q)=,14 4 STUDENT O 3 0 ( s中没有t!) I AM A WORKER,再问:Concat(SubString(s,6,2), Concat(t,SubString(s,7,8) ?,一、串的定长顺序存储表示,二、串的堆分配存储表示,三、串的块链存储表示,5.2 串的表示和实现,5.2串的表示和实现,定长顺序存储表示用一组地址连续的存储单元存储串值
13、的字符序列 堆分配存储表示用一组地址连续的存储单元存储串值的字符序列,但存储空间是在程序执行过程中动态分配而得。 串的块链存储表示链式方式存储,首先强调:串与线性表的运算有所不同,是以“串的整体”作为操作对象,例如查找某子串,在主串某位置上插入一个子串等。,串有三种机内表示方法:,顺序存储,链式存储,定长顺序存储特点:用一组连续的存储单元来存放串,直接使用定长的字符数组来定义,数组的上界预先给出,故称为静态存储分配。,例如:#define Maxstrlen 255 /用户可用的最大串长 typedef unsigned char SStringMaxstrlen+1; SString s;
14、/s是一个可容纳255个字符的顺序串。,注: 一般用SString0来存放串长信息; C语言约定在串尾加结束符 0,以利操作加速,但不计入串长; 若字符串超过Maxstrlen 则自动截断(因为静态数组存不 进去)。,讨论:想存放超长字符串怎么办?静态数组有缺陷!,实现方式:两串连接和求子串,改用动态分配的一维数组,“堆”!,5.2.1 串的定长顺序存储表示,void Concat_Sq( char S1 , char S2 , char T ) j=0; k=0; while ( S1j != 0 ) Tk+ = S1j+; /复制串S1 j = 0; while ( S2j != 0 )
15、Tk+ = S2j+; /接着复制串S2 Tk = 0; / Concat,#define MAXSTRLEN 255 /串长度最大为255 char SStringMAXSTRLEN;,void SubString_Sq( char Sub , char S, int pos, int len) / 用Sub返回串S的第pos个字符起长度为len的子串。 / 其中,0posslen-1|lenslen-pos ) ERROR( 参数不合法); for ( j = 0; j len; j+ ) Sub j = S pos + j ; Sublen = 0; / SubString,将串S中从第
16、pos个字符开始长度为len的字符序列复制到串Sub中(注:串Sub的预留长度与S一样),typedef struct char *ch; / 若是非空串,则按串实用长度分配存储区,否则 ch 为NULL int length; / 串长度 HString;,5.2.2 串的堆分配存储表示,通常,C/C+语言中提供的串类型就是以这种存储方式实现的。系统利用函数malloc( ) /new和 free( )/delete 进行串值空间的动态管理,为每一个新产生的串分配一个存储区,称串值共享的存储空间为堆。 C语言中的串以一个空字符为结束符,串长是一个隐含值。,这类串操作实现的算法为: 先为新生成
17、的串分配一个存储空间,然后进行串值的复制。,void StrInsert_ HSq (char *S, int pos, char *T) /1posStrLength(S)+1。在串S的第pos个字符之前插入串T slen=StrLength_HSq (S); tlen=StrLength_HSq (T); char S1slen +1 ; / S1作为辅助串空间用于暂存S if ( posslen+1 ) ERROR( 插入位置不合法); if ( tlen0 ) i=0; while ( (S1i=Si)!=0 ) i+; / 暂存串S S = new charslen+tlen+1;
18、/ 为S重新分配空间 for ( i=0, k=0; ipos-1; i+ ) Sk+ = S1i; j = 0; while ( Tj!= 0 ) Sk+ = Tj+; / 插入T while ( S1i!= 0 ) Sk+ = S1i+; 串 Sk = 0; / 置串S的结束标志 ,void StrInsert ( char *S, int pos, char *T ) char *S1, *Sub; slen = strlen(S); tlen = strlen(T); if ( posslen+1 ) ERROR( “ 插入位置不合法” ); if ( tlen0 ) S1 = str
19、dup(S); S = new charslen+tlen+1; Sub = s1+pos-1; strncpy( S, S1, pos-1 ); spos-1 = 0; strcat( S, T ); strcat( S, Sub ); ,例:用堆实现串插入操作,5.2.3 串的块链存储表示,也可用链表来存储串值,由于串的数据元素是一个字符,它只有 8 位二进制数,因此用链表存储时,通常一个结点中存放的不是一个字符,而是一个子串。,存储密度 =,数据元素所占存储位,实际分配的存储位,#define CHUNKSIZE 80 / 可由用户定义的块大小 typedef struct Chunk
20、/ 结点结构 char chCUNKSIZE; struct Chunk *next; Chunk; typedef struct / 串的链表结构 Chunk *head, *tail; / 串的头和尾指针 int curlen; / 串的当前长度 LString;,例如: 在编辑系统中,整个文本编辑区可以看成是一个串,每一行是一个子串,构成一个结点。即: 同一行的串用定长结构(80个字符),行和行之间用指针相联接。,实际应用时,可以根据问题所需来设置结点的大小。,讨论:法1存储密度为 ;法2存储密度为 ;,显然,若数据元素很多,用法2存储更优称为块链结构,链式存储特点 :用链表存储串值,易
21、插入和删除。,法1:链表结点(数据域)大小取1,法2:链表结点(数据域)大小取n(例如n=4),1/2,9/15=3/5,模式匹配(Pattern Matching) 即子串定位运算(Index函数).,初始条件:串S和T存在,T是非空串,1posStrLength(s) 操作结果:若主串S中存在和串T值相同的子串,则返回它在主串S中第pos个字符之后第一次出现的位置;否则函数值为0。,注:S称为被匹配的串,T称为模式串。若S包含串T,则称匹配成功。否则称匹配不成功。,算法目的:确定主串中所含子串第一次出现的位置(定位) 即如何实现Index(S,T,pos)函数,5.3 串的模式匹配算法,B
22、F算法 (又称古典的、经典的、朴素的、穷举的) KMP算法 (特点:速度快),Index(S,T,pos)函数,S串,T串,T串,i,pos,n-m+1,S串,T 串,T串,i,j,jm,T串,BF算法设计思想: 将主串的第pos个字符和模式的第1个字符比较, 若相等,继续逐个比较后续字符; 若不等,从主串的下一字符(pos+1)起,重新与第一个字符比较。,直到主串的一个连续子串字符序列与模式相等 。返回值为S中与T匹配的子序列第一个字符的序号,即匹配成功。 否则,匹配失败,返回值 0 .,S=a b a b c a b c a c b a b,T=a b c a c,pos=5,int In
23、dex( char char S, char T, int pos ) I = pos; j = 1; Slen = strlen(S); Tlen = strlen(T); while ( iTlen ) return i-j+1; /子串结束,说明匹配成功 else return 0; /Index,BF算法的实现即Index()操作的实现,相当于子串向右滑动一个字符位置,匹配成功后指针仍要回溯!因为要返回的是被匹配的首个字符位置。,S,a,b,b,b,a,a,T,朴素的模式匹配过程,a b a,a b a,a b a,a b a,模式匹配的最简单的做法是:用T中的字符依次与S中的字符比较
24、:如果S0 = T0,S1 = T1,Sm-1 = Tm-1,则匹配成功,调用求子串的操作subString(S,1,m)即是找到的子串。否则必有某个i(0im-1),使得Si Ti,这时可将T右移一个字符,用T中字符从头开始与S中字符依次比较;如此反复执行,直到下面两种情况之一:或者到达某步时,Si = T0,Si+1 = T1,Si+m-1 = Tm-1,匹配成功,subString(S,i+1,m)即是找到的(第一个)与模式T相同的子串;或者一直将T移到无法与S继续比较为止,则匹配失败。,a,第一趟匹配 a b a b c a b c a c b a b,i=3,a b c,j=3,第二
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 华师本科生数据结构课件 第5章 串和数组 本科生 数据结构 课件 数组
限制150内