Indice del forum Olimpo Informatico
I Forum di Zeus News
Leggi la newsletter gratuita - Attiva il Menu compatto
 
 FAQFAQ   CercaCerca   Lista utentiLista utenti   GruppiGruppi   RegistratiRegistrati 
 ProfiloProfilo   Messaggi privatiMessaggi privati   Log inLog in 

    Newsletter RSS Facebook Twitter Contatti Ricerca
Aiuto linguaggio C
Nuovo argomento   Rispondi    Indice del forum -> Programmazione
Precedente :: Successivo  
Autore Messaggio
SverX
Supervisor Macchinisti
Supervisor Macchinisti


Registrato: 25/03/02 11:16
Messaggi: 11559
Residenza: Tokelau

MessaggioInviato: 14 Feb 2014 16:01    Oggetto: Rispondi citando

se devo essere davvero onesto, mi ricordo talmente poco degli alberi che posso essere di ben poco aiuto...
comunque l'idea di avere degli alberi dove ad ogni livello i nodi hanno le lettere dell'alfabeto mi sembra corretta... anche se a questo punto farei degli alberi dove i nodi hanno direttamente la sottostringa, e ovviamente solo quelli che 'esistono davvero' nel tuo file...

intendo: immagina di avere un set di parole tipo

abaco
abbonamento
abbottonare
bravo

la radice dell'albero è la stringa vuota. Sotto alla stringa vuota hai due figli: 'ab' e 'bravo'. Sotto 'bravo' ovviamente non avrai niente, mentre sotto 'ab' avrai 'abaco' e 'abbo'. Sotto 'abaco' niente, sotto 'abbo' avrai 'abbonamento' e 'abbottonare'.

Quando ricerchi, devi scendere fino a trovare un nodo che soddisfa il confronto della sottostringa e a quel punto tutti i suoi sotto-nodi che sono foglie (ovvero nodi SENZA figli) sono le possibili parole che soddisfano la ricerca.

L'inserimento di una voce in un albero di questo tipo non è un'operazione molto semplice, in effetti... si tratta di scendere fino a che non si trova una foglia che ha una sottostringa in comune e generare un nodo 'padre' che soddisfi entrambi.

Ad esempio metti di volere inserire 'brodo':
parti dalla radice e guardi i figli:
- 'ab' non è sottostringa di 'brodo', e nessuna sottostringa 'sinistra' di 'brodo' (neanche solo 'b') è sottostringa sinistra di 'ab', quindi niente
- 'bravo' non è sottostringa di 'brodo', ma 'br' è sottostringa di entrambi. Quindi inserisci il nodo 'br' e attacchi 'bravo' e 'brodo' come figli...

funziona no? speriamo! Laughing
Top
Profilo Invia messaggio privato HomePage
kiara91
Mortale pio
Mortale pio


Registrato: 31/01/14 17:56
Messaggi: 20

MessaggioInviato: 14 Feb 2014 17:07    Oggetto: Rispondi citando

Innanzitutto grazie come sempre:)

Quello che non mi convince di usare le sottostringhe al posto dei semplici caratteri è che se (supponendo di trovarmi nel tuo esempio) voglio aggiungere la stringa armadio allora dovrei inserire un altro figlio alla radice dell'albero contenente la sottostringa 'ar'.
O almeno è così se ho capito bene quello che mi suggerisci

Diciamo che sì, magari riduco la profondità dell'albero ma aumento il numero dei figli di ciascun nodo dato che ad esempio devo inserire al primo livello tutte le coppie di caratteri dell'alfabeto 26^2 invece di 26. E questo se voglio usare sottostringhe di soli 2 caratteri. Oppure davvero ho capito male cosa intendi..
Top
Profilo Invia messaggio privato
SverX
Supervisor Macchinisti
Supervisor Macchinisti


Registrato: 25/03/02 11:16
Messaggi: 11559
Residenza: Tokelau

MessaggioInviato: 14 Feb 2014 21:00    Oggetto: Rispondi citando

'armadio' andrebbe a confrontarsi con il nodo 'ab' e, dato che hanno in comune la sottostringa 'a', dovresti creare il nodo 'a' e collegare a questo nodo nuovo i due figli 'ab' e 'armadio'

in ogni caso non seguire questa strada, mi sono accorto che c'è un errore dietro l'angolo... mi spiego: prendi parole come

aroma
aromatico
aromatizzato

il problema è che ad esempio 'aroma' sarà genitore degli altri due nodi, e quindi non sarà una foglia... e siamo fregati Confused

Se fai come dicevi tu avrai una lettera per ogni nodo e una parola completa per ogni percorso dalla radice ad una foglia... molti più nodi di come pensavo io ma alla fine in effetti meno problematico... Rolling Eyes
Top
Profilo Invia messaggio privato HomePage
kiara91
Mortale pio
Mortale pio


Registrato: 31/01/14 17:56
Messaggi: 20

MessaggioInviato: 16 Feb 2014 18:31    Oggetto: Rispondi citando

Eccomi, scusa l'assenza Embarassed

Ho proseguito, ho costruito il mio trie e ho definito funzioni di ricerca 'statica' e inserimento.
Il problema ora è con la ricerca 'dinamica' o 'interattiva', ovvero digito k>0 caratteri e ricevo in output tutte le stringhe che hanno come prefisso quei caratteri.

La mia funzione procede così:

Supponiamo che nel trie ci siano le stringhe

'VERONA'
'VERCELLI'
'VERBANIA'
'VICENZA'
'VENEZIA'

e che io inserisca i caratteri (o comunque la stringa 'VER').

La mia funzione (RicercaDinamica) scandisce l'albero fino ad arrivare al figlio di 'E' relativo alla lettera 'R'. Ora inizia la parte che serve a recuperare le stringhe che hanno 'VER' come prefisso. Svolgo questo lavoro attraverso una funzione (Recupera).

Dunque per ogni figlio del nodo relativo alla lettera 'R'

