Liste in C

C, C++, Java, ...

Liste in C

Messaggioda lcproductions » 15/11/2016, 15:54

Salve, da un po' di tempo sto smanettando con il linguaggio C.
Devo dire che mi trovo bene, tuttavia ho difficoltà a comprendere il concetto di lista e come usarla.
Da quel che ho capito, una lista è una concatenazione di "nodi".
Un nodo è una coppia formata da un valore e un puntatore.
Quando non ci sono più nodi , il puntatore dell'ultimo nodo punta a NULL.
Qualcosa del tipo :


VALORE1 | PUNTATORE1 -----> | VALORE2 | PUNTATORE2 --------> NULL

Non ho capito:
    Qual'è l'utilità di queste liste
    Come implementarle in un programma
Potreste anche farmi un'esempio di un programma, molto semplice, che utilizzi le liste?
Grazie anticipatamente a chi risponderà.
Spesso l'informatica è più un'arte che una scienza
lcproductions
Jr. Member
Jr. Member
 
Messaggi: 51
Iscritto il: 30/12/2015, 22:07

Re: Liste in C

Messaggioda _Alex_ » 02/09/2017, 9:18

Quello che hai scritto e' solo il primo tipo di lista linkata, quella semplice.
Ne esistono diverse altre:
- bidirezionale: ogni nodo ha sia il puntatore al precedente che quello al successivo
- circolare: l'ultimo nodo non punta a NULL, ma al primo
- circolare con sentinella: il primo nodo e' fittizio, non contiene dati utili e si usa per semplificare alcune operazioni di controllo

Estendendo il concetto delle liste si passa ad alberi e grafi, ma qui entriamo in argomenti da affrontare piu' avanti.

L'utilita' del concetto di lista risiede nel limite di quello di array:
quando crei un array nella memoria statica (stack) devi sapere quanto dev'essere grande prima di compilare il programma, cioe' mentre lo scrivi; con la memoria dinamica (heap) le cose vanno leggermente meglio, ma questo limite continua a farsi sentire perche' anche se puoi chiedere memoria al gestore di sistema a run-time devi comunque decidere prima quanta te ne serve, se non basta non puoi ridimensionarla, devi chiedere al gestore un altro spazio di memoria piu' grande e fare la copia della porzione che avevi chiesto prima.
Il vantaggio degli array e' che le celle di memoria che contengono i dati sono contigue, quindi l'accesso a qualsiasi cella e' molto veloce.

Nella lista linkata possiamo chiedere memoria al gestore di sistema per una singola cella a run-time, senza dover fare copie delle celle precedenti, ma perdiamo la contiguita' delle celle, per questo servono i puntatori ad ogni singola cella.

A causa della diversa struttura dati uno stesso algoritmo puo' funzionare bene su array e male su liste, o viceversa, percio' uno degli esami della facolta' di Informatica (a cui mi sono reiscritto da poco e l'ho appena superato) e' Algoritmi e Strutture Dati.

In esso si studia, appunto, una serie di algoritmi adatti a ciascuna struttura dati e come calcolare matematicamente l'efficienza degli stessi (intesa come numero di operazioni da effettuare sui dati e memoria occupata), oltre a cominciare a parlare di Information Hiding, concetto che servira' piu' avanti per la programmazione ad oggetti.

Per quanto riguarda gli esempi noi stiamo programmando in C++, non so se puo' andarti bene lo stesso.
_Alex_
Newbie
Newbie
 
Messaggi: 18
Iscritto il: 02/09/2017, 8:32
Località: Genova

Re: Liste in C

Messaggioda lcproductions » 02/09/2017, 12:55

Quindi, vediamo se ho capito:

se uso un array devo conoscere a priori la quantità di memoria che mi serve, mentre con le liste no, giusto?

Comunque si, l'esempio va bene anche in C++
Spesso l'informatica è più un'arte che una scienza
lcproductions
Jr. Member
Jr. Member
 
Messaggi: 51
Iscritto il: 30/12/2015, 22:07

Re: Liste in C

Messaggioda _Alex_ » 02/09/2017, 18:38

Esatto, ti faccio un esempio banale:
in un software come un videogame (tetris?) la mappa del livello potrebbe stare in un array bidimensionale n*m (una matrice), tanto ne conosciamo le dimensioni quando lo programmiamo, ma se volessimo trovare il MDC tra n numeri dati in input dall'utente senza conoscere n a priori non sapremmo quanto fare grande l'array e converrebbe usare le liste.

