Einführung in die imperative Programmierung

WS 2018/19

Listen

Rotieren einer Liste ( NK2010 Aufg 1)

Umdrehen einer Liste

program liste (input,output);
   type
   tRefElement = ^tElement;
   tElement = record
   zahl : integer;
   next : tRefElement;
   end;
   
   var 
   listenanfang : tRefElement; 
   zeiger : tRefElement; 
   endeListe : tRefElement;
   eingabe : integer;
   
   procedure alleDrucken(zuDrucken:  tRefElement);
   var
   zeiger: tRefElement;
   begin
   writeln('Liste');
   zeiger := zuDrucken;
   while zeiger <> nil do 
   begin
   writeln(zeiger^.zahl);
   zeiger:= zeiger^.next;
   end;
   end;
   
   procedure RotiereListe(var ioRefAnfang: tRefElement);
   { Liste rotieren durch Ändern der Verkettung}
   var 
   zeiger: tRefElement;
   begin
   if (ioRefAnfang<>nil) then
   if (ioRefAnfang^.next <> nil) then
   begin
   {letztes Element finden und next auf erstes umbiegen}
   zeiger:= ioRefAnfang;
   while (zeiger^.next<>nil) do
   zeiger:=zeiger^.next;
   zeiger^.next:= ioRefAnfang; 

 {Anfangszeiger umsetzen}
   ioRefAnfang := ioRefAnfang^.next;

 {Zeiger next des letzten Elements auf nil}
   {zeiger^.next^.next := nil;}
   zeiger:= zeiger^.next;
   zeiger^.next := nil; 
   end; {if (ioRefAnfang<>nil)}
   
   end; {prozedure RotiereListe}
   
   procedure umdrehen(var ioRefAnfang: tRefElement);
   var
   vorher,zeiger,nachher: tRefElement;
   begin
   if (ioRefAnfang<>nil) then
   if (ioRefAnfang^.next <> nil) then
   begin
   zeiger:= ioRefAnfang;
   vorher:= nil;
   nachher:= zeiger^.next;
   while (zeiger<>nil) do
   begin
   zeiger^.next:= vorher;
   vorher:=zeiger;
   zeiger:=nachher;
   if (zeiger<>nil) then
   nachher:= zeiger^.next;
   end;
   ioRefAnfang := vorher;
   
   end; 
   
   end;
   
   BEGIN
   listenanfang := nil;
   writeln('Eingabe der Zahlen, Beenden mit 0'); 
   readln(eingabe);
   while eingabe <> 0 do
   begin
   new(zeiger);
   zeiger^.zahl := eingabe;
   zeiger^.next:=nil;
   if listenanfang = nil then
   listenanfang := zeiger
   else
   endeListe^.next:=zeiger;
   endeListe := zeiger; 
   readln(eingabe);
   end;
   
   alleDrucken(listenanfang);
   
   RotiereListe(listenanfang);

   alleDrucken(listenanfang);
   
   umdrehen(listenanfang);
   
   alleDrucken(listenanfang);
   
   END.
 

Zyklische Listen

Rotieren einer Liste

Einfügen am Anfang oder Ende (NK 2010 Aufg 2)

