[C] Liste concatenate
Salve, sto studiando C per l'esame della facoltà alla quale sono iscritto.
Sono arrivato all'ultimo capitolo, che riguarda le Strutture.
Ebbene in questo capitolo c'è un paragrafo dedicato alle liste concatenate e concetti simili che non riesco proprio a capire!
Tra l'altro su internet non si riesce a trovare molto a riguardo.
Sapresti spiegarmi il concetto?
Conto nel vostro aiuto, grazie!
Sono arrivato all'ultimo capitolo, che riguarda le Strutture.
Ebbene in questo capitolo c'è un paragrafo dedicato alle liste concatenate e concetti simili che non riesco proprio a capire!
Tra l'altro su internet non si riesce a trovare molto a riguardo.
Sapresti spiegarmi il concetto?
Conto nel vostro aiuto, grazie!
Risposte
qui ( http://www.macs.hw.ac.uk/~rjp/Coursewww ... klist.html ) trovi qualcosa di basico sulle linked list in C.
In due parole, in C, una lista è una strutura che contiene il dato e un puntatore al prossimo elemento della lista(che ha sua volta avrà la suddetta forma).
E un modo per implementare vettori "infiniti".
Se serve altro, sempre a disposizione.
In due parole, in C, una lista è una strutura che contiene il dato e un puntatore al prossimo elemento della lista(che ha sua volta avrà la suddetta forma).
E un modo per implementare vettori "infiniti".
Se serve altro, sempre a disposizione.
"Luc@s":
qui ( http://www.macs.hw.ac.uk/~rjp/Coursewww ... klist.html ) trovi qualcosa di basico sulle linked list in C.
In due parole, in C, una lista è una strutura che contiene il dato e un puntatore al prossimo elemento della lista(che ha sua volta avrà la suddetta forma).
E un modo per implementare vettori "infiniti".
Se serve altro, sempre a disposizione.
Credo di aver capito qualcosa in più.
Scusa se rispondo solo ora ma mi sono cimentato in esercizi nei quali però non ne sono mai venuto a capo, come per esempio nel seguente:
#include <stdio.h>
#include <stdlib.h>
struct listnode {
char data;
struct listnode *nextptr;
};
typedef struct listnode listnode;
void instructions(void);
void insert(listnode *sptr, char value);
void printlist(listnode *currentptr);
int isempty(listnode *sptr);
int delete(listnode *sptr);
int main() {
listnode *startptr;
startptr = NULL;
int choice;
char item;
instructions();
printf("Enter choice: ");
scanf("%d", &choice);
while (choice != 3) {
switch(choice) {
case 1:
printf("Enter a character: ");
scanf("\n%c", &item);
insert(startptr, item);
printf("%x\n",startptr); //DEBUG
printlist(startptr);
break;
case 2:
if(!isempty(startptr)){
printf("Enter character to be deleted: ");
scanf("\n%c", &item);
if (delete(startptr)) {
printf("%c deleted.\n", item);
printlist(startptr);
}
else {
printf("%c not found.\n\n", item);
}
}
else {
printf("List is empty.\n\n");
}
break;
}
printf("Enter choice: ");
scanf("%d", &choice);
}
return 0;
}
void instructions(void) {
printf("Enter your choice:\n"
" 1 to insert an element into the list.\n"
" 2 to delete an element from the list.\n"
" 3 to end.\n");
}
void insert(listnode *sptr, char value) {
listnode *newptr;
newptr = malloc(sizeof(listnode));
if (newptr != NULL) {
newptr->data = value;
newptr->nextptr = NULL;
if (sptr == NULL)
sptr = newptr;
else
sptr->nextptr = newptr;
}
}
int delete(listnode *sptr) {
listnode *currentptr;
listnode *prevptr;
currentptr = sptr;
prevptr = NULL;
if (currentptr == NULL) {
return 0;
}
while (currentptr->nextptr != NULL) {
prevptr = currentptr;
currentptr = prevptr->nextptr;
}
prevptr->nextptr = NULL;
free(currentptr);
}
int isempty(listnode *sptr) {
return sptr == NULL;
}
void printlist(listnode *currentptr) {
if (currentptr == NULL) {
printf("List is empty.\n\n");
return ;
}
printf("The list is:\n");
while (currentptr != NULL) {
printf("%c --> ", currentptr->data);
currentptr = currentptr->nextptr;
}
printf("NULL\n\n");
}Se tu, o qualcuno altro, ha la possibilità di provarlo, se gentilmente mi spiegaste dove sbaglio... perchè il programma non funziona
Per la gestione degli indici di un archivio, si usano tecniche molto simili.
In effetti ogni record che inserisci in un archivio, deve concatenarsi con il precedente, e lui stesso deve puntare al successivo, cosi' facendo sara' possibile leggere un file con una certa chiave.
Per quanto riguarda il codice che hai scritto, prova a spiegare un po cosa deve fare. Capire da zero il codice scritto da un altro utente non è cosa semplicissima.
Ciao.
In effetti ogni record che inserisci in un archivio, deve concatenarsi con il precedente, e lui stesso deve puntare al successivo, cosi' facendo sara' possibile leggere un file con una certa chiave.
Per quanto riguarda il codice che hai scritto, prova a spiegare un po cosa deve fare. Capire da zero il codice scritto da un altro utente non è cosa semplicissima.
Ciao.
In questo genere di programmi l'uso di grafici in questo caso aiuterebbe molto... Spero di riuscire a descriverti i problemi a parole.
Partiamo dalla funzione di inserimento che riscrivo
Osservazione. Non so se hai la possibilità di modificare il tipo di ritorno della funzione ma sarebbe meglio restituire un int che restituisce un codice di errore in caso di mancato inserimento. In questo modo l'utente della tua "libreria" è in grado di sapere se l'inserimento ha avuto successo e in caso contrario gestire l'errore.
Errore. Non stai modificando il puntatore della lista ma solo il parametro della funzione. sptr = newptr non cambia cioè il valore che ha il puntatore nel main ma solo quello del parametro locale nella funzione. È necessario usare un puntatore a puntatore.
Errore. Considera la seguente lista: sptr = 'a' -> 'b' -> 'c' -> NULL e supponi di voler inserire 'd' nella lista. Allora usando il tuo codice crei prima la lista newptr = 'd' -> NULL e poi inserisci il nuovo nodo subito dopo il nodo puntato da sptr ottenendo quindi la lista sptr = 'a' -> 'd' -> NULL. Ovviamente non è il funzionamento corretto di una funzione di inserimento. Per prima cosa l'inserimento in una lista di questo tipo viene solitamente fatto in testa e non in coda. L'inserimento in coda ha infatti complessità O(n) perché richiede, diversamente da come hai fatto, lo scorrimento dell'intera lista. L'inserimento in testa ha invece complessità O(1). Consiste principalmente nell'assegnare la vecchia lista al puntatore nextptr del nuovo nodo e poi modificare il puntatore alla vecchia lista in modo che punti al nuovo nodo di testa.
Una funzione di inserimento corretta dovrebbe essere (non l'ho testata):
Se invece vuoi proprio inserire un elemento alla fine della lista al posto di NULL (operazione molto inefficiente per una lista) puoi fare qualcosa come il seguente:
Non ho tempo di verificare le altre funziona ma credo possa bastare come punto di partenza per una correzione dell'esercizio. Se ho tempo, più tardi, verifico anche le altre funzioni.
Partiamo dalla funzione di inserimento che riscrivo
void insert(listnode *sptr, char value) {
listnode *newptr;
newptr = malloc(sizeof(listnode));
if (newptr != NULL) {
newptr->data = value;
newptr->nextptr = NULL;
if (sptr == NULL)
sptr = newptr;
else
sptr->nextptr = newptr;
}
}
Osservazione. Non so se hai la possibilità di modificare il tipo di ritorno della funzione ma sarebbe meglio restituire un int che restituisce un codice di errore in caso di mancato inserimento. In questo modo l'utente della tua "libreria" è in grado di sapere se l'inserimento ha avuto successo e in caso contrario gestire l'errore.
Errore. Non stai modificando il puntatore della lista ma solo il parametro della funzione. sptr = newptr non cambia cioè il valore che ha il puntatore nel main ma solo quello del parametro locale nella funzione. È necessario usare un puntatore a puntatore.
Errore. Considera la seguente lista: sptr = 'a' -> 'b' -> 'c' -> NULL e supponi di voler inserire 'd' nella lista. Allora usando il tuo codice crei prima la lista newptr = 'd' -> NULL e poi inserisci il nuovo nodo subito dopo il nodo puntato da sptr ottenendo quindi la lista sptr = 'a' -> 'd' -> NULL. Ovviamente non è il funzionamento corretto di una funzione di inserimento. Per prima cosa l'inserimento in una lista di questo tipo viene solitamente fatto in testa e non in coda. L'inserimento in coda ha infatti complessità O(n) perché richiede, diversamente da come hai fatto, lo scorrimento dell'intera lista. L'inserimento in testa ha invece complessità O(1). Consiste principalmente nell'assegnare la vecchia lista al puntatore nextptr del nuovo nodo e poi modificare il puntatore alla vecchia lista in modo che punti al nuovo nodo di testa.
Una funzione di inserimento corretta dovrebbe essere (non l'ho testata):
int insert(listnode **sptr, char value)
{
listnode *newptr = malloc(sizeof(listnode));
if (NULL != newptr) {
newptr->data = value;
newptr->nextptr = *sptr;
*sptr = newptr;
return NO_ERROR;
} else {
return MEMORY_ERROR;
}
}
Se invece vuoi proprio inserire un elemento alla fine della lista al posto di NULL (operazione molto inefficiente per una lista) puoi fare qualcosa come il seguente:
int insert_last(listnode **sptr, char value)
{
listnode *newptr = malloc(sizeof(listnode));
if (NULL != newptr) {
newptr->data = value;
newptr->nextptr = NULL;
if (NULL != *sptr) {
listnode *lastnode;
for (lastnode = *sptr; NULL != lastnode->nextptr; lastnode = lastnode->nextptr);
lastnode->nextptr = newptr;
return NO_ERROR;
} else {
*sptr = nextptr;
return NO_ERROR;
}
} else {
return MEMORY_ERROR;
}
}
Non ho tempo di verificare le altre funziona ma credo possa bastare come punto di partenza per una correzione dell'esercizio. Se ho tempo, più tardi, verifico anche le altre funzioni.
Veniamo quindi alla funzione delete. Cosa deve fare esattamente? Dal main sembrerebbe che lo scopo della funzione sia quello di eliminare un nodo che contiene un certo carattere, ma il carattere non viene passato alla funzione e dal codice sembra cercare di cancellare l'ultimo nodo della lista (come al solito quando si lavora con le liste è meglio lavorare sulla testa e non sulla coda...). Correggo solo il tuo codice.
La funzione è abbastanza corretta ma non funziona, se non sbaglio, nel caso in cui ci sia un solo nodo nella lista. Inoltre non vengono restituiti valori nel caso in cui l'operazione abbia successo (è strano che il compilatore non restituisca almeno un warning...). Vediamo tutti i casi da considerare:
1. La lista è vuota e quindi non ci sono operazioni da fare
2. La lista contiene un solo nodo e quindi bisogna settare la lista a NULL
3. La lista contiene più elementi e si utilizza l'algoritmo che hai scritto nel tuo codice
Il secondo punto mostra la necessità di utilizzare un puntatore a puntatore anche in questo caso.
La funzione per cancellare l'ultimo elemento è quindi:
Ti inserisco il codice per l'eliminazione di un nodo alla testa della lista in modo da confrontarlo con l'altro e comprendere il motivo per cui si preferisce sempre lavorare all'inizio delle liste e non alla fine.
int delete(listnode *sptr) {
listnode *currentptr;
listnode *prevptr;
currentptr = sptr;
prevptr = NULL;
if (currentptr == NULL) {
return 0;
}
while (currentptr->nextptr != NULL) {
prevptr = currentptr;
currentptr = prevptr->nextptr;
}
prevptr->nextptr = NULL;
free(currentptr);
}
La funzione è abbastanza corretta ma non funziona, se non sbaglio, nel caso in cui ci sia un solo nodo nella lista. Inoltre non vengono restituiti valori nel caso in cui l'operazione abbia successo (è strano che il compilatore non restituisca almeno un warning...). Vediamo tutti i casi da considerare:
1. La lista è vuota e quindi non ci sono operazioni da fare
2. La lista contiene un solo nodo e quindi bisogna settare la lista a NULL
3. La lista contiene più elementi e si utilizza l'algoritmo che hai scritto nel tuo codice
Il secondo punto mostra la necessità di utilizzare un puntatore a puntatore anche in questo caso.
La funzione per cancellare l'ultimo elemento è quindi:
int delete_last(listnode **list)
{
if (NULL == *list) {
return EMPTY_LIST;
} else if (NULL == *list->nextptr) {
free(*list);
*list = NULL;
return NO_ERROR;
} else {
listnode *prevnode = *list;
listnode *currentnode = *list->nextptr;
while (NULL != currentnode->nextptr) {
prevnode = currentnode;
currentnode = currentnode->nextptr;
}
prevnode->nextptr = NULL;
free(currentnode);
return NO_ERROR;
}
}
Ti inserisco il codice per l'eliminazione di un nodo alla testa della lista in modo da confrontarlo con l'altro e comprendere il motivo per cui si preferisce sempre lavorare all'inizio delle liste e non alla fine.
int delete_first(listnode **list)
{
if (NULL != *list) {
listnode *newlist = *list->nextptr;
free(*list);
*list = newlist;
return NO_ERROR;
} else {
return EMPTY_LIST;
}
}
apatriarca, veramente grazie per la tua analisi.
Ma prima ancora di attuare le tue indicazioni (riprendo a studiare domani) volevo chiederti subito cosa significa complessità O(n) e complessità O(1)...
Ma prima ancora di attuare le tue indicazioni (riprendo a studiare domani) volevo chiederti subito cosa significa complessità O(n) e complessità O(1)...
Il discorso potrebbe dilungarsi parecchio e non ho il tempo e forse neanche le capacità per dare una descrizione soddisfacente dell'analisi asintotica della complessità degli algoritmi. Qualsiasi libro di algoritmi dovrebbe trattare gli argomenti abbastanza nel dettaglio e ti consiglio di prenderne uno e studiarlo.
Volendo dare una descrizione intuitiva... n rappresenta la dimensione dell'input (nel tuo caso la dimensione della lista) mentre l'espressione all'interno delle parentesi indica in che modo il "numero di passaggi" eseguiti dipende da n. O(1) significa che il numero di operazioni effettuate non dipende dalla dimensione dell'input mentre O(n) significa che il numero di operazioni cresce linearmente con il crescere della dimensione dell'input. Altri esempio possono essere O(n^2) o O(n logn). Mi rendo conto che probabilmente non è molto chiaro. Prova a dare un occhiata ad esempio su http://en.wikipedia.org/wiki/Big_O_notation
Volendo dare una descrizione intuitiva... n rappresenta la dimensione dell'input (nel tuo caso la dimensione della lista) mentre l'espressione all'interno delle parentesi indica in che modo il "numero di passaggi" eseguiti dipende da n. O(1) significa che il numero di operazioni effettuate non dipende dalla dimensione dell'input mentre O(n) significa che il numero di operazioni cresce linearmente con il crescere della dimensione dell'input. Altri esempio possono essere O(n^2) o O(n logn). Mi rendo conto che probabilmente non è molto chiaro. Prova a dare un occhiata ad esempio su http://en.wikipedia.org/wiki/Big_O_notation
Ho letto e riletto il tuo codice, al di la dell'errore logico di inserire l'elemento in testa o in coda, non mi è ben chiaro l'utilizzo del doppio puntatore.
Perchè, quando e come si usa?
Purtroppo il libro che sto seguendo "Corso completo di programmazione" Apogeo, non spiega questo concetto.
L'esempio che pone è:
typedef struct listnode Listonde:
typedef Listnode *ListnodePtr
void insert(ListnodePtr *sptr)
che a quanto pare, credo sia equivalente a: void insert(Listnode **sptr)
giusto?
Il libro oltre l'esempio non va... e non mi è chiaro il perchè si usa il doppio puntatore.
Grazie
Perchè, quando e come si usa?
Purtroppo il libro che sto seguendo "Corso completo di programmazione" Apogeo, non spiega questo concetto.
L'esempio che pone è:
typedef struct listnode Listonde:
typedef Listnode *ListnodePtr
void insert(ListnodePtr *sptr)
che a quanto pare, credo sia equivalente a: void insert(Listnode **sptr)
giusto?
Il libro oltre l'esempio non va... e non mi è chiaro il perchè si usa il doppio puntatore.
Grazie
ListnodePtr* è equivalente a Listnode** con le definizione date nel libro. Quando passi qualcosa ad una funzione il suo valore viene copiato in una variabile locale (il parametro della funzione) ed è il valore di questo che modifichi nella funzione e non il valore contenuto nella variabile che hai passato. Quando quindi vuoi modificare tale valore diventa necessario l'utilizzo di un puntatore. Il parametro non conterrà quindi più il valore della variabile ma il suo indirizzo e sei quindi in grado di modificare il suo valore. L'unico motivo per cui usi un doppio puntatore invece che quello singolo è che la variabile iniziare è un puntatore, ma è una situazione del tutto equivalente a quando ad esempio scrivi una funzione per scambiare i valori di due variabili:
Se invece di usare puntatori ci fossero stati dei semplici int allora i valori di a e b sarebbero cambiati ma non quelli delle variabili passate alla funzione.
void swap(int *a, int *b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
Se invece di usare puntatori ci fossero stati dei semplici int allora i valori di a e b sarebbero cambiati ma non quelli delle variabili passate alla funzione.
L'unico motivo per cui usi un doppio puntatore invece che quello singolo è che la variabile iniziare è un puntatore
giusto per capire il concetto di doppio puntatore,
questo concetto vale in generale o solo in questo caso?
Un doppio puntatore (o anche uno triplo, quadruplo...) è semplicemente un puntatore ad un puntatore e quindi il discorso vale in generale. Se hai una variabile che è un puntatore e hai bisogno di memorizzare il suo indirizzo allora devi usare un puntatore a puntatore. Raramente comunque si va oltre un paio di indirezione (il puntatore a puntatore) e quando si fa è sempre meglio fare uso di typedef in modo da semplificare la notazione (soprattutto quando poi si mischiano con const o altri qualificatori...). Per esempio, che cosa significa la seguente dichiarazione? Che cosa è var?
const char * const ** var;
SOLUZIONE:
const char * const ** var;
SOLUZIONE:
ciao!!!
ho un problema con le liste concatenate...nel senso che devo fare un programma in C dove devo riordinare una lista concatenata di interi...però non so nè come inserire gli interi nella lista e non ho nemmeno idea di come ordinarla (il prof ci ha detto di utilizzare il quicksort modificato per le liste concatenate...ma come si fa??)
se qualcuno sa rispondermi...grazie!!!
ho un problema con le liste concatenate...nel senso che devo fare un programma in C dove devo riordinare una lista concatenata di interi...però non so nè come inserire gli interi nella lista e non ho nemmeno idea di come ordinarla (il prof ci ha detto di utilizzare il quicksort modificato per le liste concatenate...ma come si fa??)
se qualcuno sa rispondermi...grazie!!!
Per il problema di inserire gli interi nella lista non ti posso fornire un codice generale perché dipende da come il tuo professore ha implementato le liste. Per il secondo problema sinceramente preferisco usare l'odd-even mergesort rispetto al quicksort. Il fatto che ti abbia parlato di quicksort modificato per le liste concatenate mi fa pensare comunque che vi abbia almeno fornito uno pseudo-codice e vi stia chiedendo semplicemente di implementare quello che ha fatto a lezione. Ti consiglio quindi di iniziare a dare un occhiata alle dispense del corso.
Se proprio non riuscirai a proseguire con l'esercizio cercherò di scrivere qualcosa.
Se proprio non riuscirai a proseguire con l'esercizio cercherò di scrivere qualcosa.
credo di essere riuscita a creare una lista linkata di interi, però per riordinarla non so davvero come fare...scrivo sotto il programma che il prof ci ha detto di implementare..se qualcuno può darmi una mano ne sarei grata...
#include <stdio.h>
#include <stdlib.h>
/* funzione base per il quick sort;
determina la posizione corretta dell'elemento
a[lp] nella lista da lp ad rp */
int cardine(int a[],int lp, int rp)
{
int pivot,flag=1;
pivot=a[lp];
while (flag)
{
while (pivot < a[rp])
rp--;
if (lp < rp)
{
a[lp]=a[rp];
a[rp]=pivot;
lp++;
while (a[lp] < pivot)
lp++;
if (lp < rp)
{
a[rp]=a[lp];
a[lp]=pivot;
rp--;
}
else
flag=0;
}
else
flag=0;
}
return(lp);
}
/* funzione ricorsiva che implementa l'algoritmo
di ordinamento noto come quick sort */
void quicksort(int a[],int lp,int rp)
{
int i;
if (lp < rp)
{
i=cardine(a,lp,rp);
if (lp < i) quicksort(a,lp,i-1);
if (i < rp) quicksort(a,i+1,rp);
}
}
int main()
{
int *a;
int n,i;
printf("\nDai num. elementi ");
scanf("%d",&n);
a=(int*)malloc(n*sizeof(int));
printf("Dai gli elementi \n");
for (i=0; i<n; i++)
scanf("%d",&a[i]);
quicksort(a,0,n-1);
for (i=0; i<n; i++)
printf("%d ",a[i]);
printf("\n");
free(a);
return(1);
}
Ma tu hai allocato un array di interi, non hai creato una lista concatenata. Ti consiglio di partire dall'articolo di wikipedia (http://it.wikipedia.org/wiki/Lista_concatenata) per capire di cosa si tratta. Se il professore non vi ha fornito una implimentazione di lista concatenata dovrai probabilmente implementarlo tu.
so già come creare una lista concatenata...quello che ho scritto è il programma quicksort per l'ordinamento di un array di interi che il prof ci ha detto di modificare in modo da riuscire a ordinare una lista concatenata, solo che non so come fare.
Avevo capito che quello fosse il tuo tentativo per risolvere l'esercizio. Per poterti aiutare avrei bisogno di capire come sono fatte le liste concatenate con cui devi lavorare. Se per esempio hai solo collegamenti al nodo successivo oppure se puoi anche tornare indietro, se puoi accedere direttamente sia alla testa che alla coda... Il codice del quicksort dipende molto da queste caratteristiche. Se posti il codice che hai scritto per creare la lista e le funzioni che usi posso anche scrivere del codice.
Se osservi con attenzione il codice le operazioni che fai nelle tue due funzioni sono:
1. la possibilità di definire una sotto-sequenza di numeri. Quello che fai con gli indici lp e rp nel caso degli array lo devi fare con i nodi nel caso delle liste;
2. la possibilità di accedere al primo e all'ultimo elemento e all'ultimo della sottosequenza;
3. la possibilità di passare sia all'elemento successivo che a quello precedente;
4. la capacità di scambiare due nodi.
Se con la tua lista è possibile fare queste cose allora puoi fare una conversione abbastanza veloce dalla funzione che usa gli array a quello con le liste. In caso contrario è necessario adattare l'algoritmo.
Se osservi con attenzione il codice le operazioni che fai nelle tue due funzioni sono:
1. la possibilità di definire una sotto-sequenza di numeri. Quello che fai con gli indici lp e rp nel caso degli array lo devi fare con i nodi nel caso delle liste;
2. la possibilità di accedere al primo e all'ultimo elemento e all'ultimo della sottosequenza;
3. la possibilità di passare sia all'elemento successivo che a quello precedente;
4. la capacità di scambiare due nodi.
Se con la tua lista è possibile fare queste cose allora puoi fare una conversione abbastanza veloce dalla funzione che usa gli array a quello con le liste. In caso contrario è necessario adattare l'algoritmo.
#include <stdio.h>
#include <stdlib.h>
/* esempio di allocazione di una lista linkata
dal primo elemento all'ultimo */
int main()
{
struct nodo
{
int num;
struct nodo *next;
};
typedef struct nodo NODO;
NODO *p,*p_old,*q,*head;
int i,n,k=sizeof(NODO);
printf("\nDai il numero di elementi della lista: ");
scanf("%d",&n);
head=malloc(k);
head->num=1;
p_old=head;
for (i=2; i<=n; i++)
{
p=malloc(k);
p->num=i;
p_old->next=p;
p_old=p;
}
printf("\nFine allocazione e inizializzazione\n");
if (head!=NULL)
{
p=head;
do
{
q=p;
printf("%d \n",p->num);
p=p->next;
}while (q->next !=NULL);
}
return(1);
}[mod="Luc@s"] Potresti usare i tag CODE? Aiutano la visibilità e l'organizzazione[/mod]
Il tuo codice sul mio computer non funziona. Cerchi di accedere ad una qualche locazione di memoria che non è stata allocata. Inoltre manca la deallocazione della memoria allocata.
Quando scrivi un codice che deve usare una qualche struttura devi inserirla in modo che tutte le funzioni possano vederla e quindi non la puoi definire all'interno del main. L'inizio del file o un file header separato sono i posti più comuni. È inoltre utile definire delle funzioni ausiliarie in grado di semplificare l'uso della struttura dati. Ho scritto il seguente esempio che mostra una lista e il suo riempimento in due modi diversi. L'ho scritta abbastanza velocemente ma dovrebbe essere abbastanza corretta.
Quando scrivi un codice che deve usare una qualche struttura devi inserirla in modo che tutte le funzioni possano vederla e quindi non la puoi definire all'interno del main. L'inizio del file o un file header separato sono i posti più comuni. È inoltre utile definire delle funzioni ausiliarie in grado di semplificare l'uso della struttura dati. Ho scritto il seguente esempio che mostra una lista e il suo riempimento in due modi diversi. L'ho scritta abbastanza velocemente ma dovrebbe essere abbastanza corretta.
#include <stdio.h>
#include <stdlib.h>
/*
* Definizione della struttura dei nodi della lista.
*/
typedef struct Node Node;
struct Node
{
int num;
Node *next;
};
/*
* Alloca lo spazio per un nuovo nodo di una lista e inizializza i valori.
* I nodi vanno deallocati singolarmente con free.
*/
Node *newNode(int num, Node *next)
{
Node *node = malloc(sizeof(Node));
if (NULL != node) {
node->num = num;
node->next = next;
}
return node;
}
/*
* Dealloca tutta la lista che inizia con /list/.
*/
void freeList(Node *list)
{
Node *next = list;
while (list != NULL) {
next = list->next;
free(list);
list = next;
}
}
/*
* Aggiunge un nuovo nodo con il valore /num/ dopo quello corrente.
* Restituisce un puntatore al nuovo nodo.
*/
Node *insertAfter(Node *current, int num)
{
current->next = newNode(num, current->next);
return current->next;
}
/*
* Ti ho scritto questa funzione per mostrarti la creazione di liste. Crea una lista
* che contiene tutti gli interi tra start e end compresi. La costruisce al "contrario"
* aggiungendo in testa perché è molto più facile.
*/
Node *range(int start, int end)
{
int i;
Node *node = NULL;
for (i = end; i >= start; --i) {
node = newNode(i, node);
}
return node;
}
/*
* Ti ho scritto questa funzione per mostrarti la creazione di liste. Crea una lista
* che contiene tutti gli interi tra start e end compresi. Questa volta la costruisce
* da /start/ ad /end/.
*/
Node *range2(int start, int end)
{
int i;
Node *node = NULL;
Node *head;
if (end < start) return NULL;
head = newNode(start, NULL);
node = head;
for (i = start+1; i <= end; ++i) {
node = insertAfter(node, i);
}
return head;
}
int main()
{
int n;
Node *head;
Node *node;
fputs("Inserisci il numero di elementi della lista: ", stdout);
scanf("%d", &n);
/*
* Primo metodo per creare la lista (inserimento all'inizio).
*/
head = range(1, n);
putc('[', stdout);
for (node = head; node != NULL; node = node->next) {
printf("%d, ", node->num);
}
puts("NULL]");
freeList(head);
/*
* Secondo metodo per creare la lista (inserimento alla fine).
*/
head = range2(1, n);
putc('[', stdout);
for (node = head; node != NULL; node = node->next) {
printf("%d, ", node->num);
}
puts("NULL]");
freeList(head);
return 0;
}
Per quanto riguarda il quicksort non l'ho mai implementato per liste e sto dando un occhiata su internet. La maggior parte dei metodi per velocizzare il quicksort richiedono l'accesso casuale agli elementi e anche la funzione che hai scritto in precedenza fa uso di operazioni non possibili sulla struttura che stai usando. Quando ho un idea più precisa di come implementarlo in modo efficiente ti faccio sapere.
EDIT: ho postato due post consecutivi... guarda anche l'altro nella pagina precedente.
EDIT: ho postato due post consecutivi... guarda anche l'altro nella pagina precedente.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo