insertionsort linkedlist in c

[ReDruM5]

ok ich oute mich mal als linkedlist nub.
muss die methode
link listinsertion(link);
schreiben.
ich weiß wie es funkioniert, nicht wie ich es umsetze, da es lange her ist dass ich was mit linked lists gemacht habe.

zum prinzip:
ich durchlaufe die vollständige liste stück für stück, nehme das element raus an dem ich mich in der schleife befinde, schaue i ob es größer als das elemente der zweiten schleife der zweiten liste ist.

dazu brauche ich zwischenspeicher und ggf einen dummy.

ok starten wir:

link listinsertion(heada){

link input=heada;
link dummy=NEW(0, NULL);
link output=dummy->next;
link tmp;

while(input->next != NULL){ /*durchlaufen der ersten liste*/
while(output != NULL){
/* Hier ist nun der Zwischenspeicher gefragt
um das aktuelle element zu speichern*/
tmp=input->item;
/*wenn das ak. elem. > das aktuelle output, tausche*/
if(tmp>output->item){insert(tmp, output->item);}
else{
output=output->next; /*sonst springe einen weiter*/
{

void insert(link a, link b){
link c;
/*hier versage ich ganz*/

vielen dank für hilfe!
ich weiß, peinlich genug (aber linkedlist wissen läßt sich echt schwer im netz fnden).



ja soweitr so gut

 

[cart]

Ist im Prinzip ganz einfach. Hier mal ein Beispiel, welches wir mal in einer Vorlesung hatten. Es geht an einigen Stellen noch schneller und besser, aber erstmal ist es ja wichtig das es funktioniert. Natürlich musst du da noch einiges ändern, aber das Grundprinzip sollte dir danach klar sein:

/**
 * Bundestagswahl.
 * 
 * Ziel: Rekursive Strukturen/Liste
 *       malloc und free
 * 
 */
#include <stdlib.h> 
#include <stdio.h>
#include <string.h>

typedef struct partei_zaehler *ParteiZaehler;
typedef struct partei_liste  *ParteiListe;

struct partei_zaehler {
    char* partei;
    unsigned long stimmen;
};
struct partei_liste {
    ParteiZaehler zaehler;
    ParteiListe  next_element;
};

ParteiZaehler createZaehler(char* partei) {
    ParteiZaehler zaehler = (ParteiZaehler) malloc(sizeof(struct partei_zaehler));
    zaehler->partei = partei;
    zaehler->stimmen = 0;
    return zaehler;
}

ParteiListe  addZaehler(ParteiListe liste, ParteiZaehler zaehler) {
    ParteiListe neu = (ParteiListe) malloc(sizeof(struct partei_liste));
    neu->next_element = NULL;
    neu->zaehler = zaehler;
    if (liste == NULL) {
        return liste = neu;
    } else {
        neu->next_element = liste->next_element;
        liste->next_element = neu;
    }
    return liste;
}

ParteiListe addPartei(ParteiListe liste, char *partei) {
    ParteiZaehler schein = createZaehler(partei);
    liste = addZaehler(liste, schein);
    return liste;
}


ParteiZaehler findeSchein(ParteiListe liste, char* partei) {
    ParteiZaehler zaehler = NULL;
    if(liste) {
       zaehler = liste->zaehler;
       if (strcmp(partei,zaehler->partei)) {
          return findeSchein(liste->next_element,partei);
       }
    } 
    return zaehler;
}

void addiereStimmen(ParteiListe liste, char* partei, long votes) {
    ParteiZaehler zaehler = findeSchein(liste, partei);
    zaehler->stimmen += votes;
}


void printZaehler(ParteiZaehler schein) {
    printf("%8s: %ld \n",schein->partei, schein->stimmen);
}

void printListe(ParteiListe liste){
    if(liste) {
       printZaehler(liste->zaehler);
       printListe(liste->next_element);
    } 
    fflush(stdout);
}

int wahlTest(int argc, char *argv[]) {
    int i;
    ParteiListe liste = NULL;
    char *parteien[] = {"CDU","SPD","GRUENE","FDP","LINKE"};
    for(i=0;i<5;i++) {                 
        liste = addPartei(liste, parteien[i]);             
    }
    for(i=0;i<5;i++) {                 
        addiereStimmen(liste,parteien[i],1000-50*i);              
    }
    printListe(liste);
    return 0;
}

 

[Whcttyh]

zwischenspeicher brauchst du keinen.

 

[ReDruM5]

ok mal eben zusammenfassend:

eine linkedlist besteht aus einzelnen elementen (mit einer bestimmten struktur), die wiederum auf ein element der gleichen struktur zeigen uswusw bis man sagt du und du zeige auf NULL.
nehmen wir mal eine liste her:

(Florian, X)->(Peter, Z)->(Martin, H)->NULL

wie wäre es nun möglich nur Peter, Z auszugeben?
bzw wie wäre es möglich abgesehen einer schleife oder ähnlichem

?
danke

 

[cart]

Nur der letzte zeigt auf NULL. Die Liste ist zu Ende, sobald einer auf NULL zeigt. Wie du etwas "ausgeben" kannst, findest du in dem Beispiel. Da wird zwar nicht direkt was ausgegeben, aber mit den Strukturen gearbeitet. Die Pointer sind so oder so gleich.

 

[ReDruM5]

ok habs nun! danke!

 

[IPSWiZarD]

dein prof heißt nicht zufällig wulff ???

 

[ReDruM5]

lol!
wobei das nicht für wulff relevant ist

 

[cart]

Doch heisst er. Wieso? Seid ihr Erstis AI/EE in ST?

 

[ReDruM5]

rofl
bin 5. sem, hab aber bisher nix getan um es mal ehrlicherweise zuzugeben

 

[cart]

5. Semester und C machen?
Etechniker?

 

[IPSWiZarD]

Original geschrieben von cart
5. Semester und C machen?
Etechniker?

trifft auf mich zu
aber c ist gay !

und etechniker sind eh die geilsten

 

[ReDruM5]

Original geschrieben von cart
5. Semester und C machen?
Etechniker?

ein jahr "pausiert"

 

[cart]

Hehe ok

und etechniker sind eh die geilsten

 

[ReDruM5]

jo ich nochmal....
prof sagt es sei falsch
link listinsertion(link heada){
link innode,tmp;
link headb=NEW(0,NULL);
link out;

while(heada!=NULL){
innode=heada;
out=headb;
printf("Current %lf \n", innode->item);


while(out!=NULL){
printf("Out-Element %lf \n", out->item);

if(out->next==NULL){
tmp=NEW(innode->item, NULL);
out->next=tmp;
printf("END: %lf , %lf\n\n", out->item, tmp->item);
break;

}if(innode->item > out->next->item){
out=out->next;

}else{
printf("Border %lf \n", out->next->item);
tmp=NEW(innode->item, out->next);
out->next=tmp;

printf("In_Node %lf \n", tmp->item);
printf("Previous %lf \n\n", out->item);
break;


}

}
heada=heada->next;
}

return out;

}

out wandert durch die liste, bis eine grenze gefunden wird, für die gilt, dass die in_node kleiner ist.
wenn dem so ist, wird die innode zwishcen dem out element und der grenze eingefügt.

heada: 0.06878 0.84385 0.34013 0.62626 0.20738 0.25773 0.37843 0.55478 0.59149 0.50542 0.69000

als bsp für das debug:
Current 0.690001
Out-Element 0.000000
Out-Element 0.068778
Out-Element 0.207382
Out-Element 0.257732
Out-Element 0.340127
Out-Element 0.378429
Out-Element 0.505418
Out-Element 0.554785
Out-Element 0.591491
Out-Element 0.626262
Border 0.843852
In_Node 0.690001
Previous 0.626262

es läuft auch bis zum ende durch, doch ich erhalte:
0.00000 0.00000 0.06878 0.20738 0.25773 0.34013 0.37843 0.50542 0.55478 0.59149 0.62626 0.69000

er sortiert also, überschreibt aber den größten wert...

wenn einer zeit hat................

 

[Whcttyh]

mach mal return headb.

 

[ReDruM5]

leider gleicher fehler

 

[ReDruM5]

[UEP]Xyz hat den fehler in der show methode gefunden.
thema abgehakt!