se è nullo (ma in questo caso non è così dato che la stringa 'VER' non appartiene al trie) restituisce la stringa che 'termina' in quel nodo (sottolineo che il trie che ho creato ha nell'ultimo nodo di ogni cammino la stringa che quel cammino rappresenta).
Quando dico restituisce significa che la memorizza in un array di stringhe che viene inizialmente passato alla funzione.

se non è nullo (quindi significa che ci sono stringhe che iniziano con 'VER' ma che contengono altri caratteri) applica ricorsivamente la funzione (Recupera) a ciascuno sei suoi figli.

Spero di essermi spiegata non troppo male.

Il punto è che ho qualche difficoltà con questo vettore di stringhe che voglio passare alla funzione. Innanzitutto ho notato che una funzione in C non può restituire un array, nè tantomeno un array di stringhe (array di array di caratteri).
Dunque devo passarlo 'per indirizzo' alle due funzioni (RicercaDinamica) e (Recupera). Ma ho problemi di segmentation fault.

In particolare vorrei chiedere alcune cose

- quando passo un array di stringhe a una funzione devo specificarne le dimensioni? O almeno una delle 2 dimensioni? (Una è il numero di stringhe, l'altra è la massima lunghezza della singola stringa)

- devo in qualche modo inizializzare le singole stringhe? o posso inizializzare direttamente l'array di stringhe? E come? (devo usare una malloc?)

- quando voglio inserire una stringa nel mio array di stringhe devo usare strcpy o posso usare l'assegnamento (stringa="ciao")? Ho notato che strcpy mi dà errore se non inizializzo la stringa, mentre l'assegnamento sembra funzionare ma quando ho iniziato (da poco) a studiare le stringhe ho letto che non si può utilizzare l'uguaglianza per assegnare una stringa ad una variabile stringa.

Spero di non essere stata troppo noiosa..e anche se non rispondete a tutto, magari qualche piccolo cenno mi farebbe tanto piacere:)

Penso di essere quasi giunta alla fine ma ora mi sono un attimo bloccata.
Please help! Sad
Top
Profilo Invia messaggio privato
SverX
Supervisor Macchinisti
Supervisor Macchinisti


Registrato: 25/03/02 11:16
Messaggi: 11559
Residenza: Tokelau

MessaggioInviato: 16 Feb 2014 18:53    Oggetto: Rispondi citando

innanzitutto se fai un assegnamento stai cambiando il valore di un punatatore, non stai copiando una stringa in un altra. Ovvero
Codice:
stringa="ciao"

fa sì che il tuo puntatore a carattere stringa punti alla memoria del programma dove è memorizzata la stringa costante "ciao". Se provi a modificarla quindi ti darà poi facilmente errore (distruggi il programma se ci scrivi sopra, quindi segmentation fault o altre amenità del genere...)
Devi sempre allocare uno spazio per la stringa e copiarci dentro, non c'è un altro modo.
Per un array di stringhe puoi allocare l'array in modo statico (ma volendo anche in modo dinamico) e poi tutte le stringhe vanno allocate comunque. Per passare l'array puoi usare comunque il puntatore a carattere e per passare alla stringa successiva puoi usare l'aritmetica dei puntatori. Poi puoi definire che il contenuto dell'array (quante stringhe contiene) non sia noto a priori, ma dovrai imporre che l'array finisca con una stringa di lunghezza zero, altrimenti andrai avanti fino a debordare...
Top
Profilo Invia messaggio privato HomePage
kiara91
Mortale pio
Mortale pio


Registrato: 31/01/14 17:56
Messaggi: 20

MessaggioInviato: 16 Feb 2014 19:06    Oggetto: Rispondi citando

Uh grazie..allora..sto facendo un pochino di prove per impratichirmi..supponiamo che che io voglia modificare un array di stringhe tramite una funzione Modifica

Codice:

void modifica(char *array[], int n) //Prende come argomenti anche un intero (che non indica la dimensione)


questo è il giusto prototipo della mia funzione?

Ora, devo inizializzare quell'array di stringhe all'interno della funzione o dovrò farlo solo nel main?
Posso scrivere nella funzione cose del tipo
Codice:

if(n%2==0){
    array[0]="pippo";
    array[1]="casa";}
else{
    array[0]="fungo";
    array[1]="elmo";}


oppure devo usare strcpy?

Grazie ancora per la pazienza che stai avendo con me Embarassed
Top
Profilo Invia messaggio privato
SverX
Supervisor Macchinisti
Supervisor Macchinisti


Registrato: 25/03/02 11:16
Messaggi: 11559
Residenza: Tokelau

MessaggioInviato: 16 Feb 2014 19:21    Oggetto: Rispondi citando

l'array va comunque allocato, direi che potresti farlo a priori (nel main) per semplicità. Poi le stringhe anche vanno allocate, una per una... quindi una malloc() e una strcpy() per ognuna.
Infine se memorizzi due stringhe nell'array, dovrai settare a NULL il terzo puntatore a stringa altrimenti non saprai mai quante stringhe la funzione ha restituito, a meno di non dichiarare invece la funzione come
Codice:
int modifica(....)

e farle restituire il numero di stringhe memorizzate nell'array, che potrebbe anche essere una valida opzione, valuta te. Non c'è mai un solo modo di risolvere un problema Smile

Ciao
Top
Profilo Invia messaggio privato HomePage
kiara91
Mortale pio
Mortale pio


Registrato: 31/01/14 17:56
Messaggi: 20

MessaggioInviato: 16 Feb 2014 19:33    Oggetto: Rispondi citando

Se nel main definisco il mio vettore di stringhe (elenco) e lo inizializzo in questo modo,

Codice:
char *elenco[40];
  for (i=0;i<40;i++)
    elenco[i]=(char*)malloc(sizeof(char *) * 100);


dove ho supposto che l'array contenga al più 40 stringhe di 100 caratteri max (o forse 99), poi sono libera di utilizzarlo, ovvero di lanciare istruzioni del tipo

Codice:
strcpy(elenco[i],"Marzapane")


?

Oppure devo compiere altre operazioni preliminari?
Top
Profilo Invia messaggio privato
SverX
Supervisor Macchinisti
Supervisor Macchinisti


Registrato: 25/03/02 11:16
Messaggi: 11559
Residenza: Tokelau

MessaggioInviato: 16 Feb 2014 20:56    Oggetto: Rispondi citando

intendi:
Codice:
malloc(sizeof(char) * 100)


comunque sì, se vuoi puoi allocare lo spazio per tutte e 40 le stringhe, anche se poi non le userai...

se invece vuoi avere qualcosa di ottimizzato, in termini di spazio, dovresti allocare solo quello che ti serve, quando ti serve. A quel punto poi potresti allocare per ogni stringa solo lo spazio che intendi occupare, invece di 100 caratteri.

Infine, con un po' di malizia potrei suggerirti che se nei nodi tuo albero (tree, non trie!) ci sono già le stringhe, vuol dire che le hai già allocate da qualche parte, e quindi potresti evitare di allocare altro spazio per ricopiarci dentro le stringhe e semplicemente fare puntare i tuoi puntatori (l'array) alle stesse stringhe... intendiamoci, non c'è nessuna regola che dice che due variabili puntatore distinte non possano puntare allo stesso indirizzo di memoria... tutto sta nel saperle poi gestire no? Smile
Top
Profilo Invia messaggio privato HomePage
kiara91
Mortale pio
Mortale pio


Registrato: 31/01/14 17:56
Messaggi: 20

MessaggioInviato: 16 Feb 2014 21:52    Oggetto: Rispondi citando

