[C] liste tramite array collegati

[Fla@sh_b]

Ciao! Mi trovo ad implementare (a scopo puramente accademico) una lista tramite array collegati. Ho trovato in giro il seguente codice:

#include <stdio.h>
#include <stdlib.h>
#define MAXLS 30

typedef struct elem 
{
    int elem;
    int next;
} ArrLs;

//VARIABILI GLOBALI

ArrLs key[MAXLS];       //Array dati!
int head=0;             //Indice che "punta" al primo elemento della lista!
int freeHead=0;         //Indice che "punta" al primo el. della lista libera!

void insEl(void) 
{
    int elem=0;
    int freeHeadbck=0;
    
    printf("Inserisci un integer > ");
    scanf("%d", &elem);
    
    if(freeHead==-1) {
       printf("Spazio in memoria insufficiente\n");
       return;
    }  
  
    freeHeadbck=freeHead;                        
    freeHead=key[freeHead].next; 
    key[freeHeadbck].elem=elem;   
    key[freeHeadbck].next=head;  
    head=freeHeadbck;
}

Ad ogni inserimento la funzione mi sovrascrive il primo elemento.
Sospetto che l'errore stia da queste parti:

 freeHead=key[freeHead].next;

Ma non riesco ad uscire fuori dal tunnel! Qualcuno ha qualche idea (oltre al suggerimento di usare lista concatenate) ?

Plz!

[perzem]

questa costruisce una lista linkata e la ordina in maniera particolare

#include <stdio.h>
#include <math.h>
#include <malloc.h>
#include <stdlib.h>

/* Implementazione della lista Linkata */
struct Lista {
   int dato;                 /* Dato contenuto in questo nodo */
   struct Lista* prossimo;   /* Link al prossimo elemento */
};

/* Questa procedura si occupa di inserire un elemento in un nodo
 * e di creare il nodo successivo, senza doverlo fare a manina
 * per tutti e 10 gli elementi
 */
void creaElemento(struct Lista *lst, int d) {
   lst->dato = d;
   lst->prossimo = (struct Lista*) malloc(sizeof(struct Lista));
   lst->prossimo->dato = -1;   /* Così so che quifinisce la lista */
}

void ordinaLista(struct Lista *lst);                /* Implementata dopo */
void scambia(struct Lista *l1, struct Lista *l2);   /* Implementata dopo */

int main() {
  int i;
   int z;
do{
   struct Lista *lst;
   struct Lista *ptr;


   srand(time(NULL));   /* Inizializzo il seme del generatore di numeri casuali */
   lst = (struct Lista*) malloc(sizeof(struct Lista));   /* Alloco la lista (1° elemento) */
   ptr = lst;   /* Memorizzo il puntatore */

   printf("quanti elementi vuoi inserire?");
   scanf("%d",&z);

   /* Popolo la lista con elementi casuali */

   for(i=0; i<z; i++) {
      creaElemento(lst, rand());
      lst = lst->prossimo;
   }

   lst = ptr;   /* Riposiziono il puntatore */

   /* Stampo la lista non ordinata */
   printf("Lista disordinata:\n");
   for (i=0; i<z; i++) {
      printf("Elemento di posizione %d nella lista: %d\n", i, lst->dato);
      lst = lst->prossimo;
   }

   lst = ptr;   /* Riposiziono il puntatore */

   ordinaLista(lst);   /* Ordino la lista */

   /* Stampo la lista che ora è ordinata */
   printf("\n\nLista ordinata:\n");
   for (i=0; i<z; i++) {
      printf("Elemento di posizione %d nella lista: %d\n", i, lst->dato);
      lst = lst->prossimo;
   }
                 }while(z!=0);
   return 0;

}

void scambia(struct Lista *l1, struct Lista *l2) {
   int datoTmp;   /* Dato temporaneo */
   datoTmp = l1->dato;
   l1->dato = l2->dato;
   l2->dato = datoTmp;
}

void ordinaLista(struct Lista *lst) {
   struct Lista *ptr = lst;    /* Memorizzo l'indirizzo */
   struct Lista *prec = lst;   /* Devo memorizzare il puntatore al valore precedente */

   while(lst->prossimo->dato > 0) {   /* Fino alla fine della lista */
      while (lst->prossimo->dato > 0) {   /* Fino alla fine della lista */
         if (ptr->dato%2==0) {
            scambia(ptr, lst->prossimo);   /* Scambio i due elementi */
         }
         lst = lst->prossimo;
      }
      ptr = ptr->prossimo;
      lst = ptr;
   }
}

[LeleFT]

Il codice di perzem mi sembra di conoscerlo
C'è pure un'istruzione inutile che avevo dimenticato di togliere: la dichiarazione del puntatore a Lista prec, all'interno della procedura di ordinamento.


Ciao.

[perzem]

è gia è proprio la tua lista!!! ho fatto male??

[LeleFT]

No, non hai fatto male... solo non so se lo aiuta!


Ciao.

[Fla@sh_b]

Più che una lista allocata dinamicamente il problema consisteva nel crearne una tramite un array.
In pratica il medesimo array contiene due liste una delle quali (la lista libera) contiene gli elementi che possono essere sovrascritti (che quindi non fanno parte della prima). L'eliminazione di un elemento comporta l'aggiunta di quest'ultimo alla lista libera.
Cmq credo di aver risolto (finalmente!) il problema! Vi ringrazio per le risposte!