bubblesort

[nihilfire]

Hallo!
Ich soll ein Char-Array mit Telefonbucheinträgen, mit Hilfe des Bubblesort-Algorithmus nach Namen sortieren. Die Klassenhierarchie und Methodennamen waren soweit vorgeben.

Mein Programm sieht so aus:

#include <iostream>

using namespace std;

class sortable
{
	public:
		char *primkey;

		sortable(){}

		sortable* sinkingSort(sortable *feld, int anz)
		{
			for(int obergrenze = anz-1; obergrenze > 0; --obergrenze)
			{
				bool austausch = false;
				for(int pos = 0; pos < obergrenze; ++pos)
				{
					if(strcmp(feld[pos].primkey, feld[pos+1].primkey))
					{
						char *tmp = feld[pos].primkey;
						feld[pos].primkey = feld[pos-1].primkey;
						feld [pos-1].primkey = tmp;
						austausch = true;
					}
				}
				if(!austausch)
				{
					break;
				}
			}
			return feld;
		}

		~sortable(){}
};

class Telefonbucheintrag : public sortable
{
	private:
		char *telefonnummer;
		char *vorname;
		char *name;

	public:
		Telefonbucheintrag(){}

		Telefonbucheintrag(char* telefonnummer, char* vorname, char* name)
		{
			this->telefonnummer = telefonnummer;
			this->vorname = vorname;
			this->name = name;
			primkey = name;
		}

		char *getTelefonnummer()
		{
			return telefonnummer;
		}

		char *getVorname()
		{
			return vorname;
		}

		char *getName()
		{
			return name;
		}

		~Telefonbucheintrag(){}
};

int main()
{
	Telefonbucheintrag* Telefonbuch[10];
	Telefonbuch[0] = new Telefonbucheintrag("94949","fritz","mueller");  
	Telefonbuch[1] = new Telefonbucheintrag("49649","karl","tell");
	Telefonbuch[2] = new Telefonbucheintrag("66161","heiz","tor");
	Telefonbuch[3] = new Telefonbucheintrag("94125","hilde","mett");
	Telefonbuch[4] = new Telefonbucheintrag("12144","helga","zabel");
	Telefonbuch[5] = new Telefonbucheintrag("32629","emma","tillmann");
	Telefonbuch[6] = new Telefonbucheintrag("46998","ursula","maier");
	Telefonbuch[7] = new Telefonbucheintrag("26598","ute","keller");
	Telefonbuch[8] = new Telefonbucheintrag("71561","maria","mustermann");
	Telefonbuch[9] = new Telefonbucheintrag("82321","herbert","schmitz");

	for(int i = 0; i < 10; ++i)
	{
		cout << Telefonbuch[i]->getTelefonnummer() << ' ' 
			 << Telefonbuch[i]->getVorname() << ' ' 
			 << Telefonbuch[i]->getName() << endl;
	}

	Telefonbuch[0]->sinkingSort((sortable*)Telefonbuch, 10);

	for(int i = 0; i < 10; ++i)
	{
		cout << Telefonbuch[i]->getTelefonnummer() << ' ' 
			 << Telefonbuch[i]->getVorname() << ' ' 
		 	 << Telefonbuch[i]->getName() << endl;
	}

	cin.get();

	return 0;
}

bei:

if(strcmp(feld[pos].primkey, feld[pos+1].primkey))

bekomme ich eine Speicherzugriffverletzung

Was kann ich ändern damit es funktioniert?

Gruß, nihilfire

[ChrisPHL]

Der Hase versteckt sich in der Zeile 17, wenn mich nicht alles täuscht, passiert folgendes:
Wenn pos == ( obergrenze - 1 ) ist, dann kracht´s beim Zugriff auf das feld[pos+1] (in dieser if- Bedingung). Das Feld gibt es nämlich nicht, der Zugriff geht ins Leere.

Gruß
Christian

[nihilfire]

hmmm... so:

if(strcmp(feld[pos].primkey, feld[pos-1].primkey))

geht es aber auch nicht

Komisch ist auch, dass der Debugger angibt anz(Zeile 13) hat den Wert: 4848328, statt der übergebenen 10 (Zeile 96)... ich kann aber nicht herausfinden woran es liegt.

Gruß, nihilfire

[ChrisPHL]

nihilfire schrieb:

hmmm... so:

if(strcmp(feld[pos].primkey, feld[pos-1].primkey))

geht es aber auch nicht

Natürlich nicht! Jetzt passiert der Fehlerhafte Zugriff immer noch, nur eben gleich beim ersten Durchlauf der for()- Schleife. (Zugriff auf das "minus-erste-Element) Lass es einfach so wie vorher und reduziere die anzahl auf (obergrenze - 1) , dann macht es glaube ich Sinn.

Das andere Problem kann ich nicht angehen, da fehlt mir das Wissen... die Synthax ist mir unbekannt.

Gruß
Christian

[Werner Salomon]

Es gibt so an die drei bis vier Fehler in der Methode sinkingSort. Hier die korrigierte Fassung

sortable** sinkingSort(sortable** feld, int anz) // Pointer-Pointer statt nur Pointer
        {
            for(int obergrenze = anz-1; obergrenze > 0; --obergrenze)
            {
                bool austausch = false;
                for(int pos = 0; pos < obergrenze; ++pos)
                {
                    if( strcmp(feld[pos]->primkey, feld[pos+1]->primkey) > 0 ) // > 0 vergessen
                    {
                        sortable* tmp = feld[pos]; // tausche sortable* und nicht nur primkey
                        feld[pos] = feld[pos+1];  // +1 statt -1
                        feld [pos+1] = tmp;
                        austausch = true;
                    }
                }
                if(!austausch)
                {
                    break;
                }
            }
            return feld;
        }

Und der Aufruf muss dann entsprechend

Telefonbuch[0]->sinkingSort( (sortable**)Telefonbuch , 10);

heißen.

Gruß
Werner

[nihilfire]

Hallo Werner!

Jetzt geht es, vielen Dank für deine Hilfe!

Gruß, nihilfire