数据结构课设:基于字符串模式匹配算法的病毒感染检测问题

举报
是Dream呀 发表于 2022/07/30 22:26:33 2022/07/30
【摘要】 数据结构课设:基于字符串模式匹配算法的病毒感染检测问题

@TOC

一、Chapter One【实验题目】

1.【实验目的】

1.掌握字符串的顺序存储表示方法。
2.掌握字符串模式匹配算法BF算法或KMP算法的实现。

2.【实验内容】

问题描述
医学研究者最近发现了某些新病毒,通过对这些病毒的分析,得知它们的DNA序列都是环状的。现在研究者已收集了大量的病毒DNA和人的DNA数据,想快速检测出这些人是否感染了相应的病毒。为了方便研究,研究者将人的DNA和病毒DNA均表示成由一些字母组成的字符串序列,然后检测某种病毒DNA序列是否在患者的DNA序列中出现过,如果出现过,则此人感染了该病毒,否则没有感染。例如,假设病毒的DNA序列为baa,患者1的
DNA序列为aaabbba,则感染;患者2的 DNA序列为babbba,则未感染。(注意:人的
DNA序列是线性的,而病毒的DNA序列是环状的。)

输入要求
多组数据,每组数据有1行,为序列A和B,A对应病毒的DNA序列,B对应人的 DNA序列。A和B都为“0”时输入结束。
输出要求
对于每组数据输出1行,若患者感染了病毒输出“YES"”,否则输出“NO”。
输人样例

abbab abbabaab
baa cacdvcabacsd
abc def
0 0

输出样例

YES
YES
NO

3.【实验提示】

此实验内容即要求实现主教材的案例4.1,具体实现可参考算法4.5。算法4.5是利用BF算法来实现字符串的模式匹配过程的,效率较低,可以利用KMP算法完成模式匹配以提高算法的效率。读者可以模仿算法4.5,利用KMP算法来完成病毒感染检测的方案。

二、Chapter Two【实验分析】

1.实验整体思路:

在本题中,我们采用BF算法来实现对病毒检测问题的描述,本程序的难点是如何找出病毒DNA环状字符串的所有展开字符串。原理:首先要传递参数到int judge函数中,将字符串长度为n的病毒DNA扩展为长度为2n的字符串,再用双重循环输出长度为m的病毒展开字符串。调用BF函数进行模式匹配,返回判断结果到主函数中。
虑到程序需要输入输出多组数据,有两种方法可以实现:1、用二维数组进行字符串存储,并且同时进行字符串匹配,并将匹配结果输出。2、程序使用一维数组存储,在输入完一组数据后存储在缓存区内,然后将判断结果存入数组s中,最后根据数组s统一输出判断结果。本程序使用方法二。

实验详细步骤:

2.数据结构定义

定义全局变量数组V,D。
char V[20]; //病毒DNA数组
char D[20]; //人的DNA数组
定义标识符YES为1,标识符NO为0
#define YES 1
#define NO 0

3.主要功能模块设计

(1)int BFjudge()函数:
找出病毒DNA环状字符串的所有展开字符串,char D, char V:形参D是数组D,形参V是数组V。
(2)int BF()函数:
利用BF算法进行模式匹配char D, char :形参D是数组D,形参V是环状字符串的展开字符串。
(3)int PRINThand()函数:
输入多组数据,每输入一组数据就将匹配结果存进数组s中,最后统一输出检测结果。

4.主要步骤描述

(1)首先引用我们的头文件和需要的全局变量;
(2)然后用模式匹配函数BF,进行模式匹配;
(3)使用循环展开函数,将字符串长度为m的病毒DNA扩展为长度为2m的字符串;
(4)再创建输入函数,输入病毒DNA及人的DNA,程序使用一维数组存储,在输入完一组数据后存储在缓存区内,然后将判断结果存入数组s中,最后根据数组s统一输出判断结果。;
(5)最后通过主函数,调用我们之前已经构建好的函数,实现我们的判断功能,将结果进行输出。

三、Chapter Three【运行截图】

在这里插入图片描述

四、Chapter Four【源码详析】

#include <stdio.h> //头文件 
#include<iostream>
#include <string.h>
#define _CRT_SECURE_NO_WARNINGS
#define YES 1
#define NO  0

//全局变量部分
char V[20];  //病毒DNA字符串
char D[20];  //人的DNA字符串


//主要功能函数的具体实现及说明
//模式匹配函数(BF)
int BF(char *D, char *V)
{  //用BF算法进行模式匹配
    int i=0,j=0;
    while (i<strlen(D) && j<strlen(V))
{
    if (D[i]==V[j]) 
    {
        i++; j++;
}
	    else
	    {
             i = i-j+1;
             j = 0;
	    }
}
    if (j>=strlen(V)) return YES;
    else return NO;
}

//循环展开函数(BFjudge)
int BFjudge(char *D, char *V)
{
	int flag = 0;
	int i,j,m;
	char temp[20]; 
	m = strlen(V);
	for(i=m,j=0;j<m;j++)	V[i++]=V[j]; 
	V[2*m] = '\0';  //将字符串长度为m的病毒DNA扩展为长度为2m的字符串
	
	for(i=0; ;i++)
	{
	    for(j=0;j<m;j++)    temp[j] = V[i+j];   
	    temp[m] = '\0';  //循环展开环状病毒DNA
	    flag = BF(D,temp);  //调用BF模块进行模式匹配
	    if (flag) break;
	    else if (i>=m) return NO;  //所有展开字符串均匹配失败
	    else continue;
	 } 
	 return YES;
}

// 程序使用一维数组存储,在输入完一组数据后存储在缓存区内,
// 然后将判断结果存入数组s中,最后根据数组s统一输出判断结果。 
int PRINThand()
{
	FILE *fp1,*fp2;
    int i=0,k=0;
    int s[20]; 

    printf("\n请输入病毒DNA及人的DNA(输入0 0结束):\n");
	while(1)
    {			     
    	scanf("%s", &V[i]);
    	scanf("%s", &D[i]);	
    	if(V[i]=='0' && D[i]=='0') break;
    	
        if(BFjudge(D, V)==1) 	s[k]=1;
		else 	s[k]=0;
		k++;
    }
	printf("病毒感染检测输出结果:\n");
	for(k=0;s[k]<2;k++)
	{
		if(s[k]==1)	printf("YES\n");
	    else	printf("NO\n");
	} 
    return 0;
 }
 
 //主函数
int main()
{
	int key = 0, Num;
	while(1)
	{
	printf("欢迎使用病毒感染检测系统\n");
	PRINThand(); break;
	}
} 
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。