一、Chapter One【實驗題目】

1.【實驗目的】

1．掌握字符串的順序存儲表示方法。
2．掌握字符串模式匹配算法BF算法或KMP算法的實現(xiàn)。

2.【實驗內(nèi)容】

問題描述
醫(yī)學研究者最近發(fā)現(xiàn)了某些新病毒，通過對這些病毒的分析，得知它們的DNA序列都是環(huán)狀的?，F(xiàn)在研究者已收集了大量的病毒DNA和人的DNA數(shù)據(jù)，想快速檢測出這些人是否感染了相應的病毒。為了方便研究，研究者將人的DNA和病毒DNA均表示成由一些字母組成的字符串序列，然后檢測某種病毒DNA序列是否在患者的DNA序列中出現(xiàn)過，如果出現(xiàn)過，則此人感染了該病毒，否則沒有感染。例如，假設病毒的DNA序列為baa，患者1的
DNA序列為aaabbba,則感染;患者2的 DNA序列為babbba，則未感染。(注意：人的
DNA序列是線性的，而病毒的DNA序列是環(huán)狀的。)

輸入要求
多組數(shù)據(jù)，每組數(shù)據(jù)有1行，為序列A和B，A對應病毒的DNA序列，B對應人的 DNA序列。A和B都為“0”時輸入結(jié)束。
輸出要求
對于每組數(shù)據(jù)輸出1行，若患者感染了病毒輸出“YES"”，否則輸出“NO”。
輸人樣例

abbab abbabaab
baa cacdvcabacsd
abc def
0 0

輸出樣例

YES
YES
NO

3.【實驗提示】

此實驗內(nèi)容即要求實現(xiàn)主教材的案例4.1，具體實現(xiàn)可參考算法4.5。算法4.5是利用BF算法來實現(xiàn)字符串的模式匹配過程的，效率較低，可以利用KMP算法完成模式匹配以提高算法的效率。讀者可以模仿算法4.5，利用KMP算法來完成病毒感染檢測的方案。

二、Chapter Two【實驗分析】

1.實驗整體思路：

在本題中，我們采用BF算法來實現(xiàn)對病毒檢測問題的描述，本程序的難點是如何找出病毒DNA環(huán)狀字符串的所有展開字符串。原理：首先要傳遞參數(shù)到int judge函數(shù)中，將字符串長度為n的病毒DNA擴展為長度為2n的字符串，再用雙重循環(huán)輸出長度為m的病毒展開字符串。調(diào)用BF函數(shù)進行模式匹配，返回判斷結(jié)果到主函數(shù)中。
慮到程序需要輸入輸出多組數(shù)據(jù)，有兩種方法可以實現(xiàn)：1、用二維數(shù)組進行字符串存儲，并且同時進行字符串匹配，并將匹配結(jié)果輸出。2、程序使用一維數(shù)組存儲，在輸入完一組數(shù)據(jù)后存儲在緩存區(qū)內(nèi)，然后將判斷結(jié)果存入數(shù)組s中，最后根據(jù)數(shù)組s統(tǒng)一輸出判斷結(jié)果。本程序使用方法二。

實驗詳細步驟：

2.數(shù)據(jù)結(jié)構(gòu)定義

定義全局變量數(shù)組V,D。
char V[20]; //病毒DNA數(shù)組
char D[20]; //人的DNA數(shù)組
定義標識符YES為1，標識符NO為0
#define YES 1
#define NO 0

3.主要功能模塊設計

（1）int BFjudge()函數(shù)：
找出病毒DNA環(huán)狀字符串的所有展開字符串，char D, char V：形參D是數(shù)組D，形參V是數(shù)組V。
（2）int BF()函數(shù)：
利用BF算法進行模式匹配char D, char ：形參D是數(shù)組D，形參V是環(huán)狀字符串的展開字符串。
（3）int PRINThand()函數(shù)：
輸入多組數(shù)據(jù)，每輸入一組數(shù)據(jù)就將匹配結(jié)果存進數(shù)組s中，最后統(tǒng)一輸出檢測結(jié)果。

4.主要步驟描述

（1）首先引用我們的頭文件和需要的全局變量；
（2）然后用模式匹配函數(shù)BF，進行模式匹配；
（3）使用循環(huán)展開函數(shù)，將字符串長度為m的病毒DNA擴展為長度為2m的字符串；
（4）再創(chuàng)建輸入函數(shù)，輸入病毒DNA及人的DNA，程序使用一維數(shù)組存儲，在輸入完一組數(shù)據(jù)后存儲在緩存區(qū)內(nèi)，然后將判斷結(jié)果存入數(shù)組s中，最后根據(jù)數(shù)組s統(tǒng)一輸出判斷結(jié)果。；
（5）最后通過主函數(shù)，調(diào)用我們之前已經(jīng)構(gòu)建好的函數(shù)，實現(xiàn)我們的判斷功能，將結(jié)果進行輸出。

三、Chapter Three【運行截圖】

文章來源地址http://www.zghlxwxcb.cn/news/detail-426580.html

四、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字符串


//主要功能函數(shù)的具體實現(xiàn)及說明
//模式匹配函數(shù)(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;
}

//循環(huán)展開函數(shù)（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';  //循環(huán)展開環(huán)狀病毒DNA
	    flag = BF(D,temp);  //調(diào)用BF模塊進行模式匹配
	    if (flag) break;
	    else if (i>=m) return NO;  //所有展開字符串均匹配失敗
	    else continue;
	 } 
	 return YES;
}

// 程序使用一維數(shù)組存儲，在輸入完一組數(shù)據(jù)后存儲在緩存區(qū)內(nèi)，
// 然后將判斷結(jié)果存入數(shù)組s中，最后根據(jù)數(shù)組s統(tǒng)一輸出判斷結(jié)果。 
int PRINThand()
{
	FILE *fp1,*fp2;
    int i=0,k=0;
    int s[20]; 

    printf("\n請輸入病毒DNA及人的DNA（輸入0 0結(jié)束）：\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("病毒感染檢測輸出結(jié)果：\n");
	for(k=0;s[k]<2;k++)
	{
		if(s[k]==1)	printf("YES\n");
	    else	printf("NO\n");
	} 
    return 0;
 }
 
 //主函數(shù)
int main()
{
	int key = 0, Num;
	while(1)
	{
	printf("歡迎使用病毒感染檢測系統(tǒng)\n");
	PRINThand(); break;
	}
} 

到了這里，關于數(shù)據(jù)結(jié)構(gòu)課設：基于字符串模式匹配算法的病毒感染檢測問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！