comparare stringhe in C da un file di testo

[trediman]

Ancora una volta vi pongo qsto quesito... Ho già il listato di come comparare le stringhe e ve lo posto mi aiutate ad applicarlo ad un file di testo?? Devo cancellare le stringhe uguali in un file di testo formato da mails..
ogni mail va a capo... il listato è qsto:
#include <stdio.h>
#include <string.h>
int
strcmp (const char *s1, const char *s2)
{
unsigned char *a = (unsigned char *) s1;
unsigned char *b = (unsigned char *) s2;
size_t i;
for (i = 0; ; i++)
{
if (a[i] = b[i])
{
return a[i]
}
}
}
so anke come si apre un file di testo ma sto provando difficoltà ad integrare le 2 cose... per favore aiutatemiii:muro:

[DanieleC88]

http://digilander.libero.it/uzappi/C/librerie/funzioni/strcmp.html

[trediman]

ma non so come integrarla già mi sono documentato su strcmp il problema è come integrarla mi servirebbe + un frammento di codice

[DanieleC88]

Vediamo, se non ho capito male hai una lista di mail e vuoi togliere tutti i duplicati.

Una cosa di questo tipo dovrebbe andare (pseudocodice):
a = lista vuota;

per ogni riga del file
{
aggiungi riga ad a;
}

n = lunghezza di a;

per i che va da 1 ad n
{
per j che va da (i + 1) ad n
{
se a[i] è uguale ad a[j]
{
rimuovi a[j];
}
}
}
Questo è in tempo O(n²).

Se invece fai una cosa simile:
a = lista vuota;

per ogni riga del file
{
aggiungi riga ad a;
}

ordina a;
n = lunghezza di a;
i = 1;

finché (i < n)
{
j = (i + 1);

finché (a[i] è uguale ad a[j])
{
rimuovi a[j];
j = (j + 1);
}

i = j;
}
Dovrebbe essere O(n·log(n)).

Ovviamente il tutto è molto approssimativo. Per confrontare stringhe hai la strcmp() (se ti dà 0, le stringhe sono identiche).

[trediman]

l'algoritmo è proprio qsto il problema è implementarlo in C...
ma la strcmp non risolve il mio problema.. o almeno se mi rimanda allo 0 ..
Non mi serve saxe quale stringa è uguale mi serve che non ci siano mails uguali nel testo specifico quindi deve anke cancellarmi i doppioni... Visto che qsto è solo una parte di un problema molto + grande ho anke una certa urgenza e poca voglia di perderci tempo.. Quindi mi chiedo se qualcuno poteva aiutarmi o scrivendomi o rendendomi facile la scrittura di qsto programmino grazie ancora

[DanieleC88]

L'algoritmo te l'ho dato con tanto di spiegazione su come comparare le stringhe, resterebbe da fare l'implementazione di una lista (doppiamente?) linkata. Purtroppo ho anche io molto da fare e poco tempo per farlo, quindi non posso aiutarti più di così, mi spiace. :)

ciao ;)

[trediman]

Grazie lo stesso ma ho risolto con un semplice sort -u da shell linux e le ho eliminate a mano xkè chissà x quale oscura ragione il comando uniq non andava... ma se avete il listato fate pure

[nuovoUtente86]

Vediamo, se non ho capito male hai una lista di mail e vuoi togliere tutti i duplicati.

Una cosa di questo tipo dovrebbe andare (pseudocodice):
a = lista vuota;

per ogni riga del file
{
aggiungi riga ad a;
}

n = lunghezza di a;

per i che va da 1 ad n
{
per j che va da (i + 1) ad n
{
se a[i] è uguale ad a[j]
{
rimuovi a[j];
}
}
}
Questo è in tempo O(n²).

Se invece fai una cosa simile:
a = lista vuota;

per ogni riga del file
{
aggiungi riga ad a;
}

ordina a;
n = lunghezza di a;
i = 1;

finché (i < n)
{
j = (i + 1);

finché (a[i] è uguale ad a[j])
{
rimuovi a[j];
j = (j + 1);
}

i = j;
}
Dovrebbe essere O(n·log(n)).

Ovviamente il tutto è molto approssimativo. Per confrontare stringhe hai la strcmp() (se ti dà 0, le stringhe sono identiche).

