Domanda Ordinare una lista

[burgos13]

Ciao ragazzi!
Sapreste dirmi il modo più semplice ed efficace per ordinare una lista secondo un certo criterio?? E invece per cancellare un elemento al suo interno(ovvero scorrere la lista per trovare un elemento, sempre secondo un certo criterio, per poi eliminarlo e ritornare quindi la lista senza quel valore)??
Grazie a tutti anticipatamente!

 

[CrashTest]

Ciao ragazzi!
Sapreste dirmi il modo più semplice ed efficace per ordinare una lista secondo un certo criterio??
Grazie a tutti anticipatamente!

Che tipo di elementi contiene la lista? Sono ordinati o no? Senza sapere nulla su come è fatta la lista direi che puoi provare ad implementare il quicksort

 

[burgos13]

Che tipo di elementi contiene la lista? Sono ordinati o no? Senza sapere nulla su come è fatta la lista direi che puoi provare ad implementare il quicksort

Aspetta, cosa intendi per "sono ordinati"?? La lista devo ordinarla quindi inizialmenti sono inseriti in modo casuale...inoltre ogni elemento della lista è un elemento di una struttura.
Grazie per la risposta

 

[XXXGcs]

Cè un po di confusione in ciò che scrivi la tua lista cosa contiene interi?

Messaggio unito automaticamente: 14 Dicembre 2018

Se intendi ordinare una lista in cui ci sono numeri , ho capito senno no

Messaggio unito automaticamente: 14 Dicembre 2018

C++ o C?

 

[xDazuk]

Per ordinare una lista comincia da algoritmi più semplici come il Bubble Sort, il Quick Sort è già abbastanza complicato con gli array "normali" figurati con un array di strutture. Per l'eliminazione se la lista è ordinata fai una ricerca binaria e una volta che hai trovato l'elemento lo elimini, se non è ordinata l'unico modo è una ricerca sequenziale. Per il Quick Sort, se non vuoi implementarlo tu c'è la funzione qsort (ora non mi ricordo in quale header) dove ti basta scrivere solo la funzione per verificare quale elemento sia maggiore.

PS: se proprio vuoi prestazioni estreme allora devi provare il Bogo Sort! (Ovviamente si scherza...)

 

[burgos13]

Cè un po di confusione in ciò che scrivi la tua lista cosa contiene interi?

Messaggio unito automaticamente: 14 Dicembre 2018

Se intendi ordinare una lista in cui ci sono numeri , ho capito senno no

Messaggio unito automaticamente: 14 Dicembre 2018

C++ o C?

No la mia lista contiene elementi di strutture...ti faccio un esempio. In C++

struct struttura{
    char a[20];
    char b[15];
    int x;
}

struct lista{
    struttura s;
    lista *next;
}

Come faccio ad ordinarla per esempio in ordine alfabetico per char a??

Messaggio unito automaticamente: 14 Dicembre 2018

Per ordinare una lista comincia da algoritmi più semplici come il Bubble Sort, il Quick Sort è già abbastanza complicato con gli array "normali" figurati con un array di strutture. Per l'eliminazione se la lista è ordinata fai una ricerca binaria e una volta che hai trovato l'elemento lo elimini, se non è ordinata l'unico modo è una ricerca sequenziale. Per il Quick Sort, se non vuoi implementarlo tu c'è la funzione qsort (ora non mi ricordo in quale header) dove ti basta scrivere solo la funzione per verificare quale elemento sia maggiore.

PS: se proprio vuoi prestazioni estreme allora devi provare il Bogo Sort! (Ovviamente si scherza...)

Il mio problema è cercare di implementare anche un comune Bubble Sort in una lista contenente elementi di una struttura invece che per esempio in un array di caratteri...
Per quanto riguarda l'eliminazione, dopo aver trovato l'elemento cosa dovrei fare?? Perche con il classico "delete x; x=x->next" mi ritorna valori errati!!

 

[St3ve]

Gli algoritmi per confronto si basano sul fatto che presi due elementi tu sai dire quale elemento dovrà precedere l'altro. Il modo di calcolare l'elemento più piccolo lo definisci tu, nel tuo caso vuoi un ordinamento lessicografico sul campo a della tua struttura. Per cancellare un elemento ovviamente non puoi fare delete x; x=x->next;, perché nel momento in cui fai la delete l'elemento non esiste più. Devi dire che il predecessore di x avrà per successivo il successore di x, poi puoi cancellare il tuo elemento. Per l'ordinamento ci sono diversi modi, ma nel momento in cui definisci una funzione di swap (scambiare due elementi nella lista) sei sostanzialmente libero di usare qualsiasi algoritmo basato sul confronto.

