数据结构课设：基于字符串模式匹配算法的感染检测问题
source link: https://blog.51cto.com/u_15492594/5607454
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
本文目录：
一、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;
}
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK