Mi aiutate con queste cosine in C ??[HELP INSIDE]

[luckye]

Ciao,
devo fare l'esame di info di ingegneria che mi porto ormai dietro da anni.....
Ho capito tutto fino ad ora.....appunto fino ad ora.
Potete cercare di farmi capire come si usano le liste e l'allocazione dinamica della memoria malloc e il suo amico free ??

Sto cercando di fare il seguente programma:

Si implementino le strutture dati CANZONE e NODO e le opportune procedure per realizzare una lista di brani musicali. In particolare di ogni brano dovrà essere memorizzato il titolo,l?autore e la durata (in secondi). L?applicazione dovrà permettere le seguenti operazioni (realizzate tramite opportune funzioni):?inserimento di un brano in coda alla lista?rimozione del brano in cima alla lista?ricerca di un brano?inserimento di un brano (in una posizione qualsiasi)?rimozione di un brano (in una posizione qualsiasi)

BRANCOLO NEL BUIO PIU TOTALE !

[cionci]

struct canzone {
   char *titolo;
   char *autore;
   int durata;
};

struct nodo {
   struct canzone;
   struct nodo *next;
};

/*Per allocare una nuova canzone*/
struct canzone *alloca(char *titolo, char *autore, int durata)
{
   struct canzone *tmp;
   tmp = (canzone *)malloc(sizeof(canzone));
   tmp->titolo = (char *)malloc(sizeof(char)*(strlen(titolo)+1));
   tmp->autore = (char *)malloc(sizeof(char)*(strlen(autore)+1));
   strcpy(tmp->titolo, titolo);
   strcpy(tmp->autore, autore);
   tmp->durata = durata;
   return tmp;
}

/*Per deallocare una canzone - gli passo il puntatore al puntatore
per rendere NULL il puntatore anche nella funzione chiamante*/
void alloca(struct canzone **c)
{
   free((*c)->titolo);
   free((*c)->autore)
   free(*c);
   (*c) = NULL;
}


/*utilizzo*/
struct canzone *c;
c = alloca("Seek'n Destroy", "Metallica", 280);
....
....
....
dealloca(&c);

Per la lista funziona nella maniera classica...

[luckye]

Ma non bisogna controllare che la lista non sia vuota ?? se faccio un puntatore a Null si verifica un errore no ?

[cionci]

In quello che ho scritto sopra non ho trattato niente della lista (a parte la struttura)...
Per la lista funziona come qualsiasi altra lista

[luckye]

Originariamente inviato da cionci
In quello che ho scritto sopra non ho trattato niente della lista (a parte la struttura)...
Per la lista funziona come qualsiasi altra lista

mmmmm però è impestata la lista e l'allocazione dinami ci dovro sbattere

[cionci]

Le liste sono tutte uguali

[VegetaSSJ5]

cosa fa la malloc, e quindi a cosa serve? la funzione malloc ha il seguente prototipo

void * malloc (size_t size);

la funzione malloc serve a creare (o per meglio dire, riservare per l'utilizzo del programma) spazio in memoria grande quanto l'intero size (size_t consideralo come il tipo intero), e ti restituisce il puntatore alla prima cella di questa memoria che hai riservato.
per esempio se voglio riservare uno spazio in memoria dove poi andrò a mettere un intero devo chiamare la malloc scrivendo

malloc (<spazio occupato da un intero in memoria>);

poichè un programmatore non è tenuto a sapere quanto spazio in memoria occupa un intero (credo che occupi 2 byte) e anche perchè questo valore cambia in base all'architettura della macchina allora si usa quasi sempre la sizeof che è una funzione che restituisce lo spazio che occupa un certo dato o un certo tipo di dato. quindi ti consiglio di usare la malloc in questo modo:
- abbiamo detto che malloc restituisce un puntatore, quindi all'interno del programma dichiaro un puntatore (in questo esempio creo un puntatore ad intero);

   .
   .
   .
int *p;
p= (int *) malloc (sizeof(int));
   .
   .

in questo modo il puntatore p punterà ad un'area di memoria adatta a contenere un intero. se volessi invece che quest'area di memoria contenga più interi, diciamo 15, allora faccio così:

p= (int *) malloc ( 15 * sizeof(int));

credo di essere stato chiaro. capito?

la funzione free diciamo che è l'inverso della malloc: libera spazio in memoria. supponiamo che ora io debba cancellare lo spazio in memoria che prima ho allocato e che era puntato da p. il prototipo della funzione free è il seguente:

void free (void *ptr)

cioè tu devi passare a free il puntatore all'area di memoria che vuoi disallocare (si dice così?? ) che è nel nostro caso p. quindi dobbiamo fare così:

   .
   .
free(p);
   .

credo che questo sia facile o no?

ora passiamo alle liste
beh lo dice la parola stessa, una lista è una lista (sequenza) di elementi. posso benissimo creare una lista di interi, ma di solito una lista si usa per gestire ADT (tipi di dato astratti) più complicati. per descrivere, cioè per far capire al compilatore, com'è fatto un elemento della lista (cioè quali sono le cose che caratterizzano il singolo elemento), usare una struttura è il modo più semplice e intuitivo (nonchè l'unico che io conosca ). Tu vuoi creare una lista di canzoni. Ad esempio una canzone è formata dalle seguenti caratteristiche:

struct song {
   char autore[25];
   char titolo[25];
   int durata;
};
typedef struct song itemtype;

