comparare stringhe in C da un file di testo

trediman · 09-08-2009, 11:53

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

DanieleC88 · 09-08-2009, 12:12

http://digilander.libero.it/uzappi/C...ni/strcmp.html

trediman · 09-08-2009, 12:24

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

DanieleC88 · 09-08-2009, 12:43

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):

Codice:

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:

Codice:

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 · 09-08-2009, 13:05

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 · 09-08-2009, 13:14

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 · 09-08-2009, 15:18

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 · 09-08-2009, 17:05

Quote:

Originariamente inviato da 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):

Codice:

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:

Codice:

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 · 09-08-2009, 19:04

Quote:

Originariamente inviato da nuovoUtente86

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...

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 · 09-08-2009, 22:09

Quote:

Originariamente inviato da DanieleC88

E meno male che l'avevo pure specificato che non avendo tempo da dedicarci il tutto era molto approssimativo...

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 · 10-08-2009, 03:10

[EDIT: database impazzito]

DanieleC88 · 10-08-2009, 03:11

[EDIT: database impazzito]

DanieleC88 · 10-08-2009, 13:55

Odio quando il database di HardwareUpgrade dà i numeri.

Ricopio:

Quote:

Originariamente inviato da nuovoUtente86

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.

Quote:

Originariamente inviato da nuovoUtente86

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.

Quote:

Originariamente inviato da nuovoUtente86

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 · 10-08-2009, 14:11

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 · 10-08-2009, 14:17

Quote:

Originariamente inviato da nuovoUtente86

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?

Quote:

Originariamente inviato da nuovoUtente86

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 · 10-08-2009, 14:21

Quote:

Originariamente inviato da DanieleC88

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.

Quote:

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 · 10-08-2009, 15:09

Quote:

Originariamente inviato da nuovoUtente86

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?

Se proprio sono costretto a dimostrare ovvietà...

Codice:

#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:

Codice:

[email protected]
[email protected]
[email protected]
[email protected]
[email protected]
[email protected]
[email protected]
[email protected]

ciao

nuovoUtente86 · 10-08-2009, 15:20

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 · 10-08-2009, 15:25

Quote:

Originariamente inviato da 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. 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 · 10-08-2009, 15:45

Quote:

Originariamente inviato da DanieleC88

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.

09-08-2009, 11:53	#1
trediman Senior Member Iscritto dal: Jun 2005 Messaggi: 711	comparare stringhe in C da un file di testo 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 __________________ Ho concluso affari positivamente con Schiac,Sam_88, Toretto, Bobosassa Vendo qui Contatto MSN/MAIL : [email protected] Sito web http://www.visioweb.it

09-08-2009, 12:12	#2
DanieleC88 Senior Member Iscritto dal: Jun 2002 Città: Dublin Messaggi: 5989	http://digilander.libero.it/uzappi/C...ni/strcmp.html __________________ C'ho certi cazzi Mafa' che manco tu che sei pratica li hai visti mai!

09-08-2009, 12:24	#3
trediman Senior Member Iscritto dal: Jun 2005 Messaggi: 711	grazie x la guida ma non so come integrarla già mi sono documentato su strcmp il problema è come integrarla mi servirebbe + un frammento di codice __________________ Ho concluso affari positivamente con Schiac,Sam_88, Toretto, Bobosassa Vendo qui Contatto MSN/MAIL : [email protected] Sito web http://www.visioweb.it

09-08-2009, 12:43	#4
DanieleC88 Senior Member Iscritto dal: Jun 2002 Città: Dublin Messaggi: 5989	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): Codice: 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: Codice: 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). __________________ C'ho certi cazzi Mafa' che manco tu che sei pratica li hai visti mai! Ultima modifica di DanieleC88 : 09-08-2009 alle 13:11.

09-08-2009, 13:05	#5
trediman Senior Member Iscritto dal: Jun 2005 Messaggi: 711	esatto ma 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 __________________ Ho concluso affari positivamente con Schiac,Sam_88, Toretto, Bobosassa Vendo qui Contatto MSN/MAIL : [email protected] Sito web http://www.visioweb.it

09-08-2009, 13:14	#6
DanieleC88 Senior Member Iscritto dal: Jun 2002 Città: Dublin Messaggi: 5989	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 __________________ C'ho certi cazzi Mafa' che manco tu che sei pratica li hai visti mai!

09-08-2009, 15:18	#7
trediman Senior Member Iscritto dal: Jun 2005 Messaggi: 711	Grazie cmq 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 __________________ Ho concluso affari positivamente con Schiac,Sam_88, Toretto, Bobosassa Vendo qui Contatto MSN/MAIL : [email protected] Sito web http://www.visioweb.it

10-08-2009, 03:10	#11
DanieleC88 Senior Member Iscritto dal: Jun 2002 Città: Dublin Messaggi: 5989	[EDIT: database impazzito] __________________ C'ho certi cazzi Mafa' che manco tu che sei pratica li hai visti mai! Ultima modifica di DanieleC88 : 10-08-2009 alle 13:46.

10-08-2009, 03:11	#12
DanieleC88 Senior Member Iscritto dal: Jun 2002 Città: Dublin Messaggi: 5989	[EDIT: database impazzito] __________________ C'ho certi cazzi Mafa' che manco tu che sei pratica li hai visti mai! Ultima modifica di DanieleC88 : 10-08-2009 alle 13:55.

10-08-2009, 14:11	#14
nuovoUtente86 Senior Member Iscritto dal: Mar 2007 Messaggi: 7863	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²).

10-08-2009, 15:20	#18
nuovoUtente86 Senior Member Iscritto dal: Mar 2007 Messaggi: 7863	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. Ultima modifica di nuovoUtente86 : 10-08-2009 alle 15:25.

Strumenti
Mostra una versione stampabile Invia questa pagina per email