当前位置：文档之家 › 数据结构—串的模式匹配

数据结构—串的模式匹配

  • 格式：docx
  • 大小：10.35 KB
  • 文档页数：3

下载文档原格式

  / 3

合集下载

数据结构中的串

数据结构中的串

next[j] = max { k | 0<k<j 且使得 1…tk-1=tj-k+1…tj-1} 当集合不空 且使得t 1
首页
其他情况
上页 下页 退出
第四章
§4.4 串的应用
一、文本编辑 二、建立索引表
思考题： 思考题： 试写出判串S是否是回文的算法。 1、试写出判串S是否是回文的算法。 若串S= S=‘ STRING’以块链存储， 2、若串S=‘THIS IS A STRING’以块链存储，结点大小 链指针占4个字节， 32位 问存储密度是多少？ 为4，链指针占4个字节，即32位，问存储密度是多少？ 是两个但单链表存储的串，试设计一个算法， 3、若X和Y是两个但单链表存储的串，试设计一个算法， 找出X中第一个不在Y中出现的字符来。 找出X中第一个不在Y中出现的字符来。
首页
上页
下页
退出
第四章
§4.1 串类型的定义
三、C语言常用的字符串处理的标准函数： 语言常用的字符串处理的标准函数：
int strlen(char s); int strcmp(chars1,char s2); char strcpy(char to,char from); char strcat(char to,char from) 但在抽象数据类型定义的13种操作中， 13种操作中 但在抽象数据类型定义的13种操作中，串赋值 StrAssign、串复制StrCopy、串比较StrCompare、求串 StrAssign、串复制StrCopy、串比较StrCompare、 StrCopy StrCompare StrLength、串联接Concat以及求子串SubString Concat以及求子串SubString等 长StrLength、串联接Concat以及求子串SubString等6 种操作构成串类型的最小操作子集。 种操作构成串类型的最小操作子集。 例如，可利用判等、 例如，可利用判等、求串长和求子串等操作实现串 的定位函数 Index(S,T,pos) 和串的置换操作 Replace(S,T,V)。 。 换句话说，如果在高级程序设计语言中设有"串类 换句话说，如果在高级程序设计语言中设有 串类 的话， 种操作， 型"的话，提供的基本操作不能没有这 种操作，因为它 的话 提供的基本操作不能没有这6种操作 首页 上页 下页 退出 们不能通过其它串操作实现。 们不能通过其它串操作实现。

《数据结构与算法(C++语言版)》第4章_串

《数据结构与算法(C++语言版)》第4章_串

串函数与串的类定义
• 常用的 常用的C++串函数 串函数 • C++的串库（string.h）中提供了许多字符串的操作函数，几 个常用的C++字符串函数及其使用方法如下。 •假设已有以下定义语句：
串函数与串的类定义
• （1）串拷贝函数 • char *strcpy(char *s1, const char *s2)，将字符串s2复制到字 符串数组s1中，返回s1的值。 • char *strncpy(char *s1, const char *s2, size_tn)将字符串s2中最 多n个字符复制到字符串数组s1中，返回s1的值。 • 例如：
串函数与串的类定义
• （3）串比较函数 • int strcmp(const char *s1, const char *s2)，比较字符串s1和字 符串s2。函数在s1等于、小于或大于s2时，分别返回0、小 于0或者大于0的值。 • int strncmp(const char *s1, const char *s2, size_tn)比较字符串 s1中的n个字符和字符串s2。函数在s1等于、小于或大于s2 时，分别返回0、小于0或者大于0的值。 • 例如：
串模式匹配
• 无回溯的匹配算法 • 在上面介绍的匹配算法中，某趟匹配失败时，下一趟的匹 配相当于将子串P后移1位再从头与主串中对应字符进行比 较，即相当于i指示器回溯到上趟（最近失败的一趟）匹配 的起点的下一个位置，这样，主串中每个字符都要与子串 中的第1个字符对应一次，再向后比较。因此，主串中每个 字符参加比较的次数最多可达n次（n为子串长度），因此 时间复杂度为O(nm)。那么，能否使目标串中每个字符只参 加一次比较呢？也就是说，能否不回溯i指示器？回答是肯 定的。这个问题是由D.E.Knoth与V.R.Pratt和J.H.Morris同时 解决的，所以有的文献也称这种思想的串匹配算法为KMP 算法。

数据结构 串 实验报告

数据结构 串 实验报告