Solitamente mi limiterei a darti qualche consiglio e vedrei cosa ne esce, ma mi pare di aver capito che non sai proprio che pesci pigliare. Ho perso un quarto d'ora per implementare sta roba, ho scelto di utilizzare il C perché io sono dell'idea che bisogna programmare in modo decente. Tirare fuori il C++ per poi usare array di caratteri invece di stringhe, strutture invece di classi e raw pointers... beh, allora per quale motivo stiamo usando C++?

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

typedef struct data {
  char a[20];
  char b[15];
  int x;
} data;

int compare(data left, data right) { return strncmp(left.a, right.a, 20); }

void print_data(data *value) {
  printf("a = %s, b = %s, x = %d\n", value->a, value->b, value->x);
}

typedef struct node {
  struct node *next;
  data value;
} node;

node *new_node(data value) {
  node *new = malloc(sizeof(node));
  assert(new != NULL);

  new->next = NULL;
  new->value = value;
  return new;
}

node *prepend(data value, node *head) {
  node *new = new_node(value);
  new->next = head;
  return new;
}

node *previous(node *head, node *curr) {
  if (head == curr) return NULL;

  while (head && head->next != curr) head = head->next;
  assert(head);  // curr is not in the list

  return head;
}

node *swap(node *head, node *left, node *right) {
  if (left == right) return head;
  node *prev_left = previous(head, left);
  node *prev_right = previous(head, right);

  node *tmp = left->next;
  left->next = left != right->next ? right->next : right;
  right->next = right != tmp ? tmp : left;

  if (prev_left && prev_left != right) prev_left->next = right;
  if (prev_right && prev_right != left) prev_right->next = left;

  if (!prev_left) return right;
  if (!prev_right) return left;
  return head;
}

node *smallest(node *head) {
  node *min = head;

  while (head = head->next) {
    if (compare(min->value, head->value) > 0) min = head;
  }

  return min;
}

node *selection_sort(node *head) {
  node *curr = head;

  while (curr) {
    node *min = smallest(curr);
    head = swap(head, curr, min);
    curr = min->next;
  }

  return head;
}

void print_list(node *head) {
  for (; head; head = head->next) {
    print_data(&head->value);
  }
}

node *delete(node *head, node *elem) {
  node *prev = previous(head, elem);

  if (prev)
    prev->next = elem->next;
  else
    head = head->next;

  free(elem);
  elem = NULL;
  return head;
}

int main() {
  node *head = prepend((data){"Mario", "Rossi", 15}, NULL);
  head = prepend((data){"John", "Doe", 20}, head);
  head = prepend((data){"Ciccio", "Pasticcio", 10}, head);
  head = prepend((data){"Mickey", "Mouse", 40}, head);
  head = prepend((data){"Donald", "Duck", 30}, head);

  printf("Unsorted: \n");
  print_list(head);

  head = selection_sort(head);
  printf("\nSorted:\n");
  print_list(head);

  printf("\nRemoving the third element:\n");
  head = delete (head, head->next->next);
  print_list(head);

  printf("\nDeleting the whole list\n");
  while (head) head = delete(head, head);
  print_list(head);

  return 0;
}

Alcune cose sono un po' tricky se non le hai mai viste, potrebbe anche esserci qualche bug, prenditi un po' di tempo per analizzarlo bene e fammi sapere se c'è qualcosa che non ti è chiaro. Ho tenuto buona la tua idea di lista, ma sappi che ci sono diverse strategie su come strutturarla.

 

[burgos13]

Gli algoritmi per confronto si basano sul fatto che presi due elementi tu sai dire quale elemento dovrà precedere l'altro. Il modo di calcolare l'elemento più piccolo lo definisci tu, nel tuo caso vuoi un ordinamento lessicografico sul campo a della tua struttura. Per cancellare un elemento ovviamente non puoi fare delete x; x=x->next;, perché nel momento in cui fai la delete l'elemento non esiste più. Devi dire che il predecessore di x avrà per successivo il successore di x, poi puoi cancellare il tuo elemento. Per l'ordinamento ci sono diversi modi, ma nel momento in cui definisci una funzione di swap (scambiare due elementi nella lista) sei sostanzialmente libero di usare qualsiasi algoritmo basato sul confronto.

Solitamente mi limiterei a darti qualche consiglio e vedrei cosa ne esce, ma mi pare di aver capito che non sai proprio che pesci pigliare. Ho perso un quarto d'ora per implementare sta roba, ho scelto di utilizzare il C perché io sono dell'idea che bisogna programmare in modo decente. Tirare fuori il C++ per poi usare array di caratteri invece di stringhe, strutture invece di classi e raw pointers... beh, allora per quale motivo stiamo usando C++?

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