Uso il secondo esempio definendo induttivamente/ricorsivamente il MCD (non saro' rigorosissimo):
- base induttiva: il MCD di un numero solo e' se stesso, quello di 0 e' 0
- passo di induzione: il MCD di n numeri e' uguale al MCD tra il primo numero e gli n-1 numeri restanti

Grazie al passo dell'induzione possiamo reiterare il calcolo dell'MCD tra soli due numeri fino ad ottenere quello di tutti gli n insieme.

Ora vediamo i file coinvolti.

mcd.h

Codice: Seleziona tutto
// Contiene i prototipi delle nostre funzioni piu' alcune definizioni
#ifndef MCD
// Se mcd.h e' stato gia' incluso da qualche altro programma non abbiamo bisogno di reincluderlo
// quindi controlliamo l'esistenza di un token inventato da noi
#define MCD
#include <iostream>

using namespace std;
{   
    struct node
    {   
        int value;
        node *next;
    }

    typedef *node list; // La nostra lista e' il puntatore al primo valore
    list emptyList=NULL;

    bool isEmpty(list);
    void headInsert(list, list);
    int mcd(list);
}
#endif

mcd.cpp

// Contiene le funzioni vere e proprie definite in mcd.h
#include <iostream>
#include "mcd.h"

using namespace std;

bool isEmpty(list l) {
    return (l == emptyList);
}

void headInsert(list l, list n) {
    if (isEmpty(l)) {
        l = n;
        n->next = emptyList;
        return;
    }
    else {
        n->next = l;
        l = n;
    }
}

int mcd(list l)
// Contiene l'algoritmo euclideo, non la scrivo


Dentro il main dovrai includere mcd.h e fare due cicli:
- uno while per inserire i numeri finche' l'utente desidera usando la funzione headInsert
- un if che se la lista e' vuota o contiene un numero solo restituisce, rispettivamente 0 o il numero, altrimenti chiama ricorsivamente mcd su l->next.

Per effettuare cicli con la ricorsione NON servono ne' for ne' while, il ciclo lo realizza la ricorsione in se'.
_Alex_
Newbie
Newbie
 
Messaggi: 18
Iscritto il: 02/09/2017, 8:32
Località: Genova

Re: Liste in C

Messaggioda _Alex_ » 02/09/2017, 18:40

Scusate l'indentazione, l'editor delle risposte ha eliminato gli spazi e non mi faceva inserire le tabulazioni.
_Alex_
Newbie
Newbie
 
Messaggi: 18
Iscritto il: 02/09/2017, 8:32
Località: Genova

Re: Liste in C

Messaggioda marcomg » 03/09/2017, 9:30

Usa il tag
Codice: Seleziona tutto
[code][/code]
e non avrai problemi :D
P.S. Ho fatto le dovute modifiche ;)
Windows is what you open when you want fresh air from outside.
Avatar utente
marcomg
Global Moderator
Global Moderator
 
Messaggi: 5425
Iscritto il: 22/08/2011, 18:54

Re: Liste in C

Messaggioda _Alex_ » 03/09/2017, 10:42

Grazie ;)

Ne approfitto per fare una correzione ed una precisazione (ho scritto di fretta prima di uscire....):
- il prototipo della funzione headInsert va modificato passando il primo argomento (la lista vera e propria) per riferimento, altrimenti non viene inserito nulla nella lista stessa perche' il parametro sara' passato per valore e sara' una copia, non l'originale, quindi: void headInsert(list &l, list n)
- il secondo parametro l'ho passato come puntatore al nodo per semplificare il codice, ma si potrebbe passare il nodo e poi appiccicargli un puntatore dentro la funzione headInsert; questo si puo' passare sia per valore che per riferimento a scelta del programmatore, il programma funziona lo stesso, passando per riferimento risparmio memoria ed il tempo della copia, passandolo per valore qualcuno lo considera piu' safe
_Alex_
Newbie
Newbie
 
Messaggi: 18
Iscritto il: 02/09/2017, 8:32
Località: Genova

Re: Liste in C

Messaggioda lcproductions » 11/09/2017, 21:29

Vi ringrazio per i chiarimenti, ma mi sono accorto di essere parecchio arrugginito per quanto riguarda la programmazione in C, dunque mi servirebbe prima una ripassatina a struct, puntatori ecc....

Grazie ancora per le risposte
Spesso l'informatica è più un'arte che una scienza
lcproductions
Jr. Member
Jr. Member
 
Messaggi: 51
Iscritto il: 30/12/2015, 22:07


Torna a Programmazione

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite