#include #include using namespace std; //Het maken van een random getal int randomgetal () { // tussen 0 en 999 static int getal = time (NULL) % 1000; getal = ( 621 * getal + 1 ) % 1000; return getal; } //Een list bestaat uit allemaal vakjes. class Vakje { public: int Getal_int; //Waarde van het vakje Vakje * Volgende_Vakje_pt; //Zijn 'rechterbuur' Vakje * Vorige_Vakje_pt; //Zijn 'linkbuur' }; class listvak { public: //default constuctor (NULL pointers) listvak( ); //destructor: niks doen ~listvak( ) { }; //creer de list van random lengte met randomgetallen void randomlist(); //druk de list van links naar rechts af void drukaf_l_r(); //druk de list van recht naar links af void drukaf_r_l(); //sorteer de list, volgens bubblesort methode int sorteren(); //merge L1 en L2 met opvolgend principe void merge(listvak * L1, listvak * L2); //vernietig de list. void vernietig(); private: Vakje * Eerste_Vakje_pt; //pointer naar het eerste vakje Vakje * Laatste_Vakje_pt; //pointer naar het laatste vakje }; listvak::listvak( ) { Eerste_Vakje_pt = NULL; Laatste_Vakje_pt = NULL; } //voeg een AantalGetallen_int getallen toe aan de List die door Lbgin wordt gepointerd. void listvak::randomlist() { Vakje * VakjeNew_Vakje_pt; for (int i = 0; i < randomgetal(); i++) { VakjeNew_Vakje_pt = new Vakje; VakjeNew_Vakje_pt->Getal_int = randomgetal(); if (Eerste_Vakje_pt != NULL) { VakjeNew_Vakje_pt->Volgende_Vakje_pt = Eerste_Vakje_pt; VakjeNew_Vakje_pt->Volgende_Vakje_pt->Vorige_Vakje_pt = VakjeNew_Vakje_pt; } else { Laatste_Vakje_pt = VakjeNew_Vakje_pt; } //end if Eerste_Vakje_pt = VakjeNew_Vakje_pt; } //end for } //end listvak::randomlist //druk de list af van links naar rechts void listvak::drukaf_l_r() { Vakje * Hulp_Vakje_pt = Eerste_Vakje_pt; while (Hulp_Vakje_pt != NULL) { cout << Hulp_Vakje_pt->Getal_int << " "; Hulp_Vakje_pt = Hulp_Vakje_pt->Volgende_Vakje_pt; } //end while } //end listvak::drukaf_lr //druk de list af van rechts naar links void listvak::drukaf_r_l() { Vakje * Hulp_Vakje_pt = Laatste_Vakje_pt; while (Hulp_Vakje_pt != NULL) { cout << Hulp_Vakje_pt->Getal_int << " "; Hulp_Vakje_pt = Hulp_Vakje_pt->Vorige_Vakje_pt; } //end while } //end listvak::drukaf_rl //sorteren volgens de bubblesort methode (grootste getal achteraan) //uitvoer: aantal verwisselingen die plaatsgevonden hebben. int listvak::sorteren() { int Verwisselingen_int = 0; Vakje * BubbleHulp_Vakje_pt = Eerste_Vakje_pt; //Dit is het vakje dat gechecked wordt Vakje * BubbleStop_Vakje_pt = Laatste_Vakje_pt; //Hierna hoeft niet meer gechecked worden Vakje * BubbleVakA_Vakje_pt; Vakje * BubbleVakB_Vakje_pt; Vakje * BubbleVakC_Vakje_pt; Vakje * BubbleVakD_Vakje_pt; while (BubbleStop_Vakje_pt->Vorige_Vakje_pt != NULL) { while ( BubbleHulp_Vakje_pt != BubbleStop_Vakje_pt ) { if (BubbleHulp_Vakje_pt->Getal_int > BubbleHulp_Vakje_pt->Volgende_Vakje_pt->Getal_int) { /* Methode voor het omwisselen van vak B en C * Oude situtatie * ___________________________________ * | Vorige | Vak Nummer | Volgende | * |========|=============|===========| * | | A | 1->B | * | 2->A | B | 3->C | * | 4->B | C | 5->D | * | 6->C | D | | * ------------------------------------ * * Nieuwe situatie * ___________________________________ * | Vorige | Vak Nummer | Volgende | * |========|=============|===========| * | | A | 1->C | * | 2->C | B | 3->D | * | 4->A | C | 5->B | * | 6->B | D | | * ------------------------------------ * * Uitzondering betreft als A de pointer in het begin is of als * D de eind pointer is. */ BubbleVakA_Vakje_pt = BubbleHulp_Vakje_pt->Vorige_Vakje_pt; BubbleVakB_Vakje_pt = BubbleHulp_Vakje_pt; BubbleVakC_Vakje_pt = BubbleHulp_Vakje_pt->Volgende_Vakje_pt; BubbleVakD_Vakje_pt = BubbleHulp_Vakje_pt->Volgende_Vakje_pt->Volgende_Vakje_pt; //Pointer 1,2 if (BubbleVakA_Vakje_pt == NULL) { Eerste_Vakje_pt = BubbleVakC_Vakje_pt; BubbleVakC_Vakje_pt->Vorige_Vakje_pt = NULL; } else { BubbleVakA_Vakje_pt->Volgende_Vakje_pt = BubbleVakC_Vakje_pt; BubbleVakC_Vakje_pt->Vorige_Vakje_pt = BubbleVakA_Vakje_pt; } //end if //Pointer 3,4 BubbleVakB_Vakje_pt->Vorige_Vakje_pt = BubbleVakC_Vakje_pt; BubbleVakC_Vakje_pt->Volgende_Vakje_pt = BubbleVakB_Vakje_pt; //Pointer 5,6 if (BubbleVakD_Vakje_pt == NULL) { Laatste_Vakje_pt = BubbleVakB_Vakje_pt; BubbleVakB_Vakje_pt->Volgende_Vakje_pt = NULL; BubbleStop_Vakje_pt = BubbleVakB_Vakje_pt; } else { BubbleVakD_Vakje_pt->Vorige_Vakje_pt = BubbleVakB_Vakje_pt; BubbleVakB_Vakje_pt->Volgende_Vakje_pt = BubbleVakD_Vakje_pt; } //end if //In het geval dat het vakje van de stop pointer kleiner is als het vakje ervoor, //zal de stop pointer over het nieuwe vakje moeten vallen, anders komt hij het stop //teken nooit tegen. // A B C D // 5 9 7 10 // ^ ^ // | |Stop pointer // | Huidige Waarde // // ZONDER AANPASSING MET AANPASSING // // A C B D A C B D // 5 7 9 10 5 7 9 10 // ^ ^ ^ ^ // | |Huidige Waarde | |Huidige Waarde + Stop Pointer // | Stop Pointer | // if (BubbleStop_Vakje_pt == BubbleVakC_Vakje_pt) { BubbleStop_Vakje_pt = BubbleVakB_Vakje_pt; } //end if Verwisselingen_int++; } else { BubbleHulp_Vakje_pt = BubbleHulp_Vakje_pt->Volgende_Vakje_pt; } //end if } //end while BubbleHulp_Vakje_pt = Eerste_Vakje_pt; BubbleStop_Vakje_pt = BubbleStop_Vakje_pt->Vorige_Vakje_pt; } //end while return (Verwisselingen_int); } //end listvak::sorteren void listvak::merge(listvak * L1, listvak * L2) { bool Toevoegen_bool = true; //zolang true bestaan er nog waardes die toegevoegd moeten worden Vakje * HulpL1_Vakje_pt = L1->Laatste_Vakje_pt; //pointer die bijhoudt waar we in L1 zijn Vakje * HulpL2_Vakje_pt = L2->Laatste_Vakje_pt; //pointer die bijhoudt waar we in L2 zijn Vakje * VakjeNew_Vakje_pt; //pointer bij gebruikt wordt bij het maken van nieuwe vakjes while (Toevoegen_bool) { VakjeNew_Vakje_pt = new Vakje; if (Eerste_Vakje_pt != NULL) { VakjeNew_Vakje_pt->Volgende_Vakje_pt = Eerste_Vakje_pt; VakjeNew_Vakje_pt->Volgende_Vakje_pt->Vorige_Vakje_pt = VakjeNew_Vakje_pt; } else { Laatste_Vakje_pt = VakjeNew_Vakje_pt; } //end if Eerste_Vakje_pt = VakjeNew_Vakje_pt; if ((HulpL1_Vakje_pt != NULL) && (HulpL2_Vakje_pt != NULL)) { //beiden bevatten nog een getal if (HulpL1_Vakje_pt->Getal_int > HulpL2_Vakje_pt->Getal_int) { VakjeNew_Vakje_pt->Getal_int = HulpL1_Vakje_pt->Getal_int; HulpL1_Vakje_pt = HulpL1_Vakje_pt->Vorige_Vakje_pt; } else { VakjeNew_Vakje_pt->Getal_int = HulpL2_Vakje_pt->Getal_int; HulpL2_Vakje_pt = HulpL2_Vakje_pt->Vorige_Vakje_pt; } //end if } else if (HulpL1_Vakje_pt != NULL) { //L2 leeg, enkel waardes uit L1 plakken VakjeNew_Vakje_pt->Getal_int = HulpL1_Vakje_pt->Getal_int; HulpL1_Vakje_pt = HulpL1_Vakje_pt->Vorige_Vakje_pt; } else if (HulpL2_Vakje_pt != NULL) { //L1 leeg, enkel waardes uit L2 plakken VakjeNew_Vakje_pt->Getal_int = HulpL2_Vakje_pt->Getal_int; HulpL2_Vakje_pt = HulpL2_Vakje_pt->Vorige_Vakje_pt; } else { //alles leeg, 'over en sluiten' Toevoegen_bool = false; } //end if } //end while } //end listvak::merge //vernietig de list void listvak::vernietig() { Vakje * Hulp_Vakje_pt; while (Eerste_Vakje_pt != NULL) { Hulp_Vakje_pt = Eerste_Vakje_pt->Volgende_Vakje_pt; delete Eerste_Vakje_pt; Eerste_Vakje_pt = Hulp_Vakje_pt; } //end while; Laatste_Vakje_pt = NULL; } //end listvak::vernietig int main() { listvak L1; listvak L2; listvak L3; L1.randomlist(); L2.randomlist(); L1.sorteren(); L2.sorteren(); L1.drukaf_l_r(); cout << endl << endl; L2.drukaf_l_r(); cout << endl << endl; L3.merge(&L1,&L2); cout << endl << endl; L3.drukaf_l_r(); cout << endl; }