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
kiara91
Mortale pio
Mortale pio


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

MessaggioInviato: 31 Gen 2014 18:03    Oggetto: Aiuto linguaggio C Rispondi citando

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 Smile
Top
Profilo Invia messaggio privato
SverX
Supervisor Macchinisti
Supervisor Macchinisti


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

MessaggioInviato: 03 Feb 2014 15:48    Oggetto: Rispondi citando

Google è tuo amico... prova cercando "Tutorial programmazione C" per iniziare...

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


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

MessaggioInviato: 10 Feb 2014 01:50    Oggetto: Rispondi citando

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? Embarassed
Spero di avere il vostro aiuto, grazie Smile
Top
Profilo Invia messaggio privato
SverX
Supervisor Macchinisti
Supervisor Macchinisti


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

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

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? Shocked
Top
Profilo Invia messaggio privato HomePage
kiara91
Mortale pio
Mortale pio


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

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

grazie ancora SverX..cosa intendi per ricerca fulltext? Embarassed
Top
Profilo Invia messaggio privato
kiara91
Mortale pio
Mortale pio


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

MessaggioInviato: 11 Feb 2014 11:44    Oggetto: Rispondi citando

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
Profilo Invia messaggio privato
SverX
Supervisor Macchinisti
Supervisor Macchinisti


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

MessaggioInviato: 12 Feb 2014 11:26    Oggetto: Rispondi citando

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

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


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

MessaggioInviato: 12 Feb 2014 17:23    Oggetto: Rispondi citando

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
Profilo Invia messaggio privato
SverX
Supervisor Macchinisti
Supervisor Macchinisti


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

MessaggioInviato: 13 Feb 2014 17:03    Oggetto: Rispondi citando

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
Profilo Invia messaggio privato HomePage
kiara91
Mortale pio
Mortale pio


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

MessaggioInviato: 13 Feb 2014 17:21    Oggetto: Rispondi citando

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
Profilo Invia messaggio privato
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

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