[C] Inserire elementi ordinati in lista linkata

[toni00c]

ciao siccome ho alcuni dubbi mi potresti scrivere per cortesia il codice della definizione della lista nel file header


ad esempio ;

devo definire una lista list_element

ho bisogno di creare due file , un header per la definizione e un file sorgente per l'implementazione delle primitive

se ad esempio creassi un file.h con dentro

typedef struct list_element  ;

e nel file sorgente definissi una struttura del tipo

typedef struct list_element {

int i ;
char b ;


} nodo ;

sarebbe corretto il tutto ?

grazie

[Celebron]

Originariamente inviato da toni00c
ciao siccome ho alcuni dubbi mi potresti scrivere per cortesia il codice della definizione della lista nel file header


ad esempio ;

devo definire una lista list_element

ho bisogno di creare due file , un header per la definizione e un file sorgente per l'implementazione delle primitive

se ad esempio creassi un file.h con dentro

typedef struct list_element  ;

e nel file sorgente definissi una struttura del tipo

typedef struct list_element {

int i ;
char b ;


} nodo ;

sarebbe corretto il tutto ?

grazie

No °-° l'uso della typedef nel .h ti darebbe subito errore, questo perchè non rispetti la sintassi corretta

guarda per farti un semplice esempio, riprendendo list.h e list.c che feci circa un anno e mezzo fa:

.h

   
    typedef struct node node_t;
    typedef struct lista lista_t;

.c

struct node{
    item_t* oggetto; //definito in item.h
    node_t* next;
};


struct lista{
    node_t* ptesta;
    node_t* pcoda;
    int num_elementi;
};

[Laikius91]

Originariamente inviato da Celebron
No °-° l'uso della typedef nel .h ti darebbe subito errore, questo perchè non rispetti la sintassi corretta

guarda per farti un semplice esempio, riprendendo list.h e list.c che feci circa un anno e mezzo fa:

.h

   
    typedef struct node node_t;
    typedef struct lista lista_t;

.c

struct node{
    item_t* oggetto; //definito in item.h
    node_t* next;
};


struct lista{
    node_t* ptesta;
    node_t* pcoda;
    int num_elementi;
};

Niente di sbagliato, ma quella che hai definito tu non è una lista ma una coda (politica FIFO -> First In First Out), caratterizzata dal fatto che si passano sia il puntatore al primo elemento sia il puntatore all'ultimo.

In genere le liste sono così definite:

typedef int element; \* in questo caso definisco una lista di interi *\ 

typedef struct node {element value; struct node* next;} node;
typedef node* list;

p.s. Ragazzi io ho l'esame di fondamenti d'informatica T1 sul C proprio domani

[Celebron]

Originariamente inviato da Laikius91
Niente di sbagliato, ma quella che hai definito tu non è una lista ma una coda (politica FIFO -> First In First Out), caratterizzata dal fatto che si passano sia il puntatore al primo elemento sia il puntatore all'ultimo.

In genere le liste sono così definite:

typedef int element; \* in questo caso definisco una lista di interi *\ 

typedef struct node {element value; struct node* next;} node;
typedef node* list;

p.s. Ragazzi io ho l'esame di fondamenti d'informatica T1 sul C proprio domani

in realtà una coda è una sottocategoria di lista (se implementata tramite puntatori)
Tutta l'interfaccia che caratterizza quel mio header infatti lavora sulle liste:

typedef enum{LSuccess, LParametersError, LMemoryError} listError;

    lista_t* initList();
    listError deleteList(lista_t* list);
    listError insertHead(lista_t* list, item_t* oggetto);
    listError insertTail(lista_t* list, item_t* oggetto);
    listError insertPos(lista_t* list, item_t* obj, int position);
    listError deletePos(lista_t* list, int position);
    listError printList(lista_t* list);
    listError getNodeFromPosition(lista_t* list, int position, node_t* returned);
    listError toArray(lista_t* list, item_t*** arrayReturned, int *nelementi);
    int getDimension(lista_t* list);

    listError getNext(node_t* actual, node_t* returned);
    boolean hasNext(node_t* actual);

l'aggiunta del puntatore a coda non fa altro che semplificare e ottimizzare alcuni algoritmi (per esempio l'inserimento diretto in coda e alcuni casi particolari delle altre funzioni). Da nessuna parte è specificato che si debba usare una politica FIFO, ma se uno vuole può adottare il mio list.c per gestire una fifo o una lifo con la massima semplciità

distinguiamo un possibile uso da un uso obbligatorio

Anzi, se ai tempi la avessi implementata come lista doppiamente linkata probabilmente sarebbe stato ancora meglio

[Laikius91]

Originariamente inviato da Celebron
in realtà una coda è una sottocategoria di lista (se implementata tramite puntatori)
Tutta l'interfaccia che caratterizza quel mio header infatti lavora sulle liste:

