Selection Art mit verketteten Liste der

Question

Ich habe folgende Datenstruktur:

struct scoreentry_node { 
    struct scoreentry_node *next; 
    int score; 
    char name[1];  
}; 
typedef struct scoreentry_node *score_entry; 

Ich versuche, eine Funktion zu erstellen, die meine Struktur, um verbraucht und ordnet sie um aufsteigend auf den Namen basiert. Ich möchte die Eingabe ändern, ohne Speicher-Zuweisung oder Befreiung nichts:

ich Ihre Vorschläge versucht haben:

void selectionsort(score_entry *a) { 
    for (; *a != NULL; *a = (*a)->next) { 
     score_entry *minafteri = a; 
     // find position of minimal element 
     for (score_entry j = (*a)->next; j != NULL; j = j->next) { 
      if (strcmp(j->name, (*minafteri)->name) == -1) { 
       *minafteri = j; 
      } 
     } 
     // swap minimal element to front 
     score_entry tmp = *a; 
     a = minafteri; 
     *minafteri = tmp; 
    } 
} 

Ich teste den obigen Code mit den folgenden:

score_entry x = add(8, "bob", (add(8 , "jill", (add (2, "alfred", NULL))))); 
iprint("",x); 
selectionsort(&x); 
iprint("", x); 
clear(x); //Frees the whole list 

iprint() druckt die Score- und Namensfelder in der Struktur. Meine Add-Funktion ist wie folgt:

score_entry add(int in, char *n, score_entry en) {  
    score_entry r = malloc(sizeof(struct scoreentry_node) + strlen(n)); 
    r->score = in; 
    strcpy(r->name, n); 
    r->next = en; 
    return r; 
} 

Ich erhalte Haufen Fehler und meinen zweiten Druck ist die sortierte Liste nicht drucken, ist es nichts druckt. Was mache ich falsch, und was kann ich tun, um es zu beheben?

Answer 1

Sie haben das Argument selectionsortdurch Verweis übergeben:

void selectionsort(score_entry *a) { 
    for (; *a != NULL; *a = (*a)->next) 
    { 
     score_entry *minafteri = a; 
     // find position of minimal element 
     for (score_entry j = (*a)->next; j != NULL; j = j->next) { 
     if (strcmp(j->name, (*minafteri)->name) == -1) { 
     *minafteri = j; 
     } 
    } 
    // swap minimal element to front 
     score_entry tmp = *a; 
     a = minafteri; 
     *minafteri = tmp; 
    } 
} 

Answer 2

neben den Zeiger nach Adressen vorbei (siehe Kommentare unten) müssen Sie auch, wie Sie Elemente austauschen beheben zu

void selectionsort(score_entry *a) { 
    for (; *a != NULL; *a = (*a)->next) 
    { 
    score_entry *minafteri = a; 
    // find position of minimal element 
    for (score_entry j = (*a)->next; j != NULL; j = j->next) { 
     if (strcmp(j->name, (*minafteri)->name) == -1) { 
     *minafteri = j; 
     } 
     } 
    // swap minimal element to front 
    score_entry tmp = *a; 
    a = minafteri; // put the minimal node to current position 
    tmp->next = (*a)->next ; //fix the links 
    (*minafteri)->next=tmp; //fix the links 
    } 
} 

Answer 3

Dieser Code ist hässlich! Nicht nur haben Sie uns nicht mit allen Notwendigkeiten versorgt, um Ihr Problem zu reproduzieren (wir können das nicht kompilieren!), Aber Sie haben Zeiger-Abstraktionen hinter typedef versteckt (auch ein Albtraum für uns). Generell sollte man nicht einmal verkettete Listen in C verwendet mehr allein lassen Art sie ...

Dennoch gibt es zwei Antworten hier.

---

*minafteri = j; innerhalb Ihrer Schleife Ihrer Liste finden gefunden tatsächlich ändert! Warum sollte Ihre finden Schleife ändern Ihre Liste?

Antwort: es sollte nicht! Durch statt minafteri = &j->next zuweisen, werden Sie nicht die Liste mit Ihren Fund Schleife werden Modifizieren ...

---

Alternativ können Sie den Swap innerhalb dieser Schleife durchzuführen.

*minafteri = j; müssten die folgenden tauschen, in dieser Reihenfolge:

• (*minafteri)->next und j->next
• *minafteri und j

Glauben Sie, dass einzelne Codezeile der Lage ist, die von der Durchführung zwei Swaps? Nun, es wird halb durch einen von ihnen ...und entfernt dabei einen Haufen von Elementen aus Ihrer Liste!

---

Im Folgenden wird ein fehlerhaftes Versuch Swapping Elemente sein:

score_entry *minafteri = a; // half of assigning `a` to `a` 
/* SNIP! 
* Nothing assigns to `minafteri` in this snippet. 
* To assign to `minafteri` write something like `minafteri = fubar;` */ 
score_entry tmp = *a;  // half of assigning `*a` to `*a` 
a = minafteri;    // rest of assigning `a` to `a` 
*minafteri = tmp;   // rest of assigning `*a` to `*a` 

Es ist wirklich nur *a-*a und a-a zuweisen ... Glauben Sie, dass Sie das tun müssen?

Ich hätte gedacht, du dass bemerken würde, wenn Sie kreierten Ihre MCVE ... Ohh, warten Sie eine Minute! Schäm dich!

---

Konzentrieren Sie sich auf das Austauschen von zwei Knoten innerhalb einer Liste als eine kleinere Aufgabe. Wenn Sie das getan haben, sollten Sie diese Aufgabe übernehmen.

Answer 4

Es gibt mehrere Probleme im Code:

• if (strcmp(j->name, (*minafteri)->name) == -1) { ist falsch: strcmp() nicht unbedingt -1 zurück, wenn der erste String kleiner als die zweite ist, kann es keine negativen Wert zurück.
• Die Art und Weise, wie Sie die Verknüpfungen anpassen, um den unteren Eintrag zu verschieben, ist falsch: Sie können die Verknüpfung vom vorherigen Knoten zu dem Knoten, den Sie an den Anfang verschieben, nicht aktualisieren. Die Liste ist beschädigt.

Hier ist eine verbesserte Version:

void selectionsort(score_entry *a) { 
    for (; *a != NULL; a = &(*a)->next) { 
     // find position of minimal element 
     score_entry *least = a; 
     for (score_entry *b = &(*a)->next; *b != NULL; b = &(*b)->next) { 
      if (strcmp((*b)->name, (*least)->name) < 0) { 
       least = b; 
      } 
     } 
     if (least != a) { 
      // swap minimal element to front 
      score_entry n = *least; 
      *least = n->next; /* unlink node */ 
      n->next = *a;  /* insert node at start */ 
      *a = n; 
     } 
    } 
}