Precedente :: Successivo |
Autore |
Messaggio |
kiara91 Mortale pio
Registrato: 31/01/14 17:56 Messaggi: 20
|
Inviato: 31 Gen 2014 18:03 Oggetto: Aiuto linguaggio C |
|
|
Ciao a tutti, ho trovato questo forum cercando un aiuto in rete per un progetto di informatica (precisamente si algoritmi) che devo svolgere in linguaggio C.
Ovviamente non chiedo che qualcuno lo faccia al posto mio, ma avendo basi abbastanza scarse di programmazione vorrei chiedervi se potreste darmi una mano a procedere un po' alla volta.
Se è possibile e qualcuno ha voglia di aiutarmi vi sarei grata infinitamente e potrei iniziare a postare il testo del progetto e un po' di idee/dubbi che avevo a riguardo.
Grazie a tutti |
|
Top |
|
|
SverX Supervisor Macchinisti
Registrato: 25/03/02 11:16 Messaggi: 11594 Residenza: Tokelau
|
Inviato: 03 Feb 2014 15:48 Oggetto: |
|
|
Google è tuo amico... prova cercando "Tutorial programmazione C" per iniziare...
|
|
Top |
|
|
kiara91 Mortale pio
Registrato: 31/01/14 17:56 Messaggi: 20
|
Inviato: 10 Feb 2014 01:50 Oggetto: |
|
|
Grazie SverX..ho trovato con google una guida. L'ho studiata qualche giorno e ho ripreso confidenza con alcune cose che avevo dimenticato, in particolare con le liste che penso siano la struttura più adeguata a svolgere il mio progetto.
Infatti quello che dovrei fare è memorizzare dei dati contenuti in un file in modo tale da poter fare ricerche su questi dati.
Supponiamo che il file su cui devo lavorare (non è così ma vorrei semplificare un po' la spiegazione) contiene 2 classi di oggetti, diciamo Titoli di libri e Argomenti trattati. Ad ogni Titolo è associata una serie di Argomenti trattati all'interno di quel libro.
Voglio costruire un programma in C che prendendo in input il nome di un argomento mi dia in output i titoli dei libri in cui è trattato e viceversa prendendo in input un libro mi dia in output gli argomenti trattati al suo interno.
La struttura di dati che penso possa essere la più idonea (ma correggetemi se sbaglio perchè ancora non sono molto pratica) è un dizionario. Il file è di grandi dimensioni e vorrei chiedervi qualche suggerimento su come implementare questa struttura.
Dunque quello intendo fare è:
- aprire il file con fopen
- attraverso fgets memorizzare tutti i titoli dei libri in una lista di liste
--(ogni elemento della lista sarà una lista che contiene nel primo campo il Titolo del libro e nei successivi gli argomenti trattati)
E' la strada giusta o mi sto perdendo?
Spero di avere il vostro aiuto, grazie |
|
Top |
|
|
SverX Supervisor Macchinisti
Registrato: 25/03/02 11:16 Messaggi: 11594 Residenza: Tokelau
|
Inviato: 10 Feb 2014 10:18 Oggetto: |
|
|
Sì, direi che per memorizzare i titoli e gli argomenti va bene una lista multipla, ovvero una lista semplice con i titoli dove ogni elemento è la testa di una lista di argomenti correlati (qui c'è uno schema, in questo caso le liste sono addirittura bidirezionali, tu magari non ne hai bisogno...)
Per il dizionario... vuoi fare una ricerca fulltext? |
|
Top |
|
|
kiara91 Mortale pio
Registrato: 31/01/14 17:56 Messaggi: 20
|
Inviato: 10 Feb 2014 12:59 Oggetto: |
|
|
grazie ancora SverX..cosa intendi per ricerca fulltext? |
|
Top |
|
|
kiara91 Mortale pio
Registrato: 31/01/14 17:56 Messaggi: 20
|
Inviato: 11 Feb 2014 11:44 Oggetto: |
|
|
Rieccomi, prima di procedere vorrei chiarirmi un dubbio riguardante alcune operazioni sulle liste.
Ho definito il tipo lista in questo modo
Codice: | struct EL {
int dato;
struct EL *succ;
}; |
dopodichè ho creato una funzione InserisciInCoda che agisce nel modo ovvio
Codice: | void InserisciInCoda(ListaDiElementi *lista, int x){
ListaDiElementi aux;
ListaDiElementi ultimo;
aux=malloc(sizeof(ElementoLista));
aux->dato=x;
aux->succ=NULL;
if(*lista==NULL) *lista=aux;
else {
ultimo=*lista;
while(ultimo->succ!=NULL) {
ultimo=ultimo->succ;
}
ultimo->succ=aux;
} |
Quello che mi chiedo è perchè se uso la malloc funziona mentre se non la uso e implemento la funzione in questo modo
Codice: | void InserisciInCoda(ListaDiElementi *lista, int x){
ListaDiElementi aux;
ListaDiElementi ultimo;
ElementoLista EL;
aux=⪙
aux->dato=x;
aux->succ=NULL;
if(*lista==NULL) *lista=aux;
else {
ultimo=*lista;
while(ultimo->succ!=NULL) {
ultimo=ultimo->succ;
}
ultimo->succ=aux;
} |
non funziona più..
Sarò stupida ma davvero non riesco a capire..la memoria la alloco ugualmente definendo la variabile EL giusto? Allora perchè non va?+
Grazie ancora a tutti |
|
Top |
|
|
SverX Supervisor Macchinisti
Registrato: 25/03/02 11:16 Messaggi: 11594 Residenza: Tokelau
|
Inviato: 12 Feb 2014 11:26 Oggetto: |
|
|
con "fulltext" si intende quando vuoi cercare una parola (o un set di parole) all'interno dei testi di alcuni/tutti i campi testo di un archivio... se devi fare una cosa di questo tipo allora sì, ti serve un dizionario, e un indice fulltext.
il problema di non usare la malloc() è dovuto al fatto che se definisci una variabile all'interno di una funzione, questo spazio è allocato nello stack, e viene liberato quando la funzione termina. Malloc invece alloca nello heap e la deallocazione è SOLO manuale.
un piccolo consiglio: se non hai il vincolo di rispettare l'ordine, fai inserimenti in TESTA e non in coda alla lista. E' molto più facile e veloce O(1).
|
|
Top |
|
|
kiara91 Mortale pio
Registrato: 31/01/14 17:56 Messaggi: 20
|
Inviato: 12 Feb 2014 17:23 Oggetto: |
|
|
Benissimo:) Mi hai fatto capire finalmente cosa non andava..quanto alla ricerca fulltext, sinceramente non saprei..
Il mio file è fatto così:
Titolo1......................Argomento1
................................Argomento2
................................Argomento3
................................Argomento4
................................Argomento5
................................Argomento6
................................Argomento7
................................Argomento8
Titolo2.......................Argomentox
................................Argomentoy
................................Argomentoz
................................Argomentov
................................Argomentou
................................Argomentow
Titolo3.......................Argomentoi
................................Argomentoj
................................Argomentok
................................Argomentoh
................................Argomentop
................................Argomentoq
................................Argomentor
................................Argomentos
dove al posto dei puntini ci sono dei TAB. Una volta che ho memorizzato i miei dati nella mia 'lista di liste' (o conviene un array di liste?) non posso semplicemente (quando ricevo un input tramite scanf) fare un
Codice: | for(i=0;i<MAX_SIZE;I++){
if(strcmp(Array[i]->Titolo,Stringa_letta_in_input)==0){
Stampa_Lista_Argomenti;
exit(1)}
} |
?
Ovviamente supponendo di aver memorizzato i dati in un array di liste Array[MAX_SIZE] e con opportuni aggiustamenti del codice.
Un ultima cosa: mi viene richiesto di fare in modo che digitando le prime 3 lettere che compongono il nome del Titolo o dell'Argomento il programma mi suggerisca tutte le corrispondenze idonee. Mi viene suggerito (ma non è obbligatorio) l'uso della struttura di dati Trie che da quello che ho letto dovrebbe aver a che fare con gli alberi. Posso evitare di usarla e utilizzare più semplicemente la funzione strncmp che confronta le liste in base ai primi n caratteri?
Grazie ancora e scusate se mi dilungo troppo! |
|
Top |
|
|
SverX Supervisor Macchinisti
Registrato: 25/03/02 11:16 Messaggi: 11594 Residenza: Tokelau
|
Inviato: 13 Feb 2014 17:03 Oggetto: |
|
|
chiaro che se la tua chiave di ricerca è identica al valore cercato, fare una strcmp su qualunque valore è più che sufficiente...
per la ricerca di sotto-stringhe di 3 caratteri, puoi usare strncmp (nota la n in mezzo...) però se l'esercizio suggerisce gli alberi (tree) forse dovresti usare quelli... |
|
Top |
|
|
kiara91 Mortale pio
Registrato: 31/01/14 17:56 Messaggi: 20
|
Inviato: 13 Feb 2014 17:21 Oggetto: |
|
|
Grazie ancora SverX..aspetto sempre con impazienza le tue risposte..si penso di usare questi alberi trie..non dovrebbe essere molto più complicato delle liste..ma se hai qualche suggerimento particolare su come implementarli sono tutta orecchie..
In particolare dovrebbero essere degli alberi k-ari (ovvero ogni nodo ha k figli eventualmente 'nulli' e dove k è il numero di lettere dell'alfabeto che voglio usare) che potrei implementare così
Codice: |
struct EL {
char valore;
struct Nodo *figli[k];
};
typedef struct EL Nodo_trie;
typedef trie *Nodo_trie;
|
potrebbe andare?
Nel frattempo ho provveduto ad analizzare il mio file ed ora riesco a isolare titoli e argomenti e a copiarli ad esempio in array di stringhe del tipo argomenti[DIM] e titoli[DIM]..ovviamente ho fatto questo giusto per vedere se riuscivo a manipolare i dati che avevo nel file dato che non avevo mai fatto nulla del genere prima d'ora (e non so se questi array mi serviranno davvero in seguito) comunque una volta fatto questo posso incasellare le stringhe (titoli e argomenti) dove voglio..
Che ne dici?
Grazie della pazienza che hai nei confronti di una studentessa ignorante in materia:( |
|
Top |
|
|
SverX Supervisor Macchinisti
Registrato: 25/03/02 11:16 Messaggi: 11594 Residenza: Tokelau
|
Inviato: 14 Feb 2014 16:01 Oggetto: |
|
|
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! |
|
Top |
|
|
kiara91 Mortale pio
Registrato: 31/01/14 17:56 Messaggi: 20
|
Inviato: 14 Feb 2014 17:07 Oggetto: |
|
|
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 |
|
|
SverX Supervisor Macchinisti
Registrato: 25/03/02 11:16 Messaggi: 11594 Residenza: Tokelau
|
Inviato: 14 Feb 2014 21:00 Oggetto: |
|
|
'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
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... |
|
Top |
|
|
kiara91 Mortale pio
Registrato: 31/01/14 17:56 Messaggi: 20
|
Inviato: 16 Feb 2014 18:31 Oggetto: |
|
|
Eccomi, scusa l'assenza
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! |
|
Top |
|
|
SverX Supervisor Macchinisti
Registrato: 25/03/02 11:16 Messaggi: 11594 Residenza: Tokelau
|
Inviato: 16 Feb 2014 18:53 Oggetto: |
|
|
innanzitutto se fai un assegnamento stai cambiando il valore di un punatatore, non stai copiando una stringa in un altra. Ovvero
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 |
|
|
kiara91 Mortale pio
Registrato: 31/01/14 17:56 Messaggi: 20
|
Inviato: 16 Feb 2014 19:06 Oggetto: |
|
|
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 |
|
Top |
|
|
SverX Supervisor Macchinisti
Registrato: 25/03/02 11:16 Messaggi: 11594 Residenza: Tokelau
|
Inviato: 16 Feb 2014 19:21 Oggetto: |
|
|
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
|
|
Top |
|
|
kiara91 Mortale pio
Registrato: 31/01/14 17:56 Messaggi: 20
|
Inviato: 16 Feb 2014 19:33 Oggetto: |
|
|
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 |
|
|
SverX Supervisor Macchinisti
Registrato: 25/03/02 11:16 Messaggi: 11594 Residenza: Tokelau
|
Inviato: 16 Feb 2014 20:56 Oggetto: |
|
|
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? |
|
Top |
|
|
kiara91 Mortale pio
Registrato: 31/01/14 17:56 Messaggi: 20
|
Inviato: 16 Feb 2014 21:52 Oggetto: |
|
|
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 |
|
|
|