Einfach verkettete Listen nach der Kundennummer sortieren?

Wie sortiert man einfach verkettete Listen nach der Kundennummer? Also als Beispiel hat man den Namen, Vornamen, und die Kundennummer. Beispiel main-funktion code:

root = createCustomer(1, "Hans", "Maurer");

addCustomer(root, createCustomer(3, "Tatjana", "Roth"));

addCustomer(root, createCustomer(2, "Anna-Maria", "Schmidt"));

Dann soll als erstes Hans Maurer, als zweites Anna-Maria Schmidt und als letztes Tatjana Roth kommen.

2 Antworten

Destranix

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

programmieren, Informatik, Programmieren & Softwareentwicklung

11.06.2022, 12:38

Es gibt verschiedenste Sortieralgorithmen:

https://de.wikipedia.org/wiki/Sortierverfahren

Wenn du die Liste nachträglich sortieren möchtest, würde ich Merge-Sort verwenden, da sich das auf Listen einfach realisieren lässt.

Wenn du die Liste beim Hinzufügen neuer Elemente sortieren möchtest, würde sich Insertion-Sort anbieten.

RopickHD

Fragesteller

11.06.2022, 12:46

Ich hab mir schonmal Insertion-Sort angeguckt, aber das ist irgendwie extrem kompliziert für mich. Werde es trotzdem nochmal versuchen, wenns dann nicht klappt mach ich einfach Merge-Sort. Vielen Dank für deine Hilfe.

Destranix

11.06.2022, 12:47

@RopickHD

Eigentlich ist das extremst einfach:

Du gehst durch alle Elemente deiner Liste der Reihe nach durch.
Hast du den passenden Platz für das Element gefunden, fügst du es dort ein.

Einzige Schwierigkeit besteht darin, sich beim Durchhangeln und EInfügen nicht zu vertun mit den Pointern.

Merge-Sort ist by-the-way nicht einfacher, sondren schwerer hier.

RopickHD

Fragesteller

11.06.2022, 12:56

@Destranix

Also muss ich erstmal alle Elemente der Liste eingelesen haben?

RopickHD

Fragesteller

11.06.2022, 12:58

@Destranix

Bei mir ist das Problem das ich nicht weiß wie man ein bestimmtes Element dann verschiebt. Also als Beispiel eins nach hinten oder vorne

Destranix

11.06.2022, 13:02

@RopickHD

Ne, musst du nicht. Du sortierst das Element beim Einlesen ein.
Du greifst dir quasi immer ein Element und vregleichst das mit deinem neuem. Wenn das größer/kleiner ist, dann gehst du weiter zum nächstem Element, wenn nicht, dann sortierst du es entsprechend ein.

Das "Verschieben" funktioniert so, wie das Einfügen auch, das habe ich dir unter einer anderen Frage erklärt. (Wenn da noch Rückfragen offen sind, würde ich dich bitten, diese dort zu stellen.)

RopickHD

Fragesteller

11.06.2022, 13:10

@Destranix

Ok die Logik hab ich jetzt mehr oder weniger verstanden. Das jetzt umzusetzen wird aber schwer. :D

RopickHD

Fragesteller

11.06.2022, 13:16

@Destranix

Aber muss den Insert-Sort in eine neue Funktion schreiben bzw. kann ich das auch in diese Funktion schreiben?

customer* createCustomer(int zahl, char* vorname, char* name)

{

customer * neu = (customer*)malloc(sizeof(customer));

if(neu==NULL)

{

exit(-1);

}

strcpy(neu->vorname, vorname);

strcpy(neu->name, name);

neu->kundennummer = zahl;

neu->next = anker;

anker = neu;

return anker;

}

Destranix

11.06.2022, 13:17

@RopickHD

Ich würde das bei der "addCustomer"-Funktion dazuimplementieren.

RopickHD

Fragesteller

11.06.2022, 13:21

