《数据结构第四章串A教学ppt》由会员分享，可在线阅读，更多相关《数据结构第四章串A教学ppt（48页珍藏版）》请在金锄头文库上搜索。
1、辽宁工程技术大学辽宁工程技术大学数数 据据 结结 构构李李 鑫鑫辽宁工程技术大学电信学院辽宁工程技术大学电信学院内 容 安 排章内 容 学时时 章 内 容 学时时 1绪绪 论论27图图6 2线线性表88动态动态 存储储管理略3栈栈和队队列49查查找4 4串310内部排序8 5数组组和广义义表 311外部排序26树树和二叉树树 1012文件略Date2数据结构第4章 串（String）4.1 串类型的定义4.2 串的表示和实现4.3 串的模式匹配算法Date3数据结构记为： s = a1 a2 . an (n0 )串名串值（用 括起来）串即字符串，是由零个或多个字符组成的有限序列，是数据 元素为
2、单个字符的特殊线性表。4.1 串类型的定义隐含结束符0 ， 即ASCII码NULL为何要单独讨论“串”类型？1） 字符串操作比其他数据类型更复杂（如拷贝、连接操作）2） 程序设计中，处理对象很多都是串类型。Date4数据结构若干术语：串长：串中字符的个数（n0）. n=0 时称为空串 。 空白串：由一个或多个空格符组成的串。问：空串和空白串有无区别？答：有区别。空串(Null String)是指长度为零的串；而空白串(Blank String),是指包含一个或多个空白字 符 (空格键)的字符串.Date5数据结构子串： 子串位置： 字符位置：串相等：例1：现有以下4个字符串： a =BEI b
3、 =JING c = BEIJING d = BEI JING问： 他们各自的长度？a是c和d的子串，在c和d中的位置都是1串S中任意个连续的字符序列叫S的子串; S叫主串。 子串的第一个字符在主串中的序号。 字符在串中的序号。 串长度相等，且对应位置上字符相等。 a是哪个串的子串？在主串中的位置是多少？a =3，b =4，c = 7，d=8“空串是任意串的子串；任意串S都是S本身的子串，除S本身 外，S的其他子串称为S的真子串。” 数据结构与算法中山大学出版社 空串是哪个串的子串？ a是不是自己的子串？Date6数据结构C语言中已有类似串运算函数！ADT String Objects: D=
4、ai | aiCharacterSet, i=1, 2,，n, n0 Relations: R1= | ai-1,ai D, i=2, ，n functions: /至少有13种基本操作StrAssign( /若pos和len参数越界，则告警Sub1len=Spospos+len-1;Sub0=len; return OK;将串S中从第pos个字符开始、长度为len的字符序列复制到串Sub中。 （注：考虑到函数的通用性，应当让串Sub的预留长度与S一样）子串长度s = a1 a2 . anposlenSub 讨论：想存放超长字符串怎么办？ 改用动态分配的一维数组堆Date19数据结构思路：利用
5、malloc函数合理预设串长空间。特点： 若在操作中串值改变，还可以利用realloc函数按新串长 度增加空间（即动态数组概念） 。Typedef struct char *ch; /若非空串,按串长分配空间; 否则ch=NULLint length; /串长度HString堆分配存储特点：仍用一组连续的存储单元来存放串， 但存储空间是在程序执行过程中动态分配而得。堆T的存储结构描述：T.ch T.lengthDate20数据结构C是指针变量，可以自增 ！意即每次后移一个数据 单元。直到终值为“假” 停止，串尾特征是 c0NULL 0Status StrAssign(HString /释放T原
6、有空间for ( i=0, c=chars; c c; +i, +c); /求chars的串长度i例1：编写建堆函数 (参见教材P76）此处T.ch0没有 用来装串长，因为 另有T.length 分 量if ( !i ) T.ch = NULL; T.length = 0;elseif (!(T.ch = (char*)malloc( i *sizeof(char)exit(OVERFLOW);T.ch0.i-1 = chars0.i-1;T.length =i;Return OK; /StrAssignDate21数据结构Status StrInsert ( HString /pos不合法则
7、告警if(T.length) /只要串T不空，就需要重新分配S空间，以便插入Tif (!（S.ch=(char*)realloc(S.ch, (S.length+T.length)*sizeof(char) ) exit(OVERFLOW); /若开不了新空间，则退出for ( i=S.length-1; i=pos-1; -i ) S.chi+T.length = S.chi; / 为插入T而腾出pos之后的位置，即从S的pos位置起全部字符均后移S.chpos-1pos+T.length-2 = T.ch0T.length-1; /插入T，略/0 S.length + = T.length
8、; /刷新S串长度 return OK; /StrInsert例2：用“堆”方式编写串插入函数 (参见教材P75) 1posS.length+1Date22数据结构讨论：法1存储密度为 ；法2存储密度为 ；显然，若数据元素很多，用法2存储更优称为块链结构链式存储特点 ：用链表存储串值，易插入和删除。法1：链表结点的数据分量长度取1 1（个字符）（个字符）法2：链表结点（数据域）大小取n(例如n=4)1/29/15=3/5A B C I NULLheadheadA B C D E F G H I # # # NULL串值所占的存储位置 存储密度= 实际分配的存储位 Date23数据结构对块链表的
9、整体描述#define CHUNKSIZE 80 /每块大小，可由用户定义 typedef struct Chunk /首先定义结点类型char ch CHUNKSIZE ; /每个结点中的数据域struct Chunk * next ; /每个结点中的指针域 Chunk; 块链类型定义：块链函数的编写略typedef struct /其次定义用链式存储的串类型Chunk *head; /头指针Chunk *tail; /尾指针int curLen; /结点个数 Lstring; /串类型只用一次，前面可以不加Lstring对每个结点的描述Date24数据结构算法目的：确定主串中所含子串第一次
10、出现的位置（定位） 4.3 串的模式匹配算法 BF算法 （又称古典的、经典的、朴素的、穷举的） KMP算法算法种类：带回溯，速度慢避免回溯，匹配速度快， 是全课程的亮点之一定位问题称为串的模式匹配(Pattern Matching)，即子串定位运 算， 它是串处理系统中最重要的操作之一。典型函数为Index(S,T,pos)Index(S,T,pos)，见教材P71Date25数据结构BF算法的实现即编写Index(S,T,pos)函数 例1： S=ababcabcacbab，T=abcac， pos=1，求：串T在串S中第pos个字符之后的位置。 利用演示系统看BF算法执行过程。BF算法设计
11、思想： 将主串S的第pos个字符和模式T的第1个字符比较，若相等，继续逐个比较后续字符；若不等，从主串S的下一字符（pos+1）起，重新与T第一 个字符比较。 直到主串S的一个连续子串字符序列与模式T相等。返回值 为S中与T匹配的子序列第一个字符的序号，即匹配成功。 否则，匹配失败，返回值 0 .Date26数据结构Int IndexIndex(SString S, SString T, int pos) i=pos; j=1;while ( iT0) return i-T0; /子串结束，说明匹配成功else return0;/Index例2： S=ababcabcacbab，T=abcac
12、，求Index(S,T,5)Index(S,T,5)（参见教材参见教材P79P79）相当于子串向右滑动一个字符位置匹配成功后指针仍要回溯！因为要返回的 是被匹配的首个字符位置。ijS=a b a b c a b c a c b a bT=a b c a cpos=5Date27数据结构讨论： 若n为主串长度，m为子串长度，则串的BF匹配算法最坏的情况下需要 比较字符的总次数为(n-m+1)*mO(n*m)一般的情况是：O(n+m)推导方法：要从最好到最坏情况统计总的比较次数，然后要从最好到最坏情况统计总的比较次数，然后 取平均。取平均。BF算法的时间复杂度最好的情况是：一配就中！ 只比较了m次
13、。能否利用已部分匹配过的信息而加快模式串的滑动速度？ 能！而且主串S的指针i不必回溯！最坏情况也能达到O(n+m)请看请看KMPKMP算法算法！最恶劣情况是：主串前面n-m个位置都部分匹配到子串的最后一 位，即这n-m位比较了m次，别忘了最后m位也各比较了一次，还 要加上m！所以总次数为：(n-m)*m+m (n-m+1)*mDate28数据结构KMP算法（特点：速度快） KMP算法设计思想 KMP算法的推导过程 KMP算法的实现 （关键技术:计算nextj） KMP算法的时间复杂度全书一大亮点！全书一大亮点！Date29数据结构奇妙的结果：奇妙的结果： k k 仅与模式串仅与模式串T T有关
14、！有关！ KMP算法的推导过程：（见教材P81）请抓住部分匹配时的两个特征：两式联立可得： T T1 1TTk-1k-1=T=Tj-(k-1)j-(k-1) TTj-1j-1 S=a b a b c a b c a c b a bT=a b c a cik则T的k-11位S前i-1i-1i-(k-1)i-(k-1)位即(4-2）式含义设目前打算与T的第k字符开始比较(1)(2)TT1 1TTk-1k-1 则T的j-1j-(k-1)位 S前i-1i-1i-(k-1)i-(k-1)位即(4-3）式含义ikjS=a b a b c a b c a c b a bT=a b c a c刚才肯定是在S的i处和T的第j字符 处失配 T Tj-(k-1)j-(k-1) TTj-1j-1 截取一段，但截取一段，但k k有限制，有限制，11时，Nextj的值为：模式串的位置从1到j-1 构成的串中所出现的首尾相同的子串的最大长度加1 。无首尾相同的子串时Nextj的值为1。 / Nextj=1表示从模式串头部开始进行字符比较（2） next j 怎么计算？怎样计算怎样计算模式模式T T所有可能的失配点所有可能的失配点 j j 所对应的所对应的
