NGI.Home > Forum
  EOLO HOME  OFFERTE INTERNET WIRELESS EOLO  FORMULA ADSL
   
   
WEBMAIL
   
 
  > Register  
  > FAQ  
  > Members List  
 
  > Calendar  
  > Today's Posts  
   
 

Go Back   NGI Forum > Tech & Tech > Developer's Zone

Reply
 
Thread Tools Rate Thread
Old 27th January 2011, 11:09   #1
Arësius
Soft computer
 
Arësius's Avatar
 
Join Date: Feb 2000
Posts: 67,351
[Impariamo il C] Lezione 14

Buongiorno.

Nelle puntate precedenti del corso collaborativo di programmazione:
  1. installazione dell'IDE, cenni di architettura degli elaboratori
  2. sintassi del C, programmazione strutturata
  3. ancora sulla sintassi, i tipi di dato, le variabili
  4. variabili parte seconda: gli array
  5. introduzione delle funzioni
  6. operatori aritmetici e logici
  7. costrutti di selezione
  8. costrutti di iterazione
  9. ancora sull'iterazione
  10. array multipli e struct
  11. ricorsione
  12. ancora ricorsione, memoria (record attivazione, heap, stack, ecc), introduzione dei puntatori
  13. Le liste e l'allocazione di memoria (malloc)
In questo capitolo:
  • primi accenni all'analisi dei costi asintotici
  • ancora sulle liste

Primi accenni all'analisi dei costi asintotici

Nella lezione precedente abbiamo visto il concetto di lista, definita ricorsivamente come una struttura formata da un valore e un puntatore ad una lista.

Abbiamo osservato che, per raggiungere il valore n-esimo di una lista, dobbiamo

1) posizionarci sulla testa della lista
2) eseguire n salti di elemento

Questo che conseguenze ha? Beh, prima di tutto che, a differenza degli array grazie ai quali potevamo accedere all'elemento n facendo

Code:
elemento[ n ]
quì sono necessari n salti. Anche senza aver studiato informatica teorica, ci rendiamo conto che è una operazioni molto più "costosa" in termini di operazioni, e sappiamo che ogni operazione consuma dei cicli di macchina. Anche se il processore è molto veloce, sono comunque n operazioni contro una.

E se la lista fosse lunga un miliardo di elementi e volessimo leggere l'ultimo? ci metteremmo un miliardo di operazioni per leggerlo! Con un processore ad 1GHz, avendo tutta la potenza a disposizione impiegheremmo un secondo per dare la risposta, mentre un array ce la darebbe in un miliardesimo di secondo!

Dovreste dunque intuire che riveste grande importanza la scelta della struttura dati che utilizziamo per risolvere i nostri problemi informatici. In particolare, nella disciplina nota come analisi della complessità algoritmica, è importante studiare come si comporta un algoritmo in funzione della dimensione del suo input.

Dunque, se io volessi fare un programma che legge un miliardo di dati e mi stampa l'ultimo, probabilmente non userei un algoritmo che coinvolge una lista e la sua scansione lineare, perché impiegherei un fracco di tempo; molto meglio un array che ci mette UN solo passaggio.

Per usare la terminologia informatica, si dice che "nel caso peggiore la lista ha un tempo di accesso pari alla dimensione della lista stessa". Questa cosa viene scritta in maniera formale con la notazione "o grande":

O(n)

ovvero "se la lista è lunga n, ci mette al massimo n operazioni". Si osservi che "O grande" è un tetto massimo ovvero, a meno di non aver fatto fesserie nel codice, non dovremmo impiegare più tempo di così. Nel caso dell'array, sappiamo che l'accesso è esattamente pari ad una sola operazione. In questo caso si usa la notazione "theta":

Θ(1)

cioè stavolta sappiamo che ci vuole almeno e al più una operazione. E' una informazione più forte di quella precedente, che non si ricava molto spesso nel design di algoritmi. Infine, se avessimo una lista di caratteri e volessimo togliere le vocali, quanto tempo ci vorrebbe almeno? Beh, quantomeno dovremmo scorrere tutti gli elementi della lista, per vedere se ci sono!, dunque avremmo un limite inferiore di operazioni. Viene detta notazione "omega":

Ω(n)

Cercate di fissare in mente il senso intuitivo di queste notazioni (molto, molto semplificate), perché man mano che vedremo le strutture dati basilari cercheremo di ragionare anche sui loro costi asintotici, in modo da saper scegliere la struttura dati più adeguata al problema in esame.


