Zum Inhalt springen

Array sortieren mit Hilfe von nachfolger keys


Empfohlene Beiträge

Geschrieben

Hi

ich soll ein array erstellen, wo ich verschiedene werte(Element[]) speichern kann. per nachfolger-key(Key[]) soll ich dann immer den nachfolger im element array suchen und das damit sortieren.

außerdem in der bitmaske nach der nächsten freien null suchen und dort an stelle Position den wert in Element[] speichern.

mit der dynamischen speicherverwaltung mit new und delete hat es nicht so geklappt, deswegen hab ich mal alle arrays auf 1024 gesetzt.

jetzt hab ich aber ein anderes problem.

wie sortier ich jetzt am besten die neuen elemente und veränder dann in Key[] die nachfolger, daß das array Element[] der größe nach ausgegeben wird?

ist ein bißchen umständlich geschrieben, aber ich hoffe ihr versteht was ich vorhabe ;)

hier mein bisheriger code:


#include<iostream.h>

#include <stdlib.h>


int Anzahl = 0;

int Element[1024];

int Key[1024];

int Bitmaske[1024]={NULL};

int i,x,Position,Wert;

int Startkey = -1;




void main()

{ 

	char index;

	int Hinzufuegen(int x);

	do

	 {

		system("cls");	

		cout <<("\n\nAuswahlmenue:");

		cout <<("\n****************");

		cout <<("\n1. Alle Elemente anzeigen lassen");

		cout <<("\n2. Element hinzufuegen");

		cout <<("\n3. Element loeschen");

		cout <<("\n4. Programm beenden\n");

        cin >>index;


		switch(index) // Auswahlfkt. der Funktionen des Programms

		{


			case '1': // Anzeigefunktion


				{

					if (Anzahl==0)

					{

						cout << "Keine Elemente vorhanden.";

						break;

					}

				Wert = Anzahl-1;						//von anzahl des arrays eins abziehen, da ich 0 [0] nicht nutze

				cout <<("\n\nAlle Elemente:");

				cout << "\nElemente: ";

				for(i=0;i<Wert;i++)

						cout << Element[i] << ",";

				cout << "\nKey: ";

				for(i=0;i<Wert;i++)

						cout << Key[i] << ",";

				cout << "\nBitmaske: ";

				for(i=0;i<Wert;i++)

						cout << Bitmaske[i] << ",";

				cout << "\nAnzahl: " << Anzahl;			//die ganzen cout nur zum testen, damit ich die werte sehe 

				cout << "\nWert: " << Wert;

				cout << "\nStartkey: " << Startkey;						

				cout << "\nNachfolger: " << Key[1];


				}


			break;


			case '2': // Hinzufuegefunktion


				{

					cout <<("\nBitte geben Sie das Element zum hinzufuegen ein: ");

					cin >> x;

					Hinzufuegen(x);

				}

			break;


			case '3': // Loeschfunktion

				{

				cout <<("\nBitte geben Sie das Element zum loeschen ein: ");

				}

			break;


			case '4': // Programmende

				cout <<("\n\n\t\tPROGRAMMENDE\n");				

			break;


		default:

			cout <<("\n\nBenutzen Sie nur die Zahlen 1 bis 4!");



		}



	}while(1); 

}


int Hinzufuegen(int x)

{

	if (Anzahl==0)					//sonderfall erstes Element

		{

		Anzahl++;					//Anzahl auf 1 setzen. 0 wird nicht benutzt

		Bitmaske[Anzahl]=1;			//Position 1 als "vergeben" markieren

		Element[Anzahl]=x;			//an Position 1 ersten Wert setzen

		Startkey=Anzahl;			//den startkey auf den ersten wert setzen

		Key[Anzahl]=-1;				//den nachfolger von dem ersten wert auf -1 setzen...kein nachfolger

		Anzahl++;					//anzahl um eins erhöhen, damit eventueller nächster wert eingetragen werden kann

		Bitmaske[Anzahl]=NULL;		//letzte anzahl auf NULL setzen, hier kann nächstes element hin

		}

	else

	{

	for(i=0;i<Anzahl;i++)			//naechste 0 in Bitmaske suchen

		if(Bitmaske[i]==NULL)

		{

			Position=i;             //Die naechste 0 Stelle wird Position übergeben

			break;

		}

        Bitmaske[Position]=1;		//Stelle wo x hinkommt auf 1 setzen

        Element[Position]=x;		//Element an die postion setzen wo bitmaske von 0 auf 1 geaendert wurde

        Anzahl++;					//Anzahl um 1 erhoehen..fuer weitere elemente

		Bitmaske[Anzahl]=NULL;		//letzte Stelle auf 0 setzen

	}

	return 1;						//kp...compiler will das 

}



