Migliorare il mio mergesort per liste concatenate. Come?

Question

prima di tuffarsi nelle spiegazioni, si dovrebbe essere consapevoli del fatto che il codice riportato di seguito potrebbe essere davvero male. Ho iniziato la programmazione circa 2 mesi fa (un paio d'ore lì e non). Quindi sono inesperienza, il mio stile di codifica è molto migliorabile e mi manca ancora la pratica e un sacco di (base) della conoscenza. Questo include anche me chiamare le cose con il nome sbagliato, probabilmente:.)

mi sono interessato in algoritmi (università) e voleva praticare alcuni trattamenti puntatore (avuto abbastanza alcuni problemi con esso inizialmente) così ho deciso di fare mergesort con liste collegate singolarmente e vedere come si svolge rispetto all'algoritmo mergesort della mia professore (che ordina array). E no questo non è lavoro (nessuno del mio corso universitario (ingegneria elettrica) hanno compiti a casa) -. Questo sono io il miglioramento nella comprensione di algoritmi, C e semplicemente praticando cose

---

Il mio codice funziona già. A scopo di verifica ho sempre creato liste ordinate inversa. E 'ancora manca qualcosa per casi come quello della lista è NULL.

Quindi, prima di pubblicare il codice di questo è la struct sto usando:

struct list{
  int nbr;
  struct list *next_el;
};
typedef struct list LIST;
typedef LIST *z_LIST;

Ho due funzioni, Mergesort e si fondono. mergesort restituisce il nuovo capo della (sotto) gli elenchi ordinati e ritorna di unione il capo del fuse sequenze.

In questo momento io do mergesort l'attuale capo della lista non ordinata e la quantità di elementi. E poi rompe l'elenco in modo ricorsivo (ovviamente :)). Non sono sicuro su come molto da dire sul codice seguente. Se qualcosa non è chiaro io rispondo e spiegherò il più velocemente possibile, ma

z_LIST mergeSort ( z_LIST head, int length ) {

  int steps;
  int m = 0;
  z_LIST head1 = NULL, head2 = NULL, new_head = NULL;

if( length > 1) {

  m = (length+1)/2;


  head2 = head; 
  for(steps = 0; steps<m; steps++) {
    head2 = head2->next_el;
  }

  head1 = mergeSort(head, m);
  head2 = mergeSort(head2, length-m);

  new_head = merge(head1, head2, m, length-m);

  return new_head;

  } else {
    return head;
  }
}

unione riceve le teste dei due sotto-liste (che sono o un elemento o sequenze già ordinate) e gli elementi del primo e secondo elenco.

z_LIST merge (z_LIST head1, z_LIST head2, int l1, int l2)  {

  int i,j;
  z_LIST part1 = head1, part2 = head2;
  z_LIST temp_head = NULL, head = NULL;

/*First I let it check what the head of the new list is going to 
be and thus initiating the merging process with either i=1/j=0
or i=0/j=1.*/

  if(part1->nbr < part2->nbr){
    head = part1;
    if(part1->next_el != NULL)  {
      part1 = part1->next_el;
    }
    i=1;
    j=0;
  } else {
    head = part2;
    if(part2->next_el != NULL)  { //The last element of the original list points
      part2 = part2->next_el;     //to NULL. If I would then make part2 = NULL,
    }                             //then there wouldn't be part2->nbr ->lots
    i=0;
    j=1;
  }

  temp_head = head;

  while( (i<l1) || (j<l2) ) {
    if( ((part1->nbr < part2->nbr) && i<l1)||( j>=l2 ))  {
      temp_head->next_el = part1;
      part1 = part1->next_el;
      temp_head = temp_head->next_el;
      if (j>=l2)  { //If j>=l2 then I let merge add one more item of list1
       break;       //since list 1 is already sorted and linked correctly.
      }             //Same below. Should shave off some operations/time?
      i++;
    } else {
      temp_head->next_el = part2;
      part2 = part2->next_el;
      temp_head = temp_head->next_el;
      if (i>=l1)  {
        break;
      }
      j++;
    }
  }

  return head;
}

Così mi piacerebbe trasmettere eventuali osservazioni su quello che ho fatto semplicemente stupido, dove non ci ho pensato su eventuali problemi, in cui un codice di ingresso del codice pausa o su come farlo meglio, sono sicuro che ci sono un fermo un po 'di possibilità di miglioramento. Grazie in anticipo.

Answer 1

La struttura 'normale' per la fase di fusione di una specie è:

set output list to empty
while (list1 not empty && list2 not empty)
{
    if (list1->headvalue < list2->headvalue
        move head of list1 to output list
    else
        move head of list2 to output list
}
while (list1 not empty)
    move head of list1 to output list
while (list2 not empty)
    move head of list2 to output list

L'operazione di 'movimento' include l'aggiornamento del puntatore al successivo elemento nella lista.

Hai una struttura un po 'diversa in funzione merge().

E 'anche aconventional di richiedere le liste da contare. Normalmente, si determina la fine dell'elenco utilizzando 'successivo è nullo' o 'successivo è testa' a seconda se l'elenco è puramente lineare o se si tratta di una lista circolare.