數(shù)據(jù)結(jié)構(gòu)試驗 文學(xué)助手KMP

1、數(shù)據(jù)結(jié)構(gòu)試驗 文學(xué)助手 KMP  實驗報告     實驗名稱：數(shù)據(jù)結(jié)構(gòu)實驗三 實驗內(nèi)容 ：文學(xué)家助手 實驗儀器： 計算機(jī)     學(xué)院：計算機(jī)學(xué)院 班級：B軟件工程 學(xué)號 ：姓名： XXXX 成績： 指導(dǎo)教師：XXX     一、 問題描述  文章存于一個文本文件中。待統(tǒng)計的詞聚集合要一次輸入完畢，即統(tǒng)計工作必須在程序的一次運行之后就全部完成。程序的輸出結(jié)果是每個詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在的行號，格式自行設(shè)計。  要

2、求采用基于KMP的算法實現(xiàn)。  整個統(tǒng)計過程只對文章文字掃描一遍以提高效率。     程序代碼  #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();