文章存放在一个文本文件中。要查找的人名,地名和形容词一次性输入,放在另一个文本文件中。 请帮我写一个基于c语言的kmp算法统计系统,完成以下功能: (1)系统读取这两个文本文件 (2)统计所有查找对象出现的概率(某个查找对象的次数/所有查找对象出现次数之和),并给出每个查找对象的哈夫曼编码。 (3)系统运行一次,全部统计完成,并把结果存放在文件result.txt中。
时间: 2024-02-12 15:08:11 浏览: 140
KMP-----c语言代码实现,能够实现查找功能
好的,我可以帮你编写一个基于C语言的KMP算法统计系统,实现你需要的功能。
首先,我们需要读取两个文本文件,一个是文章文件,一个是查找对象文件。可以使用C标准库中的`fopen`、`fread`、`fclose`等函数来实现文件读取。
接下来,我们需要实现KMP算法来查找文章中是否包含查找对象。KMP算法的核心是构建next数组,用来记录模式串中前缀和后缀的最长公共部分,然后根据next数组在文本串中匹配模式串。可以参考如下代码实现KMP算法:
```c
void getNext(char *p, int *next) {
int i = 0, j = -1;
next[0] = -1;
while (i < strlen(p)) {
if (j == -1 || p[i] == p[j]) {
i++;
j++;
next[i] = j;
} else {
j = next[j];
}
}
}
void kmp(char *t, char *p, int *next, int *count) {
int i = 0, j = 0;
while (i < strlen(t)) {
if (j == -1 || t[i] == p[j]) {
i++;
j++;
if (j == strlen(p)) {
(*count)++;
j = next[j];
}
} else {
j = next[j];
}
}
}
```
接下来,我们可以读取查找对象文件中的所有查找对象,然后依次在文章中查找每个对象出现的次数。同时,我们需要记录所有查找对象出现的总次数,以便计算概率。
可以参考如下代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_OBJ_LEN 100
#define MAX_LINE_LEN 1000
typedef struct {
char obj[MAX_OBJ_LEN];
int count;
} Object;
int cmp(const void *a, const void *b) {
Object *pa = (Object *) a;
Object *pb = (Object *) b;
return pb->count - pa->count;
}
int main() {
FILE *fp1, *fp2, *fp3;
char line[MAX_LINE_LEN];
char *text;
int textLen;
Object *objs;
int objCount = 0;
int total = 0;
// 读取文章文件
fp1 = fopen("article.txt", "r");
fseek(fp1, 0, SEEK_END);
textLen = ftell(fp1);
rewind(fp1);
text = (char *) malloc(textLen + 1);
fread(text, sizeof(char), textLen, fp1);
fclose(fp1);
// 读取查找对象文件
fp2 = fopen("objects.txt", "r");
while (fgets(line, MAX_LINE_LEN, fp2) != NULL) {
line[strlen(line) - 1] = '\0'; // 去掉换行符
objs = (Object *) realloc(objs, (objCount + 1) * sizeof(Object));
strcpy(objs[objCount].obj, line);
objs[objCount].count = 0;
objCount++;
}
fclose(fp2);
// 统计所有查找对象出现的次数
int *next = (int *) malloc((strlen(objs[0].obj) + 1) * sizeof(int));
int i, j;
for (i = 0; i < objCount; i++) {
getNext(objs[i].obj, next);
kmp(text, objs[i].obj, next, &objs[i].count);
total += objs[i].count;
}
// 计算概率
for (i = 0; i < objCount; i++) {
float prob = (float) objs[i].count / total;
printf("%s: %d, %.2f\n", objs[i].obj, objs[i].count, prob);
}
// 对查找对象按出现次数排序
qsort(objs, objCount, sizeof(Object), cmp);
// 哈夫曼编码
int codeLen[objCount];
char code[objCount][MAX_OBJ_LEN];
for (i = 0; i < objCount; i++) {
codeLen[i] = 0;
for (j = 0; j < strlen(objs[i].obj); j++) {
code[i][j] = '-';
}
code[i][j] = '\0';
}
while (objCount > 1) {
int min1 = objCount - 1, min2 = objCount - 2;
objs[min1].count += objs[min2].count;
for (i = 0; i < strlen(objs[min2].obj); i++) {
code[min2][i] = '0';
codeLen[min2]++;
}
for (i = 0; i < strlen(objs[min1].obj); i++) {
code[min1][i] = '1';
codeLen[min1]++;
}
objs = (Object *) realloc(objs, objCount * sizeof(Object));
objs[objCount - 2] = objs[min1];
objCount--;
for (i = min2; i < objCount - 1; i++) {
objs[i] = objs[i + 1];
strcpy(code[i], code[i + 1]);
codeLen[i] = codeLen[i + 1];
}
}
// 输出结果
fp3 = fopen("result.txt", "w");
for (i = 0; i < objCount; i++) {
fprintf(fp3, "%s: %d, %.2f, %s\n", objs[i].obj, objs[i].count, (float) objs[i].count / total, code[i]);
}
fclose(fp3);
// 释放内存
free(text);
free(objs);
free(next);
return 0;
}
```
代码中使用了一个Object结构体来记录每个查找对象的出现次数,以及一个code二维字符数组来存储每个对象的哈夫曼编码。
最后,我们将结果输出到result.txt文件中。
希望这个基于C语言的KMP算法统计系统能够帮助到你!
阅读全文