Elemente in einer Liste sortiert einfügen
-
Hallo,
ich habe ein Problem mit der Methode add, und zwar möchte ich, dass beim Einfügen direkt sortiert wird.
(z.B: hallo c plusplus forum -> c forum hallo plusplus)
Ich habe es versucht ähnlich wie insertion sort zu machen, doch es gelingt mir nicht, dies an meiner add-methode zu implementieren:
hier mein code:#include<stdio.h> #include<stdlib.h> #include<string.h> typedef struct node{ struct node *next; char *s; }node; typedef node *ptr; ptr head =NULL; void show_list(ptr l){ if(l!=NULL){ l=l->next; for(;l;l=l->next) printf("%s\n", l->s); } } void delete_liste(ptr l){ while(l){ ptr n=l->next; free(l); l=n; } } ptr add(ptr l, char *s){ if(head==NULL){ l=malloc(sizeof(node)); l->s=s; l->next=head; head=l; } ptr last=head; while(last->next!=NULL) last=last->next; ptr n=malloc(sizeof(node)); n->s=s; n->next=NULL; last->next=n; return l; } int main(int argc, char *argv[]){ ptr l=NULL; int i; for(i=1;i<argc;i++){ l=add(l,argv[i]); } show_list(l); delete_liste(l); return 0; }
-
Hallo pronix_2008,
in deiner add Funktion sortierst du nicht!
Du müßtest dort strcmp aufrufen, damit du entscheiden kannst,
welcher String "größer" ist.Dazu kommt noch, dass du in deinem Programm globale Variablen
wie head verwendest. Soetwas birgt immer eine Fehlerquelle.Deine Add-Funktion müßte etwa so aussehen: (Pseudocode)
function add(l, el) begin last = NULL; first = l; solange l != NULL und l->s nicht größer als el begin last = l l = l->next end n = neues element n->next = l; if (last) { last->next = n; return first; } return n; end
und deine show_list function ist auch noch fehlerhaft.
Gruß mcr
-
Hier mal ein wahrscheinlich höchst verbesserungswürdiger Algorithmus von mir (trivialer Ansatz ohne durchdachte Verbesserungen):
void add(NODE **list, const char *str) { // Liste noch leer if(*list == NULL) { *list = malloc(sizeof(NODE)); strncpy( (*list)->str, str, SIZE); (*list)->next = NULL; return; } // Liste besitzt mindestens 1 Element NODE *i, *j; for(i=(*list); i != NULL; i = i->next) { // list zeigt auf erstes und einziges Element, s.o. // Vergleich/Einordnung anhand der Zeichenfolge int result = strcmp(str, i->str); if(result < 0) { if(i==(*list)) { // Element wird ganz am Anfang eingefügt NODE *tmp = *(list); // Zwischenspeicherung (*list )= malloc(sizeof(NODE)); // neues Element an Anfang setzen strncpy((*list)->str, str, SIZE); // Zeichenkette kopieren (*list)->next = tmp; // Listenanfang (neues Element) auf ehemalig Erstes zeigen lassen return; } else { // Element wird in Mitte eingefügt j->next = malloc(sizeof(NODE)); // Vorgänger zeigt auf das neue Element strncpy(j->next->str, str, SIZE); // j->next: neues Element (s.o.). Kopieren... j->next->next = i; // neues Element zeigt auf Nachfolger (i) return; } } else if(result == 0) { // Element direkt danach einfügen. Auch davor möglich if(i->next == NULL) { // Einfügen am Ende i->next = malloc(sizeof(NODE)); strncpy(i->next->str, str, SIZE); i->next->next = NULL; // neues Element liegt am Listenende return; } else { // Einfügen in Mitte NODE *tmp = i->next; // alten Nachfolger speichern i->next = malloc(sizeof(NODE)); strncpy(i->next->str, str, SIZE); i->next->next = tmp; // an Nachfolger anschließen return; } } else if(result >0) { // neues Element größer als das von i Verwiesene -> weiterlaufen in Liste, // bis (eine der Bedingungen oben eintrifft oder) das Listenende erreicht wird if(i->next == NULL) { // Listenende erreicht -> Einfügen am Ende i->next = malloc(sizeof(NODE)); strncpy(i->next->str, str, SIZE); i->next->next = NULL; // neues Element am Listenende return; } else if(strcmp(str, i->next->str) <= 0) { // nur einfügen, falls kleiner oder gleich dem Nachfolger, //ansonsten wird weitergelaufen NODE *tmp = i->next; i->next = malloc(sizeof(NODE)); strncpy(i->next->str, str, sizeof(str)); i->next->next = tmp; // Zeiger auf Nachfolger return; } } // Zeiger j zeigt auf das Vorgängerelement von i. j ist erst nach einem Durchlauf initialisiert, // wird aber auch nur für Einfügen in der Listenmitte gebraucht, daher in Ordnung. // (j wird "bereits" oben benutzt) j = i; } }