typedef enum{LSuccess, LParametersError, LMemoryError} listError;

    lista_t* initList();
    listError deleteList(lista_t* list);
    listError insertHead(lista_t* list, item_t* oggetto);
    listError insertTail(lista_t* list, item_t* oggetto);
    listError insertPos(lista_t* list, item_t* obj, int position);
    listError deletePos(lista_t* list, int position);
    listError printList(lista_t* list);
    listError getNodeFromPosition(lista_t* list, int position, node_t* returned);
    listError toArray(lista_t* list, item_t*** arrayReturned, int *nelementi);
    int getDimension(lista_t* list);

    listError getNext(node_t* actual, node_t* returned);
    boolean hasNext(node_t* actual);

l'aggiunta del puntatore a coda non fa altro che semplificare e ottimizzare alcuni algoritmi (per esempio l'inserimento diretto in coda e alcuni casi particolari delle altre funzioni). Da nessuna parte è specificato che si debba usare una politica FIFO, ma se uno vuole può adottare il mio list.c per gestire una fifo o una lifo con la massima semplciità

distinguiamo un possibile uso da un uso obbligatorio

Anzi, se ai tempi la avessi implementata come lista doppiamente linkata probabilmente sarebbe stato ancora meglio

Ripeto, tutto giustissimo, la tua implementazione è eccellente e permette davvero tante comodità! Se per caso è passato che io volessi fare l'arrogante chiedo davvero scusa, io sono poco più in là degli inizi dell'informatica e non posso certo permettermi di giudicare gli altri, soprattutto se sembrano notevolmente più esperti di me come te!
Quella che ho proposto io era solo la definizione più generale che mi veniva in mente di lista, ma di sicuro a livello pratico la tua permette parecchio di più!

[Celebron]

Originariamente inviato da Laikius91
Ripeto, tutto giustissimo, la tua implementazione è eccellente e permette davvero tante comodità! Se per caso è passato che io volessi fare l'arrogante chiedo davvero scusa, io sono poco più in là degli inizi dell'informatica e non posso certo permettermi di giudicare gli altri, soprattutto se sembrano notevolmente più esperti di me come te!
Quella che ho proposto io era solo la definizione più generale che mi veniva in mente di lista, ma di sicuro a livello pratico la tua permette parecchio di più!

si si avevo capito volevo solo specificare a colui che aveva posto la domanda che, lavorare ad una base dati un pelino più complessa può favorire parecchio nell'implementazione dei metodi relativi

Poi certo, se è interessato ad un implementazione più semplice, l'adt va costruito esattamente come tu hai suggerito

[toni00c]

Originariamente inviato da Laikius91
Niente di sbagliato, ma quella che hai definito tu non è una lista ma una coda (politica FIFO -> First In First Out), caratterizzata dal fatto che si passano sia il puntatore al primo elemento sia il puntatore all'ultimo.

In genere le liste sono così definite:

typedef int element; \* in questo caso definisco una lista di interi *\ 

typedef struct node {element value; struct node* next;} node;
typedef node* list;

p.s. Ragazzi io ho l'esame di fondamenti d'informatica T1 sul C proprio domani

...anchio domani.. !

cmq adesso ho capito il concetto
grazie!

[toni00c]

..ma una cosa del genere è valida ?

[CODE]

==================

typedef struct list_element {
int value;
struct list_element *next;
} item;

typedef item *list;

int main() {
list root = NULL , L; /* questa riga mi lascia dubbioso */

=================

[/CODE ]

cioè creo un puntatore a una lista di tipo "item" root , lo inizializzo a NULL e nella stessa riga dichiaro un altro puntatore L..

boh..

[_Alfabetagamma_]

Originariamente inviato da toni00c
...anchio domani.. !

cmq adesso ho capito il concetto
grazie!

Che studiate?? Dove??

[_Alfabetagamma_]

Originariamente inviato da toni00c
..ma una cosa del genere è valida ?

[CODE]

typedef struct list_element {
int value;
struct list_element *next;
} item;

typedef item *list;

int main() {
list root = NULL , L; /* questa riga mi lascia dubbioso

[/CODE ]

cioè creo un puntatore a una lista di tipo "item" root , lo inizializzo a NULL e nella stessa riga dichiaro un altro puntatore L..

boh..

Vediamo se riusciamo a cavar ragno dal buco.

Tu crei una struttura che chiami ITEM.

A questo punto se volessi fare un assegnamento con malloc, ogni inizializzazione dovresti scrivere

item* nomepuntatore

o ancora peggio

struct list_element* nomepuntatore.

Così lui cosa decide di fare? di rinominare item* list in modo tale che ora il tipo LIST è un puntatore a item. Così dichiarando list root=NULL equivale dire

struct list_element(ITEM)* nomepuntatore.

Se tutto va bene è giusto così XD