WINAK

Code: Select all

MODULE Insertion;
(*
	Doel: Een array met getallen sorteren volgens het insertion algoritme gebruikmakend van pointers
	Auteur: Nick De Frangh
	Datum: 22-11-05
*)
	IMPORT
		In, OutExt;
	
	TYPE
		Getallenrij = POINTER TO Getal;
		Getal =
			RECORD
				prev: Getallenrij;
				getal : REAL;
				next: Getallenrij;
			END;
	
	PROCEDURE LeesRij(VAR Lijst: Getallenrij);
	(* 
      Omschrijving : Lees een rij getallen in
      Parameters : 
         Lijst : De lijst waarin de getallen zullen worden ingelezen
      Returntype : - 
      Algoritme : - 
   *)
		VAR
			Tempgetal: REAL;
			Tempnode: Getallenrij;
			First: Getallenrij;
   BEGIN
		In.Open();
		In.Real(Tempgetal);
		First := Lijst;
		IF In.Done THEN
			NEW(Tempnode);
			Tempnode^.getal := Tempgetal;
			Tempnode^.next := NIL;
			Tempnode^.prev := NIL;
			
			First^.next := NIL;
			First^.prev := NIL;
			First^.getal := Tempgetal;
		ELSE
			Lijst := NIL;
		END;
		In.Real(Tempgetal);
		WHILE (In.Done) DO
			NEW(Tempnode);
			Tempnode^.getal := Tempgetal;
			Tempnode^.next := NIL;
			Tempnode^.prev := NIL;
			
			WHILE (First^.next # NIL) DO
				First := First^.next;
			END;
			First^.next := Tempnode;
			Tempnode^.prev := First;
			Tempnode^.next := NIL;
			
			In.Real(Tempgetal);
		END; 		
	END LeesRij;
   
   PROCEDURE DrukRij(Lijst: Getallenrij);
   (* 
      Omschrijving : Print een rij getallen af
      Parameters : 
         Lijst : De gesorteerde lijst die afgedrukt zal worden
      Returntype : - 
      Algoritme : - 
   *)
   	VAR
   		First : Getallenrij;
   BEGIN
   	First := Lijst;
   	OutExt.Color(3);
   	OutExt.String("De Geordende lijst volgens insertion sort is: ");
   	OutExt.Ln;
   	OutExt.String("---------------------------------------------");
   	OutExt.Ln;
   	OutExt.Color(8);
   	WHILE Lijst # NIL DO
   		OutExt.RealFix(Lijst^.getal, 3, 2);
   		OutExt.Ln;
   		Lijst := Lijst^.next;
   	END;	
   END DrukRij;
   
   PROCEDURE Insert(VAR Lijst: Getallenrij;
   								Node1: Getallenrij;
   							    Node2: Getallenrij);
   (* 
      Omschrijving : De insertion zelf uitvoeren
      Parameters : 
      	Lijst : De lijst die gesorteerd wordt
      	Node1: Het getal dat ingevoegd moet worden
      	Node2: Het getal waarvoor het getal van Node1 moet worden geplaatst
      Returntype : - 
      Algoritme : - 
   *)
   	VAR
   		Tempnode: Getallenrij;
   		First: Getallenrij;
   BEGIN
   	NEW(Tempnode);											(* maak een node aan met de getalwaarde van de node die ingevoegd moet worden *)
   	Tempnode^.prev := NIL;
   	Tempnode^.next := NIL;
   	Tempnode^.getal := Node1^.getal;
   	
   	First := Lijst;													(* ga opzoek naar de node waarvoor de Tempnode moet worden ingevoegd *)
   	WHILE First # Node2 DO
   		First := First^.next;
   	END;
   	IF First = Lijst THEN											(* het getal moet op de eerste plaats gezet worden *)
   		First^.prev := Tempnode;
   		Tempnode^.next := First;
   		Lijst := Tempnode;
   	ELSE																(* het getal moet ergens anders ingevoegd worden *)
  	 	First^.prev^.next := Tempnode;
 	  	Tempnode^.prev := First^.prev;
 	  	First^.prev := Tempnode;
 	  	Tempnode^.next := First;
 	  END;	

 	  First := Lijst;														(* ga opzoek naar de node die ingevoerd moest worden en laat deze overslaan *)
 	  WHILE First^.next # Node1 DO
 	  	First := First^.next;
	   END;
	   IF First^.next^.next = NIL THEN						(* controleer of Node1 de laatste node is of niet *)
	   	First^.next^.prev := NIL;
	   	First^.next := NIL;
	   ELSE																	(* Als Node1 niet de laatste node is *)
	   	First^.next^.next^.prev := Node1^.prev;
	   	First^.next := Node1^.next;
	   END;  	
   END Insert;
   
   PROCEDURE Insertion*;
   (* 
      Omschrijving : De insertion sort procedure starten
      Parameters : -
      Returntype : - 
      Algoritme : Insertion Sort
   *)
   	VAR
   		Lijst: Getallenrij;
   		Tempnode1, Tempnode2: Getallenrij;
   		insert: BOOLEAN;
   		First: Getallenrij;
   BEGIN
   	NEW(Lijst);
   	Lijst^.next := NIL;
   	LeesRij(Lijst);
   	
   	IF (Lijst = NIL) THEN
   		OutExt.Color(1);
   		OutExt.String ("De lijst is leeg");
   	ELSIF (Lijst^.next = NIL) THEN
   		DrukRij(Lijst);
   	ELSE
   		Tempnode1 := Lijst^.next;
   		WHILE (Tempnode1 # NIL) DO
   			First := Lijst;
   			Tempnode2 := Lijst;
   			insert := FALSE;
   			REPEAT
   				IF (Tempnode2^.getal > Tempnode1^.getal) THEN
   					Insert(Lijst, Tempnode1, Tempnode2);
   					insert := TRUE;
       			END;
   				Tempnode2 := Tempnode2^.next;
   			UNTIL (Tempnode2 = Tempnode1) OR (insert);
   			Tempnode1 := Tempnode1^.next;
   		END; 	  		  		
   		DrukRij(Lijst);
   	END;
   	
   END Insertion;
   
BEGIN
OutExt.Open();
OutExt.Clear; 
END Insertion.

Code: Select all

(*
	Auteur: Nick De Frangh
	Date: 24-11-05
	Werkwijze:
		Ik heb mijn vorige insertion sort module gebruikt en deze volledig opnieuw geschreven door gebruik te maken van pointers.
		Ik heb voor de implementatie van de pointers een dubbel gelinkte niet circulaire lijst gebruikt aangezien deze volgens mij het
		makkelijkst was om te implementeren.
		De insertion sort werkt op dezelfde manier als in de vorige module:
			Ik neem aan dat mijn eerste getal het voorlopig kleinste is
			Dan vergelijk ik alle volgende getallen met hun voorgangers
			Kom ik een getal tegen dat groter is dan mijn huidige getal, dan voeg ik mijn huidige getal in voor het getal dat net groter is.
			Ik loop zo heel de lijst af tot ik aan het einde ben gekomen.
	Algoritme: Insertion Sort
*)

Builder.Compile \ws
	OutExt.Mod
	Insertion.Mod
	~
	
Builder.Compile \f*

System.Free
	Insertion.Mod
	OutExt.Mod
	~

OutExt.Clear


Insertion.Insertion 1.2 45.3 0.33 5.21 8.2 -3.5 2.35 7.88 5.12 6.23 2.36 55.8 -5.66 0.0 6.66 3.2 1.5 5.5~
Insertion.Insertion ~
Insertion.Insertion 1~
Insertion.Insertion 2 1 2 3~
Insertion.Insertion 1 3 6 9 4 5~
Insertion.Insertion 1.5 2.3 1.5 1.6 1.7 1.5 1.3 2.4 0 1 0~
Insertion.Insertion 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0~
Insertion.Insertion 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15~

Code: Select all

MODULE InsertionPointers;
(*
	Doel : Portfolio opdracht III (Sorteeralgoritmes & dynamisch geheugenbeheer) : 
				Vorm de module "Insertion" van opdracht II om zodat in plaats van een array van getallen een gelinkte lijst wordt gebruikt.
	Auteur : Kristof Overdulve
	Datum : 28/11/2005
*)

	IMPORT 
		In, OutExt;
		
	TYPE
		pNode* = POINTER TO Node;
		Node* = 
			RECORD
				prev : pNode;
				getal : REAL;
				next : pNode;
			END;
	
	VAR
		head : pNode;
		
		
	PROCEDURE LeesRij(VAR lijst : pNode);
	(*
		Omschrijving : Leest een aantal getallen in en cre‘rt een lijst.
		Parameters : 
			lijst : pNode : pointer naar een record van het type Node.
		Returntype : -
		Algoritme : Circulair dubbelgelinkte lijsten implementeren.
	*)
		
		VAR
			getal : REAL;
			newNode : pNode;
						
	BEGIN
		In.Open;
		(* Leest het eerste getal in *)
		In.Real(getal);
		(* Controleert of er wel inputwaarden te vinden zijn *)
		IF (~In.Done) THEN 
			OutExt.String("WARNING : Controleer of U correcte inputwaarden hebt gespecifieerd!");
			OutExt.Ln;
			(* Cre‘rt een TRAP venster *)
			HALT(90);
		ELSE
			(* Initialiseert de lijst *)
			lijst^.getal := getal;
			lijst^.prev := lijst;
			lijst^.next := lijst;
			head := lijst;
		END;
			
		(* Voegt de overige getallen toe aan de lijst *)
		REPEAT
			lijst := lijst^.next;
			In.Real(getal);
			(* Verhindert dat een nieuwe node wordt toegekend aan de lijst zonder een nieuwe waarde in te hebben gelezen *)
			IF (In.Done) THEN
				(* Initialiseert de toe te voegen node *)
				NEW(newNode);
				newNode^.getal := getal;
				(* Voegt de nieuwe node toe aan de lijst *)
				newNode^.next := head;
				newNode^.prev := lijst;
				lijst^.next^.prev := newNode;
				lijst^.next := newNode;
			END;
		UNTIL (~In.Done);
	END LeesRij;
	
	
	PROCEDURE Sort(VAR lijst : pNode);
	(*
		Omschrijving : Sorteert de lijst.
		Parameters : 
			node : pNode : pointer naar een record van het type Node
		Returntype : -
		Algoritme : Circulair dubbelgelinkte lijsten & Insertion sorteeralgoritme.
	*)
	
		VAR
			temp :pNode;
			node : pNode;

	BEGIN
		(* Zorgt ervoor dat de pointer naar het eerste element uit de lijst wijst *)
		lijst := head;
		(* node is de pointer die element per element de lijst afgaat om getallen te wisselen zonder de hoofdpointer, die van lijst te veranderen *)
		NEW(node);
		
		(* Loopt de hele lijst  af tot het voorlaatste element*)
		REPEAT
			node := lijst;
			NEW(temp);
			(* Voegt temp toe aan de lijst op de juiste plaats *)
			temp^.getal := lijst^.getal;

			WHILE ((node # head) & (node^.prev^.getal > temp^.getal)) DO
				(* Schuift alle elementen eentje op *)
				node := node^.prev;
			END;
			
			(* temp is de variabele die de waarde van het getal waarnaar de pointer op dat moment wijst tijdelijk bevat *)
			temp^.next := node;
			temp^.prev := node^.prev;
			node^.prev^.next := temp;
			node^.prev := temp;
			(* Als temp het kleinste getal tot dan toe is dan moet het vooraan komen te staan *)
			IF (node = head) THEN
				head := temp;
			END;
			
			(* Verwijdert temp uit de foutieve plaats *)
			lijst^.next^.prev := lijst^.prev;
			lijst^.prev^.next := lijst^.next;
			
			(* Gaat naar het volgende element in de lijst *)
			lijst := lijst^.next;
		UNTIL (lijst^.next = head^.next);
	END Sort;
				
	
	PROCEDURE DrukRij(lijst : pNode);
	(*
		Omschrijving : Drukt de gesorteerde lijst af.
		Parameters : 
			node : pNode : pointer naar een record van het type Node
		Returntype : -
		Algoritme : Circulair dubbelgelinkte lijsten.
	*)
	
	BEGIN
		OutExt.String("De geordende lijst is: ");
		OutExt.Ln;
		(* Zorgt ervoor dat bij een eerste verwijzing naar het volgende element het eerste element van de lijst wordt bedoeld *)
		lijst := head^.prev;
		(* Herhaalt het afdrukproces totdat het laatste element van de lijst wordt bereikt *)
		REPEAT
			lijst := lijst^.next;
			(* Drukt getal getal af met drie getallen achter de komma *)
			OutExt.RealFix(lijst^.getal, 0, 3);
			OutExt.Ln;
		UNTIL (lijst^.next = head);
	END DrukRij;			
		
	
	PROCEDURE Insertion*;
	(*
		Omschrijving : Dit is de hoofdprocedure van de module.
		Parameters : -
		Returntype : -
		Algoritme : -
	*)
	
		VAR
			lijst : pNode;
	
	BEGIN
		OutExt.Open;
		OutExt.Clear;
		(* Cre‘ert de lijst *)
		NEW(lijst);
		LeesRij(lijst);
		Sort(lijst);
		DrukRij(lijst);
	END Insertion;
	
BEGIN
END InsertionPointers.

Code: Select all

-InsertionPointers.Tool
(*
	Author : Kristof Overdulve
	Date : 28/11/2005
	Werkwijze : Voordat ik aan deze opdracht begon heb ik eerst reeks 4 gemaakt zodat ik gemakkelijker de Insertion van opdracht II en Reeks 4 kon combineren 
						en optimaliseren voor deze opdracht. Eerst lees ik alle getallen in een dubbelgelinkte circulaire lijst in en nadien pas ik het Insertion 
						sorteeralgoritme op deze lijst toe d.m.v. enkele tijdelijke pointers die kunnen schuiven over de elementen van de lijst zonder de hoofdpointer, die
						naar het te sorteren element uit de lijst te wijzigen. Nadien wordt alles afgedrukt in een standaard afdrukprocedure.
*)

	Builder.Compile \ws
		OutExt.Mod
		InsertionPointers.Mod
	~
	
	Builder.Compile \f *
	
	System.Free
		InsertionPointers;
		OutExt.Mod
	~
	
	InsertionPointers.Insertion 8 2 5 4~	(* Test de gewone gevallen *)
	InsertionPointers.Insertion 8.005 5.254 3.458 7.624 9.211 15.0012 32.01 1.5389~   (* Test de kommagetallen *)
	InsertionPointers.Insertion "Test 1 2 3"~	(* Test het gedrag bij een foutieve invoer *)
	InsertionPointers.Insertion~	(* Test het gedrag bij de afwezigheid van invoer *)
	InsertionPointers.Insertion 2~