4.1 串的抽象数据类型的定义 4.2 串的表示和实现 4.3 串的模式匹配算法.

Slides:



Advertisements
Similar presentations
一、 一阶线性微分方程及其解法 二、 一阶线性微分方程的简单应用 三、 小结及作业 §6.2 一阶线性微分方程.
Advertisements

数据结构的引入. 通讯录管理 社团机构管理 校园导航管理 通讯录管理 社团机构管理 校园导航管理.
阻塞操作. 在 linux 里,一个等待队列由一个 wait_queue_head_t 类型的结构来描述 等待队列的初始化: static wait_queue_head_t testqueue; init_waitqueue_head(&testqueue);
数据结构——树和二叉树 1/96.
数据结构与算法 (C++语言版) 第4章 串.
C++中的声音处理 在传统Turbo C环境中,如果想用C语言控制电脑发声,可以用Sound函数。在VC6.6环境中如果想控制电脑发声则采用Beep函数。原型为: Beep(频率,持续时间) , 单位毫秒 暂停程序执行使用Sleep函数 Sleep(持续时间), 单位毫秒 引用这两个函数时,必须包含头文件
第九章 字符串.
單向鏈結串列 Singly Linked Lists.
第四章 串 2018/11/13.
第4章 串 串的基本概念和C语言的串函数 串的存储结构 动态数组实现的顺序串 串的模式匹配算法——BF算法 主要知识点.
数据结构 Data Structure 主讲人:王国军,郑瑾 中南大学 中南大学信息院计科系
第4章 串、数组和广义表 丽水学院工学院.
C语言高级编程(第四部分) 字符串 北京大学 信息科学技术学院.
数据结构 第4章 串.
数据结构——串 1/15.
第四章 串和数组(一) 1/.
走进编程 程序的顺序结构(二).
辅导课程六.
串和数组.
第4章 串 4.1 串的基本概念及其抽象数据 4.2 串的存储结构 4.3 串类 4.4 串的模式匹配算法.
第 3 讲 线性表(一).
第三章 栈与队列 £3.1 栈 £3.3 队列 £3.2 栈的应用举例 £3.1.1 栈的定义 £3.1.2 栈的顺序存储结构
第3章 栈和队列(一).
第三章 栈和队列.
数 据 结 构 Ch.4 串 计 算 机 学 院 肖明军
陈海明 副教授 信息学院 计算机系 电子信息类非计算机专业选修课 程序设计实践 陈海明 副教授 信息学院 计算机系
第4章 串 4.1 串的基本概念 4.2 串的存储结构 4.3 串的模式匹配.
模式匹配算法的原理及应用.
动态规划(Dynamic Programming)
数据结构概论 第4章 串 董黎刚 浙江工商大学信电学院 2019年1月18日.
第四章串 4.1 串类型定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.4 串操作应用举例.
第四章 串.
第4章 串和数组 本章主要介绍下列内容: 串的定义、存储结构和基本运算 数组的定义、基本运算和存储结构 特殊矩阵的压缩存储.
顺序表的插入.
王玲 第 2 章 线性表 王玲 2019/2/25.
第五章 数组 5.1 数组的定义 5.2 数组的表示和实现* 5.3 数组的压缩.
从zval看PHP变量
第五章 串和数组 5.1 串的定义和操作 5.2 串的表示和实现 5.3 字符串应用 5.4 字符串匹配算法 5.5 数组
第四章 串.
7.1 广义表的概念 广义表是n(n≥0)个数据元素组成的序列,其中每个数据元素或是单个数据元素(简称原子),或仍然是一个广义表 。
C++语言程序设计 C++语言程序设计 第七章 类与对象 第十一组 C++语言程序设计.
C语言程序设计 主讲教师:陆幼利.
简单介绍 用C++实现简单的模板数据结构 ArrayList(数组, 类似std::vector)
学习目标 1、什么是字符集 2、字符集四个级别 3、如何选择字符集.
顺序表的删除.
C++语言程序设计 C++语言程序设计 第六章 指针和引用 第十一组 C++语言程序设计.
第五章 串和数组 5.1 串的定义和操作 5.2 串的表示和实现 5.3 字符串应用 5.4 字符串匹配算法 5.5 数组
5.1 串的基本概念 5.2 串的存储结构 5.3 串的基本运算 5.4 模式匹配 5.5 串在文本编辑中的应用
数 据 结 构 刘家芬 Sept 2012.
第四章 串和数组 4.1 串的定义* 4.2 串的表示和实现* 4.3 数组 4.4 数组的压缩.
顺序查找.
第 四 讲 线性表(二).
字符串 (String) 字符串是 n (  0 ) 个字符的有限序列, 记作 S = “c1c2c3…cn” 其中,S 是串名字
第4章 Excel电子表格制作软件 4.4 函数(一).
<编程达人入门课程> 本节内容 为什么要使用变量? 视频提供:昆山爱达人信息技术有限公司 官网地址: 联系QQ:
§6.7 子空间的直和 一、直和的定义 二、直和的判定 三、多个子空间的直和.
3.16 枚举算法及其程序实现 ——数组的作用.
第 六 讲 栈和队列(一).
第四章 串 £4.1 串的定义 £4.2 串的顺序存储结构 £4.3 串的链式存储结构 £4.4 串的应用—文本编辑
多层循环 Private Sub Command1_Click() Dim i As Integer, j As Integer
第五章 串和数组 5.1 串的定义和操作 5.2 串的表示和实现 5.3 正文匹配模式 5.4 正文编辑 5.5 数组 5.6 数组的压缩.
_03宽字符与Unicode编程 本节课讲师——void* 视频提供:昆山爱达人信息技术有限公司 官网地址:
实验目的:掌握数据的顺序存储结构及它们在计算机中的操作。 实验内容:
第1章 数据结构基础概论 本章主要介绍以下内容 数据结构研究的主要内容 数据结构中涉及的基本概念 算法的概念、描述方法以及评价标准.
第四章 串 String
基于列存储的RDF数据管理 朱敏
C++语言程序设计 C++语言程序设计 第一章 C++语言概述 第十一组 C++语言程序设计.
C++语言程序设计 C++语言程序设计 第九章 类的特殊成员 第十一组 C++语言程序设计.
插入排序的正确性证明 以及各种改进方法.
第5章 其他线性数据结构.
Presentation transcript:

