My program uses the Knuth–Morris–Pratt algorithm to search for a particular substring in a .txt file and then store it in a binary search tree.
Note that testfile.txt should be contain only spaces and normal characters (no newlines! - except maybe as the last byte).
There is a lot of code, so note that I am primarily concerned about the KMP algorithm in countWord.c, which I am new to.
wordCount.h
#ifndef WORDCOUNT_H
#define WORDCOUNT_H
#include<stdlib.h>
#include<stdio.h>
typedef struct BSTnode{
char data[20];
struct BSTnode* leftchild; //if less than, put it on the left
struct BSTnode* rightchild; //if greater than, on the right
int num;
}BSTnode;
char* findWord(FILE*); //This function is used to find out a new word again and again in the file.
int countWord(FILE*,char*); //this is used to count out occurrences of the word found
int inputWord(BSTnode*,char*,int); //this is used to insert the word into the binary search tree(but I don' try to loop through the tree)
int createTable(char*,int,int*); //this function is for the KMP algorithm
#endif
main.c
#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include<stdbool.h>
#include "wordCount.h"
char arr[20]={0};
int main()
{
/*initialize the firstNode*/
BSTnode* firstNode=malloc(sizeof(BSTnode));
firstNode->leftchild=NULL;
firstNode->rightchild=NULL;
strcpy(firstNode->data,"");
firstNode->num=0;
FILE* fs=fopen("testfile.txt","r");
if(!fs){
printf("Failed to open fiel!!\n");
return 2;
}
int i=0;
while(++i<=30){ //To keep it simple, I only find out 30 words and search it in the testfile.txt
memset(arr,'\0',20);
char* newWord=findWord(fs);
int totalNumberOfTheWord=countWord(fs,newWord);
inputWord(firstNode,newWord,totalNumberOfTheWord);
}
return 0;
}
findWord.c
#include<string.h>
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include "wordCount.h"
extern char arr[20];
char* findWord(FILE* fs)
{
static long pos=0;
fseek(fs,pos,SEEK_SET);
if(ferror(fs)){
perror("fseek() failed!!!\n");
fprintf(stderr,"fseek() failed in file %s\n",__FILE__);
exit(EXIT_FAILURE);
}
char chr[1]={'\0'};
bool flag1=false;
bool flag2=false;
while((1==fread(chr,1,1,fs))&&(!(flag1==false&&flag2==true))){
/* I set two bool vars(flag1 and flag2) to make findWord() find only one
* word(with only normal characters, no space, no newline*/
if(chr[0]!=32){
strncat(arr,chr,1);
flag2=true;
flag1=true;
}
else
flag1=false;
}
pos=ftell(fs)-1;
//maybe everytime you use "fseek()", "ftell()", the
//file-position will move one byte ahead.
return arr;
}
countWord.c
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include "wordCount.h"
int next[20]={0};
/*create table of the word for search. this table is for using KMP algorithm*/
int createTable(char* word, int lengthOfWord, int* next){
int i=0;
int j=-1;
next[0]=-1;
while(i<lengthOfWord-1){
if(j==-1||word[i]==word[j]){
++i;
++j;
next[i]=j;
}
else{
j=next[j];
}
}
return 0;
}
int countWord(FILE* fs,char* word)
{
rewind(fs);
fseek(fs,0L,SEEK_END);
int lengthOfBuf=ftell(fs);
char* buf=calloc(1,sizeof(char)*lengthOfBuf+1);
if(!buf){
perror("Memory allocation failed!!\n");
exit(1);
}
rewind(fs);
/*read the content of testfile.txt into buf*/
if(!lengthOfBuf==fread(buf,1,lengthOfBuf,fs)){
perror("File not read into buf yet!");
exit(1);
}
int lengthOfWord=strlen(word);
createTable(word,lengthOfWord,next);
int posOfBuf=0;
int posOfWord=-1;
int count=0;
while(posOfBuf<lengthOfBuf-1){
if(posOfWord==-1||(word[posOfWord]==buf[posOfBuf])||(word[posOfWord]-buf[posOfBuf]==32)||(word[posOfWord]-buf[posOfBuf]==-32)){
if(posOfWord==lengthOfWord-1){
count+=1;
posOfWord=-1;
continue;
}
else{
++posOfWord;
++posOfBuf;
}
}
else
posOfWord=next[posOfWord];
}
return count;
}
inputWord.c
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include"wordCount.h"
/*input a the word and its occurrences into the binary search tree(but not trying to print the tree out*/
int inputWord(BSTnode* Node,char* word,int num){
BSTnode* ptr=Node;
while(1){
if(stricmp(word,ptr->data)>0){
if(ptr->rightchild!=NULL){
ptr=ptr->rightchild;
continue;
}
else{
ptr->rightchild=malloc(sizeof(BSTnode));
if(!(ptr->rightchild)){
perror("Failed to allocate memory for right-child!");
exit(1);
}
ptr=ptr->rightchild;
ptr->rightchild=NULL;
ptr->leftchild=NULL;
strcpy(ptr->data,word);
ptr->num=num;
fprintf(stdout,"New data '%s(%d)' successfully inserted into a new (left) node at (value of pointer)\n",word,num);
break;
}
}
else if(stricmp(word,ptr->data)<0){
if(ptr->leftchild!=NULL){
ptr=ptr->leftchild;
continue;
}
else{
ptr->leftchild=malloc(sizeof(BSTnode));
if(!(ptr->leftchild)){
perror("Failed to allocate memory for left-child!");
exit(1);
}
ptr=ptr->leftchild;
ptr->leftchild=NULL;
ptr->rightchild=NULL;
strcpy(ptr->data,word);
ptr->num=num;
fprintf(stdout,"New data '%s(%d)' successfully inserted into a new (left) node at (value of pointer)\n",word,num);
break;
}
}
else{
fprintf(stdout,"It is the same word!!\n");
return 0;
}
}
return 0;
}
printf()statement (for test) in my original code. \$\endgroup\$