数据结构-串模式匹配与文本检索
串模式匹配算法的设计与实现
#define MaxStrSize 256 //根据用户需要自己定义大小
typedef struct
{
char ch[MaxStrSize]; //ch是一个可容纳256个字符的字符数组
int length;
} SString; //定义顺序串类型
#include<stdio.h>
#include<string.h>
/**********************************/
/* 朴素模式匹配 */
/**********************************/
int Index(SString S,SString T)
{
//求子串T在主串S中首次出现的位置
int i,j,k,m,n;
m=T.length; //模式串长度赋m
n=S.length; //目标串长度赋n
for(i=0;i<n-m;i++)
{
j=0;
k=i; //目标串起始位置i送入k
while(j<=m && S.ch[k]==T.ch[j])
{
k++;
j++; //继续下一个子符的比较
}
if(j==m) //若相等，则说明找到匹配的子串，返回匹配位置i
return i; //否则从下一个位置重新开始比较
}
return -1;
}
/**********************************/
/* 给定位置的串匹配 */
/**********************************/
int PartPosition(SString s1,SString s2,int k)
{
int i,j;
i=k-1; //扫描s1的下标，因为c中数组下标是从0开始，串中序号相差1
j=0; //扫描s2的开始下标
while(i<s1.length && j<s2.length)
if(s1.ch[i]==s2.ch[j])
{
i++;
j++; //继续使下标移向下一个字符位置
}
else
{
i=i-j+1; //使i下标回溯到原位置的下一个位置
j=0; //使j指向s2的第一个字符，再重新比较
}
if(j>=s2.length)
return i-s2.length; //表示s1中存在s2，返回其起始位置
else
return -1; //表示s1中不存在s2,返回-1
}
void main()
{
int i,j,k;
SString S1,T1;
int wz[80]; //记录子串出现的位置
i=0; //计数器清零
printf("请输入主字符串：");
gets(S1.ch); //读入主串
printf("请输入模式串：");
gets(T1.ch); //读入子串
S1.length=strlen(S1.ch);
T1.length=strlen(T1.ch);
k=0; //初始化开始检索位置
while(k<S1.length-1) //检索整个主串S1
{
j=PartPosition(S1,T1,k);//调用串匹配算法
if(j<0)
{
printf("没有检索到需要的子串\n");
break;
}
else
{
i++; //计数器加1
wz[i]=j;
k=j+T1.length; //继续下一个子串的检索
}
}
printf("子串%s出现在主串中的次数为%d\n",T1.ch,i);
printf("%d次匹配位置分别为：",i+1);
for(k=1;k<=i;k++)
printf("%4d",wz[k]);
printf("\n");
}
文本文件单词的检索与计数
#include<stdio.h>
#include<string.h>
#define MaxStrSize 256 //根据用户需要自己定义大小
typedef struct
{
char ch[MaxStrSize]; //ch是一个可容纳256个字符的字符数组
int length;
} SString; //定义顺序串类型
/**********************************/
/* 给定位置的串匹配 */
/**********************************/
int PartPosition(SString s1,SString s2,int k)
{
int i,j;
i=k-1; //扫描s1的下标，因为c中数组下标是从0开始，串中序号相差1
j=0; //扫描s2的开始下标
while(i<s1.length && j<s2.length)
if(s1.ch[i]==s2.ch[j])
{
i++;
j++; //继续使下标移向下一个字符位置
}
else
{
i=i-j+1; //使i下标回溯到原位置的下一个位置
j=0; //使j指向s2的第一个字符，再重新比较
}
if(j>=s2.length)
return i-s2.length; //表示s1中存在s2，返回其起始位置
else
return -1; //表示s1中不存在s2,返回-1
}
/**********************************/
/* 建立文本文件函数 */
/**********************************/
void CreateTextFile()
{
SString S;
char fname[10],yn;
FILE *fp;
printf("输入要建立的文件名：");
scanf(" %s",fname);
fflush(stdin); //清理缓存
fp=fopen(fname,"w");
yn='n'; //输入结束标志初值
while(yn=='n'||yn=='N')
{
printf("输入一行文本：");
gets(S.ch);
fflush(stdin); //清理缓存
S.length=strlen(S.ch);
fwrite(&S,sizeof(SString),1,fp);
// fputc('\n',fp); //写入换行符
printf("结束输入吗? y or n:");
yn=getchar();
fflush(stdin); //清理缓存
}
fclose(fp); //关闭文件;
printf("建立文件结束！\n");
}
/**********************************/
/* 文本文件单词计数函数 */
/**********************************/
void SubStrCount()
{
FILE *fp;
SString S,T; //定义两个变量
char fname[10];
int i=0,j,k;
printf("输入文本文件名：");
scanf(" %s",fname);
fp=fopen(fname,"r");
printf("输入要统计计数的单词：");
scanf(" %s",T.ch);
T.length=strlen(T.ch);
while(!feof(fp)) //扫描整个文本文件
{
fread(&S,sizeof(SString),1,fp); //读入一行文本
//printf("读取的内容为：%s",S.ch);
k=1; //初始化开始检索位置
while(k<S.length-1) //检索整个主串S
{
j=PartPosition(S,T,k); //调用串匹配函数
if(j<0)
break;
else
{
i++; //单词计数器加1
k=j+T.length; //继续下一个子串的检索
}
}
}
printf("\n单词%s在文本文件%s中共出现%d次\n",T.ch,fname,i);
}
/**********************************************************/
/*检索单词出现在文本文件中的行号、位置及在该行中出现的次数*/
/**********************************************************/
void SubStrInd()
{
FILE *fp;
SString S,T; //定义两个变量
char fname[10];
int i,j,k,l,m;
int wz[20]; //存放一行中子串匹配的多个位置
printf("输入文本文件名：");
scanf(" %s",fname);
fp=fopen(fname,"r");
printf("输入需要检索的单词：");
scanf(" %s",T.ch);
T.length=strlen(T.ch);
l=0; //行计数器置0
while(!feof(fp)) //扫描整个文本文件
{
fread(&S,sizeof(S),1,fp); //读入一行文本
l++; //行计数器自增1
k=1; //初始化开始检索位置
i=0; //初始化单词记数器
while(k<S.length-1) //检索整个主串S
{
j=PartPosition(S,T,k); //调用串匹配函数
if(j<0) break;
else
{
i++; //单词计数器加1
wz[i]=j; //记录匹配单词位置
k=j+T.length; //继续下一个子串的检索
}
}
if(i>0)
printf("行号：%d，次数：%d，位置分别为：",l,i);
for(m=1;m<=i;m++)
printf("%4d",wz[m]);
printf("\n");
}
}
/**********************************/
/* 主控菜单程序 */
/**********************************/
void main()
{
void CreateTextFile(),SubStrCount(),SubStrInd(); //函数声明
int xz;
do
{
printf("*************************************\n");
printf("* 文本文件的检索、子串的统计及定位 *\n");
printf("*************************************\n");
printf("* 1.建立文本文件 *\n");
printf("* 2.单词子串的计数 *\n");
printf("* 3.单词子串的定位 *\n");
printf("* 4.退出整个程序 *\n");
printf("*************************************\n");
printf("* 请选择：(1-4) *\n");
scanf(" %d",&xz);
switch(xz)
{
case 1:
CreateTextFile();
break;
case 2:
SubStrCount();
break;
case 3:
SubStrInd();
break;
case 4:
return;
default:
printf("选择错误！，重新选\n");
}
} while(1);
}