Einführung
in die imperative Programmierung
WS 2018/19
Listen
Umdrehen einer Liste rekursiv
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;
function umdrehen_rekursiv( inRefAnfang: tRefElement): tRefElement;
var
liste: tRefElement;
begin
if inRefAnfang=nil then
umdrehen_rekursiv:=nil
else
if inRefAnfang^.next=nil then
umdrehen_rekursiv:= inRefAnfang
else
begin
liste:= umdrehen_rekursiv(inRefAnfang^.next);
inRefAnfang^.next^.next := inRefAnfang;
inRefAnfang^.next:= nil;
umdrehen_rekursiv := liste;
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);}
{umdrehen(listenanfang);}
alleDrucken(umdrehen_rekursiv(listenanfang));
END.
Arrays
Addition und Multiplikation von Matrizen
program Felder (input,output);
const FELDMAX = 3;
type
tIndex = 1..FELDMAX;
tFeld = array[tIndex,tIndex] of integer;
var
a,b,c : tFeld;
eingabe : integer;
zeiger : integer;
zeile,spalte: integer;
procedure alleDrucken(zuDrucken: tFeld);
var
zeile,spalte: integer;
begin
for zeile := 1 to FELDMAX do
begin
for spalte := 1 to FELDMAX do
write(zuDrucken[zeile, spalte],' ');
writeln;
end;
writeln;
end;
function addMatrix(inA,inB: tFeld): tFeld;
var
zeile,spalte: integer;
erg: tFeld;
begin
for zeile := 1 to FELDMAX do
begin
for spalte := 1 to FELDMAX do
erg[zeile, spalte] := inA[zeile, spalte] + inB[zeile, spalte] ;
end;
addMatrix := erg;
end;
function multMatrix(inA,inB: tFeld): tFeld;
var
zeile,spalte,i: integer;
erg: tFeld;
begin
for zeile := 1 to FELDMAX do
for spalte := 1 to FELDMAX do
begin
erg[zeile, spalte]:=0;
for i:=1 to FELDMAX do
erg[zeile, spalte]:= erg[zeile, spalte] + inA[zeile,i]*inB[i,spalte];
end;
multMatrix := erg;
end;
BEGIN
writeln('Eingabe der Zahlen');
for zeile := 1 to FELDMAX do
begin
for spalte := 1 to FELDMAX do
read(a[zeile,spalte]);
writeln;
end;
writeln('Eingabe der Zahlen');
for zeile := 1 to FELDMAX do
begin
for spalte := 1 to FELDMAX do
read(b[zeile,spalte]);
writeln;
end;
alleDrucken(a);
alleDrucken(b);
c:=addMatrix(a,b);
alleDrucken(c);
c:=multMatrix(a,b);
alleDrucken(c);
END.
Binärer Suchbaum
Aufbau des Baums und Suchen eines Binärindexes
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 baumaufbau(inWurzel: tRefBinBaum; inTiefe:integer);
var
i:integer;
begin
if (inWurzel = nil) then
begin
for i:=0 to inTiefe do
write(' ');
writeln('nil');
end
else
begin
baumaufbau(inWurzel^.rechts, inTiefe+1);
for i:=0 to inTiefe do
write(' ');
writeln(inWurzel^.Info);
baumaufbau(inWurzel^.links, inTiefe+1);
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;
function KnotenVonIndex( inBaum : tRefBinBaum;
inIndex : integer) : tRefBinBaum;
{ findet den Knoten zum Binärbaumindex }
var
BinaerString: String;
i:integer;
zeiger: tRefBinBaum;
begin
BinaerString:='';
i:= inIndex;
while i>1 do
begin
if (i mod 2)=0 then
BinaerString := '0' + BinaerString
else
BinaerString := '1' + BinaerString;
i:= i div 2;
end;
i:=1;
zeiger:= inBaum;
for i:=1 to length(BinaerString) do
begin
if (BinaerString[i]='0') then
zeiger:= zeiger^.links
else
zeiger:= zeiger^.rechts;
end;
KnotenVonIndex := zeiger;
end;
function KnotenVonIndex2( inBaum : tRefBinBaum;
inIndex : integer; inAktuellIndex: integer ) : tRefBinBaum;
{ findet den Knoten zum Binärbaumindex }
var
zeiger: tRefBinBaum;
begin
if inBaum=nil then
KnotenVonIndex2 := nil
else
begin
if (inIndex=inAktuellIndex) then
KnotenVonIndex2 := inBaum
else
begin
zeiger:= KnotenVonIndex2(inBaum^.links, inIndex, inAktuellIndex*2);
if zeiger =nil then
zeiger:= KnotenVonIndex2(inBaum^.rechts, inIndex, inAktuellIndex*2+1);
KnotenVonIndex2:= zeiger;
end;
end;
end;
function KnotenVonIndex3 ( baum : tRefBinBaum;
index : integer) : tRefBinBaum;
{ findet den Knoten zum Binärbaumindex }
var
elter : tRefBinBaum; { Zeiger auf Elternknoten }
begin
if (index = 1) then { Wurzel, Rekursionsabbruch }
KnotenVonIndex3 := baum
else
begin { Rekursion }
elter := KnotenVonIndex3(baum, index div 2);
if ( (index mod 2 ) = 0 ) then
KnotenVonIndex3 := elter^.links
else
KnotenVonIndex3 := elter^.rechts
end;
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));}
{baumaufbau(Wurzel,0);}
{writeln(KnotenVonIndex(Wurzel, 5)^.Info);}
{writeln(KnotenVonIndex2(Wurzel, 5,1)^.Info);}
writeln(KnotenVonIndex3(Wurzel, 5)^.Info);
end. { suchbaum }