program liste (input,output);
   type
   tRefElement = ^tElement;
   tElement = record
   zahl : integer;
   next : tRefElement;
   end;
   
   var 
   listenanfang : tRefElement; 
   zeiger : tRefElement; 
   endeListe : tRefElement;
   eingabe : integer;
   
   procedure alleDrucken(zuDrucken:  tRefElement);
   var
   zeiger: tRefElement;
   begin
   writeln('Liste');
   zeiger := zuDrucken;
   if (zuDrucken <> nil) then
   repeat 
   writeln(zeiger^.zahl);
   zeiger:= zeiger^.next;
   until zeiger = zuDrucken 
   end;
   
   procedure RotiereListe(var ioRefAnfang: tRefElement);
   { Liste rotieren durch Ändern der Verkettung}
   var 
   zeiger: tRefElement;
   begin
   if (ioRefAnfang<>nil) then
   if (ioRefAnfang^.next <> nil) then
   begin
   {letztes Element finden und next auf erstes umbiegen}
   zeiger:= ioRefAnfang;
   while (zeiger^.next<>nil) do
   zeiger:=zeiger^.next;
   zeiger^.next:= ioRefAnfang; 

 {Anfangszeiger umsetzen}
   ioRefAnfang := ioRefAnfang^.next;

 {Zeiger next des letzten Elements auf nil}
   {zeiger^.next^.next := nil;}
   zeiger:= zeiger^.next;
   zeiger^.next := nil; 
   end; {if (ioRefAnfang<>nil)}
   
   end; {prozedure RotiereListe}
   
   procedure einfuegen ( inInfo: integer;
   inEinfuegenAmAnfang: Boolean;
   var ioRefAnfang: tRefElement);
   {Fügt ein neues Element mit Info-Wert inInfo in eine zyklische Liste
   ein, auf deren erstes Element ioRefAnfang zeigt.
   Ist inEinfuegenAmAnfang = true, wird am Listenanfang, andernfalls am
   Listenende eingefügt.}
   var
   zeiger,neu:tRefElement;
   
   begin
   if inEinfuegenAmAnfang then
   begin
   {Listenelement anlegen}
   new(neu);
   neu^.zahl:=inInfo;
   
   {next-Zeiger des letzten Elements umbiegen}
   zeiger:= ioRefAnfang;
   while (zeiger^.next <> ioRefAnfang) do
   zeiger := zeiger^.next;
   zeiger^.next := neu;
   
   {next von neuem Element umsetzen}
   neu^.next :=  ioRefAnfang;
   
   {}
   ioRefAnfang := neu; 
   
   end
   else
   begin
   {Listenelement anlegen}
   new(neu);
   neu^.zahl:=inInfo;
   
   {next-Zeiger des letzten Elements umbiegen}
   zeiger:= ioRefAnfang;
   while (zeiger^.next <> ioRefAnfang) do
   zeiger := zeiger^.next;
   zeiger^.next := neu;
   
   {next von neuem Element umsetzen}
   neu^.next :=  ioRefAnfang;
   
   end;
   
   end;
   
   BEGIN
   listenanfang := nil;
   writeln('Eingabe der Zahlen, Beenden mit 0'); 
   readln(eingabe);
   while eingabe <> 0 do
   begin
   new(zeiger);
   zeiger^.zahl := eingabe;
   zeiger^.next:=nil;
   if listenanfang = nil then
   begin
   listenanfang := zeiger;
   zeiger^.next := listenanfang;
   end 
   else
   begin
   endeListe^.next:=zeiger;
   zeiger^.next := listenanfang;
   end;
   endeListe := zeiger; 
   readln(eingabe);
   end;
   
   alleDrucken(listenanfang);
   
   einfuegen(7, true, listenanfang);
   
   einfuegen(8, false, listenanfang);
   
   alleDrucken(listenanfang);
   
   END.

Arrays

Sudoku ( NK2010 Aufg 4)

function pruefeTeilfeld(inSudoku: tSudokuFeld;
   inStartZeile, inStartSpalte,
   inEndZeile, inEndSpalte: tZiffer):boolean;
   {Prueft, ob das eingegebene Sudokufeld (inSudoku) innerhalb des durch
   die restlichen vier Parameter definierten Ausschnittes jede der Ziffern
   von 1 bis 9 mindestens einmal enthält.}
   var
   marker:tZifferMarkerFeld;
   i,j:integer;
   begin
   initZifferMarkerFeld(marker);
   
   for i:= inStartSpalte to inEndSpalte do
   for j:= inStartZeile to inEndZeile do
   marker[inSudoku[j,i]] := true;
   
   pruefeTeilfeld:= alleZiffernMarkiert(marker);
   
 {pruefeTeilfeld:= marker[1] and marker[2] ... and marker[9];}

end;

Binärer Suchbaum

Umdrehen, Suche von Zahlen aus einem Intervall im Baum, Suche nach einer Zahl