4.1 串的抽象数据类型的定义 4.2 串的表示和实现 4.3 串的模式匹配算法

4.1 串的抽象数据类型的定义如下: 数据关系: ADT String { D={ ai |ai∈CharacterSet, 4.1 串的抽象数据类型的定义如下: 串是有限长的字符序列,由一对单引号相括,如: a string ADT String { 数据对象: D={ ai |ai∈CharacterSet, i=1,2,...,n, n≥0 } 数据关系: R1={ < ai-1, ai > | ai-1, ai ∈D, i=2,...,n }

基本操作: StrAssign (&T, chars) DestroyString(&S) StrCopy (&T, S) StrLength(S) StrCompare (S, T) Concat (&T, S1, S2) StrEmpty (S)

SubString (&Sub, S, pos, len) ClearString (&S) Index (S, T, pos) Replace (&S, T, V) StrInsert (&S, pos, T) StrDelete (&S, pos, len) } ADT String

StrAssign (&T, chars) 初始条件:chars 是字符串常量。 操作结果:把 chars 赋为 T 的值。

StrCopy (&T, S) 初始条件:串 S 存在。 操作结果:由串 S 复制得串 T。

DestroyString (&S) 初始条件:串 S 存在。 操作结果:串 S 被销毁。

StrEmpty (S) 初始条件:串S存在。 操作结果:若 S 为空串,则返回TRUE, 否则返回 FALSE。  表示空串,空串的长度为零。

StrCompare (S, T) 初始条件:串 S 和 T 存在。 操作结果:若S  T,则返回值  0; 若S  T,则返回值  0; 若S  T,则返回值  0。 例如:StrCompare(data, state) < 0 StrCompare(cat, case) > 0

StrLength (S) 初始条件:串 S 存在。 操作结果:返回 S 的元素个数, 称为串的长度。

Concat (&T, S1, S2) 初始条件:串 S1 和 S2 存在。 操作结果:用 T 返回由 S1 和 S2 联接而成的新串。 例如: Concate( T, man, kind) 求得 T = mankind

串 S 存在,1≤pos≤StrLength(S) 操作结果: SubString (&Sub, S, pos, len) 初始条件: 串 S 存在,1≤pos≤StrLength(S) 且0≤len≤StrLength(S)-pos+1。 操作结果: 用 Sub 返回串 S 的第 pos 个字符起 长度为 len 的子串。

子串为“串” 中的一个字符子序列 例如: SubString( sub, commander, 4, 3) 求得 sub = man ; SubString( sub, commander, 1, 9) 求得 sub = commander; SubString( sub, commander, 9, 1) 求得 sub = r;

SubString(sub, commander, 4, 7) sub = ? SubString(sub, beijing, 7, 2) = ? sub = ? 起始位置和子串长度之间存在约束关系 SubString(student, 5, 0) =  长度为 0 的子串为“合法”串

Index (S, T, pos) 初始条件:串S和T存在,T是非空串, 1≤pos≤StrLength(S)。 操作结果: 若主串 S 中存在和串 T 值相同 的子串, 则返回它在主串 S 中第pos个 字符之后第一次出现的位置; 否则函数值为0。

“子串在主串中的位置”意指子串 中的第一个字符在主串中的位序。 假设 S = abcaabcaaabc, T = bca Index(S, T, 1) = 2; Index(S, T, 3) = 6; Index(S, T, 8) = 0;

Replace (&S, T, V) 初始条件:串S, T和 V 均已存在, 且 T 是非空串。 操作结果:用V替换主串S中出现 的所有与(模式串)T 相等的不重叠的子串。

例如: 假设 S = abcaabcaaabca,T = bca 若 V = x, 则经置换后得到 S = axaxaax 若 V = bc, 则经置换后得到 S = abcabcaabc

StrInsert (&S, pos, T) 初始条件:串S和T存在, 1≤pos≤StrLength(S)+1。 操作结果:在串S的第pos个字符之前 插入串T。 例如:S = chater,T = rac, 则执行 StrInsert(S, 4, T)之后得到 S = character

StrDelete (&S, pos, len) 初始条件:串S存在 1≤pos≤StrLength(S)-len+1。 操作结果:从串S中删除第pos个字符 起长度为len的子串。

ClearString (&S) 初始条件:串S存在。 操作结果:将S清为空串。

例如:C语言函数库中提供下列串处理函数: 对于串的基本操作集可以有不同的定义方法,在使用高级程序设计语言中的串类型时,应以该语言的参考手册为准。 例如:C语言函数库中提供下列串处理函数: gets(str) 输入一个串; puts(str) 输出一个串; strcat(str1, str2) 串联接函数; strcpy(str1, str2, k) 串复制函数; strcmp(str1, str2) 串比较函数; strlen(str) 求串长函数;

串赋值StrAssign、串复制Strcopy、 串比较StrCompare、求串长StrLength、 在上述抽象数据类型定义的13种操作中, 串赋值StrAssign、串复制Strcopy、 串比较StrCompare、求串长StrLength、 串联接Concat以及求子串SubString 等六种操作构成串类型的最小操作子集。 即:这些操作不可能利用其他串操作来实现, 反之,其他串操作(除串清除ClearString和串 销毁DestroyString外)可在这个最小操作子 集上实现。

例如,可利用串比较、求串长和求子串等操作实现定位函数Index(S,T,pos)。 算法的基本思想为: StrCompare(SubString(S, i, StrLength(T)),T ) ? 0 i S 串 pos n-m+1 T 串 T 串

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中不存在与T相等的子串 } // Index

又如串的置换函数: pos pos i S 串 sub T 串 V 串 news 串 sub V 串

串的逻辑结构和线性表极为相似,区别 仅在于串的数据对象约束为字符集。 串的基本操作和线性表有很大差别。 在线性表的基本操作中,大多以“单个元素”作为操作对象; 在串的基本操作中,通常以“串的整体”作为操作对象。

4.2 串的表示和实现 在程序设计语言中,串只是作为输入或输出的常量出现,则只需存储此串的串值,即字符序列即可。但在多数非数值处理的程序中,串也以变量的形式出现。

一、串的定长顺序存储表示 二、串的堆分配存储表示 三、串的块链存储表示

一、串的定长顺序存储表示 // 用户可在255以内定义最大串长 typedef unsigned char Sstring #define MAXSTRLEN 255 // 用户可在255以内定义最大串长 typedef unsigned char Sstring [MAXSTRLEN + 1]; // 0号单元存放串的长度

特点: 串的实际长度可在这个予定义长度的范围内随意设定,超过予定义长度的串值则被舍去,称之为 “截断” 。 按这种串的表示方法实现的串的运算时,其基本操作为 “字符序列的复制”。

// 用T返回由S1和S2联接而成的新串。若未截断, 则返回TRUE,否则FALSE。 例如:串的联接算法中需分三种情况处理: Status Concat(SString S1, SString S2, SString &T) { // 用T返回由S1和S2联接而成的新串。若未截断, 则返回TRUE,否则FALSE。 return uncut; } // Concat if (S1[0]+S2[0] <= MAXSTRLEN) {// 未截断 T[1..S1[0]] = S1[1..S1[0]]; T[S1[0]+1..S1[0]+S2[0]] = S2[1..S2[0]]; T[0] = S1[0]+S2[0]; uncut = TRUE; } else if (S1[0] <MAXSTRSIZE) { // 截断 T[1..S1[0]] = S1[1..S1[0]]; T[S1[0]+1..MAXSTRLEN] = S2[1..MAXSTRLEN-S1[0]]; T[0] = MAXSTRLEN; uncut = FALSE; } else { // 截断(仅取S1) T[0..MAXSTRLEN] = S1[0..MAXSTRLEN]; // T[0] == S1[0] == MAXSTRLEN uncut = FALSE; }

二、串的堆分配存储表示 char *ch; // 若是非空串,则按串长分配存储区, // 否则ch为NULL typedef struct { char *ch; // 若是非空串,则按串长分配存储区, // 否则ch为NULL int length; // 串长度 } HString;

这类串操作实现的算法为: C语言中的串以一个空字符为结束符, 串长是一个隐含值。 先为新生成的串分配一个存储空间,然后 进行串值的复制。 通常,C语言中提供的串类型就是以这种存储方式实现的。系统利用函数malloc( )和free( )进行串值空间的动态管理,为每一个新产生的串分配一个存储区,称串值共享的存储空间为“堆”。 C语言中的串以一个空字符为结束符, 串长是一个隐含值。 这类串操作实现的算法为: 先为新生成的串分配一个存储空间,然后 进行串值的复制。

Status Concat(HString &T, HString S1, HString S2) { // 用T返回由S1和S2联接而成的新串 if (T.ch) free(T.ch); // 释放旧空间 if (!(T.ch = (char *) malloc((S1.length+S2.length)*sizeof(char)))) exit (OVERFLOW); T.ch[0..S1.length-1] = S1.ch[0..S1.length-1]; T.length = S1.length + S2.length; T.ch[S1.length..T.length-1] = S2.ch[0..S2.length-1]; return OK; } // Concat

… … int pos, int len) { // 用Sub返回串S的第pos个字符起长度为len的子串 Status SubString(HString &Sub, HString S, int pos, int len) { // 用Sub返回串S的第pos个字符起长度为len的子串 if (pos < 1 || pos > S.length || len < 0 || len > S.length-pos+1) return ERROR; if (Sub.ch) free (Sub.ch); // 释放旧空间 if (!len) { Sub.ch = NULL; Sub.length = 0; } // 空子串 else { } // 完整子串 return OK; } // SubString … …

Sub.ch[0..len-1] = S[pos-1..pos+len-2]; Sub.length = len; Sub.ch = (char *)malloc(len*sizeof(char)); Sub.ch[0..len-1] = S[pos-1..pos+len-2]; Sub.length = len;

三、串的块链存储表示 也可用链表来存储串值,由于串的数据元素是一个字符,它只有 8 位二进制数,因此用链表存储时,通常一个结点中存放的不是一个字符,而是一个子串。 数据元素所占存储位 存储密度 = 实际分配的存储位

typedef struct Chunk { // 结点结构 char ch[CUNKSIZE]; struct Chunk *next; #define CHUNKSIZE 80 // 可由用户定义的块大小 typedef struct Chunk { // 结点结构 char ch[CUNKSIZE]; struct Chunk *next; } Chunk; typedef struct { // 串的链表结构 Chunk *head, *tail; // 串的头和尾指针 int curlen; // 串的当前长度 } LString;

实际应用时,可以根据问题所需来设置结点的大小。 例如: 在编辑系统中,整个文本编辑区可以看成是一个串,每一行是一个子串,构成一个结点。即: 同一行的串用定长结构(80个字符), 行和行之间用指针相联接。

4.3 串的模式匹配算法 这是串的一种重要操作,很多 软件,若有“编辑”菜单项的话, 则其中必有“查找”子菜单项。

首先,回忆一下串匹配(查找)的定义: INDEX (S, T, pos) 初始条件:串S和T存在,T是非空串, 1≤pos≤StrLength(S)。 操作结果:若主串S中存在和串T值相 同的子串返回它在主串S中 第pos个字符之后第一次出 现的位置;否则函数 值为0。

下面讨论以定长顺序结构 表示串时的几种算法。 一、简单算法 二、首尾匹配算法 三、KMP(D.E.Knuth, V.R.Pratt, J.H.Morris) 算法

一、简单算法 int Index(SString S, SString T, int pos) { // 返回子串T在主串S中第pos个字符之后的位置。若不存在, // 则函数值为0。其中,T非空,1≤pos≤StrLength(S)。 i = pos; j = 1; while (i <= S[0] && j <= T[0]) { if (S[i] == T[j]) { ++i; ++j; } // 继续比较后继字符 else { i = i-j+2; j = 1; } // 指针后退重新开始匹配 } if (j > T[0]) return i-T[0]; else return 0; } // Index

二、首尾匹配算法 先比较模式串的第一个字符, 再比较模式串的最后一个字符, 最后比较模式串中从第二个到 第n-1个字符。

int Index_FL(SString S, SString T, int pos) { sLength = S[0]; tLength = T[0]; i = pos; patStartChar = T[1]; patEndChar = T[tLength]; while (i <= sLength – tLength + 1) { if (S[i] != patStartChar) ++i; //重新查找匹配起始点 else if (S[i+tLength-1] != patEndChar) ++i; // 模式串的“尾字符”不匹配 else { } } return 0; // 检查中间字符的匹配情况

k = 1; j = 2; while ( j < tLength && S[i+k] == T[j]) { ++k; ++j; } if ( j == tLength ) return i; else ++i; // 重新开始下一次的匹配检测

三、KMP(D.E.Knuth, V.R.Pratt, J.H.Morris) 算法 KMP算法的时间复杂度可以达到O(m+n) 当 S[i] <> T[j] 时, 已经得到的结果: S[i-j+1..i-1] == T[1..j-1] 若已知 T[1..k-1] == T[j-k+1..j-1] 则有 S[i-k+1..i-1] == T[1..k-1]

定义:模式串的next函数

int Index_KMP(SString S, SString T, int pos) { // 1≤pos≤StrLength(S) i = pos; j = 1; while (i <= S[0] && j <= T[0]) { if (j = 0 || S[i] == T[j]) { ++i; ++j; } // 继续比较后继字符 else j = next[j]; // 模式串向右移动 } if (j > T[0]) return i-T[0]; // 匹配成功 else return 0; } // Index_KMP

求next函数值的过程是一个递推过程,分析如下: 假设:next[j] = k;又 T[j] = T[k] 则: next[j+1] = k+1 若: T[j]  T[k] 则需往前回朔,检查 T[j] = T[ ?] 这实际上也是一个匹配的过程, 不同在于:主串和模式串是同一个串

void get_next(SString &T, int &next[] ) { // 求模式串T的next函数值并存入数组next i = 1; next[1] = 0; j = 0; while (i < T[0]) { if (j = 0 || T[i] == T[j]) {++i; ++j; next[i] = j; } else j = next[j]; } } // get_next

S = aaabaaabaaabaaabaaab T = aaaab 还有一种特殊情况需要考虑: 例如: S = aaabaaabaaabaaabaaab T = aaaab next[j]=01234 nextval[j]=00004

void get_nextval(SString &T, int &nextval[]) { i = 1; nextval[1] = 0; j = 0; while (i < T[0]) { if (j = 0 || T[i] == T[j]) { ++i; ++j; if (T[i] != T[j]) next[i] = j; else nextval[i] = nextval[j]; } else j = nextval[j]; } // get_nextval

1. 熟悉串的七种基本操作的定义,并能利用这些基本操作来实现串的其它各种操作的方法。 本章学习要点 1. 熟悉串的七种基本操作的定义,并能利用这些基本操作来实现串的其它各种操作的方法。 2. 熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法。 3. 了解串的堆存储结构以及在其上实现串操作的基本方法。

4. 理解串匹配的KMP算法,熟悉NEXT函数的定义,学会手工计算给定模式串的NEXT函数值和改进的NEXT函数值。 5. 了解串操作的应用方法和特点。