2018-11-10

数据结构实验2——串的模式匹配

全文共: 806字 | 阅读时长: 3分

阅读

文章导航

大二上数据结构实验1内容，使用C语言实现串的模式匹配

一、实验题目和要求

基于串的模式匹配

（一）实验目的：

通过本次实验，熟练掌握抽象数据类型串的实现，学会使用串及其模式匹配算法解决具体应用问题，从而体会串的特点。

（二）基本要求：

1）将HTML文件按字符顺序读入；

2）基于串的模式匹配算法，设计HTML文件中的信息提取方法，识别HTML文件中每条发帖的发信人ID、发帖时间和发帖IP；

3）在屏幕输出识别得到的每条发帖的发信人ID、发帖时间和发帖IP。

（三）内容提要：

1)用KMP算法实现模式匹配;

2)提示：在文件中，每条发帖的发信人ID之前紧邻的字符串均为“发信人:”、之后均为“(”，发帖时间和发帖IP也有类似的规律。

（四）示例

上图为所提供的HTML文件部分区域截图，其中发信人ID为“Dabo”、发帖时间为“Wed Sep 13 13:15:37 2017”、发帖IP为“202.117.62.94”。

二、按不同功能分析各程序模块

(一)包含库函数、定义常量、变量类型

#include<stdio.h>
#include<stdlib.h> 
#include<string.h> 
#include<math.h>
#include <afxinet.h>
#define MAXSTRLEN 10000//主串最大元素个数
#define MAXNEXTLEN 15//next数组最大元素个数

(二)数据结构基础定义（串）、next数组定义

1
2
3

typedef int Status; 
typedef char SString[MAXSTRLEN];
int next[MAXNEXTLEN];

(三)求next数组的子函数

void get_next(SString T,int next[])
{
	int i=1,j=0;
	next[1]=0;
	while(i<MAXNEXTLEN)
	{
		if(j==0||T[i]==T[j])
		{i++;j++;next[i]=j;}
		else j=next[j];
	}
}

(四)KMP算法的子函数

int Index_KMP(SString S,SString T,int pos)
//利用模式串T的next函数求T在主串S中第pos个字符后的位置的KMP算法
//其中，T非空，1<=pos<=Strlength(S)
{
	int i=pos,j=1;
	int Tnumber=strlen(T)-1;//T数组元素的个数
	while(i<=MAXSTRLEN&&j<=Tnumber)
	{
		if(j==0||S[i]==T[j])
		{++i;++j;}
		else j=next[j];
	}
	if(j>Tnumber) return i;
	else return 0;
}

(五)主函数

int main()
{
	int pos=1;
	int i=0;
    //把文件里面的信息读取到S数组中
	SString S;
	char ch;
	    FILE *fp;
    int j=0;
 if((fp=fopen("C:\\Documents and Settings\\Administrator\\桌面\\rzh\\bbs.html","r"))==NULL)
	{
        printf("Open the file failure.\n");
        exit(0);
    }
    while(j<MAXSTRLEN)
    {
		if((ch=fgetc(fp))!=EOF)
        {
            S[j]=ch;
        } 
		j++; 
	}
    fclose(fp);
    S[j]='\0';
	//查找发信人
	char D[]={"发信人:"};    //将“发信人：”放入D数组
	printf("发信人ID为:");	
	get_next(D,next);       //求D的next数组
	i=Index_KMP(S,D,pos);   //用KMP算法查找位置
	while(S[i]!='(')
	{
		printf("%c",S[i]);
		i++;
	}                     //输出查找的内容
	printf("\n");
    //查找发帖时间
	pos=1;
	char M[]={"发信站: 兵马俑BBS ("};
	printf("发贴时间为:");	
	get_next(M,next);
	i=Index_KMP(S,M,pos);
	while(S[i]!=')')
	{
		printf("%c",S[i]);
		i++;
	}
    printf("\n");
    //查找发帖IP
	pos=1;
	char T[]={"FROM:"};
	printf("发贴IP为:");	
	get_next(T,next);
	i=Index_KMP(S,T,pos);
	while(S[i]!=']')
	{
		printf("%c",S[i]);
		i++;
	}
    printf("\n");

	return 0;

}

三、运行结果分析

从交大兵马俑bbs上保存了两个网页分别进行了检验，运行结果如下：

都成功地读取了信息。网页截图：