Wie kann ich ohne den Gebrauch von Bibliotheken eine solche Liste sortieren? (Dynamische Speicherverwaltung in C)

Question

Thema: Dynamische Speicherverwaltung in C in Verbindung mit einfach verketteten Listen.

Wie kann ich ohne den Gebrauch von Bibliotheken eine solche Liste sortieren? Insbesondere wenn die Liste Stringwerte gespeichert hat.

Ich habe bereits versucht einen einfachen Bubblesort zu implementieren, stoße dabei aber immer wieder auf Probleme im Umgang mit den Pointern und dem Vertauschen der Werte.

Answer 1

/**
 * Vertauscht zwei Zeichenketten in einem Feld.
 *
 * @param strings Feld von Zeichenketten
 * @param i      Index einer Zeichenkette
 * @param j      Index einer Zeichenkette
 */
void swap(char* strings[], int i, int j) {
    char* tmp = strings[i];
    strings[i] = strings[j];
    strings[j] = tmp;
}

Dynamische Speicherverwaltung ohne Bibliotheken gibt's in C nicht. Für dynamische Speicherverwaltung benötigst du malloc oder seine Geschwister.

eine solche Liste sortieren

Hängt von den Details der verwendeten Datenstruktur ab.

Comments

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

typedef struct Auto Auto;

struct Auto {
    char name[36];
    struct Auto *naechstes;
};

Auto* erstellen(char *name)
{
     Auto *i = malloc(sizeof(Auto));
     strcpy(i -> name, name);
     i -> naechstes = NULL;
     return i;
}

Auto* sortieren(Auto *liste)
{
     Auto *erstes = liste;
     Auto *zweites = liste -> naechstes;
 
     Auto *zwischenspeicher = NULL;
 
     if(strcmp(erstes -> name, zweites -> name) > 0)
     {
 
     }
     return liste;
}

Auto* autos_einlesen(FILE *eingabe){
    Auto *start = NULL;
    Auto *i = NULL;
    Auto *naechstes = NULL;
    char name[36];
    
    for(; fgets(name, 36, eingabe) != NULL; i = naechstes)
    {
         naechstes = erstellen(name);
         if(start == NULL) { start = naechstes; }
         if(i != NULL) 
         { 
               i-> naechstes = naechstes; 
         }
 }
 start = sortieren(start);
return start; 
}

Wahrscheinlich ist es mit etwas Code verständlicher was mein Problem ist.

Der Code funktioniert soweit und liest aus einer eingabe Datei Strings ein und alloziert zu jedem Auto Speicher im Heap. Allerdings weiß ich beim sortieren nicht wie ich mit den Pointern umzugehen habe. Meine Idee war wie bereits erwähnt einen einfachen Bubblesort zu verwenden.

---

Auto* sortieren(Auto *liste)
{
    Auto kopf = {"", liste};
    
    for (Auto* a = 𝕜 a->naechstes != NULL; a = a->naechstes) {
        Auto* kleinstes = a;
        for (Auto* b = a->naechstes; b->naechstes != NULL; b = b->naechstes) {
            if (strcmp(kleinstes->naechstes->name, b->naechstes->name) > 0) {
                kleinstes = b;
            }            
        }

        if (a != kleinstes) {
            Auto* erstes = kleinstes->naechstes;
            kleinstes->naechstes = erstes->naechstes;
            erstes->naechstes = a->naechstes;
            a->naechstes = erstes;
        }
    }

    return kopf.naechstes;
}