实验报告实验名称：串实验目的：（1）、熟悉C语言的上机环境，进一步掌握C语言的结构特点；（2）、掌握串的定义及C语言实现；（3）、掌握串的模式匹配及C语言实现；（4）、掌握串的各种基本操作；实验步骤：（1）、建立链串类型（2）、实现匹配过程中需考虑的链表的特征。

实验内容：4.一个字符串中的任意一个子序列，若子序列中各字符值均相同，则成为字符平台。

写一算法，输入任意以字符串S，输出S中长度最大的所有字符平台的起始位置及所含字符。

注意，最大字符平台有可能不止一个。

实验数据记录：（源代码及执行过程）#include<stdio.h>#include<stdlib.h>#define Maxsize 20#define n 100typedef struct Node{int element[Maxsize];int front;int rear;}Queue;int EnterQueue(Queue *Q,int x){if((Q->rear+1)%Maxsize == Q->front){printf("队列已满!\n");return 0;}Q->element[Q->rear] = x;Q->rear = (Q->rear+1)%Maxsize;return 1;}int DeleQueue(Queue *Q,int *x){if(Q->front == Q->rear){printf("队列为空!\n");return 0;}*x = Q->element[Q->front];Q->front = (Q->front+1)%Maxsize;return 1;}int Donull(Queue *Q){while(Q->front != Q->rear){Q->element[Q->front] = 0;Q->front = (Q->front+1)%Maxsize;}Q->front = Q->rear = 0;if(Q->front == Q->rear){return 1;}else{return 0;}}int main(void){char str[n];int i=0,j=1,k=1,ch,p=1,flag=1;Queue *Q;Q = (Queue *)malloc(sizeof(Queue));Q->front = Q->rear = 0;printf("请输入字符串：");gets(str);while('\0' != *(str+i)){ while(*(str+i+1) == *(str+i)){if(flag){p = i;flag = 0;}i++;j++;}if(flag){p = i;}if(j >= k){if(j > k){Donull(Q);k = j;}if(EnterQueue(Q ,j) == 0)break;if(EnterQueue(Q,p+1) == 0)break;if(EnterQueue(Q,*(str+i)) == 0)break;}j=1;i++;flag = 1;} while(Q->front < Q->rear){DeleQueue(Q,&j);DeleQueue(Q,&k);DeleQueue(Q,&ch);printf("%-10d",k);for(i = 0; i < j; i++){printf("%c",ch);}printf("\n");}printf("\n");system("pause");}。

OBE视域下《数据结构》思政教学案例探究——以“串的模式匹配算法”为例

OBE视域下《数据结构》思政教学案例探究——以“串的模式匹配算法”为例

OBE视域下《数据结构》思政教学案例探究——以“串的模
式匹配算法”为例
邱骏达;蔡秋茹;史培中;由从哲
【期刊名称】《教育进展》
【年(卷),期】2024(14)3
【摘要】目前,大部分《数据结构》教材中选用的案例较为陈旧,与国家发展战略所涉及的技术领域需求存在脱节现象。

针对这一现状,本文基于OBE教学理念,聚焦计算机网络舆情管理的应用热点,结合课程思政设计了一个“串的模式匹配算法”的教学案例。

本案例采用真实网络热点事件评论文章为素材构建数据样本,结合本教学团队公开发表在SCI期刊上的相关算法,讲授建模思想、模型求解过程及信息后处理方法,落实“研”为“教”所用的教学科研理念。

本文提出的思政教学案例共需4个理论课时和2个实验课时,学时安排合理,另外,该案例已在2022~2023学年第一学期相关专业班级进行实验教学,得到了学生良好的学习反馈。

【总页数】7页(P128-134)
【作者】邱骏达;蔡秋茹;史培中;由从哲
【作者单位】江苏理工学院计算机工程学院无锡
【正文语种】中文
【中图分类】G63
【相关文献】
1.OBE视域下专业"课程思政"教学案例库建设探究
2.课程思政视域下基于BOPPPS的混合式教学实践研究
——以"数据结构与算法"为例3.OBE视域下的高校英语课程思政教学实践——以《高级英文写作教程(第二版)》为例4.OBE理念下突出思政教育的新工科人才培养方案探究——以材料成型及控制工程专业为例5.课程思政视域下基于SPOC的混合教学模式探索与实践——以数据结构与算法课程为例
因版权原因，仅展示原文概要，查看原文内容请购买。

数据结构-第4章 串

