数据结构课程设计：病毒感染检测问题
目录
一、问题分析
本课题的内容是关于病毒感染检测即DNA序列匹配的问题，具体是通过实现KMP（Knuth-Morris-Pratt）算法来检测一个人的DNA序列中是否包含某种病毒的DNA序列。从需求上来说，最终需要完成的功能是：输入一个人的DNA序列和一种病毒的DNA序列，通过KMP字符串匹配算法判断人的DNA序列中是否包含病毒的DNA序列，并给出相应的提示信息。如果包含，则提示用户已感染病毒；如果不包含，则提示用户未感染病毒并提醒注意防护。
二、总体设计
1.输入模块：负责接收用户输入的人DNA序列和病毒DNA序列。
2.处理模块：使用KMP算法进行字符串匹配。
3.输出模块：根据匹配结果输出相应的信息，并在匹配成功时触发报警。
4.功能设计：
用户界面：提供一个简单的菜单，允许用户选择开始运行、再次运行或退出程序。
字符串处理：实现字符串的赋值、KMP算法以及用于KMP算法的nextval表计算。
报警功能：在检测到病毒感染时，通过蜂鸣器声音提示用户
5.流程图：
三、详细设计
1.数据结构：
SString：用于存储字符串及其长度，包含一个字符数组str和一个整数length。
2.功能实现：
StrAssign：将输入的字符数组赋值给SString结构体的字符数组，并计算长度。
NextVal：计算KMP算法中需要的nextval表，用于优化匹配过程。
KMP：实现KMP字符串匹配算法，返回匹配成功的位置或0（匹配失败）。
Beep：实现报警功能，通过蜂鸣器声音提示用户。
3.算法及思路：
KMP算法：通过预处理模式串（病毒DNA序列）生成nextval表，在匹配过程中利用nextval表跳过不必要的比较，从而提高匹配效率。
报警功能：使用Windows API函数Beep和Sleep实现蜂鸣器声音，并通过_kbhit和_getch函数检测用户是否按下了回车键以停止报警。
四、个性功能介绍
1.Beep报警功能：
当检测到病毒DNA时，系统会发出报警声，并提示用户按回车键停止报警。这一功能通过Beep函数实现，使用了Windows API中的Beep函数和Sleep函数来控制报警声的频率和持续时间。
2.用户交互菜单：
系统提供了一个简单的用户交互菜单，用户可以通过输入数字来选择是否运行检测或退出程序。这一功能通过main函数中的循环和条件判断实现，提高了系统的灵活性和易用性。
3.输入处理：
在读取用户输入的DNA序列时，系统使用了fgets函数来替代gets函数，以避免潜在的缓冲区溢出问题。同时，系统还通过strcspn函数去除了输入字符串中的换行符，确保字符串的正确处理。
五、实现部分
1.字符串赋值（StrAssign）
功能：将C风格的字符串（const char* chars）赋值给自定义的字符串结构（SString）。
实现：遍历输入的字符串，将其字符逐个复制到SString的str数组中，并设置字符串长度length。
2.计算nextval数组（NextVal）
功能：为KMP算法生成必要的nextval数组，用于在匹配失败时快速跳过不必要的比较。
实现：基于KMP算法的原理，通过迭代计算每个位置的nextval值，这些值表示在匹配失败时应该回退到的位置。
3.KMP字符串匹配（KMP）
功能：使用KMP算法在文本字符串（S）中搜索模式字符串（T）。
实现：利用nextval数组，在匹配失败时快速回退到正确的位置，继续匹配过程。如果找到匹配，返回匹配起始位置；否则返回0。
4.报警函数（Beep）
功能：在检测到病毒感染时发出报警声，直到用户按下回车键停止。
实现：使用Windows API的Beep函数发出声音，使用Sleep函数控制声音间隔，使用_kbhit和_getch函数检测用户输入。
5.DNA检测函数（DNA）
功能：获取用户输入的人DNA序列和病毒DNA序列，使用KMP算法进行匹配，并根据匹配结果输出相应信息。
实现：使用fgets函数获取用户输入，注意处理换行符。调用StrAssign函数将输入转换为SString结构，然后调用KMP函数进行匹配。根据匹配结果，输出未感染或感染的信息，并在感染时调用Beep函数发出报警。
6.主函数（main）
功能：提供用户交互界面，允许用户选择开始运行、再次运行或退出程序。
实现：使用while循环不断获取用户输入，根据输入调用DNA函数或退出程序。注意使用getchar函数清除输入缓冲区中的换行符，以避免影响后续输入。
六、程序运行结果
开始运行：
输入：1
输入人的DNA序列：123456789
输入病毒的DNA序列：456
此时显示
“你已感染病毒，病毒DNA在主DNA的位置为：4”
同时电脑开始发出报警的蜂鸣声
点击回车键停止报警
再次返回主菜单
输入2继续运行
输入人的DNA序列：asdfghjkl
输入病毒的DNA序列：abc
显示
“恭喜你，你没有感染病毒！请注意防护。”
并再次返回主菜单
输入：0
退出程序
七、课程设计小结
本次课程设计是一次非常宝贵的学习和实践机会。在整个过程中，我深刻体会到了理论与实践相结合的重要性，也收获了许多宝贵的经验和知识。
在课程设计的初期，我首先对所学知识进行了系统的回顾和整理，明确了设计的目标和要求。通过查阅相关资料和文献，我对设计内容有了更深入的了解，为后续的设计工作打下了坚实的基础。
在设计过程中，我遇到了不少挑战和困难。但通过不断尝试和修改，我不仅掌握了更多的设计技巧和方法，还培养了解决问题的能力。
在本次课设中，我深入学习到了深入理解字符串处理，通过实现串的赋值（StrAssign函数）和字符串匹配算法（KMP算法），加深了对字符串处理和数据结构（如结构体SString的使用）的理解。
同时掌握了KMP算法，成功实现了KMP算法，包括计算nextval数组和进行字符串匹配。这一过程中，不仅理解了KMP算法的原理，还学会了如何在实际编程中应用该算法。
还增强编程实践能力，通过编写完整的程序，包括用户输入处理、函数调用和结果输出等，增强了编程实践能力和代码组织能力。
了解错误处理和用户交互，在程序中加入了错误处理和用户交互功能，如处理无效输入和提示用户输入等，提高了程序的健壮性和用户体验。
总的来说，这次课程设计不仅提升了我的专业技能和实践能力，还让我更加清晰地认识到了自己的优势和不足。我相信在未来的学习和工作中，我会继续努力，不断进步，为实现自己的目标和梦想而奋斗。同时，我非常感谢老师的指导和帮助，让我能够顺利完成这次课程设计。
八、附录：课设源码
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <windows.h>
#include <conio.h>
using namespace std;
#define ERROR 0
#define OK 1
#define OVERFLOW -2
#define MAX 50
typedef int Status;
typedef struct
{
char str[MAX + 1];
int length;
} SString;
Status StrAssign(SString& S, const char* chars)
{
int l = strlen(chars);
for (int i = 0; i < l; i++)
S.str[i] = chars[i];
S.str[l] = '\0';
S.length = l;
return OK;
}
// 计算KMP算法中需要的nextval数组
void NextVal(const SString& T, int nextval[])
{
int m = T.length;
int k = -1;
nextval[0] = -1; //nextval[0]赋值为-1
for (int j = 1; j < m; ++j) // j为数组上标从1开始
{
while (k >= 0 && T.str[k + 1] != T.str[j])
k = nextval[k];
if (T.str[k + 1] == T.str[j])
++k;
nextval[j] = (T.str[k + 1] == T.str[j] ? nextval[j] : k);
}
}
// 实现KMP字符串匹配算法
int KMP(const SString& S, const SString& T)
{
int nextval[MAX];
NextVal(T, nextval);
int i = 0, j = 0;
while (i < S.length)
{
if (j == -1 || S.str[i] == T.str[j])
{
++i;
++j;
}
else
{
j = nextval[j];
}
if (j == T.length)
{
return i - j + 1; // 匹配成功，返回起始位置（从1开始计数）
}
}
return 0; // 匹配失败
}
// 防止有人感染后瞒报，设置报警器，字符串匹配成功后自动报警
int Beep() {
int Beeping = 3;
printf("按回车键停止报警：\n ");
while (Beeping)
{
Beep(750, 300);
Sleep(1000);
// 检查是否有键盘输入（不阻塞）
if (_kbhit())
{
char ch = _getch();
if (ch == '\r') // 检查是否是回车键（ASCII码为13，即\r）
{
Beeping = 0;
}
}
}
printf("报警已关闭！\n");
return 0;
}
void DNA(void)
{
SString S, T;
char chars[MAX + 2];
printf("\n请输入人的DNA序列: ");
fgets(chars, MAX + 2, stdin); // 使用fgets代替gets_s，注意处理换行符
chars[strcspn(chars, "\n")] = 0; // 去除换行符
StrAssign(S, chars);
printf("请输入病毒的DNA序列: ");
fgets(chars, MAX + 2, stdin);
chars[strcspn(chars, "\n")] = 0;
StrAssign(T, chars);
int position = KMP(S, T);
if (position == 0)
{
printf("恭喜你，你没有感染病毒!请注意防护。\n");
}
else
{
printf("你已感染病毒，病毒DNA在主DNA中的位置为: %d\n", position);
printf("你已感染病毒，请配合工作人员进行隔离和治疗!\n");
Beep();
}
}
int main()
{
int choice;
printf("————————病毒感染检测————————\n");
printf("输入1开始运行\n");
printf("输入2再次运行\n");
printf("输入0退出运行\n");
printf("请输入：");
while (1)
{
scanf_s("%d", &choice);
getchar(); // 清除输入缓冲区中的换行符
if (choice == 0)
{
printf("程序退出。\n");
break;
}
else if (choice == 1 || choice == 2)
{
DNA();
}
else
{
printf("无效输入，请重新输入。\n");
}
printf("\n————————病毒感染检测————————\n");
printf("输入1开始运行\n");
printf("输入2再次运行\n");
printf("输入0退出运行\n");
printf("请输入：");
}
return 0;
}更多推荐
21
0- 0
已为社区贡献1条内容
所有评论(0)