Il secondo algoritmo per il caso in esame è sbagliato. Senza discutere sugli indici(cosa vitale), la computazione si fermerebbe alla prima occorrenza di confronto diversa offuscando eventuali ripetezioni presenti in posizioni successive. Inoltre, qualora l' algoritmo fosse correttamente funzionale allo scopo, la complessità sarebbe O(n²).

[DanieleC88]

Il secondo algoritmo per il caso in esame è sbagliato. Senza discutere sugli indici(cosa vitale), la computazione si fermerebbe alla prima occorrenza di confronto diversa offuscando eventuali ripetezioni presenti in posizioni successive. Inoltre, qualora l' algoritmo fosse correttamente funzionale allo scopo, la complessità sarebbe O(n²).
E meno male che l'avevo pure specificato che non avendo tempo da dedicarci il tutto era molto approssimativo... :p
Gli indici non li ho considerati più di tanto, era più un'idea che un'implementazione, non avevo nessuna pretesa di correttezza. Non vedo perché debba essere O(n²) e perché dovrebbe fermarsi alla prima occorrenza - anche se magari mi sbaglio, anche ora vado di fretta e gli ho lanciato proprio un'occhiata.

[nuovoUtente86]

E meno male che l'avevo pure specificato che non avendo tempo da dedicarci il tutto era molto approssimativo... :p
Gli indici non li ho considerati più di tanto, era più un'idea che un'implementazione, non avevo nessuna pretesa di correttezza. Non vedo perché debba essere O(n²) e perché dovrebbe fermarsi alla prima occorrenza - anche se magari mi sbaglio, anche ora vado di fretta e gli ho lanciato proprio un'occhiata.

Per quanto riguarda gli indici, si va fuori bound sul ciclo interno per via dell' ultimo incremento di j e per la condizione esterna (<a.length).
Si ferma alla sola prima occorrenza di eventuali dati uguali non contigui, perchè la condizione è a[i]==a[j] con conseguente valore false al primo confronto fallito.
Per quanto riguarda la complessità prova ad analizzare il caso peggiore in cui la struttura contenga tutti dati uguali(o dualmente tutti dati diversi imponendo nel while interno la condizione di disuguaglanza).

[DanieleC88]

[EDIT: database impazzito]

[DanieleC88]

[EDIT: database impazzito]

[DanieleC88]

Odio quando il database di HardwareUpgrade dà i numeri.

Ricopio:
Per quanto riguarda gli indici, si va fuori bound sul ciclo interno per via dell' ultimo incremento di j e per la condizione esterna (<a.length).
Questa probabilmente ci sta, basta aggiungere banalmente una condizione al ciclo interno.
Si ferma alla sola prima occorrenza di eventuali dati uguali non contigui, perchè la condizione è a[i]==a[j] con conseguente valore false al primo confronto fallito.
Nel ciclo interno però, ed è esattamente ciò che voglio. :p
Per quanto riguarda la complessità prova ad analizzare il caso peggiore in cui la struttura contenga tutti dati uguali(o dualmente tutti dati diversi imponendo nel while interno la condizione di disuguaglanza).
I cicli sono due, ma ti viene comunque O(n). Considera che lì ipotizzavo un funzionamento "stile array", anche se puoi adattare in modo semplice l'algoritmo ad una lista vera e propria. Prendi un elemento, e, a partire dal successivo, togli tutti i suoi duplicati. Una volta rimossi, non puoi tornare sui tuoi passi, quindi non puoi analizzare più di n elementi (tutt'al più ne consideri ognuno due volte, ma è 2n, quindi O(n)). Ovviamente funziona con un precedente ordinamento degli elementi, che dà il tempo O(n·log(n)) dominante (e avevo pure scritto "ordina a;", quindi non avrai mai "dati uguali non contigui" al momento dell'esecuzione dei cicli). No? :)

ciao ;)

[nuovoUtente86]

Non avevo letto la preliminare operazione di ordinamento, quindi è vero che funziona, ma lo fa ugualmente con complessità (nel caso peggiore O(n²))data non dall' ordinamento ma dall' iterazione di eliminazione. Parti dal pressuposto che iterando su una lista le eliminazioni le dovrai andare a fare su una struttura di appoggio, onde evitare problemi di accesso in concorrenza. Come dicevo su il caso peggiore è quello di una lista contenente tutti elementi uguali: pur eliminando sulla struttura di appoggio tutti gli elementi alla prima iterazione, il ciclo while continuerà sulla lista facendo ad ogni iterazione esterno (n-i-1) confronti che per una lista di 10 elementi corrisponde a circa 50 confronti dati da n*(n/2) ovvero O(n²).

