[C] Lista circolare ordinata

[Cicchi27]

Salve, ho questo codice che dovrebbe implementare una lista concatenata circolare e vorrei sapere se è ok:

Codice:

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



typedef struct node_
{
   int data;
   struct node_* next;
}node;



void insert(node** l, char carattere)
{
   node* new = NULL;
   new = (node*) malloc(sizeof(node));
   if(new)
   {
     while(*l && carattere > (*l)->data)
     {
      l = &(*l)->next;
     }
     new->data = carattere;
     new->next = *l;
     *l = new;
   }
   else
      puts("memoria non disponibile\n");
}

void print(node* l)
{

   char primo = l->data;
   if(!l)
      printf("la lista è vuota\n");
   else
   {
      do
      {
         printf("|%c|",l->data);
         l = l->next;
      }
      while(l->data != primo);
      
      
   }
   puts("\n");
}

void init(node** l)
{
      char carattere = '9';
      for(unsigned int i = 0; i < 10; i++, carattere--)
       {
         insert(l, carattere);
      }
      /*char carattere;
      unsigned int count = 0;
      while( count < 10)
      {
      char c;
      scanf("%c", &c);
      insert(l, carattere);
      count++;
      }*/
   
   node* temp = *l;
   while(temp->next)
   {
      temp = temp->next;
   }
       temp->next = *l;
      
}


int main()
{
   node* l = NULL;   
   init(&l);
   print(l);
   
}

quello che vorrei fare in teoria sarebbe inserire da tastiera un numero indefinito di volte dei caratteri
e di volta in volta stamparli in ordine nella lista, ma quando ho provato ad usare l'altra parte di codice della init (scritto giusto per prova), il programma si è bloccato.

[apatriarca]

La logica della funzione insert mi sembra sbagliata. In particolare quello che dovrebbe essere il puntatore al primo elemento della lista finisce per essere sempre uguale all'ultimo carattere inserito.

[Cicchi27]

Quindi bisogna sempre mantenere un riferimento alla testa? Si può ovviare la cosa effettuando le operazioni con un puntatore al nodo della testa temporaneo?

[apatriarca]

Tutte le operazioni sulla lista devono partire dall'elemento di testa. Ma non vedo alcuna ragione per cui dovresti effettivamente perderlo. Non ho in effetti capito il tuo ultimo commento.

EDIT: Ho un altro dubbio.. Hai scritto lista circolare nel titolo, ma la tua implementazione non è di una lista circolare. Inoltre su una lista circolare non c'è alcun ordinamento in quanto ad un certo punto dovrai necessariamente andare ad un elemento più piccolo.

[Cicchi27]

Siccome ho cominciato a fare questo tipo di liste e mi sono imbattuto in questo esercizio:
Si sviluppi un programma che
• riceve in input una sequenza di caratteri, uno dopo l’altro;
• costruisce, mano a mano che riceve i caratteri in ingresso, una lista concatenata circolare ordinata che ospita i caratteri come campo informativo dei nodi;
• produce in output, ogniqualvolta l’utente inserisce il carattere ‘:‘, la sequenza immessa fino a quel momento, ordinata in senso crescente e poi ordinata in senso decrescente.

[apatriarca]

Una lista circolare è normalmente una lista con l'ultimo elemento collegato al primo. L'idea di avere un ordine in tale lista è a mio parere curioso perché un ordine non è ben definito in una struttura circolare. In particolare l'ordine costringe la lista ad avere un nodo di testa ben definito (quello con valore minimo), mentre una lista circolare permetterebbe di considerare qualsiasi punto della lista come "testa". Nota che in una lista di questo tipo (con almeno un nodo) non incontrerai mai un NULL durante l'iterazione sulla lista. La lista termina quando si incontra nuovamente il nodo di partenza. Una doppia lista concatenata sarebbe infine molto più comoda nel tuo esercizio..

[Cicchi27]

Avevo già usato una struttura di quel tipo in un altro esercizio e alla fine l'ho fatta così:

Codice:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
typedef struct node_
{
    int data;
    struct node_ *prev;
    struct node_ *next;
}   node;
 
typedef struct list_
{
    node *head;
    node *tail;
}   list;

 void insert(list* l, int value)
{
   node* nuovo = (node*)malloc(sizeof(node));
   if(nuovo)
   {
      nuovo->data = value;
      node* temp = l->head;
      while(temp && value > temp->data)
      {
         temp = temp->next;
      }
      if(temp)
      {
         if(!temp->prev)
         {
         nuovo->prev = NULL;
         nuovo->next = temp;
         temp->prev = nuovo;
         l->head = nuovo;
         }
         else
         {
         nuovo->prev = temp->prev;
         temp->prev->next = nuovo;
         nuovo->next = temp;
         temp->prev = nuovo;
         }
      }
      else
      {
         if(l->tail)
         {
         nuovo->prev = l->tail;
         l->tail->next = nuovo;
         nuovo->next = NULL;
         l->tail = nuovo;
         }
         else
         {
            nuovo->prev = nuovo->next = NULL;
            l->head = l->tail = nuovo;
         }
      }      
   }
   else
   {
   puts("memoria non disponibile");
   }
}
void printTesta(list *l)
{
    if(!l->head)
    {
     puts("la lista e' vuota\n");
    }
    else
    {
     puts("\nLa lista e':\n");
    while(l->head)
    {
     printf("%d-->", l->head->data);
     (l->head) = (l->head)->next;
    }
     puts("NULL\n");               
    }
}

Conviene partire da una cosa del genere quindi?

[apatriarca]

Il problema diventa molto più facile usando questa struttura dati, ma non sono sicuro fosse quello che il professore avesse in mente perché non è circolare e non si parlava di lista doppia concatenata. Tuttavia in questo secondo esercizio hai aggiornato correttamente il puntatore all'elemento di testa.

[Cicchi27]

sisi lo so, questo faceva parte di un altro esercizio. Comunque se posso usare questo tipo di struttura come base, basterebbe quindi fare le giuste modifiche per togliere i riferimenti a NULL.