typedef struct data {
  char a[20];
  char b[15];
  int x;
} data;

int compare(data left, data right) { return strncmp(left.a, right.a, 20); }

void print_data(data *value) {
  printf("a = %s, b = %s, x = %d\n", value->a, value->b, value->x);
}

typedef struct node {
  struct node *next;
  data value;
} node;

node *new_node(data value) {
  node *new = malloc(sizeof(node));
  assert(new != NULL);

  new->next = NULL;
  new->value = value;
  return new;
}

node *prepend(data value, node *head) {
  node *new = new_node(value);
  new->next = head;
  return new;
}

node *previous(node *head, node *curr) {
  if (head == curr) return NULL;

  while (head && head->next != curr) head = head->next;
  assert(head);  // curr is not in the list

  return head;
}

node *swap(node *head, node *left, node *right) {
  if (left == right) return head;
  node *prev_left = previous(head, left);
  node *prev_right = previous(head, right);

  node *tmp = left->next;
  left->next = left != right->next ? right->next : right;
  right->next = right != tmp ? tmp : left;

  if (prev_left && prev_left != right) prev_left->next = right;
  if (prev_right && prev_right != left) prev_right->next = left;

  if (!prev_left) return right;
  if (!prev_right) return left;
  return head;
}

node *smallest(node *head) {
  node *min = head;

  while (head = head->next) {
    if (compare(min->value, head->value) > 0) min = head;
  }

  return min;
}

node *insertion_sort(node *head) {
  node *curr = head;

  while (curr) {
    node *min = smallest(curr);
    head = swap(head, curr, min);
    curr = min->next;
  }

  return head;
}

void print_list(node *head) {
  for (; head; head = head->next) {
    print_data(&head->value);
  }
}

node *delete(node *head, node *elem) {
  node *prev = previous(head, elem);

  if (prev)
    prev->next = elem->next;
  else
    head = head->next;

  free(elem);
  elem = NULL;
  return head;
}

int main() {
  node *head = prepend((data){"Mario", "Rossi", 15}, NULL);
  head = prepend((data){"John", "Doe", 20}, head);
  head = prepend((data){"Ciccio", "Pasticcio", 10}, head);
  head = prepend((data){"Mickey", "Mouse", 40}, head);
  head = prepend((data){"Donald", "Duck", 30}, head);

  printf("Unsorted: \n");
  print_list(head);

  head = insertion_sort(head);
  printf("\nSorted:\n");
  print_list(head);

  printf("\nRemoving the third element:\n");
  head = delete (head, head->next->next);
  print_list(head);

  printf("\nDeleting the whole list\n");
  while (head) head = delete(head, head);
  print_list(head);

  return 0;
}

Alcune cose sono un po' tricky se non le hai mai viste, potrebbe anche esserci qualche bug, prenditi un po' di tempo per analizzarlo bene e fammi sapere se c'è qualcosa che non ti è chiaro. Ho tenuto buona la tua idea di lista, ma sappi che ci sono diverse strategie su come strutturarla.

Molte grazie.
Uso il C++ perchè devo farci un'esame

 

[St3ve]

Uso il C++ perchè devo farci un'esame

Il problema non è il C++, è il modo in cui ti hanno insegnato ad usarlo... e il fatto che sia intuibile da quelle 4 righe che hai scritto dice proprio tutto. Capisco che tu non puoi farci niente, ma io ho preferito scriverti un codice C decente piuttosto che un codice C++ che capiresti meglio, ma che non ha nulla a che fare con quello che è il C++ nel 2019.

 

[xDazuk]

Il problema non è il C++, è il modo in cui ti hanno insegnato ad usarlo... e il fatto che sia intuibile da quelle 4 righe che hai scritto dice proprio tutto. Capisco che tu non puoi farci niente, ma io ho preferito scriverti un codice C decente piuttosto che un codice C++ che capiresti meglio, ma che non ha nulla a che fare con quello che è il C++ nel 2019.

Purtroppo è un problema che ho avuto anche io all'università. Al corso di Fondamenti il nostro prof aveva deciso di usare il C++, il problema è che essendo il corso di fondamenti abbiamo utilizzato un approccio C style, per farti capire ci aveva proibito l uso della libreria string quando ora tutti i libri consigliano di usare string a char* in C++, facevamo le liste concatenate con le strutture spostando i puntatori,cioè del C++ non usavamo nulla, ci ha spiegato la programmazione OOP alle ultime 3 lezioni in modo molto approssimato.