@Destranix

Ok gut zu wissen. Die Sache ist ich benutze stetig meinen eigenen Anker den ich global definiert habe, weil ich nicht genau weiß wie ich root benutzen kann (hab ich bei der Frage ganz oben stehen), deswegen steht in der addCustomer-Funktion eigentlich gar nichts ^^

Destranix

11.06.2022, 13:23

@RopickHD

Das wäre eine Frage, die man unter der anderen Frage klären sollte.

Ich vermute entweder ist die Methodensignatur falsch oder man möchte von dir, dass das Root-Element ein Dummy-Element ist, also kein eigenes Element, sondern nur ein verweis auf die Liste.

RopickHD

Fragesteller

11.06.2022, 13:24

@Destranix

Hmm ja wie würde man das aber machen? Weil ich benutz ja root auch für die addCustomer-Funktion.

Destranix

11.06.2022, 13:27

@RopickHD

Schreib mir doch mal unter der Antwort auf die andere Frage die Methoden-Signatur.

https://www.gutefrage.net/frage/einfach-verkettete-liste-c

Vielleicht lässt sich damit das Problem bereits lösen. (wenn das nämlich eigentlich ein Doppel-Pointer ist, dann braucht es kein Dummy).

RopickHD

Fragesteller

11.06.2022, 13:28

@Destranix

Ok werd ich machen

RopickHD

Fragesteller

11.06.2022, 13:28

@Destranix

ich schreib dir da mal einfach den ganzen code :D

Destranix

11.06.2022, 13:29

@RopickHD

ich schreib dir da mal einfach den ganzen code

Eher die Aufgabenstellung.

RopickHD

Fragesteller

11.06.2022, 13:30

@Destranix

KarlRanseierIII

Von gutefrage auf Grund seines Wissens auf einem Fachgebiet ausgezeichneter Nutzer

programmieren, Informatik, Programmieren & Softwareentwicklung

11.06.2022, 13:43

Am einfachsten sind Sortierverfahren, bei denen Du eien neue Liste aufbaust/aufbauen kannst und bei denen Du keinen Indexzugriff brauchst.

Wenig effiziente Varianten wären Beispielsweise Minsort, Maxsort, Insertionsort.

Eine effiziente Variante mit relativ leichter Umsetzung ist ein abgewandelter Mergesort, bei dem Du direkt mit den Mergeschritten beginnst.

Ähnliche Fragen

Einfach verkettete Liste (C)?

Also in meiner main-Funktion steht das:

customer *root = NULL;

root = createCustomer(1, "Hans", "Maurer");

addCustomer(root, createCustomer(3, "Tatjana", "Roth"));

printList(root);

Mein Struct und createCustomer-Funktion sehen so aus:

typedef struct customer{

char vorname[20];

char name[20];

int kundennummer;

struct customer * next;

}customer;

customer * root = NULL;

customer* createCustomer(int zahl, char* vorname, char* name)

{

customer * neu = (customer*)malloc(sizeof(customer));

if(neu==NULL)

{

exit(-1);

}

strcpy(neu->vorname, vorname);

strcpy(neu->name, name);

neu->kundennummer = zahl;

neu->next = root;

root = neu;

return root;

}

Ich glaube das sollte soweit stimmen, aber ich weiß nicht wie ich die addCustomer-Funktion schreiben soll. Ich habe vieles schon probiert, aber nichts klappt. Ich wäre für jede Hilfe dankbar. Liegt es vllt. an meiner printList-funktion?

void printList(customer* root)

