数据结构试验 文学助手KMP

1、数据结构试验 文学助手 KMP  实验报告     实验名称：数据结构实验三 实验内容 ：文学家助手 实验仪器： 计算机     学院：计算机学院 班级：B软件工程 学号 ：姓名： XXXX 成绩： 指导教师：XXX     一、 问题描述  文章存于一个文本文件中。待统计的词聚集合要一次输入完毕，即统计工作必须在程序的一次运行之后就全部完成。程序的输出结果是每个词的出现次数和出现位置所在的行号，格式自行设计。  要

2、求采用基于KMP的算法实现。  整个统计过程只对文章文字扫描一遍以提高效率。     程序代码  #include "stdafx.h"  #include "stdafx.h"  #include "stdio.h"  #include "malloc.h"  #include "string.h"  #includ

3、e "conio.h"  using namespace System;  char articles="aaa bbb ccc abc abc"  struct HString  char* words;  int length;  int* next;  int count;  int j;    int row=0;  int co

4、l=0;  HString* creat(int length)  HString* words=(HString*)malloc(sizeof(HString);  words->words = (char*)malloc(sizeof(char)*length);  words->length=length;  words->next =(int*)malloc(sizeof(int)*(length+1);  words->j = 0; 

5、; words->count=0;  return words;    int Index_KMP(char* S,HString* w,int pos)  int i=pos; int j=0;  int l;  l=strlen(S);  while(i<=l&&j<w->length)  if(j<0|Si=w->wordsj)     &

6、#160;+i;  +j;       else j=w->nextj;    if(j=w->length)  return i-w->length;  else return 0;       void Do_Index_KMP(char* S,HString* w,int num)  int i=0;  int l

7、;  l=strlen(S);  while(i<l)  if (Si='.')col=0;row+;  else col+;     for (int s=0;s<num;s+)  while (ws->j >= 0 && ws->wordsws->j !=Si)  ws->j=ws->nextws->j;  +ws->j;

8、  if (ws->j=ws->length)  printf("%s is at row:%d-col:%dn",ws->words,row+1,col - ws->length+1); ws->count+;  ws->j =0;      i+;   for(int s=0;s<num;s+)  printf("The count of %s is %dn&q

9、uot;,ws->words,ws->count);    void get_next(HString* w)  int i=1;  int j=0;  w->next1=0;  while(i<w->length)  if(j=0|w->wordsi-1=w->wordsj-1)    +i;  +j;  w->nexti=j;

10、    else j=w->nextj;    for(i=0;i<w->length;i+)  w->nexti=w->nexti+1-1;    void main()  HString* words;  int word_number=0;  char input_chars128;  printf("the article is

11、：n");  int i=0;  while(articlesi!='0')   i+;  printf("%c",articlesi);  if(articlesi='.') printf("n");    printf("nn*n");  printf("how many words you want to count:n

12、");  scanf("%d",&word_number);  words=(HString*)malloc(sizeof(HString*)*word_number);  for (int i=0;i<word_number;i+)  printf("nplease input %dth word：n",i+1);  scanf("%s",input_chars);  wordsi=creat(strlen(input_chars);  strcpy(wordsi->words,input_chars);  get_next(wordsi);   Do_Index_KMP(articles,words,word_number);       for (int i=0;i<word_number;i+) free(wordsi); free(words); while(!kbhit();