evo2 Geschrieben 10. Mai 2004 Geschrieben 10. Mai 2004 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 Zitieren
Diablo999 Geschrieben 10. Mai 2004 Geschrieben 10. Mai 2004 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 Zitieren
evo2 Geschrieben 11. Mai 2004 Autor Geschrieben 11. Mai 2004 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 Zitieren
Empfohlene Beiträge
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.