[/code]

es geht erstma nur ums einfügen. löschfunktion laß ich noch außen vor. hab auch mal alles wichtige kommentiert.

dank im vorraus

evo2

Geschrieben

So in etwa...


int Hinzufuegen(int x)
{
if (Anzahl==0)//sonderfall erstes Element
{
Bitmaske[Anzahl]=1;//Position 1 als "vergeben" markieren
Element[Anzahl]=x;//an Position 1 ersten Wert setzen
Startkey=Anzahl;//den startkey auf den ersten wert setzen
Key[Anzahl]=-1;//den nachfolger von dem ersten wert auf -1 setzen...kein nachfolger
Anzahl++;//anzahl um eins erhöhen, damit eventueller nächster wert eingetragen werden kann
Bitmaske[Anzahl]=NULL;//letzte anzahl auf NULL setzen, hier kann nächstes element hin
}
else
{
for(i=0;i<=Anzahl;i++)// !!!HIER!!!
if(Bitmaske[i]==NULL)
{
Position=i; //Die naechste 0 Stelle wird Position übergeben
break;
}
Bitmaske[Position]=1;//Stelle wo x hinkommt auf 1 setzen
Element[Position]=x;//Element an die postion setzen wo bitmaske von 0 auf 1 geaendert wurde
Anzahl++;//Anzahl um 1 erhoehen..fuer weitere elemente
Bitmaske[Anzahl]=NULL;//letzte Stelle auf 0 setzen

// Einsortieren
int nKey = Startkey, nOldKey = -1;
while(nKey >= 0)
{
// Vergleich des neuen elements mit dem Alten
if (x < Element[nKey])
{
// Aha, da musses rein..
if (nOldKey >= 0)
Key[nOldKey] = Position;
else
Startkey = Position;

Key[Position] = nKey;
break;
}
else
{
nOldKey = nKey;
nKey = Key[nKey]; // zum nächsten Element
}
}
// wenn der Key noch nicht gesetzt wurde jetzt machen
if (nKey < 0)
{
Key[nOldKey] = Position;
Key[Position] = -1;
}
}
return 1;//kp...compiler will das
}
[/PHP]

1. Hab ein Kommentar "HIER" hingemacht -> Da hab ich umgebaut auf die Verwendung des Index 0

2. Der Block einsortieren

Keine Garantie für den Code, nur schnell gehackt...

Gruß

Diablo999

Geschrieben

hat super funktioniert...danke ;)

aber hab noch ein prob.

will jetzt Key[] sortieren lassen...mit Quicksort.

aber sobald ich eine zweite zahl eingebe hört er gar nich mehr auf zu rechnen.

hab schon verschiedene suchverfahren ausprobiert...alle nur mit mäßigem erfolg.

durch das sortieren soll er dann die Elemente der größe nachausgeben, anhand der Keys.


#include<iostream.h>

#include <stdlib.h>


int Anzahl = 0;

int Element[1024];

int Key[1024];

int Bitmaske[1024]={NULL};

int Sortkey[1024];

int i,x,Position,Wert;

int Startkey = -1;

int count =0;



void main()

