1 Star 1 Fork 0

qcliu / testC

Create your Gitee Account
Explore and code with more than 6 million developers,Free private repositories !:)
Sign up
This repository doesn't specify license. Without author's permission, this code is only for learning and cannot be used for other purposes.
Clone or download
trie2.c 3.66 KB
Copy Edit Web IDE Raw Blame History
qcliu authored 2015-06-10 13:46 . trie
/*
* R-way-trie
* Word Frequency Statistics
* NOTE: to use visualize, you need install graphviz before。
* qcliu 2015/06/10
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define R 255
#define TRUE 1
#define FALSE 0
static int node_num;
struct node* ROOT;
typedef struct node
{
int num;//the node number, only for dot
int value;//the ASCII
int frequecy;
char* s;//if it's a world, this is the world
struct node* child[R];
}Node;
static void throwException(char* info)
{
printf("%s\n", info);
exit(0);
}
static Node* newNode(int value)
{
node_num++;
Node* node = (Node*)malloc(sizeof(Node));
node->num = node_num;
node->value = value;
node->frequecy = 0;
node->s = NULL;
int i;
for (i=0; i<R; i++)
node->child[i] = NULL;
return node;
}
static char* openFile(char** argv)
{
FILE* cfd;
char* data;
int file_len;
cfd = fopen(argv[1], "r");
if (cfd == NULL)
throwException("NoFileInput");
fseek(cfd, 0L, SEEK_END);
file_len = ftell(cfd);
fseek(cfd, 0L, SEEK_SET);
data = (char*)malloc(file_len+1);
if (fread(data, sizeof(char), file_len, cfd) != file_len)
throwException("freed error");
data[file_len] = -1;
fclose(cfd);
return data;
}
static char* recursiveCreate(Node* curr, Node* next, char* start ,char* data)
{
if (*data<65||*data>122||(*data>90&&*data<97))
{
//a~z, A~Z
//find a world
if (curr != ROOT)
{//如果curr为ROOT,说明遇到了连续的非字母,所以不是单词,直接跳过。
curr->frequecy+=1;
if (curr->s == NULL)
{
int len = data-start;
char* world = (char*)malloc(len+1);
world[len] = '\0';
memcpy(world, start, len);
curr->s = world;
}
}
data++;
return data;
}
else
{//如果孩子中缺少这个字母,则创建新节点。
if (curr->child[*data] == NULL)
{
next = newNode(*data);
curr->child[*data] = next;
}
else
{
next = curr->child[*data];
}
}
curr = next;
data++;
return recursiveCreate(curr, next, start, data);
}
static void printNode(Node* node, FILE* fp)
{
if (node->frequecy == 0)
fprintf(fp, "node%d[label=\"%c\"];\n", node->num, node->value);
else
fprintf(fp, "node%d[label=\"%c\\n%s\\nfrequecy=%d\"];\n",
node->num, node->value, node->s, node->frequecy);
}
static void printEdge(Node* parent, Node* curr, FILE* fp)
{
fprintf(fp, "node%d->node%d;\n", parent->num, curr->num);
}
static void DFS(Node* parent,Node* curr, FILE* fp)
{
if (curr == NULL)
return;
printNode(curr, fp);
printEdge(parent, curr, fp);
int i;
for (i=0; i<R; i++)
{
DFS(curr, curr->child[i], fp);
}
}
static void visualize(Node* ROOT)
{
FILE* fp;
fp = fopen("trie.dot", "a");
fprintf(fp, "digraph{\n");
fprintf(fp, "node%d[label=\"ROOT\"];\n", ROOT->num);
int i;
for (i=0; i<R; i++)
DFS(ROOT, ROOT->child[i], fp);
fprintf(fp, "}\n");
fclose(fp);
system("dot -Tsvg trie.dot -o trie.svg");
system("rm trie.dot");
}
int main(int argc, char** argv)
{
char* data = openFile(argv);
//初始化ROOT
ROOT = newNode(0);
Node* curr = ROOT;
Node* next = ROOT;
while (*data != -1)
{
//every loop create a world, so it's always begin at ROOT
curr = ROOT;
data = recursiveCreate(curr, next, data, data);
}
//绘图
visualize(ROOT);
}

Comment ( 0 )

Sign in for post a comment

C
1
https://git.oschina.net/qcliu/testC.git
git@git.oschina.net:qcliu/testC.git
qcliu
testC
testC
master

Search