program suchbaum (input, output);
   { Binärer Suchbaum }

 type
   tRefBinbaum = ^tBinbaum;
   tBinBaum = record
   Info:integer;
   links,
   rechts : tRefBinBaum;
   end;
   tNatZahl = 0..maxint;

 var
   Wurzel : tRefBinBaum;
   Max : tNatZahl; 
   zahl1,zahl2,ergebnis,tiefe:integer;
   gefunden:boolean; 
   oben,unten:integer;
   
   procedure BBKnotenEinfuegen (
   inZahl : integer;
   var ioWurzel : tRefBinBaum);
   { fuegt in den Suchbaum, auf dessen Wurzel ioWurzel
   zeigt, ein Blatt mit Wert inZahl an. }

 var
   Zeiger : tRefBinBaum;

 begin
   if ioWurzel = nil then

 begin
   new (Zeiger);
   Zeiger^.Info := inZahl;
   Zeiger^.links := nil;
   Zeiger^.rechts := nil;
   ioWurzel := Zeiger
   end { if }
   else { ioWurzel <> nil }
   if inZahl < ioWurzel^.info then
   BBKnotenEinfuegen (inZahl, ioWurzel^.links)
   else
   BBKnotenEinfuegen (inZahl, ioWurzel^.rechts);
   end; { BBKnotenEinfuegen }

 procedure BBAufbauen (var outWurzel : tRefBinBaum);
   { Liest eine Folge von Integer-Zahlen ein (0 beendet die
   Eingabe, gehoert aber nicht zur Folge) und speichert
   die Folge in einem binren Suchbaum. }

 var 
   Zahl : integer;

 begin
   outWurzel := nil; { mit leerem Baum initialisieren }
   read (Zahl);
   while Zahl <> 0 do
   begin
   BBKnotenEinfuegen (Zahl, outWurzel);
   read (Zahl)
   end
   end; { BBAufbauen }

 
   procedure inorder(inWurzel: tRefBinBaum);
   begin
   if (inWurzel <> nil) then
   begin
   inorder(inWurzel^.links);
   writeln(inWurzel^.Info);
   inorder(inWurzel^.rechts);
   end;
   end;
   
   procedure umdrehen(inWurzel: tRefBinBaum);
   var
   tausch: tRefBinBaum;
   begin
   if inWurzel<>nil then
   begin
   umdrehen(inWurzel^.links);
   umdrehen(inWurzel^.rechts);
   
   tausch:= inWurzel^.links;
   inWurzel^.links:= inWurzel^.rechts;
   inWurzel^.rechts:= tausch; 
   
   end;
   end;
   
   procedure IntervallSuche(inWurzel: tRefBinBaum; 
   inUnten, inOben: integer);
   begin
   if (inWurzel <> nil) then
   begin
   IntervallSuche(inWurzel^.links,inUnten,inOben);
   
   if ((inWurzel^.Info>= inUnten) and (inWurzel^.Info<=inOben)) then
   writeln(inWurzel^.Info);
   
   IntervallSuche(inWurzel^.rechts,inUnten,inOben); 
   
   end;
   
   end;
   
   procedure IntervallSucheOptimiert(inWurzel: tRefBinBaum; 
   inUnten, inOben: integer);
   begin
   if (inWurzel <> nil) then
   begin
   if (inUnten < inWurzel^.Info) then
   IntervallSucheOptimiert(inWurzel^.links,inUnten,inOben);
   
   if ((inWurzel^.Info>= inUnten) and (inWurzel^.Info<=inOben)) then
   writeln(inWurzel^.Info);
   writeln('besucht: ' , inWurzel^.Info); 
   
   if (inOben > inWurzel^.Info) then
   IntervallSucheOptimiert(inWurzel^.rechts,inUnten,inOben); 
   
   end;
   
   end;
   
   function Suche(inWurzel: tRefBinBaum; inZahl: integer): boolean;
   begin 
   if (inWurzel= nil) then
   Suche:= false
   else
   if (inWurzel^.Info = inZahl) then
   Suche:=true
   else
   if (inWurzel^.Info > inZahl) then
   Suche := Suche(inWurzel^.links, inZahl)
   else
   Suche:= Suche(inWurzel^.rechts, inZahl); 
   end;
   
   function SucheIterativ(inWurzel: tRefBinBaum; inZahl: integer): boolean;
   var
   zeiger: tRefBinBaum;
   gefunden: boolean;
   begin
   zeiger:= inWurzel;
   gefunden:=false;
   while ((zeiger <> nil) and (not gefunden)) do
   begin
   if (zeiger^.Info=inZahl) then
   gefunden:= true;
   if (inZahl < zeiger^.Info) then
   zeiger:= zeiger^.links
   else 
   zeiger:= zeiger^.rechts; 
   end;
   SucheIterativ:=gefunden; 
   
   end;
 

begin
   writeln('Bitte integer-Zahlen eingeben (0=Ende):');
   BBAufbauen (Wurzel);
   writeln('Inorder-Reihenfolge');
   inorder(Wurzel);
   
   {umdrehen(Wurzel);}
   
   {write('unten: ');
   readln(unten);
   write('oben: ');
   readln(oben);
   
   IntervallSucheOptimiert(Wurzel,unten,oben);
   
   writeln('Inorder-Reihenfolge');
   inorder(Wurzel);}
   
   writeln(SucheIterativ(Wurzel, 5));
   

end. { suchbaum }