[DanieleC88]

Parti dal pressuposto che iterando su una lista le eliminazioni le dovrai andare a fare su una struttura di appoggio, onde evitare problemi di accesso in concorrenza.
Che accesso in concorrenza? :)
Come dicevo su il caso peggiore è quello di una lista contenente tutti elementi uguali: pur eliminando sulla struttura di appoggio tutti gli elementi alla prima iterazione, il ciclo while continuerà sulla lista facendo ad ogni iterazione esterno (n-i-1) confronti che per una lista di 10 elementi corrisponde a circa 50 confronti dati da n*(n/2) ovvero O(n²).
Se usi una seconda lista d'appoggio, ma non è questo il caso, visto che lui non ha necessità di evitare accessi concorrenti o roba simile, una modifica in loco della lista è sufficiente, e i due cicli possono girare in tempo O(n) senza problemi, se non ho capito male tutti i requisiti. :)

ciao ;)

[nuovoUtente86]

Che accesso in concorrenza? :)

Se usi una seconda lista d'appoggio, ma non è questo il caso, visto che lui non ha necessità di evitare accessi concorrenti o roba simile, una modifica in loco della lista è sufficiente, e i due cicli possono girare in tempo O(n) senza problemi, se non ho capito male tutti i requisiti. :)

ciao ;)

Prova ad eliminare elementi da una struttura mentre ci iteri sopra e vedi se funziona. Se si utilizza un Array si puo' far puntare a null l' elemento da eliminare, ma questo non ti risparmia di iterare sulla struttura lungo la sua dimensione originale.

e i due cicli possono girare in tempo O(n) senza problemi, se non ho capito male tutti i requisiti
O(n)se il ciclo interno non esiste oppure avesse complessità theta(1)ma cosi non è.

[DanieleC88]

Prova ad eliminare elementi da una struttura mentre ci iteri sopra e vedi se funziona. Se si utilizza un Array si puo' far puntare a null l' elemento da eliminare, ma questo non ti risparmia di iterare sulla struttura lungo la sua dimensione originale.


O(n)se il ciclo interno non esiste oppure avesse complessità theta(1)ma cosi non è.
Ma che stai dicendo? :D
Se proprio sono costretto a dimostrare ovvietà...
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct node
{
char *email;
struct node *next;
struct node *previous;
};

typedef struct node Node;

struct list
{
Node *head;
Node *tail;
};

typedef struct list List;

void DeleteNode(Node *tmp)
{
Node *n = tmp->next;
Node *p = tmp->previous;

if (p)
{
p->next = n;
}

if (n)
{
n->previous = p;
}

free(tmp->email);
free(tmp);
}

List *NewList()
{
List *p = (List *) malloc(sizeof(List));

if (!p)
{
fprintf(stderr, " [**] Cannot allocate.\n");
abort();
}

memset(p, 0, sizeof(List));
return p;
}

void DeleteList(List *l)
{
Node *tmp = l->head;

while (tmp != NULL)
{
Node *next = tmp->next;

DeleteNode(tmp);
tmp = next;
}

free(l);
}

void ListPushBack(List *l, char *s)
{
Node *tmp;
Node *n = (Node *) malloc(sizeof(Node));

if (!n)
{
fprintf(stderr, " [**] Cannot allocate.\n");
abort();
}

memset(n, 0, sizeof(Node));
n->email = s;

if (l->head == NULL)
{
l->head = n;
}

if (l->tail != NULL)
{
l->tail->next = n;
}

n->previous = l->tail;
l->tail = n;
}

void PrintList(List *l)
{
Node *tmp = l->head;

while (tmp != NULL)
{
printf(" => %s\n", tmp->email);
tmp = tmp->next;
}
}