{ 

	void QuickSort(int *A, int iLo, int iHi, int &cnt);	// <---HIER

	char index;

	int Hinzufuegen(int x);	

	do

	 {

		system("cls");	

		cout <<("\n\nAuswahlmenue:");

		cout <<("\n****************");

		cout <<("\n1. Alle Elemente anzeigen lassen");

		cout <<("\n2. Element hinzufuegen");

		cout <<("\n3. Element loeschen");

		cout <<("\n4. Programm beenden\n");

        cin >>index;

		QuickSort(Key, -1, Anzahl,count);	// <---HIER


		switch(index) // Auswahlfkt. der Funktionen des Programms

		{


			case '1': // Anzeigefunktion


				{

					if (Anzahl==0)

					{

						cout << "Keine Elemente vorhanden.";

						break;

					}				

				Wert = Anzahl;						//von anzahl des arrays eins abziehen, da ich 0 [0] nicht nutze

				cout <<("\n\nAlle Elemente:");

				cout << "\nElemente: ";

				for(i=0;i<Wert;i++)

						cout << Element[i] << ",";

				cout << "\nKey: ";

				for(i=0;i<Wert;i++)

						cout << Key[i] << ",";

				cout << "\nBitmaske: ";

				for(i=0;i<Wert;i++)

						cout << Bitmaske[i] << ",";

				cout << "\nAnzahl: " << Anzahl;			//die ganzen cout nur zum testen, damit ich die werte sehe 

				cout << "\nWert: " << Wert;

				cout << "\nStartkey: " << Startkey;						

				cout << "\nNachfolger: " << Key[1];				

				}


			break;


			case '2': // Hinzufuegefunktion


				{

					cout <<("\nBitte geben Sie das Element zum hinzufuegen ein: ");

					cin >> x;

					Hinzufuegen(x);

				}

			break;


			case '3': // Loeschfunktion

				{

				cout <<("\nBitte geben Sie das Element zum loeschen ein: ");

				}

			break;


			case '4': // Programmende

				cout <<("\n\n\t\tPROGRAMMENDE\n");				

			break;


		default:

			cout <<("\n\nBenutzen Sie nur die Zahlen 1 bis 4!");



		}



	}while(1); 

}

[/code]


...hier kommt hinzufügen...

[code] void QuickSort(int *A, int iLo, int iHi, int &cnt) // <---HIER { int Lo, Hi, Mid, T; Lo = iLo; Hi = iHi; Mid = A[(Lo+Hi)/2]; do { while (A[Lo] < Mid) Lo++; while (A[Hi] > Mid) Hi--; if (Lo <= Hi) { cnt++; T = A[Lo]; A[Lo] = A[Hi]; A[Hi] = T; Lo++; Hi--; } } while (Lo <= Hi); if (Hi > iLo) QuickSort(A, iLo, Hi,cnt); if (Lo < iHi) QuickSort(A, Lo, iHi,cnt); }

habs mit HIER markiert wo ich auf quicksort zugreifen will.

evo2

Dein Kommentar

Du kannst jetzt schreiben und Dich später registrieren. Wenn Du ein Konto hast, melde Dich jetzt an, um unter Deinem Benutzernamen zu schreiben.

Gast
Auf dieses Thema antworten...

×   Du hast formatierten Text eingefügt.   Formatierung wiederherstellen

  Nur 75 Emojis sind erlaubt.

×   Dein Link wurde automatisch eingebettet.   Einbetten rückgängig machen und als Link darstellen

×   Dein vorheriger Inhalt wurde wiederhergestellt.   Editor leeren

×   Du kannst Bilder nicht direkt einfügen. Lade Bilder hoch oder lade sie von einer URL.

Fachinformatiker.de, 2024 by SE Internet Services

fidelogo_small.png

Schicke uns eine Nachricht!

Fachinformatiker.de ist die größte IT-Community
rund um Ausbildung, Job, Weiterbildung für IT-Fachkräfte.

Fachinformatiker.de App

Download on the App Store
Get it on Google Play

Kontakt

Hier werben?
Oder sende eine E-Mail an

Social media u. feeds

Jobboard für Fachinformatiker und IT-Fachkräfte

×
×
  • Neu erstellen...