Array sortieren mit Hilfe von nachfolger keys

[evo2]

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

[Diablo999]

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

[evo2]

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