KMP 算法课设代码(含完整注释)

设计内容

打开一篇英文文章,在该文章中找出所有给定的单词,然后对所有给定的单词替换为另外一个单词,再存盘。

实现思路

简单的界面设计就不去阐述了,代码方法写的很分明。

算法的核心是串的查找和替换,我运用 kmp 算法对串进行查找操作,这个算法是整个代码最重要的地方,kmp 算法的讲解可以百度其他大神的博客,我就不献丑了。因为给定单词在一篇文章中不一定只出现一次,所以我改良了经典的算法步骤,使算法可以以数组形式返回所有匹配成功位置。

在字符串的替换问题上,有多种情况,详细可见 char* replace(char* address,char* s,char* p,char* q) 函数。

源代码

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define max 10000
int next[max];  // kmp算法中的next数组
int T[max];  // 保存匹配字符串的下标集

void UI();  // 主用户界面
void return_UI();  // 返回操作界面
void search_UI();  // 字符串查找界面
void replace_UI();  // 字符串替换界面
void inputWordString_UI();  // 输入文本串UI,将文本串保存到 word.txt文件中
int exitInterface_UI();  // 询问用户是否退出
void getNext(char* p, int next[]);  // 得到模式串next数组
int search(char* s, char* p);  // 子字符串查找函数,得到文本串中与模式串所有匹配的下标集T,无匹配则将T[0] = -1
char* replace(char* address,char* s,char* p,char* q);  // 字符串替换函数
char* readFile(char* address);  // 读取文件 
void writeFile(char* address, char* str);  // 写入文件

/*
main: 主函数 
*/
int main() {
	UI();
	return 0;
}

/*
UI: 主用户界面
无参数 
无返回值 
*/
void UI() {
	char* str = readFile("word.txt");
	printf("\t\t欢迎使用\n\
	字符串查找与替换程序\n\
	请输入命令(数字):\n\
	1.字符串的查找;\n\
	2.字符串替换;\n\
	3.输入文本串;\n\
	4.结束程序。\n\
	");
	printf("默认文本串为:%s \n\t",str);
	int state = 1;  // 状态(0为异常,1为正常, 2为结束)
	while (state < 2) {
		int operate;  // 操作命令
		scanf("%d", &operate);
		if (operate == 1) {  					// 字符串的查找
			search_UI();
			printf("\n\t字符串查找操作完成\n");
			return_UI();
			UI();
		} else if (operate == 2) {  			// 字符串的替换
			replace_UI();
			printf("\n\t字符串替换操作完成\n");
			return_UI();
			UI();
		} else if (operate == 3) {				// 输入文本串 
			inputWordString_UI();
			return_UI();
			UI();
		} else if (operate == 4) {				// 退出系统 
			state = exitInterface_UI();
			if (state == 2) {
				printf("\t\t谢谢使用\n");
				exit(0);
			} else {
				UI();
			}
		} else {  								// 处理输入错误
			printf("输入错误,请重新输入。\n");
			state = 0;
		}
	}
}

/*
return_UI: 返回操作界面
无参数
无返回值 
*/
void return_UI() {
	printf("\t------------------------\n");
	printf("\t按任意键返回\n");
	getch();
	system("cls");
} 

/*
search_UI: 字符串查找界面
无参数 
无返回值 
*/
void search_UI() {
	char* p;  						 // 子串
	p = (char*)malloc(sizeof(char)*max);
	printf("请输入要查找的子串:");
	scanf("%s",p);
	char* s = readFile("word.txt");  // 文本串
	int n = search(s, p);  			 // 得到匹配总数,匹配位置下标集为 T
	printf("\n文本串中共用%d个位置与子串相同。", n);
	printf("分别为:");
	int i;
	for (i = 0; i < n; i++) {
		printf("%d ",T[i]+1);
	}
	printf("\n");
}

/*
replace_UI: 字符串替换界面
无参数 
无返回值 
*/
void replace_UI() {
	char* str = readFile("word.txt");  		// 文本串 
	char* p = (char*)malloc(sizeof(char));  // 被替换的子串 
	char* q = (char*)malloc(sizeof(char));  // 替换后的子串 
	printf("请输入要被替换的子串:");
	scanf("%s",p);
	printf("请输入替换后的子串:");
	scanf("%s",q);
	int n = search(str,p);  // 得到 n、T
	if (n == 0) {
		printf("\n\t无法替换字符串,因为文本串中无被替换子串。\n");
	} else {
		str = replace("word.txt",str,p,q); // 替换并更新文本串 
		printf("\n\t子串替换成功!\n\t当前文本串为:");
		printf("%s\n",str); 
	}
} 

/*
inputWordString_UI: 输入文本串UI,将文本串保存到 word.txt文件中 
无参数
无返回值 
*/
void inputWordString_UI() {
	char* str;
	str = (char*)malloc(sizeof(char)*max);
	printf("请输入文本串: ");
	getchar();
	gets(str);
	getchar();
	writeFile("word.txt",str);
}