int ReadFile(const char *name, List *l)
{
FILE *fp = fopen(name, "r");

if (!fp)
{
return -1;
}

while (1)
{
size_t n;
char *s = (char *) malloc(1024 * sizeof(char));

if (fgets(s, 1024, fp) == NULL)
{
break;
}

n = (strlen(s) - 1);

if (s[n] == '\n')
{
s[n] = '\0';
}

ListPushBack(l, s);
}

fclose(fp);
return 0;
}

int main()
{
Node *tmp;
List *l = NewList();

if (ReadFile("input.txt", l) != 0)
{
DeleteList(l);

fprintf(stderr, " [**] Cannot read file.\n");
abort();
}

tmp = l->head;

while (tmp != NULL)
{
char *first = tmp->email;

tmp = tmp->next;

while ((tmp != NULL) && (strcmp(first, tmp->email) == 0))
{
Node *next = tmp->next;

DeleteNode(tmp);
tmp = next;
}
}

PrintList(l);
DeleteList(l);
return 0;
}
È una lista, e ci itero sopra mentre la modifico, bastano piccoli accorgimenti e lo puoi fare senza alzare la complessità asintotica. O(n) nel mio caso, perché il file di input lo presuppongo già ordinato, per comodità, come questo:
abc@def.it
abc@def.it
abc@def.it
abc@def.it
ciccio@pasticcio.net
ciccio@pasticcio.net
ciccio@pasticcio.net
tizio@caio.com

ciao ;)

[nuovoUtente86]

Hai utilizzato una lista concatenata ed è pacifico che funzioni, ma è solo uno scenario possibile. Prova a riscrivere lo stesso algoritmo in Java utilizzando un' ArrayList e for each(ma anche normale). Ovviamente è possibile ovviare al problema con l' utilizzo di altre strutture o di particolari stratagemmi, ma è bene ipotizzare su tutte le situazioni che possono verificarsi.

[DanieleC88]

Hai utilizzato una lista concatenata ed è pacifico che funzioni, ma è solo uno scenario possibile. Prova a riscrivere lo stesso algoritmo in Java utilizzando un' ArrayList e for each. Ovviamente è possibile ovviare al problema, ma è bene ipotizzare su tutte le situazioni che possono verificarsi.
Ma che significa, una cosa è l'algoritmo, un'altra è l'implementazione. L'algoritmo come te l'ho descritto funziona ed in tempo O(n·log(n)), una particolare implementazione dello stesso in Java o in qualsiasi altro linguaggio potrebbe anche richiedere O(n³), ma non è di nostro interesse (sarà dovuto al limite al funzionamento interno di una certa struttura dati utilizzata, ma puoi sempre sostituirla con un'altra e ottenere il risultato voluto). :)

ciao ;)

[nuovoUtente86]

Ma che significa, una cosa è l'algoritmo, un'altra è l'implementazione. L'algoritmo come te l'ho descritto funziona ed in tempo O(n·log(n)), una particolare implementazione dello stesso in Java o in qualsiasi altro linguaggio potrebbe anche richiedere O(n³), ma non è di nostro interesse (sarà dovuto al limite al funzionamento interno di una certa struttura dati utilizzata, ma puoi sempre sostituirla con un'altra e ottenere il risultato voluto). :)

ciao ;)
Quello che dici è vero a metà: è giusto astrarre dalla particolare implementazione, ci mancherebbe, ma nell' algoritmo da te descritto si parla genericamente di una struttura dati e non mi pare, nella descrizione, sia in evidenza la riduzione della dimensione in maniera diretta ad ogni eliminazione (il che rende la scelta di una lista concatenata puramente arbitraria senza fornisce generalità all' algoritmo).
Giusto per la cronaca, se l' ordinamento non è espressamento richiesto, è possibile creare un algoritmo a complessità lineare (pari alla lettura del file), utilizzando un set con funzionamento hash e trascurando in prima analisi le liste di collisione.

[DanieleC88]

Infatti anche la scelta della struttura dati è una particolarità dell'implementazione, puoi usare sia una lista che un'array e applicare in maniera praticamente identica il mio algoritmo senza modificare la complessità (se lavori su un'array di dimensione statica non riduci la sua grandezza, ma vai continuamente avanti senza mai tornare indietro, quindi riduci la dimensione dell'input da analizzare passo dopo passo).

Per l'hashmap ok, ma visto che lui chiedeva un'implementazione in C di questo semplice algoritmo, mi sembrava un po' overkill. :p

ciao ;)