A questo punto noi non abbiamo ancora descritto la lista, ma solo cosa caratterizza un elemento. Come si nota ho scritto sotto la dichiarazione della struttura che io chiamo con itemtype (ovviamente questo nome lo scegli tu, ma è giusto per farti capire che il tipo di dato che devo manovrare è una struttura song. Devi ricordare che un elemento della lista oltre a contenere tutte le caratteristiche, cioè un elemento di tipo itemtype, deve contenere anche il puntatore all'elemento successivo. Pertanto ora diamo la definizione di un elemento della lista:

typedef struct list *ptr;
typedef struct list {
   itemtype item;
   ptr next;
};

per gestire le liste in maniere più efficiente possiamo utilizzare i puntatori ad una struttura list piuttosto che manovrare direttamente le strutture list, infatti io ho creato un puntatore alla struttura list che io chiamo *ptr. Per farti capire manovrando una struttura list si deve muovere una quantità di dati che è grossa quanto l'itemtype (per esempio 10 array di caratteri, 10 interi ecc.) più il puntatore al successivo (next). Invece se noi utilizziamo un puntatore, il computer manovrerà soltanto 2 byte (oppure 4, dipende dalla macchina), cioè il numero di byte che caratterizzano un inirizzo della memoria.

A questo punto ho solo descritto la lista, ma non ho ancora descritto alcuna funzione per inserire, togliere ecc. insomma per gestire queste lista. Ti posso scrivere qui di seguito degli esempi di funzioni che potresti utilizzare per gestire la lista. Devi innanzitutti ricordarti di creare (nel main) la lista semplicemente creando il puntatore al primo elemento con la malloc:

ptr lista1;
lista1= (struct list *) malloc (sizeof(struct list));

Quando hai creato il puntatore inizializzi a NULL la sua area di memoria con una funzione che inizializza la lista in questo modo (chiaramente quando richiami questa funzione le passi come parametro il puntaotore che hai appena creato cioè lista1):

void init_list (ptr lista) {
   *lista=NULL;
}

facile no?
Ora la funzione che ti inserisce un elemento in ultima posizione (in coda alla lista):

void insert_last (ptr lista, itemtype i) {
   ptr tmp;
   tmp=lista;
   while (*tmp!=NULL) tmp=tmp->next;
   tmp->item=i;
}

come vedi ho creato un puntatore temporaneo perchè altrimenti avrei modificato il valore di lista1 che tu avresti passato come paramettro (ricorda che è importante!). Mi sono scorso tutta la lista finchè tmp non arriva alla fine (e quindi punta a NULL) e lì inserirò l'elemento.
Rimozione del brano in cima alla lista (semplicemente scorro il puntatore di 1 posizione)

void delete_first (ptr lista) {
   lista=lista->next;
}

come vedi in questo caso non ho creato il puntatore temporaneo perchè qui era proprio mia intenzione fare in modo che il primo elemento della lista (cioè quello a cui punta lista) non sia più puntato da nessuno, e quindi modifico il puntatore alla lista.
Ora la funzione di ricerca di un brano. Chiaramente restituirà il puntatore all'elemento, in caso positivo, e restituirà NULL altrimenti:

ptr search (ptr lista, char *aut, char *nome, int lung) {
   ptr tmp;
   tmp=lista;
   while (strcmp(aut, tmp->autore) && strcmp(nome, tmp->titolo) && tmp->durata!=lung) {
      tmp=tmp->next;
      if (tmp==NULL) return NULL;
   }
   return tmp;
}

spero che abbia capito il funzionamento della funzione.
Per quanto riguarda l'inserimento e la rimozione in una posizione qualsiasi ti prego di essere più chiaro perchè non ho capito esattamente cosa vuoi fare.

Spero che ti sia stato d'aiuto, se hai dubbi facci sapere. ciao!

[luckye]

chiarissimo....... grazie mille. Ora cerco di capire meglio la traccia dell'esercizio e ti rispiego cosa devo fare.
Vsito che sei online.....

questo programma deve semplicemente calcolare il numero dei divisori........

#include <stdio.h>

int calcoladivisore(int n){

int cont,temp;
temp=n;
cont=0;

while(temp!=0)
{if((n/temp)%2==0||temp==n)
{cont++;
temp--;
}
else temp--;
}

return cont;
}

void main()
{
int numero,divisori;
numero=1;

printf("Inserire un numero: ");
scanf("%d",&numero);
divisori=calcoladivisore(numero);
printf("Il numero dei divisori e %d",divisori);

}


Mi sai dire prechè se metto 8,temp scende fino a 0 a passi di uno.....e quando (8/temp )%2==0 con temp=3 incrementa il contatore come se 8/3 abbia resto zero ???

[luckye]

Link alla traccia dell'esercizio della lista di cd musicali.....

[VegetaSSJ5]

Originariamente inviato da luckye
chiarissimo....... grazie mille. Ora cerco di capire meglio la traccia dell'esercizio e ti rispiego cosa devo fare.
Vsito che sei online.....

questo programma deve semplicemente calcolare il numero dei divisori........

#include <stdio.h>

int calcoladivisore(int n){

int cont,temp;
temp=n;
cont=0;

while(temp!=0)
{if((n/temp)%2==0||temp==n)
{cont++;
temp--;
}
else temp--;
}

return cont;
}

void main()
{
int numero,divisori;
numero=1;

printf("Inserire un numero: ");
scanf("%d",&numero);
divisori=calcoladivisore(numero);
printf("Il numero dei divisori e %d",divisori);

}


Mi sai dire prechè se metto 8,temp scende fino a 0 a passi di uno.....e quando (8/temp )%2==0 con temp=3 incrementa il contatore come se 8/3 abbia resto zero ???

boh strano lo sto provando anch'io.... cionci intervieni tu!!!!!

[luckye]

Originariamente inviato da VegetaSSJ5
boh strano lo sto provando anch'io.... cionci intervieni tu!!!!!

Madonna ho trovato un bug in qualcosa........diventerò famoso

[VegetaSSJ5]

ho riscritto il programma, questo sembra funzionare correttamente (ho fatto solo 2 prove quindi non ve lo assicuro!!!):

include <stdio.h>

int calcoladivisore (int n) {
    int cont=0, i=0;
    if (n==0) return -1;
    for (i=1; i<=n; ++i) if (!(n%i)) ++cont;
    return cont;
}

void main() {
    int numero=0, divisori=0;
    printf("Inserire un numero: ");
    scanf("%d",&numero);
    divisori=calcoladivisore(numero);
    printf("Il numero dei divisori e %d\n",divisori);
    system ("PAUSE");
}

[luckye]

ma vorrei capire xè il mio non funzionava......

[VegetaSSJ5]

l'errore secondo me era qui

if((n/temp)%2==0||temp==n)

perchè in questo caso tu fai il risultato della divisione tra n e temp e poi calcoli modulo 2. ovviamente se il risultato della divisione è un numero pari e poi fai modulo 2 questo di darà la condizione vera anche se poi effettivamente poteva esserci resto. invece avresti dovuto fare come poi io ho scritto e cioè così

if (!(n%i)) ++cont;

[Luc@s]

include <stdio.h>

int div = 0; // il num dei divis
int cnt;

int calcoladivisore (int n, int * div, int * cnt) {
if (n==0) return -1;
++div;
++cnt
return calcoladivisore(n % cnt);
}


void main() {
printf("Inserire un numero: ");
scanf("%d",&numero);
calcoladivisore(numero);
printf("Il numero dei divisori e %d\n",cnt);
system ("PAUSE");
}

[VegetaSSJ5]

Originariamente inviato da Luc@s
include <stdio.h>

int div = 0; // il num dei divis
int cnt;

int calcoladivisore (int n, int * div, int * cnt) {
if (n==0) return -1;
++div;
++cnt
return calcoladivisore(n % cnt);
}


void main() {
printf("Inserire un numero: ");
scanf("%d",&numero);
calcoladivisore(numero);
printf("Il numero dei divisori e %d\n",cnt);
system ("PAUSE");
}

preferisco usare la versione che ho scritto io, non perchè la tua sia errata, ma perchè preferisco usare quando possibile (e quando mi conviene) una versione iterativa ad una ricorsiva. Le versioni ricorsive sono molto più costose ( ma a volte più efficienti) in termini di complessità spaziale di quelle iterative, e poi la versione iterativa (almeno di questo programma) è più leggibile...

[luckye]

Originariamente inviato da VegetaSSJ5
preferisco usare la versione che ho scritto io, non perchè la tua sia errata, ma perchè preferisco usare quando possibile (e quando mi conviene) una versione iterativa ad una ricorsiva. Le versioni ricorsive sono molto più costose ( ma a volte più efficienti) in termini di complessità spaziale di quelle iterative, e poi la versione iterativa (almeno di questo programma) è più leggibile...

Direi che in effetti quest'ultima è leggibile
Il programma stupidissimo cioè questo dei divisori,l'avevo fatto per provare una cosa.......fatto sta che non funzionava e estratto il pezzo di codice sopra mi ero reso conto di quel problema.

Ora spiegami...... ma quando dichiaro una lista.....il c sa già che è tale ? non riesco a capire il suo funzionamento.Mi sembra una struct.......con quel *next che boh.....non capisco......

cioè prima l'inizializzo come variabile globale a null giusto ?? dopodiche devo ricordarmi di creare un'inizio e una fine.....
non mi è chiara.........

[VegetaSSJ5]

Originariamente inviato da luckye
Direi che in effetti quest'ultima è leggibile
Il programma stupidissimo cioè questo dei divisori,l'avevo fatto per provare una cosa.......fatto sta che non funzionava e estratto il pezzo di codice sopra mi ero reso conto di quel problema.

Ora spiegami...... ma quando dichiaro una lista.....il c sa già che è tale ? non riesco a capire il suo funzionamento.Mi sembra una struct.......con quel *next che boh.....non capisco......

cioè prima l'inizializzo come variabile globale a null giusto ?? dopodiche devo ricordarmi di creare un'inizio e una fine.....
non mi è chiara.........

premetto che questa sarà la mia ultima risposta sul forum di questa settimana (tornerò nel week end) quindi non penate troppo per la mia assenza...

cosa intendi per "ma quando dichiaro una lista... il c sa già che è tale?" allora ti ripeto brevemente il concetto. tu hai creato la struttura song, e questo è il tuo (io lo chiamo così) itemtype, cioè il "tipo" che caratterizza il singolo elemento della lista. tuttavia devi ricordare che per creare una lista c'è bisogno di specificare SIA l'itemtype, ovvero la struttura song, SIA il puntatore all'elemento successivo, e cioè ptr *next. Se tu non hai questo puntatore, come faresti ad accedere all'elemento successivo della lista? Questa è la caratteristica principale della lista. Invece di essere una struttura dati indicizzata (che si scorre tramite indice, come un array), la lista si scorre tramite i puntatori agli elementi successivi. Poi ci sono altre strutture dati simili come le code, gli alberi ecc. che possono avere anche più di un puntatore, ad es. la coda ha un puntatore alla testa e un puntatore alla coda. Spero di essere stato chiaro. Riassumo:

struct song {
   char autore[25];
   char titolo[25];
   int durata;
};
typedef struct song itemtype;

typedef struct list *ptr;
typedef struct list {
   itemtype item;
   ptr next;
};

[VegetaSSJ5]

Originariamente inviato da luckye
cioè prima l'inizializzo come variabile globale a null giusto ?? dopodiche devo ricordarmi di creare un'inizio e una fine.....
non mi è chiara.........

allora cerchiamo di chiarire un attimo i concetti. so che è difficile ad apprenderli per la prima volta visto che anch'io ci ho sbattuto la testa perchè avevo una prof che spiegava mezzo libro a lezione... .
allora tu nel main del programma per creare una lista ti devi creare il puntatore all'inizio della lista (come ti ho detto la lista non ha il puntatore alla fine della lista, però questa è una caratteristica che volendo ci si può aggiungere tranquillamente). per creare questo puntatore all'inizio della lista fai così:

ptr lista1;
lista1= (struct list *) malloc (sizeof(struct list));

chiaramente nello stesso main puoi creare quante liste vuoi. poi alle funzioni di gestione sarai tu a passare come parametro la lista che vuoi manipolare. chiaramente se te ne serve una sola puoi anche crearla come variabile globale (almeno credo che si possa fare).
una volta creato il puntatore all'inizio della lista richiami la funzione init_list che semplicemente inizializza a NULL il puntatore (NULL sarà per noi come un segnale di fine lista). ogni volta che vorrai aggiungere un alemento in lista richiamerai la funzione insert_last che ti inserisce l'elemento in ultima posizione (o per lo meno, alla prima posizione == NULL). ricorda che per inserire un elemento in lista devi prima creare una nuova canzone (e quindi un nuovo oggetto di tipo struct song, oppure itemtype, che dir si voglia). io non ti ho scritto prima la funzione ma potrebbe essere una cosa del genere:

itemtype make_song (ptr lista, char *nome, char *aut, int lung) {
   itemtype new;
   strncpy (new.titolo, nome, 25);
   strncpy (new.autore, aut, 25);
   new.durata= lung;
   // insert_last (lista, new);
   return new;
}

come hai visto puoi decidere se richiamare la funzione di inserimento in lista all'interno della funzione make_song, oppure se inserirlo in seguito.

[luckye]

Siete davvero gentilissimi.......so di essere un pò ritardato su questi argomenti ma penso che infondo non siano poi tanto semplici.

Io pensavo che come dichiaravi un' array,con il c dichiarando una lista fosse già bella è pronta di dimesione scelta dalla malloc. Invece bisogna fare tutto manuale.....