数据结构-第4章 串
真子串是指不包含自身的所有子串。
4.1 串的类型定义
子串的序号：将子串在主串中首次出现时的该 子串的首字符对应在主串中的序号，称为子串 在主串中的序号（或位置）。 【例】 A=“abcdefbbcd”，B=“bcd”，B在A中的 序号为2。 特别地，空串是任意串的子串，任意串是其自 身的子串。
4.1.2 串的抽象数据类型定义
//查找ab子串
if (p->data==‘ a’ && p->next->data==‘b’)
{ p->data=‘x’; p->next->data=‘z’;
q=(LinkStrNode *)malloc(sizeof(LinkStrNode));
q->data=‘y’;
q->next=p->next; p->next=q;
s: a a a a b c d
t: a ab bac acb bc c ✓ 匹配成功 算法的思路是从s的每一个字符开始依次与t的 字符进行匹配。
4.2.1 Brute-Force算法
int BFIndex(SqString s,SqString t)
{ int i=0, j=0,k;
while (i<s.length && j<t.length)
4.1 串的类型定义 4.2 串的表示和实现 4.3 串的模式匹配算法
本章要求
理解： 1、串的基本概念、类型定义 2、串的存储表示和实现 3、串的KMP算法
掌握： 4、串的简单模式匹配算法(BF)
第4章 串的基本概念
串（或字符串）：是由零个或多个字符组成 的有限序列。
串的逻辑表示： S=“a1a2…ai…an”，其中S为 串名，ai (1≤i≤n)代表单个字符，可以是字母、 数字或其它字符(包括空白符)。 串值：双引号括起来的字符序列。双引号不是 串的内容，只起标识作用。

数据结构 判断题

数据结构 判断题

《数据结构》习题库之三：判断题1. 程序就是算法，但算法不一定是程序。

（）2. 线性表只能采用顺序存储结构或者链式存储结构。

（）3. 线性表的链式存储结构是通过指针来间接反映数据元素之间逻辑关系的。

（）4. 除插入和删除操作外，数组的主要操作还有存取、修改、检索和排序等。

（）5. 稀疏矩阵中0元素的分布有规律，因此可以采用三元组方法进行压缩存储。

（）6. 不管堆栈采用何种存储结构，只要堆栈不空，可以任意删除一个元素。

（）7. 确定串Ｔ在串Ｓ中首次出现的位置的操作称为串的模式匹配。

（）8. 深度为h的非空二叉树的第i层最多有2i-1 个结点。

（）9. 满二叉树就是完全二叉树。

（）10. 已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。

（）11. 非空二叉排序树的任意一棵子树也是二叉排序树。

（）12. 对一棵二叉排序树进行前序遍历一定可以得到一个按值有序的序列。

（）13. 若有向图G=(V,E)的拓扑序列不唯一，则图中必须有两条弧和。

（）14. 散列表的查找效率主要取决于所选择的散列函数与处理冲突的方法。

（）15. 序列初始为逆序时，泡排序法所进行的元素之间的比较次数最多。

（）16. 算法一定要有输入和输出。

（）17. 算法分析的目的旨在分析算法的效率以求改进算法。

（）18. 非空线性表中任意一个数据元素都有且仅有一个直接后继元素。

（）19. 数据的存储结构不仅有顺序存储结构和链式存储结构，还有索引结构与散列结构。

（）20. 线性链表中各个链结点之间的地址不一定要连续。

（）21. 若频繁地对线性表进行插入和删除操作，该线性表采用顺序存储结构更合适。

（）22. 若线性表采用顺序存储结构，每个数据元素占用4个存储单元，第12个数据元素的存储地址为144，则第1个数据元素的存储地址是101。

（）23. 若长度为n的线性表采用顺序存储结构，删除表的第i个元素之前需要移动表中n-i+1个元素。

（）24. 符号link(p)出现在表达式中表示p所指的那个结点的内容。

串的模式匹配算法


/* 在目标串s中找模式串t首次出现的位置，若不存在返回0。采用定长顺序
存储结构第二种方式存放串S和串T */
{
int i,j;
for(i=1,j=1;i<=s.length&&j<=t.length;)
{if(s.ch[i-1]==t.ch[j-1])
{i++;j++;}
/*字符比较成功，继续比较后续字符*/
设有两个串S和T，其中： S="s1s2s3…sn" T="t1t2t3…tm"（1≤m≤n，通常有m＜n）
模式匹配算法的基本思想是：用T中字符依次与S中 字符比较：从S中的第一个字符(i=1)和T中第一个字 符( j=1)开始比较，如果s1＝t1，则i和j各加1，继续 比较后续字符，若s1＝t1，s2＝t2，…，sm＝tm， 返回1；否则，一定存在某个整数j(1≤j≤m)使得si≠tj ，即第一趟匹配失败，一旦出现这种情况，立即中断 后面比较，将模式串T向右移动一个字符执行第二趟 匹配步骤，即用T中第一个字符( j=1)与S中的第2个字 符(i=2)开始依次比较；
数据结构
串的模式匹配算法
基本的模式匹配算法
子串定位操作又称为串的模式匹配(Pattern Matching)或串匹配，该操作是各种串处理系统中的 重要操作之一 。
子串定位操作是要在主串中找出一个与子串相同的 子串。一般将主串称为目标串，子串称之为模式串。 设S为目标串，T为模式串，把从目标串S中查找模式串 T的过程成为“模式匹配”。匹配的结果有两种：如果 S中有模式为T的子串，则返回该子串在S中的位置，若 S中有多个模式为T的子串时，则返回的是模式串T在S 中第一次出现的位置，这种情况称匹配成功；否则，称 为匹配失败。

数据结构——串


7
三、串的基本操作 C语言中常用的串运算 定义下列几个变量： char s1[20]=“dirtreeformat”,s2[20]=“file.mem”; char s3[30],*p; int result;
(1) 求串长(length) int strlen(char s); //求串的长度
例如：printf(“%d”,strlen(s1)); 输出13
char strcat(char s1 , char s2)
该函数将串s2复制到串s1的末尾，并且返回一 个指向串s1的开始处的指针。
例如：strcat(a3,”/”)
strcat(a3,a2);
2020//4//a143=“dirtreeformat/file.mem”
9
(4)串比较（compare)
A=“This is a string” B=“is” B在A中出现了两次，其中首次出现所对应的主串
位置是3。因此，称B在A中的序号（或位置）为3 特别地，空串是任意串的子串，任意串是其自身的子
串。
2020/4/14
5
二、串的抽象数据定义
• ADT String { • 数据对象:D={ai| ai
16
顺序串的类型定义和顺序表类似： typedef char ElemType;
typedef struct { ElemType ch[maxstrlen]; int length;
}sstring; //其优点是涉及到串长操作时速度快。
2020/4/14
17
4.2.2 堆分配存储表示
这种存储表示的特点是，仍以一组地址连续的存储单元存 放字符串序列，但它们的存储空间是在程序执行过程中动态 分配而得。所以也称为动态存储分配的顺序表。在C语言中， 利用malloc和realloc,free等动态存储管理函数，来根据实 际需要动态分配和释放字符数组空间。这样定义的顺序串类

数据结构教学中KMP算法解析

数据结构教学中KMP算法解析摘要：模式匹配是字符串的基本运算之一，也是数据结构教学中的难点之一。

分析了模式匹配KMP算法以及算法中next函数的含义，给出了next函数的两种实现方法，有助于在教学实践中帮助学生更好地理解该算法。

关键词：数据结构；模式匹配；KMP算法0引言模式匹配（Patten Matching）是许多计算机应用领域的基础问题，在数据结构中模式匹配是字符串的基本运算之一。

字符串模式匹配指的是，找出特定的模式串在一个较长的字符串中出现的位置。

有两个字符串S和T，字符串S称为目标串，字符串T称为模式串，要求找出模式T在S中的首次出现的位置。

一旦模式T在目标S中找到，就称发生一次匹配。

有些应用可能会要求找出所有的匹配位置<sup>[1]</sup>。

例如，目标串S= 'Shanghai'，模式串T= 'gha'，则匹配结果为4。

模式匹配的典型算法包括朴素匹配算法、KMP算法和BM算法等，其中KMP算法是效率较高且经典的模式匹配算法之一<sup>[2]</sup>。

在数据结构教学中，由于KMP算法较难理解，课堂讲授往往很难取得好的效果。

本文通过对传统的朴素匹配算法与KMP算法的比较，分析next函数的含义以及实现方法，来帮助理解KMP算法。

1朴素匹配算法在朴素匹配算法中，S和T分别为目标串和模式串，变量i和j 为两个静态指针，分别表示S和T中当前正待比较的字符位置。

算法的基本思想是：第1趟匹配：从S的第1个字符（序号为0）起和T的第一个字符比较之，如果相等，则继续逐个比较后续字符（i++；j++），否则开始下一趟匹配。

新的一趟匹配：i的初值为上一趟的初值+1 ，j的初值为1，如果比较结果相等，则继续逐个比较后续字符，否则开始下一趟匹配。

依次类推，直至某一趟匹配中，T的每个字符依次和S中的一个连续的字符序列相等，则称匹配成功，否则称匹配不成功。

数据结构实验报告-基于字符串模式匹配算法的病毒感染检测问题


《数据结构》实验报告
abcd abcde abc def
00 输出结果为：
YES
NO 四、分析过程
在主函数中利用键盘输入 human[ ]、virus[ ],即 cin>>human>>virus; ，输入时要注意模 式串 virus 的长度不要超过主串 human 的长度。
调用 BF 子函数，输入的两个实参会送到 BF 算法里进行比较，当比较次数小于各自的长 度 时 ， 开 始 匹 配 ， 即 while(i<strlen(human)&&j<strlen(virus)) 。 如 果 模 式 串 和 主 串 相 同 human[i]==virus[j]时，i 和 j 都要加 1，否则 i=i-j+1; j=0;。当 j 等于 virus 的长度时，说明匹 配成功，令输出返回值 1；否则返回值为 0。
实验时间 实验地点 指导教师
年月日 电气楼 308
实验项目
实验类别
实 验 目 的 及 要 求
基于字符串模式匹配算法的病毒感染检测问题
基础实验
实验学时
4 学时
实验目的： 1.掌握字符串的顺序存储表示方法 2.掌握字符串模式匹配算法 BF 算法或 KMP 算法的实现
实验要求： 输入多组数据，每组数据占 1 行，输入 0 0 时结束输入；每组数据输
BF 算法的基本思想是：从主串的第 pos 个字符起与模式串的第一个字符比较，若相等， 则继续逐个比较后续字符；否则从主串的下一个字符起再重新和模式串进行比较。直至模式 串中的每一个字符和主串中的一个连续字符序列相同，则称匹配成功，否则不成功。
（1）首先全局定义了两个一定长度的数组用来存储人类和病毒的 DNA，分别是 human[100] 和 virus[100]。分别用 i 和 j 来指示主串 human 和模式串 virus 当前正待比较的字符位置。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

数据结构—串的模式匹配
数据结构—串的模式匹配
1.介绍
串的模式匹配是计算机科学中的一个重要问题，用于在一个较长的字符串（称为主串）中查找一个较短的字符串（称为模式串）出现的位置。

本文档将详细介绍串的模式匹配算法及其实现。

2.算法一：暴力匹配法
暴力匹配法是最简单直观的一种模式匹配算法，它通过逐个比较主串和模式串的字符进行匹配。

具体步骤如下：
1.从主串的第一个字符开始，逐个比较主串和模式串的字符。

2.如果当前字符匹配成功，则比较下一个字符，直到模式串结束或出现不匹配的字符。

3.如果匹配成功，返回当前字符在主串中的位置，否则继续从主串的下一个位置开始匹配。

3.算法二：KMP匹配算法
KMP匹配算法是一种改进的模式匹配算法，它通过构建一个部分匹配表来减少不必要的比较次数。

具体步骤如下：
1.构建模式串的部分匹配表，即找出模式串中每个字符对应的最长公共前后缀长度。

2.从主串的第一个字符开始，逐个比较主串和模式串的字符。

3.如果当前字符匹配成功，则继续比较下一个字符。

4.如果当前字符不匹配，则根据部分匹配表的值调整模式串的位置，直到模式串移动到合适的位置。

4.算法三：Boyer-Moore匹配算法
Boyer-Moore匹配算法是一种高效的模式匹配算法，它通过利用模式串中的字符出现位置和不匹配字符进行跳跃式的匹配。

具体步骤如下：
1.构建一个坏字符规则表，记录模式串中每个字符出现的最后一个位置。

2.从主串的第一个字符开始，逐个比较主串和模式串的字符。

3.如果当前字符匹配成功，则继续比较下一个字符。

4.如果当前字符不匹配，则根据坏字符规则表的值调整模式串的位置，使模式串向后滑动。

5.算法四：Rabin-Karp匹配算法
Rabin-Karp匹配算法是一种基于哈希算法的模式匹配算法，它通过计算主串和模式串的哈希值进行匹配。

具体步骤如下：
1.计算模式串的哈希值。

2.从主串的第一个字符开始，逐个计算主串中与模式串长度相同的子串的哈希值。

3.如果当前子串的哈希值与模式串的哈希值相同，则进一步比较每个字符。

4.如果所有字符匹配成功，则返回当前子串在主串中的位置，否则继续计算下一个子串的哈希值。

附件
本文档未涉及附件。

法律名词及注释
暂无涉及法律名词及注释。