Die Verbesserung meines mergesort für verkettete Listen. Wie?

Question

, bevor ich tauchen Sie ein in Erklärungen, sollten Sie sich bewusst sein, dass der folgende Code könnte wirklich schlecht sein. Ich habe vor ca. 2 Monaten Programmierung (ein paar Stunden dort und dort). Also ich bin unerfahren ist meine Codierung Stil sehr verbesserungsfähig, und ich immer noch Fehl Praxis und viele (unverwässert) Wissen. Dies schließt auch mir Dinge durch den falschen Namen rufen wahrscheinlich.)

Ich habe in Algorithmen interessiert (Universität) und wollte einige Zeiger Handhabung üben (hatte durchaus einige Probleme mit ihm zunächst) so entschied ich mich mergesort mit einfach verkettete Listen zu tun und sehen, wie es zu dem MergeSort Algorithmus meines Vergleich führt Professor (die Arrays sortiert). Und nein, das ist keine Hausaufgaben (keiner meines Studiums (Elektrotechnik) hat Hausaufgaben.) - das ist ich das Verständnis von Algorithmen, C verbessern und einfach Dinge zu üben

---

Mein Code bereits funktioniert. Für Testzwecke I Reverse sortierten Listen immer erstellt. Es ist immer noch etwas für Fälle wie fehlen, dass die Liste ist NULL.

Also, bevor Sie den Code veröffentlichen das ist die Struktur Ich verwende:

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

Ich habe zwei Funktionen, MergeSort und verschmelzen. MergeSort gibt den neuen Kopf der sortierten (sub-) Listen und merge kehrt der Kopf der Sequenzen fusioniert.

Im Moment gebe ich MergeSort den aktuellen Leiter der unsortierten Liste und die Menge der Elemente. Es bricht dann rekursiv die Liste nach unten (natürlich :)). Ich bin nicht sicher, wie viel auf dem folgenden Code zu sagen. Wenn unklar ist etwas, werde ich antworten und so schnell wie möglich erklären, aber

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;
  }
}

merge empfängt die Köpfe der zwei Unterlisten (die entweder ein Element oder den bereits sortierten Sequenzen) und die Elemente der ersten und der zweiten Liste.

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;
}

Also habe ich keine Kommentare begrüßen würde, was ich nur dumm gemacht haben, wo ich nicht über mögliche Probleme dachte, wo einige Eingabecode Unterbrechungs-Code oder, wie man es besser machen, ich bin sicher, es gibt ein noch einiges an Verbesserungsmöglichkeiten. Vielen Dank im Voraus.

Answer 1

Die ‚normale‘ Struktur für die Mischphase von einer Art ist:

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

Die ‚Bewegung‘ Operation enthält in der Liste der Zeiger auf das nächste Element zu aktualisieren.

Sie haben eine etwas andere Struktur in Ihrer merge() Funktion.

Es ist auch ein herkömmliches, die Listen zu verlangen, gezählt werden. Normalerweise entweder verwenden, können Sie das Ende der Liste bestimmen ‚nächsten null‘ oder ‚nächsten ist Kopf‘ je nachdem, ob die Liste rein linear ist oder ob es sich um eine kreisförmige Liste.