/*
exitInterface_UI:询问用户是否退出
无参数 
返回值(int):1:不退出;2:退出
*/
int exitInterface_UI() {
	int operate;
	printf("\t是否退出程序?\n\
	选是请输入1,选否请输入0\n\
	");
	scanf("%d", &operate);
	if (operate == 1) {
		return 2;  // 退出程序,state状态为2(结束)
	} else if (operate == 0) {
		return 1;  // 保存程序运行,state状态为1(正常)
	} else {
		printf("输入错误,请重新输入!\n");
		return exitInterface_UI();
	}
}

/*
getNext: 得到模式串next数组
参数: char* p: 模式串; int next[]: kmp算法所需next数组
无返回值 
*/
void getNext(char* p,int next[]) { 
	int pLen = strlen(p);
	next[0] = -1; 
	int k = -1;
	int j = 0;
	while (j < pLen -1) {
		if (k == -1 || p[j] == p[k]) {
			++k;
			++j;
			next[j] = k;
		} else {
			k = next[k];
		}
	}
}

/*
search: 子字符串查找函数,得到文本串中与模式串所有匹配的下标集T,无匹配则将T[0] = -1
参数: char* s: 文本串;char* p: 模式串
返回值 int n : 所有匹配下标的总数 
*/
int search(char* s, char* p) {
	getNext(p, next);
	int i = 0;
	int j = 0;
	int n = 0;
	int sLen = strlen(s);
	int pLen = strlen(p);
	while (i < sLen && j < pLen) {
		if (j == -1 || s[i] == p[j]) {
			++i;
			++j;
		} else {
			j = next[j];
		}

		if (j == pLen - 1 && s[i] == p[j]) {  // 判断是否完全匹配,并为 T 赋值
			T[n++] = i - j;
			j = next[j];  // 匹配成功则初始化 j 
		}
	}
	if (n == 0) {
		T[0] = -1;
	}
	
	return n; 
}

/*
replace: 字符串替换函数
参数: char* address : 文本串的保存路径, char* s : 文本串, char* p : 被替换子串, char* q : 替换子串 
返回值 char* s : 替换后的文本串 
*/
char* replace(char* address,char* s,char* p,char* q) {
	int sLen = strlen(s);
	int pLen = strlen(p);
	int qLen = strlen(q);
	int x,y,i,j;
	int t = 0; // 计数 
	int m = qLen - pLen;  // 替换子串与被替换子串的长度差 
	for (x = 0,y = 0; x < sLen; x++) {   // 遍历所有位置 
		if (x == T[y] + t * m){  // 找到可以匹配的位置 
			++y;
			++t;
			if (pLen < qLen) {						  // 如果被替换子串长度小于替换子串
				for (i = sLen - 1 + (t-1) * m; i > x + pLen - 1; i--) {	 	// 则向后位移文本串x + pLen 位置后的字符,位移量为 m(正), 从后向前遍历 
					s[i + m] = s[i];
				}
				for (i = x, j = 0; i < x + qLen; i++, j++) {
					s[i] = q[j];
				} 
			} else if (pLen > qLen) {				 // 如果被替换子串长度小于替换子串
				for (i = x + qLen - m; i < sLen + (t-1) * m; i++) {	 // 则向前位移文本串x + qLen 位置后的字符,位移量为 m(负), 从前向后遍历 
					s[i + m] = s[i];
				}
				for (i = sLen + t * m, j = 0; j < -m; j++) {
					s[i+j] = '\0';
				}
				for (i = x, j = 0; i < x + qLen; i++, j++) {
					s[i] = q[j];
				}
			} else {								// 如果被替换子串长度等于替换子串
				for (i = x, j = 0; i < x + qLen; i++, j++) {
					s[i] = q[j];
				}
			}
		}
	}
	writeFile(address,s);
	return s;
}

/*
readFile: 读取文件
参数 char* address : 文件地址值
返回值 char* :字符串指针 
*/
char* readFile(char* address) { 
	FILE* fp;
	if ((fp = fopen(address,"rb")) == NULL) {
		fopen(address,"wb");
	}
	char str1[max];
	if (fgets(str1,max,fp) == NULL){
		str1[0] = NULL;
	}
	fclose(fp);  // 关闭文件 
	char* str;
	str = (char*)malloc(sizeof(char)*max);  // 为str分配内存 
	strcpy(str,str1);
	return str;
}

/*
writeFile: 写入文件
参数 char* address : 文件地址值 ;char* str : 要写入的字符串
无返回值 
*/
void writeFile(char* address,char* str) {
	FILE* fp;
	if ((fp = fopen(address,"wb")) == NULL) {
		printf("文件打开错误\n");
		exit(0);
	}
	fputs(str,fp);
	fclose(fp);
}  

我是 MX,喜欢我文章的记得常来哦