Ciao,
Una delle tecniche più veloci consiste nell'utilizzare un automa a stati finiti(che non comporta backtracking) e un albero di ricerca binaria.
Il codice seguente effettua una ricerca nel file "romanzo.txt" che contiene il romanzo "I Viceré" di Federico De Roberto e che puoi scaricare da qui:
http://www.liberliber.it/biblioteca/...erto/index.htm
e trova le dieci parole (con lunghezza > 10 caratteri) più frequenti.
Sulla mia macchina:
codice:
AMD Athlon(tm) 64 X2
Dual Core Processor 4800+
2.50 GHz
896 MB di RAM
Ottengo questi tempi:
Questo è il codice:
codice:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <time.h>
#include <ctype.h>
#define MAX_STACK 1024
typedef enum tagStati
{
S_ERROR_OPEN_FILE = -2,
S_ERROR = -1,
S0 = 0,
S1
} Stati;
typedef struct tagTree
{
char *parola;
int count;
struct tagTree *left;
struct tagTree *right;
} Tree;
typedef struct tagList
{
char *parola;
int count;
struct tagList *next;
} List;
Tree *NewNode(char *info);
Tree *InsertNode(Tree *node, char *key);
void FreeTree(Tree *head);
List *ListNewNode(char *info, int count);
void ListInsertNode(List **head, List *newNode);
void FreeList(List **head);
void InOrder(Tree *head, List **a, int nMax);
Stati DFA(char *szFileName, Tree **pTree);
List *ListNewNode(char *info, int count)
{
List *r;
int len;
r = (List *) malloc(sizeof(List));
if( !r )
{
printf("Memoria insufficiente.\n");
return NULL;
}
len = strlen(info);
r->parola = (char*)malloc(len*sizeof(char) + 1);
if( !r->parola )
{
printf("Memoria insufficiente.\n");
return NULL;
}
strcpy(r->parola, info);
r->count = count;
r->next = NULL;
return r;
}
void ListInsertNode(List **head, List *newNode)
{
List *current = *head;
if ( *head == NULL ||
(*head)->count <= newNode->count )
{
newNode->next = *head;
*head = newNode;
}
else
{
while ( current->next != NULL &&
current->next->count > newNode->count )
{
current = current->next;
}
newNode->next = current->next;
current->next = newNode;
}
}
void FreeList(List** head)
{
List *current = *head;
List *next;
while ( current != NULL )
{
next = current->next;
free(current->parola);
free(current);
current = next;
}
*head = NULL;
}
Tree *NewNode(char* info)
{
Tree *r;
int len;
r = (Tree *) malloc(sizeof(Tree));
if( !r )
{
printf("Memoria insufficiente.\n");
return NULL;
}
len = strlen(info);
r->parola = (char*)malloc(len*sizeof(char) + 1);
if( !r->parola )
{
printf("Memoria insufficiente.\n");
return NULL;
}
strcpy(r->parola, info);
r->count = 1;
r->left = NULL;
r->right = NULL;
return r;
}
Tree *InsertNode(Tree *node, char *key)
{
Tree *pRadice = NULL;
int nRes;
if( !node )
{
node = NewNode(key);
return node;
}
pRadice = node;
while( 1 )
{
nRes = strcmp(key, node->parola);
if ( nRes < 0 )
{
if ( !node->left )
{
node->left = NewNode(key);
break;
}
node = node->left;
}
else if ( nRes > 0 )
{
if ( !node->right )
{
node->right = NewNode(key);
break;
}
node = node->right;
}
else // Trovato
{
node->count++;
break;
}
}
node = pRadice;
return node;
}
void FreeTree(Tree *head)
{
Tree *temp1, *temp2;
Tree *stack[MAX_STACK];
int top;
top = 0;
if ( !head )
return;
temp1 = temp2 = head;
while ( temp1 != NULL )
{
for(; temp1->left != NULL; temp1 = temp1->left)
stack[top++] = temp1;
while ( (temp1 != NULL) && (temp1->right == NULL || temp1->right == temp2) )
{
temp2 = temp1;
free(temp2->parola);
free(temp2);
if ( top == 0 )
return;
temp1 = stack[--top];
}
stack[top++] = temp1;
temp1 = temp1->right;
}
}
void InOrder(Tree *head, List **a, int nMax)
{
int k = 0;
Tree *temp;
List *listNode;
List *tempListNode;
List *tempListNodePrev;
Tree *stack[MAX_STACK];
int top;
top = -1;
if ( !head )
return;
temp = head;
while ( 1 )
{
if ( temp != NULL )
{
if ( top < MAX_STACK )
{
stack[++top] = temp; // Push
temp = temp->left;
}
else
{
printf("Errore: lo stack e' pieno.\n");
return;
}
}
else
{
if ( top >= 0 )
{
temp = stack[top--]; // Pop
if ( k < nMax )
{
listNode = ListNewNode(temp->parola, temp->count);
ListInsertNode(a, listNode);
}
else
{
listNode = ListNewNode(temp->parola, temp->count);
ListInsertNode(a, listNode);
tempListNode = tempListNodePrev = *a;
while ( tempListNode->next != NULL )
{
tempListNodePrev = tempListNode;
tempListNode = tempListNode->next;
}
tempListNodePrev->next = NULL;
free(tempListNode);
}
k++;
temp = temp->right;
}
else
{
break;
}
}
}
}
Stati DFA(char *szFileName, Tree **pTree)
{
Stati stato = S0;
FILE *fp;
char *buffer;
char szTemp[256];
char c;
int numread = 0;
int k = 0;
int x = 0;
int dimFile = 0;
fpos_t pos;
fp = fopen(szFileName, "rb");
if ( fp == NULL )
return S_ERROR_OPEN_FILE;
if ( fseek(fp, 0, SEEK_END) )
return -1;
if( fgetpos(fp, &pos) != 0 )
return -1;
dimFile = (int)pos;
if ( fseek(fp, 0, SEEK_SET) )
return -1;
buffer = (char*)malloc(sizeof(char)*dimFile + 1);
if ( !buffer )
{
printf("Errore nell'allocazione della memoria.");
fclose(fp);
return -1;
}
numread = fread(buffer,
sizeof(char),
dimFile,
fp);
if ( numread != dimFile )
{
fclose(fp);
return -1;
}
*(buffer + numread + 1) = '\0';
while ( k < dimFile )
{
c = *(buffer + k++);
switch (stato)
{
case S0:
if ( isalnum(c) || c == 'è' || c == 'é' || c == 'ì' || c == 'à' || c == 'ù' || c == 'ò' )
{
*(szTemp + x++) = c;
stato = S1;
}
else
{
stato = S0;
}
break;
case S1:
if ( isalnum(c) || c == 'è' || c == 'é' || c == 'ì' || c == 'à' || c == 'ù' || c == 'ò' )
{
*(szTemp + x++) = c;
stato = S1;
}
else
{
*(szTemp + x) = '\0';
x = 0;
if ( strlen(szTemp) > 10 )
{
*pTree = InsertNode(*pTree, szTemp);
if ( *pTree == NULL )
return S_ERROR;
}
stato = S0;
}
break;
}
}
free(buffer);
if ( fp )
fclose(fp);
return stato;
}
int main()
{
Tree * p = NULL;
List *a = NULL;
List *t = NULL;
Stati stato;
clock_t c_start, c_end;
char *szNomeFile = "romanzo.txt";
int nMax = 10;
c_start = clock();
stato = DFA(szNomeFile, &p);
if ( stato == S0 || stato == S1 )
{
InOrder(p, &a, nMax);
printf("\nParola -> Occorrenze\n\n");
t = a;
while ( t != NULL )
{
printf("%s -> %d\n", t->parola, t->count);
t = t->next;
}
FreeTree(p);
FreeList(&a);
}
c_end = clock();
printf("\n\nTempo impiegato -> %5.5f secondi\n", (double)(c_end - c_start) / CLOCKS_PER_SEC);
return 0;
}
É un pochino più lungo di quello proposto da Andrea 
; è il prezzo da pagare per una soluzione efficiente(in termini di velocità di esecuzione).
Puoi modificarlo facilmente per adattarlo al tuo problema(in modo, cioè, che trovi il numero di occorrenze della sola parola specificata in input).
VVoVe: ??? A parte gli scherzi ti ringrazio moltissimo per lo sforzo. Ora vedrò di studiarmelo.
Permessi di invio
Rispondi quotando