LinkedList

Hallo,

ich habe folgendes Problem:

ich hab eine Verkettete Liste Programmiert in welche zufällig gewählte Int Zahlen eingehen. es funktioniert auch alles wunderbar, ich kann elemente hinzufügen, löschen oder suchen.
Jetzt möchte ich das die Zahlen während der Erstellung der Liste gleich in Ihrer Wertigkeit Sortiert werden. Aber irgendwie bekomm ich das nicht so hin

hoffe ihr versteht was ich meine und könnt mir helfen
mfg

unskilled

stichwort: insertion-sort

ansonsten werd halt mal genauer und zeig bissl code...

bb

PS: doofer spam-schutz... >< musste gerad noch mal alles tippen, weil ich in nem andern thread kurz zuvor was gepostet hatte...

also im mom siehts so bei mir aus:

SMultiLList::SMultiLList(int a, int *v)
{
	anker = NULL;
	for (int i = 0; i < a; i++) 
	{
	neu(v[i]);
	MAX++;
	}

}

int SMultiLList::neu(int i)
{
	Element * neu = new Element;
	if (neu == NULL)
	{ 
		cout << "Heap voll! " << endl;
		return 0;
	}	
	neu->Wert = i;
	neu->next = anker;
	anker = neu;
	return 0;
}

er fügt halt einfach die elemente nacheinander ein ohne was zu sortieren ^^

ich google mal bissl nach insertion sort danke dir für den hinweis

freaky

Da du anscheinend noch nicht so weit bist, könntest du den einfachen aber funktionierenden und bekannten Bubblesort nehmen, den du sehr einfach auf deine Klasse übertragen kannst.
Beispiel:

void SMultiLList::BubbleSort()
{
    Element *tmp = anker;
    for(int i = 0; i < _sizeoflist; i++)
    {
        for(int j = 0; j < i; j++)
        {
            if(tmp->Wert > tmp->next->Wert)
            {
                int temp = tmp->next->Wert;
                tmp->next->Wert = tmp->Wert;
                tmp->data = temp;
            }
            tmp = tmp->next;
        }
        tmp = anker;
    }
}

Das hauste jetzt in deine "neu"-Methode.

int SMultiLList::neu(int i)
{
    Element * neu = new Element;
    if (neu == NULL)
    {
        cout << "Heap voll! " << endl;
        return 0;
    }   
    neu->Wert = i;
    neu->next = anker;
    anker = neu;
    BubbleSort();
    return 0;
}

Edit:
Und warum gibt deine Add-Methode überhaupt Integer zurück, wenn könnte man da höchstens ein bool daraus machen, muss aber auch nicht unbedingt sein.

also habs mal geschrieben

void SMultiLList::BubbleSort()
{
    Element *lokal = anker;
    for(int i = 0; i < MAX; i++)
    {
        for(int j = 0; j < i; j++)
        {
            if(lokal->Wert > lokal->next->Wert)
            {
                int temp = lokal->next->Wert;
                lokal->next->Wert = lokal->Wert;
                lokal->data = temp;
            }
            lokal = lokal->next;
        }
       lokal = anker;
    }
}

nur was ist lokal->data?
hab das tmp in lokal umbenannt einfach nur weils ich in den bisherigen teilen so benannt habe.

€: kP warum ich ich nen int zurückgebe habs jetzt umgeschrieben ^^

freaky

Ja gut data musste halt in Wert umbennenen... Hatte es nur zuerst in C::B so geschrieben und dann an deins angepasst. Sollte aber eigentlich klar sein, da ein Knoten meistens immer nur den Wert enthält und auf welchen Knoten er zeigt. Wenn du lokal->data jetzt in lokal->Wert unbenennst, wird es funktionieren und bei jedem Add eines neuen Elements, wird gleichzeitig sortiert.

ja das hab ich mir gedacht und habs schon so geschrieben.
nur werden die elemente irgendwie nicht sortiert.

SMultiLList::SMultiLList(int a, int *v)
{
	anker = NULL;
	for (int i = 0; i < a; i++) 
	{
	neu(v[i]);
	MAX++;
	}
}

void SMultiLList::neu(int i)
{
	Element * neu = new Element;
	if (neu == NULL)
	{ 
		cout << "Heap voll! " << endl;
	}

	neu->Wert = i;
	neu->next = anker;
	anker = neu;
	BubbleSort();
}

void SMultiLList::BubbleSort()
{
    Element *lokal = anker;
    for(int i = 0; i < MAX; i++)
    {
        for(int j = 0; j <= i; j++)
        {
            if(lokal->Wert > lokal->next->Wert)
            {
                int temp = lokal->next->Wert;
                lokal->next->Wert = lokal->Wert;
                lokal->Wert = temp;
            }
            lokal = lokal->next;
        }
       lokal = anker;
    }
}

so siehts im moment aus.
danke schonmal für die bisherige hilfe.

mfg

unskilled

Element * neu = new Element; 
    if (neu == NULL) 
    { 
        cout << "Heap voll! " << endl; 
        return 0; 
    }

was soll das denn?
das thema haben wir doch jedes mal wieder - dann erzählt ihr das auch noch leuten, die das glauben...

new an sich gibt niemals NULL zurück - wenn überhaupt, wird eine exception geworfen (es gibt auch noch die nothrow-variante, aber die soll hier mal nicht interessieren)

bb

freaky

Keine Ahnung wo er das aufgeschmissen hat. Aufjedenfall liegt es an deiner Klasse, denn in den Tiefen meiner C++ Ordner hatte ich auch noch eine LinkedList, habe das eben implementiert und es hat funktioniert. An dem Sort liegt es nicht.