Ancora sulle liste
Uno degli esercizi della scorsa lezione - che purtroppo, finora, nessuno ha affrontato - era la cancellazione di un elemento dalla lista.

Cosa significa, in generale, cancellare un elemento da una lista? Significa che l'elemento precedente deve puntare a quello successivo!



Nell'esempio in figura, abbiamo cancellato il nodo della lista con valore "B". Vediamo il codice:

Code:
#include <stdio.h>
#include <stdlib.h>   /* su alcuni compilatori è necessaria per malloc */


// struttura Lista
struct Lista {
    char Valore;
    struct Lista* Next;
};


// scorri la lista, rimuovi i valori uguali al carattere passato come parametro
void rimuovi_valore_dalla_lista( struct Lista* posizione, char c ) {

  struct Lista* prossimo;

  do {

    prossimo = posizione->Next;

    if ( prossimo->Valore == c ) {
        posizione->Next = prossimo->Next;
        return;
    }

    posizione = prossimo;

  } while ( posizione->Next != NULL );

};


// scorri la lista e stampa il contenuto
void stampa_lista( struct Lista* p ) {
    while (p->Next != NULL ) {
        printf("%c", p->Valore);
        p = p->Next;
    }
};



int main () {

  char* stringa = "ABCDBE";
  int i;


  // primo nodo
  struct Lista* node = ( struct Lista* ) malloc ( sizeof( struct Lista ) );
  node->Valore = stringa[0];
  node->Next = NULL;


  // creo puntatori
  struct Lista* posizione = node;
  struct Lista* testa = node;


  // alloco resto della lista
  for (i=1; i<7; i++) {

    // nuovo nodo
    node = ( struct Lista* ) malloc ( sizeof( struct Lista ) );

    // appendo nuovo elemento
    posizione->Next = node;

    // setto valori nuovo elemento
    node->Valore = stringa[i];
    node->Next = NULL;

    // aggiorno posizione e itero
    posizione = node;
  }


  rimuovi_valore_dalla_lista( testa, 'B' );

  stampa_lista( testa );

  return 0;

};
Come si può immaginare, la cancellazione di un elemento nel caso peggiore richiede di scorrere tutta la lista (perché potrebbe essere l'utimo!). Dunque, impiega O(n).


Esercizio 1: provate a pensare ad un algoritmo per inserire un elemento della lista in una posizione qualsiasi (senza sovrascrivere valori: se ad esempio ho una lista 1->2->4 e inseririsco "3" in posizione 2, devo ottenere 1->2->3->4).


Esercizio 2: il mio codice ha un bug, se il carattere da rimuovere è in prima posizione lo ignora. Come si può fixare questo increscioso malfunzionamento?


Esercizio 3 (teorico, difficile): al di là delle limitazioni di spazio, come si gestirebbe l'inserimento di un valore in un array normale? che costo asintotico avrebbe l'algoritmo?
Attached Images
File Type: png Singly_linked_list_delete_after.png (2.5 KB, 330 views)
__________________
Lode a Bacco, in saecula saeculorum.
Emergent

Last edited by Arësius; 27th January 2011 at 15:44.
Arësius is offline   Reply With Quote
Old 27th January 2011, 14:48   #2
uizz
Registered User
 
uizz's Avatar
 
Join Date: Jan 2010
Posts: 513
Grande Ares^^

ti dico già che nel metodo rimuovi_valore hai messo return dopo aver rimosso la prima occorrenza del valore, il che non permette al metodo di rimuovere anche le ricorrenze successive
uizz is offline   Reply With Quote
Old 27th January 2011, 15:38   #3
Arësius
Soft computer
 
Arësius's Avatar
 
Join Date: Feb 2000
Posts: 67,351
lo so, ce l'ho messo perché volevo cancellare UN elemento ^^

però bravo che hai perfettamente inteso la logica.
__________________
Lode a Bacco, in saecula saeculorum.
Emergent

Last edited by Arësius; 27th January 2011 at 15:45.
Arësius is offline   Reply With Quote
Old 27th January 2011, 16:09   #4
Pier4R
Ex falso quodlibet
 
Pier4R's Avatar
 
Join Date: Jul 2004
Location: equgpbc.r2.Frisia
Posts: 18,664
sono alla dieci, per oggi conto di arrivare alla 12 (si vedono le mod sul wiki), intanto approvo la prosecuzione!!! (mi piace il corso, cerca di essere autocostruente alla Euclide. I corsi non corposi all'uni, invece, lasciano in sospeso ventordici dubbi).
__________________
Ngi the e.FlameeXperience .Fe ! ngi.agorà@twitter (sottoscrivi per essere incluso)
You must play online: warSow EnemyTerritory + etpro quake 4 + q4max & quake 3 + cpma & quakelive Teeworlds! hoi2series

Ringrazio i grammar nazi che mi fanno comprendere gli errori ; my.IL
; lettere porno
Pier4R is offline   Reply With Quote
Old 29th January 2011, 10:59   #5
Pier4R
Ex falso quodlibet
 
Pier4R's Avatar
 
Join Date: Jul 2004
Location: equgpbc.r2.Frisia
Posts: 18,664
Allora qui c'è spoilerato l'esercizio sulla lista che volevo fare (asd, poi quando finisco voglio compararlo con la lista che avevo fatto in object pascal per vedere le differenze c-pascal, per ora sembran poche ) quindi prima faccio l'esercizio della lez13 poi uppo la lez14
__________________
Ngi the e.FlameeXperience .Fe ! ngi.agorà@twitter (sottoscrivi per essere incluso)
You must play online: warSow EnemyTerritory + etpro quake 4 + q4max & quake 3 + cpma & quakelive Teeworlds! hoi2series

Ringrazio i grammar nazi che mi fanno comprendere gli errori ; my.IL
; lettere porno
Pier4R is offline   Reply With Quote
Old 29th January 2011, 19:32   #6
Pier4R
Ex falso quodlibet
 
Pier4R's Avatar
 
Join Date: Jul 2004
Location: equgpbc.r2.Frisia
Posts: 18,664
Esercizio 1: provate a pensare ad un algoritmo per inserire un elemento della lista in una posizione qualsiasi (senza sovrascrivere valori: se ad esempio ho una lista 1->2->4 e inseririsco "3" in posizione 2, devo ottenere 1->2->3->4).

credo di averlo fatto qui: http://learn2code.talk4fun.net/doku....und:playground

però non compila


Esercizio 2: il mio codice ha un bug, se il carattere da rimuovere è in prima posizione lo ignora. Come si può fixare questo increscioso malfunzionamento?

Spoiler:

Code:
/ struttura Lista
struct Lista {
    char Valore;
    struct Lista* Next; //le variabili a lettere maiuscole funzionano?
};
 
struct Lista* testa; 
  //modifica, altrimenti non saprei come passare il puntatore (e non l'indirizzo memorizzato nel puntatore)
  //alla funzione. Si, potrei fare &testa , ma in che tipo di dato dovrei memorizzarlo? Un int (indirizzo a 32 bit) ?
  //i puntatori generici non li conosco!
 
// scorri la lista, rimuovi i valori uguali al carattere passato come parametro
void rimuovi_valore_dalla_lista( struct Lista* posizione, char c ) {
  //oss: ma non cancella davvero!!!! Voglio saperlo fare!
 
  //posizione è pari a testa
  if (posizione->Valore == c){
    testa = posizione->Next;
    cancellaInQualcheModo(posizione);
    return;
  }
 
  struct Lista* prossimo;
 
  do {
 
    prossimo = posizione->Next;
 
    if ( prossimo->Valore == c ) {
        posizione->Next = prossimo->Next;
        return;
    }
 
    posizione = prossimo;
 
  } while ( posizione->Next != NULL );
 
};
 
 
// scorri la lista e stampa il contenuto
void stampa_lista( struct Lista* p ) {
    while (p->Next != NULL ) {
        printf("%c", p->Valore);
        p = p->Next;
    }
};
 
 
 
int main () {
 
  char* stringa = "ABCDBE";
  int i;
 
 
  // primo nodo
  struct Lista* node = ( struct Lista* ) malloc ( sizeof( struct Lista ) );
  node->Valore = stringa[0];
  node->Next = NULL;
 
 
  // creo puntatori
  struct Lista* posizione = node;
  testa = node;
 
 
  // alloco resto della lista
  for (i=1; i<7; i++) {
 
    // nuovo nodo
    node = ( struct Lista* ) malloc ( sizeof( struct Lista ) );
 
    // appendo nuovo elemento
    posizione->Next = node;
 
    // setto valori nuovo elemento
    node->Valore = stringa[i];
    node->Next = NULL;
 
    // aggiorno posizione e itero
    posizione = node;
  }
 
 
  rimuovi_valore_dalla_lista( testa, 'B' );
 
  stampa_lista( testa );
 
  return 0;
 
};



Esercizio 3 (teorico, difficile): al di là delle limitazioni di spazio, come si gestirebbe l'inserimento di un valore in un array normale? che costo asintotico avrebbe l'algoritmo?
Spoiler:

se sovrascrivo e me ne frego: theta di 1 in termini di numero di posizioni.
__________________
Ngi the e.FlameeXperience .Fe ! ngi.agorà@twitter (sottoscrivi per essere incluso)
You must play online: warSow EnemyTerritory + etpro quake 4 + q4max & quake 3 + cpma & quakelive Teeworlds! hoi2series

Ringrazio i grammar nazi che mi fanno comprendere gli errori ; my.IL
; lettere porno
Pier4R is offline   Reply With Quote
Old 31st January 2011, 16:55   #7
uizz
Registered User
 
uizz's Avatar
 
Join Date: Jan 2010
Posts: 513
L'esercizio 2 mi sta facendo impazzire
uizz is offline   Reply With Quote
Old 7th February 2011, 10:21   #8
Pier4R
Ex falso quodlibet
 
Pier4R's Avatar
 
Join Date: Jul 2004
Location: equgpbc.r2.Frisia
Posts: 18,664
ma ci siamo bloccati?
__________________
Ngi the e.FlameeXperience .Fe ! ngi.agorà@twitter (sottoscrivi per essere incluso)
You must play online: warSow EnemyTerritory + etpro quake 4 + q4max & quake 3 + cpma & quakelive Teeworlds! hoi2series

Ringrazio i grammar nazi che mi fanno comprendere gli errori ; my.IL
; lettere porno
Pier4R is offline   Reply With Quote
Old 7th February 2011, 10:31   #9
Arësius
Soft computer
 
Arësius's Avatar
 
Join Date: Feb 2000
Posts: 67,351
scusate, periodo esami domani sera ci do una sbirciata promesso!
__________________
Lode a Bacco, in saecula saeculorum.
Emergent
Arësius is offline   Reply With Quote
Old 8th February 2011, 23:10   #10
[En][gma]
Registered User
 
[En][gma]'s Avatar
 
Join Date: Dec 2001
Posts: 2,929
io un po' bloccato si, ma arriverò spero presto ^^
tanto so già che partiranno pagine di roba che non ho capito asd!!
__________________
.: NoS - Nitrous Oxide System :.
[En][gma] is offline   Reply With Quote
Old 20th February 2011, 14:53   #11
Pier4R
Ex falso quodlibet
 
Pier4R's Avatar
 
Join Date: Jul 2004
Location: equgpbc.r2.Frisia
Posts: 18,664
up up up up up
__________________
Ngi the e.FlameeXperience .Fe ! ngi.agorà@twitter (sottoscrivi per essere incluso)
You must play online: warSow EnemyTerritory + etpro quake 4 + q4max & quake 3 + cpma & quakelive Teeworlds! hoi2series

Ringrazio i grammar nazi che mi fanno comprendere gli errori ; my.IL
; lettere porno
Pier4R is offline   Reply With Quote
Old 13th March 2011, 17:46   #12
Pier4R
Ex falso quodlibet
 
Pier4R's Avatar
 
Join Date: Jul 2004
Location: equgpbc.r2.Frisia
Posts: 18,664
are... secondo te io mi scordo!? Magari sei ancora impegnato, ma io sono qui!
__________________
Ngi the e.FlameeXperience .Fe ! ngi.agorà@twitter (sottoscrivi per essere incluso)
You must play online: warSow EnemyTerritory + etpro quake 4 + q4max & quake 3 + cpma & quakelive Teeworlds! hoi2series

Ringrazio i grammar nazi che mi fanno comprendere gli errori ; my.IL
; lettere porno
Pier4R is offline   Reply With Quote
Old 14th March 2011, 16:19   #13
Arësius
Soft computer
 
Arësius's Avatar
 
Join Date: Feb 2000
Posts: 67,351
sono ancora in ballo con gli esami non ho un minuto libero cazz
__________________
Lode a Bacco, in saecula saeculorum.
Emergent
Arësius is offline   Reply With Quote
Reply

Bookmarks

Thread Tools
Rate This Thread
Rate This Thread:

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT +2. The time now is 20:45.


Powered by vBulletin® Version 3.8.6
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
Copyright 1998-2014 by NGI SpA