{

customer * ptr = root;

while(ptr!=NULL)

{

printf("%d: %s %s\n", ptr->kundennummer, ptr->vorname, ptr->name);

ptr = ptr->next;

}

...zur Frage

Was ist an diesem Code falsch (C)?

Was ist an diesem Code falsch?

Das ist die main-Funktion:

Ich bekomme 42 1 3 4 99 raus, aber es soll so 42 3 4 1 99 aussehen.

...zur Frage

C Programm das Brüche multipliziert/dividiert?

Also ich muss ein Programm schreiben, was 2 Brüche multipliziert/dividiert. Dazu soll eine ich Struktur und Funktionen benutzen. Eine Beispieleingabe wäre "1/2" und "3/4".

Ich weiß nicht wie ich dabei vorgehen soll. Wäre für jede Hilfe dankbar.

...zur Frage

Welcher Nachname beim Kind?

Hallo Leute,

mein Partner und ich bekommen bald unser erstes Kind. Mein Partner hat 2 Nachnamen. Wenn unser Kind sein Nachname bekommt, muss er dann beide Nachnamen bekommen? Oder kann er auch nur einen übernehmen?

Beispiel:

Partner heißt

Hans Müller Schmidt

Kind heißt

Peter Schmidt?

...zur Frage

Eine Funktion die das Minimum eines Zahlen Arrays ausgibt (C)?

Also ich soll bekomm ein Array und die Länge des Arrays. Wie würde eine void Funktion aussehen?

Mein Code sieht bisher so aus, aber da gibt es Fehler und ich weiß nicht woran das liegt:

void minimum(int* numbers, int laenge) {

for(int i=0; i<laenge; i++)

{

for(int k=0; k<laenge; k++)

{

if(numbers[i]<numbers[k])

{

numbers[i] = numbers[i];

}

else

{

numbers[i] = numbers[k];

}

Fehler: invalid use of void expression

Würde mich über Vorschläge freuen, aber bitte keine fertigen Codes :D

...zur Frage

Wie findet ihr es, wenn man seinem Kind 2 Vornamen gibt, wobei beide Vornamen dieselbe Endung haben wie "Susanna Anna", "Maria Sophia", "Darius Marius"?

"Mara Dilara", "Sascha Natascha", "Hans Franz", "Giselle Isabelle", "Florian Fabian", "Arlett Odett", "Jannis Johannis", "Marina Celina"

...zur Frage

Was sind kürzel?

hi leute, was sind genau kürzel von namen?

ich mach mal ein beispiel, ich muss meinen vor und nachnamen angeben und das kürzel, wie würde von zum beispiel "hans schmidt" (ausgedachter name) der kürzel lauten? mfg

...zur Frage

Warum enden die Namen aller Mädchen die Süß oder hübsch sind mit A?

Ich kenne nur hübsch Mädchen die mit a enden zum Beispiel Anna Lea Maria

...zur Frage

Was muss man alles installieren, um in VSCode in C programmieren zu können?

Ich habe die C/C++ Extension installiert und Code Runner. Dennoch funktioniert es nicht

Was benötige ich noch?

...zur Frage

[C] Zahl aus txt-Datei lesen und als int speichern?

Hi.

Ich habe eine Aufgabenstellung bekommen wobei ich Zahlen aus einer .txt Datei einlesen und damit weiterarbeiten soll.

Also im Programm soll es ein int sein.

Nur bin ich ein kompletter Anfänger in Programmieren und weiß nicht welchhe Optionen ich habe.

Kann mir jemand verraten wie ich weiter komme? Bitte mit Syntax.

...zur Frage

Was ist der Unterschied zwischen einem lokal/statisch und einem dynamisch deklarierten Struct/Struktur in C?

Ich weiß, wie man sowas deklariert, zumindest finde ich folgende Folien dafür hilfreich:

https://www.luis.uni-hannover.de/fileadmin/kurse/material/CKurs/c9_Strukturen.pdf

Was mir aber nicht klar ist, ist, wann man Structs lokal, wann statisch deklarieren sollte, also die Verwendung, und was der Zweck der jeweiligen Implementierung ist.

Liebe Grüße,

Katharina

...zur Frage

C++: invalid use of non-static data member ...?

Hallo, ich habe in C++ einen Header für ein Projekt geschrieben aber ich kann innerhalb einer Klasse nicht auf eine Variable zugreifen.

Es kommt immer der Fehler:

..\ast.cpp:61:19: error: invalid use of non-static data member 'Tree::nodes'

p.set_type(Tree::nodes[id].get_type());

Hier ist der Code:

ast.h:

#ifndef AST_H_
#define AST_H_

class Tree {
public:
    class Node {
    public:
        enum class Type {
            METHOD,
            IF,
            WHILE,
            STATEMENT,
            EXPRESSION
        };

        void set_id(int id);
        void set_id_parent(int id_parent);
        void set_content(const char* content);
        void set_type(Type type);

        Type get_type();
        const char* get_content();
        int get_id();
        int get_parent_id();
        int* get_child_ids();

    private:
        Type m_type{};
        const char* m_content{};
        int  m_id=0;
        int  m_id_parent=-1;
        int* m_child_ids{};
    };

    void create_node(int parent, const char* content);

    Node get_node(int id);

private:
    Node* nodes{};
    int node_amount=0;
};

#endif

ast.cpp:

#include "ast.h"

void Tree::Node::set_id(int id) {
    m_id = id;
}

void Tree::Node::set_id_parent(int id_parent) {
    m_id_parent = id_parent;
}

void Tree::Node::set_content(const char *content) {
    m_content = content;
}

void Tree::Node::set_type(Type type) {
    m_type = type;
}

const char* Tree::Node::get_content() {
    return m_content;
}

Tree::Node::Type Tree::Node::get_type() {
    return m_type;
}

int Tree::Node::get_id() {
    return m_id;
}

int Tree::Node::get_parent_id() {
    return m_id_parent;
}

int* Tree::Node::get_child_ids() {
    return m_child_ids;
}

//

void Tree::create_node(int parent, const char *content) {
    Node p;
    p.set_id(node_amount);
    p.set_id_parent(parent);
    p.set_content(content);
    nodes[node_amount] = p;
    node_amount++;
}

Tree::Node get_node(int id) {
    Tree::Node p;
    p.set_type(Tree::nodes[id].get_type());
    return p;
}

Ich hoffe jemand kann mir sagen warum dieser Fehler kommt

Außerdem wollte ich etwas C benutzen und lernen, also hätte ich noch eine zweite Frage: Kann mir jemand sagen wie ich das ganze nicht in C++ sondern in C mache?

...zur Frage

Zwei Zufallszahlen in einer do-while Schleife erzeugen?

Servus Leute, ich habe nächste Woche Informatik-Prüfung und bin bei dieser Übung hängengeblieben:

Schreiben Sie ein Programm für folgende Aufgabenstellung:

In einer do-while Schleife sollen zwei Zufallszahlen im Bereich von 0 bis 20 erzeugt werden. Für diese beiden Zahlen werden die Grundrechnungsarten (Addition, Subtraktion, Multiplikation, Division) und die Modulo Berechnung durchgeführt.

Die Division und die Modulo Berechnung soll nur durchgeführt werden, wenn die zweite Zahl ungleich O ist (Division durch O ist nicht definiert). Statt der Division bzw. der Modulo Berechnung soll in diesem Fall die Meldung „,Division durch 0 ist nicht erlaubt" ausgegeben werden.

Die Schleife soll maximal 10 mal ausgeführt

werden beziehungsweise solange der Benutzer in einer Abfrage für die Wiederholung ein ,j' eingibt.

Die Ausgabe auf dem Bildschirm soll annähernd so aussehen:

...zur Frage

Was ist an diesem Code falsch (C)?

Ich bin eher neu bei den einfach verketteten Listen. Also bitte ich um Rücksicht :D Freue mich um jede Hilfe. Im Grunde soll der Code neue Zahlen hinten dranhängen.

...zur Frage

Was möchtest Du wissen?

Deine Frage stellen