Topic: [Linguaggio C] Lista doppiamente linkata  (Letto 683 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline Badly

  • python unicellularis
  • *
  • Post: 24
  • Punti reputazione: 0
    • Mostra profilo
[Linguaggio C] Lista doppiamente linkata
« il: Giugno 30, 2016, 22:59 »
Salve a tutti, vorrei realizzare un inserimento "in order" per liste doppiamente concatenate/linkate.
data questa struttura con rispettive funzioni per creare il nodo:
[codice]
typedef struct nodo{
  char *stringa;
  struct nodo *next,*prec;
} tiponodo;

tiponodo *createnodo(char *stringa){
  tiponodo *new;

  new=(tiponodo *)malloc(sizeof(tiponodo));
  if(!new){
createnodoerr:
    fprintf(stderr,"Errore di allocazione in createnodo()
");
    exit(-1);
  }

  new->stringa=malloc(sizeof(strlen(stringa)+1));
  if(!new->stringa) goto createnodoerr;

  strcpy(new->stringa,stringa);

  return new;
}
[/codice]
vorrei realizzare un inserimento ordinato.
Per le liste singolarmente linkate una soluzione potrebbe essere questa (metto anche la struttura):
[codice]
typedef struct nodo2 {
int mese, sum;
struct nodo2 *next;} tiponodo2;

tiponodo2 *insertorder(tiponodo2 *head,tiponodo2 *n){
  if(!head){
    n->next=NULL;
    return n;
  }
  if(head->mese>n->mese) { // il nodo in esame andrebbe dopo quello che voglio inserire -> inserimento in testa
    n->next=head;
    return n;
  }

  head->next=insertorder(head->next,n);
  return head;
}
[/codice]
credo che la modifica sia minima, ma purtroppo ogni soluzione che ho provato, a basso livello dava delle incorrettezze (link *prec sbagliati).
Sapreste darmi una soluzione?

Offline bebo

  • python erectus
  • ***
  • Post: 195
  • Punti reputazione: 0
    • Mostra profilo
    • bebo_sudo's personal homepage
Re: [Linguaggio C] Lista doppiamente linkata
« Risposta #1 il: Luglio 01, 2016, 00:38 »
Sai di essere su un forum di python vero?

In ogni caso, credo che tu debba sempre inizializzare a NULL i puntatori prev e next di una lista al momento della creazione.
Inoltre, io non sarò un bravo programmatore, ma non vedo il senso di fare dynamic allocation in quel modo..

Nel caso delle semplicemente concatenate io personalmente preferisco l'iterazione alla ricorsione.. farei un:
[codice]tiponodo2* insertorder(tiponodo2* list_, tiponodo2* node) {
    if (list_ == NULL) {
        return n;
    }

    if (list_->mese > node->mese) {
        node->next=list_;
        return node;
    }

    tiponodo2* temp_index = list_;   // bisogna fare una copia e lavorare sulla copia, altrimenti si perde il valore di list_ scorrendolo
    while (temp_index->next != NULL) {
        if (temp_index->next->mese > node->mese) {   // se il nodo seguente a quello su cui sto scorrendo verifica l'ordinamento,
                                                     // inserisco node tra il nodo presente e il successivo.
            node->next=temp_index->next;   //occhio a non invertire queste due fasi
            temp_index->next=node;
            return list_;   // una volta inserito il nodo, posso ritornare il puntatore al primo elemento della lista
        }
    }
    temp_index->next=node;   // se sono arrivato a questo punto, node non ha mai verificato la condizione e va posto in fondo alla lista
    node->next=NULL;   // non dovrebbe essere necessario se viene fatto nell'inizializzazione
    return list_;
}[/codice]

io per una semplicemente concatenata farei così. L'ho fatto senza testarlo, ma dovrebbe essere giusto.
Consiglio vivamente di farsi un disegno a mano su un pezzo di carta quando si gioca con liste in C/C++, è l'unica cosa che mi salva da errori.

Spero ti ispiri per le doppiamente concatenate!
« Ultima modifica: Luglio 01, 2016, 00:41 da bebo »