D'accordo grazie ancora..ora mi metto all'opera..
Comunque no, intendevo proprio trie (si pronuncia come l'inglese try), una particolare struttura di dati che mi serve per fare questo tipo di ricerca. Ovviamente per implementarla servono gli alberi i tree
Top
Profilo Invia messaggio privato
SverX
Supervisor Macchinisti
Supervisor Macchinisti


Registrato: 25/03/02 11:16
Messaggi: 11559
Residenza: Tokelau

MessaggioInviato: 17 Feb 2014 10:46    Oggetto: Rispondi citando

Shocked ecco, si impara sempre qualcosa.

si vede che quando ho studiato io, gli alberi di questo tipo non erano ancora spuntati Laughing Laughing Laughing
Top
Profilo Invia messaggio privato HomePage
kiara91
Mortale pio
Mortale pio


Registrato: 31/01/14 17:56
Messaggi: 20

MessaggioInviato: 17 Feb 2014 17:08    Oggetto: Rispondi citando

evvaiiii funziona Very Happy grazie SverX per il supporto che mi hai dato

Allora, il trie funziona, riesco a inserire e fare ricerche interattive digitando solo alcuni caratteri (se vuoi ti regalo il codice come regalo per il tuo aiuto ahaha Very Happy )

A parte tutto mi hai dato una mano grandissima..non ho ancora finito

Devo mettere insieme le due parti

- ho lavorato sul file per isolare le varie stringhe
- ho creato il trie e le funzioni di inserimento e ricerca

Ora devo fare in modo di inserire tutti i dati del file all'interno del trie (o dei trie?)

Per fare le mie ricerche di Titoli e Argomenti ho bisogno di 2 strutture (cioè di un trie per i titoli e nel campo che contiene il titolo mettere anche tutti gli argomenti e di un trie per gli argomenti con analogo comportamento) oppure c'è un modo per utilizzarne uno solo?

Scusa se continuo ancora a stressarti ma sei l'unico che mi ha dato una mano Sad ti sono debitrice
Top
Profilo Invia messaggio privato
SverX
Supervisor Macchinisti
Supervisor Macchinisti


Registrato: 25/03/02 11:16
Messaggi: 11559
Residenza: Tokelau

MessaggioInviato: 18 Feb 2014 10:59    Oggetto: Rispondi citando

probabilmente hai bisogno di due trie, uno per i titoli e uno per gli argomenti. In più direi che hai bisogno di qualcosa che colleghi i due, ovvero che colleghi ogni titolo ai suoi argomenti... e qui cosa scegliere dipende soprattutto dal senso in cui andrai a fare le ricerche, immagino...
Top
Profilo Invia messaggio privato HomePage
kiara91
Mortale pio
Mortale pio


Registrato: 31/01/14 17:56
Messaggi: 20

MessaggioInviato: 18 Feb 2014 14:09    Oggetto: Rispondi citando

La mia idea iniziale era quella di inserire in ciascuna foglia del trie relativo ai Titoli (ovviamente nelle foglie che mi rappresentano un percorso di lunghezza >0 e dunque a cui è associato un Titolo) una lista (o un array) di Argomenti e viceversa nel trie relativo agli argomenti inserire in ogni foglia una lista (o un array) contenente i Titoli..
che dici? può andare?
Top
Profilo Invia messaggio privato
SverX
Supervisor Macchinisti
Supervisor Macchinisti


Registrato: 25/03/02 11:16
Messaggi: 11559
Residenza: Tokelau

MessaggioInviato: 19 Feb 2014 15:36    Oggetto: Rispondi citando

penso funzioni... o potresti semplicemente inserire una lista di puntatori alle strutture dell'altro albero...
Top
Profilo Invia messaggio privato HomePage
kiara91
Mortale pio
Mortale pio


Registrato: 31/01/14 17:56
Messaggi: 20

MessaggioInviato: 21 Feb 2014 20:47    Oggetto: Rispondi citando

Ho finito Smile Alla fine ho usato un trie di liste e ho fatto come ti avevo spiegato nel post precedente.

Io non so come ringraziarti, mi hai aiutata tantissimo e senza di te non ce l'avrei mai fatta Embarassed Squeeze Squeeze

Un'ultima cosa poi chiudo: Devo creare un file .h in cui inserire tutte le strutture che ho definito e relative funzioni o posso lasciare tutto nel file .c?
E nel primo caso, nel file .h vanno inserite altre cose?
Grazie (spero sia l'ultimo disturbo che ti darò) Smile
Top
Profilo Invia messaggio privato
SverX
Supervisor Macchinisti
Supervisor Macchinisti


Registrato: 25/03/02 11:16
Messaggi: 11559
Residenza: Tokelau

MessaggioInviato: 24 Feb 2014 09:35    Oggetto: Rispondi citando

i file .h sono fondamentali se nel tuo progetto userai più di un file .c solo, e quindi avrai delle definizioni che 'condividerai' tra i vari sorgenti, altrimenti non è per niente necessario (come hai detto funziona, no? Smile )

detto che non è necessario, se vuoi comunque farlo fai pure. attenzione che nel file .h vanno messe solo definizioni (tipi, prototipi delle funzioni etc etc) e NON vanno messe le funzioni e le dichiarazioni di variabili.

Ciao
Top
Profilo Invia messaggio privato HomePage
kiara91
Mortale pio
Mortale pio


Registrato: 31/01/14 17:56
Messaggi: 20

MessaggioInviato: 19 Mar 2014 18:03    Oggetto: Rispondi citando

Rieccomi di nuovo. Scusami se riesumo questo topic ma avrei un piccolo quesito ancora sul progette di qualche tempo fa.
Mi rivolgo a te, SverX perchè tu mi hai aiutato l'ultima volta, ma ovviamente la richiesta di aiuto è estesa a tutti coloro che volessero gentilmente aiutarmi.

Il problema è questo..ho il mio trie in cui in ogni foglia vi è una lista contenente delle stringhe. Quando voglio inserire una nuova stringa, funziona tutto bene se uso l'inserimento in Coda, ma non funziona per nulla quando uso l'inserimento in Testa.

Essendo il mio un file di dimensioni notevoli, usare l'inserimento in Coda diventa troppo dispendioso e quindi sono costretta ad utilizzare l'inserimento in Testa.

Tuttavia quando uso quest'ultimo metodo e poi vado a fare una ricerca nel trie e stampo la lista corrispondente alla stringa cercata, ottengo soltanto la stringa che vi era prima dell'Inserisci in Testa.

E' come se il puntatore alla mia lista, puntasse in maniera fissa all'elemento che avevo prima di fare Inserisci In Testa e quindi tutti gli elementi che inserisco successivamente si perdono e non vi posso più accedere. Mentre con l'Inserisci In Coda li trovo perchè li inserisco dopo l'elemento al quale posso accedere.

Però non capisco come fare a risolvere. La funzione Inserisci In Testa è corretta, se applicata su una normale lista fa quello che deve fare, ma sul mio trie non va proprio.

Come posso risolvere?


Scusate se mi sono espressa male, probabilmente senza codice sotto mano per voi è difficile giudicare, ma se poteste darmi una mano ve ne sarei grata. Se vi servono ulteriori info o pezzi di codice ve li posso postare.


Grazie ancora a tutti Embarassed
Top
Profilo Invia messaggio privato
SverX
Supervisor Macchinisti
Supervisor Macchinisti


Registrato: 25/03/02 11:16
Messaggi: 11559
Residenza: Tokelau

MessaggioInviato: 20 Mar 2014 12:05    Oggetto: Rispondi citando

Da come spieghi il malfunzionamento sembra che non aggiorni il puntatore all'inizio della lista... negli aggiornamenti in testa in effetti devi fare solo due cose (item è l'elemento, list la lista):

item.next=list;
list=&item;

vedi se per caso hai una funzione con qualche cosa passato per valore e non per indirizzo e quindi in effetti non stai facendo l'update...

Ciao
Top
Profilo Invia messaggio privato HomePage
kiara91
Mortale pio
Mortale pio


Registrato: 31/01/14 17:56
Messaggi: 20

MessaggioInviato: 20 Mar 2014 17:09    Oggetto: Rispondi

grazie per avermi risposto Smile

allora..questa è la mia funzione InserisciInTesta

Codice:
void InserisciInTesta(ListaDiElementi *lista, char *string){
  ListaDiElementi aux;
  aux=malloc(sizeof(ElementoLista));
  strcpy(aux->dato,string);
  aux->succ=*lista;
  *lista=aux;
}


E mi sembra che sia a posto. Dici di controllare se la funzione in cui la chiamo abbia gli argomenti che mi interssano passati per valore?
Ora controllo..nel frattempo..non ci sono errori nella mia funzione giusto?
Top
Profilo Invia messaggio privato
Mostra prima i messaggi di:   
Nuovo argomento   Rispondi    Indice del forum -> Programmazione Tutti i fusi orari sono GMT + 1 ora
Vai a 1, 2  Successivo
Pagina 1 di 2

 
Vai a:  
Non puoi inserire nuovi argomenti
Non puoi rispondere a nessun argomento
Non puoi modificare i tuoi messaggi
Non puoi cancellare i tuoi messaggi
Non puoi votare nei sondaggi