数据结构与算法教程，数据结构C语言版教程！（第四部分、字符串，数据结构中的串存储结构）四

第四部分、字符串，数据结构中的串存储结构

串存储结构，也就是存储字符串的数据结构。

很明显，字符串之间的逻辑关系也是“一对一”，用线性表的思维不难想出，串存储结构也有顺序存储和链式存储。

提到字符串，常做的操作就是串之间的匹配，因为，本章给初学者介绍 2 种串的模式匹配算法，BF 算法和 KMP 算法。

七、[数据结构实践项目]字符过滤系统]

字符过滤系统简介：由用户给定一串字符文本和要查询的字符或者字符串，要求系统能够自动检测出该字符或字符串在文本中的位置，同时系统中需设有全部替换功能，必要时将文本中的所有查询到的字符替换成指定字符。

1、项目实例

例如在字符串文本 “abcabc” 中检测是否含有字符 ‘a’ 时，字符过滤系统应反馈给用户该字符存储于文本中的位置，即 1 和4，同时询问用户是否将所有的字符 ‘a’ 替换成其它指定字符，假设用户指定字符 ‘a’ 全部转换成字符 ‘d’，系统应将替换后的字符串 “dbcdbc” 反馈给用户。

2、设计思路

字符过滤系统的设计，其主要功能的实现主要分为两部分：字符串的模式匹配和字符串的替换。有关字符串的模式匹配算法，可以选择 BF 算法或是 KMP 算法，

和之前所接触的算法不同的是，系统是要将文本中所有与指定字符相同的都筛选出来，而不是找出一个就结束。不过换汤不换药，只要在前面的学习中领会了模式匹配的思想，就可以轻松解决该问题。

在实现字符串的替换功能时，没有成型的算法，需要自己设计方案去编码实现。本节有提供了一种实现的思路，建议大家先自己思考，试着独立解决，培养自己的编程解题思路，若实在不会了再借鉴本节给的思路。

3、完整实现代码

#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)) { i

????????????????f (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