字符过滤系统简介:由用户给定一串字符文本和要查询的字符或者字符串,要求系统能够自动检测出该字符或字符串在文本中的位置,同时系统中需设有全部替换功能,
必要时将文本中的所有查询到的字符替换成指定字符。 项目实例 例如在字符串文本 “abcabc” 中检测是否含有字符 ‘a’ 时,字符过滤系统应反馈给用户该字符存储于文本中的位置,即 1 和4,同时询问用户是否将所有的
字符 ‘a’ 替换成其它指定字符,假设用户指定字符 ‘a’ 全部转换成字符 ‘d’,系统应将替换后的字符串 “dbcdbc” 反馈给用户。 设计思路 字符过滤系统的设计,其主要功能的实现主要分为两部分:字符串的模式匹配和字符串的替换。有关字符串的模式匹配算法,可以选择 BF 算法或是 KMP 算法, 和之前所接触的算法不同的是,系统是要将文本中所有与指定字符相同的都筛选出来,而不是找出一个就结束。不过换汤不换药,只要在前面的学习中领会了
模式匹配的思想,就可以轻松解决该问题。 在实现字符串的替换功能时,没有成型的算法,需要自己设计方案去编码实现。本节有提供了一种实现的思路,建议大家先自己思考,试着独立解决,培养自己
的编程解题思路,若实在不会了再借鉴本节给的思路。
完整实现代码
#include <stdio.h> #include <stdlib.h> #include <string.h> #define SIZE 1000
//KMP算法中的next数组 void Next(char *T, int *next)
{ int i=1; next[1]=0; int j=0; while (i<strlen(T))
{ if (j==0 || T[i-1]==T[j-1])
{ i++; j++; if (T[i-1] != T[j-1])
{ next[i] = j; } else
{ next[i] = next[j]; } }
else
{ j = next[j]; } } }
//KMP算法(快速模式匹配)实现函数 void KMP(char *S, char *T, int (*a)[], int *number)
{ int next[10]; Next(T, next); //根据模式串T,初始化next数组 int i = 1; int j = 1; *number = 0; while (i <= strlen(S))
{ if (j==0 || S[i-1]==T[j-1])
{ i++; j++; }
else
{ j = next[j]; } if (j>strlen(T))
{ (*number)++; (*a)[(*number)] = i-(int)strlen(T); j = 0; i--; } } }
//字符串替换算法,oldData:原字符串,selectData要替换掉的字符串,数组 a 存储的是需替换字符在原字符串中的首地址,number表示数组 a 的长度,newData用于存储新字符串,replace为替换的新字符 void replaceData(char *oldData, int *a, int number, char *replace, char *selectData, char *newData)
{ int order = 0; //表示newData存储字符的位置 int begin = 0; for (int i=1; i<=number; i++)
{ //先将替换位置之前的字符完整的复制到新字符串数组中 for (int j=begin; j<a[i]-1; j++)
{ newData[order] = oldData[j]; order++; } //替换字符,用新字符代替 for (int k=0; k<strlen(replace); k++)
{ newData[order] = replace[k]; order++; } //代替完成后,计算出原字符串中隔过该字符串的下一个起始位置 begin = a[i] + (int)strlen(selectData)-1; } //要替换位置全部替换完成后,检测是否还有后续字符,若有直接复制 while(begin < strlen(oldData))
{ newData[order] = oldData[begin]; order++; begin++; } }
int main()
{ while (1)
{ printf("字符过滤检测系统启动(S),关闭(O),请选择:\n"); char s; char oldData[SIZE]; char selectData[SIZE]; char replace[SIZE]; char judge; char *newData = (char*)malloc(SIZE*sizeof(char)); FILE *out; scanf("%c", &s); getchar(); if (s == 'O')
{ break; }
else
{ printf("请输入原字符串:\n"); scanf("%[^\n]", oldData); getchar(); //用于承接缓冲区冲的换行符 printf("输入要查找的字符或字符串:\n"); while (scanf("%s", selectData))
{ getchar(); int a[SIZE], number; KMP(oldData, selectData, &a, &number); if (number == 0)
{ printf("未检测到文章中有该字符串!是否重新输入(Y/N):\n"); scanf("%c", &judge); getchar(); if (judge == 'N')
{ break; }
else
{ printf("输入要查找的字符或字符串:\n"); } }
else
{ printf("系统检测到该字符在原字符串中出现 %d 次,起始位置依次是:\n", number); for (int i=1; i<=number; i++)
{ printf("%d ", a[i]); } printf("\n"); printf("是否使用新字符串替换所有的 %s(Y/N)\n", selectData); scanf("%c", &judge); getchar(); if (judge == 'Y')
{ printf("请输入用于替换的字符串:\n"); scanf("%[^\n]", replace); getchar(); replaceData(oldData, a, number, replace, selectData, newData); printf("新生成的字符串为: %s\n", newData); if((out=fopen("new.txt", "wr")) == NULL)
{ printf("新生成的字符串为%s,写入文件失败", newData); } if(fputs(newData, out))
{ printf("已将新字符串写入new.txt文件中\n"); } free(newData); fclose(out); } break; } } } }
return 0; }
运行结果: 字符过滤检测系统启动(S),关闭(O),请选择: S 请输入原字符串: hello world! 输入要查找的字符或字符串: ! 系统检测到该字符在原字符串中出现 1 次,起始位置依次是: 12 是否使用新字符串替换所有的 !(Y/N) Y 请输入用于替换的字符串: ,I love you! 新生成的字符串为: hello world,I love you! 已将新字符串写入new.txt文件中 字符过滤检测系统启动(S),关闭(O),请选择: O