Tömb-típuskonstrukció
(speciális mátrixok)

A feladat

Speciális (szabályosan ismétlődő elemeket tartalmazó) mátrix folytonos ábrázolás melletti, helytakarékos megvalósítása.

Műveletek a mátrixokkal

o       Létrehoz (konstans mátrixot)

o       Be / Ki

o       Összead / Kivon / Szoroz

o       Skalárral szoroz

o       elemÉrték / ElemMódosít

o       …

Specialitások – ábrázolások

o       Konstans

Rekord
(ism:TElem
 n:Egész)

o       Diagonális

Rekord
(elemek:Tömb(0[az ismétlődő elemnek]..MaxN:TElem)
 n:Egész)

o       Alsó-háromszög

Rekord
(elemek:Tömb(0..MaxN*(MaxN+1) Div 2:TElem)
 n:Egész)

o       Felső-háromszög

Rekord
(elemek:Tömb(0..MaxN*(MaxN+1) Div 2:TElem)
 n:Egész)

o       Szimmetrikus

Rekord
(elemek:Tömb(0..MaxN*(MaxN+1) Div 2:TElem)
 n:Egész)

o       …


…és a „mihez képest”:

o       „Teljes”

Rekord
(elemek:Tömb(1..MaxN2:TElem)
 n:Egész)

A „standard” tömb tulajdonságai

Fix mérettel jön létre, folytonos memóriatartományon:

Típus TTömb=Tömb(TIndex:TElem)Þ

Méret’TTömb=Számosság’TIndex*Méret’TElem

 

Függvény Cím(Kons. T:TTömb, i:TIndex):Mem.
  Cím:=BázisCím+RelCím(i,Méret’TElem)
Függvény vége.

Függvény RelCím(Kons. i:TIndex, m:Egész):Eg.
  RelCím:=Sorszám(i)*m
Függvény vége.

A tömbök méretének statikusan (fordítási időben) ki kell derülnie!

Típus TTömb = Tömb(1..N:TElem) – N előre definiált konstans lehet csak

A dinamikusság „turbo receptje”

Mód van adott méretű darabot lefoglalni a memóriából.

Algoritmikusan

Turbo Pascal-ul [1]

Változó mut:TTípus’Mutató

…

Lefoglal(mut)
         [ha nincs hely: mut=Sehova]

…

Var mut:^TTípus;
    p:Pointer;

…

New(mut); {egy TTípus-únak foglal helyet}…

GetMem(p,SizeOf(TTípus)); {TTípus-nyi helyet foglal}

…

Felszabadít(mut)  [mut=Sehova]

Dispose(mut); …

FreeMem(p,SizeOf(TTípus));

…

A kényelmes kezelés Pascal trükkje:

Type TSpecMat = Record
                  n:Byte;         {a mátrix rendje}
                  elemek:Pointer; {a mátrix elemeit tartalmazó elemsorozat kezőcíme}
                  …
                 End;

     TVektor = Array [0{az ismétlődő elem helye}..MaxN{tetszőleges!!!}] of TElem;

              {0. elemhez l. a Létrehoz-nál!}

     TMutVektor = ^TVektor;

…

Procedure …(… m:TSpecMat; …);
  Var raDef{iniál}:TMutVektor;
Begin
  …
  raDef:=m.elemek; {megengedett „típuskeveredés”: TMutVektor := Pointer}
  …
  … raDef^[i] {a raDef vektorbeli i. elem, azaz az elemek-beli i. elem}
  …
End; {…}
  

A főprogram

Az alábbi a főprogram forrás kódja: SPMXPROB.PAS.

 

Program SpecialisMatrixok;

  Uses

    SpecMat,Newdelay,Crt;

    {$i AltRutin.inc}

  Const

    cim ='Speciális mátrix -- Próba';

  Var

     m,m1,m2:TSpecMat;

     s:TElem;

     N,i,j:Byte;

 

Begin

  UjLap(cim,0);

  N:=5;

  Letrehoz(N,1,m1); Ki('csupa 1: m1',m1);

  Letrehoz(N,2,m2); Ki('csupa 2: m2',m2);

  {konstans mátrixból szimmetrikus létrehozás:}

  For i:=1 to N do

  Begin

    ElemModosit(i,i,i,m1);

  End;

  Ki('szimmetrikus m1',m1);

  Be('Mátrix-beolvasás',m2);

  Osszead(m1,m2,m); Ki('m1+m2',m);

  Kivon(m1,m2,m); Ki('m1-m2',m);

  Szoroz(m1,m2,m); Ki('m1*m2',m);

  s:=2; SkalSzor(m1,s,m); Ki('m1*s',m);

End.

A típus megvalósítása Turbo Pascal unit-tal

Az alábbi unit (a típus „keretének” a) forrás kódja: SPECMAT.PAS.

 

Unit SpecMat;

(*

  Speciális (szabályosan ismétlödö elemeket tartalmazó) mátrix

  folytonos ábrázolás melletti, helytakarékos megvalósítása.

  Asszociált müveletek:

  * Letrehoz {konstans mátrixot}

  * Ki

  * Be

  * Osszead

  * Kivon

  * Szoroz

  * SkalSzor

  * HibasE

  * ElemErtek

  * ElemModosit

*)

  Interface

    Const

      MaxN = 100;

    Type

      TElem = Integer;

      TFajta = (Kons,Diag,A3Szog,F3Szog,Szim,Teljes);

    Const

      SFajta : Array [TFajta] of String[6]=

               ('Kons','Diag','A3Szog','F3Szog','Szim','Teljes');

    Type

      TSpecMat = Record

                   n:Byte;

                   elemek:Pointer;

                   fajta:TFajta;

                   siker:Boolean;

                 End;

 

    Procedure Letrehoz(Const n:Byte; ism:TElem; Var m:TSpecMat);

    {Ef: -

     Uf: m.n=n ÉS m.elemek^[0..0]=ism ÉS m.fajta=Kons ÉS m.siker}

 

    Procedure Ki(Const cim:String; Const m:TSpecMat);

    {Ef: -

     Uf: ...}

 

    Procedure Be(Const cim:String; Var m:TSpecMat);

    {Ef: -

     Uf: ...}

 

    Procedure Osszead(Const m1,m2:TSpecMat;

                      Var osszeg:TSpecMat);

    {Ef: -

     Uf: ...}

 

    Procedure Kivon(Const m1,m2:TSpecMat;

                    Var kulonbseg:TSpecMat);

    {Ef: -

     Uf: ...}

 

    Procedure Szoroz(Const m1,m2:TSpecMat;

                     Var szorzat:TSpecMat);

    {Ef: -

     Uf: ...}

 

    Procedure SkalSzor(Const m:TSpecMat; Const skal:TElem;

                       Var szorzat:TSpecMat);

    {Ef: -

     Uf: ...}

 

    Function HibasE(Var m:TSpecMat):Boolean;

    {Ef: -

     Uf: HibasE(m) = NEM m.siker ÉS m.siker’}

 

    Function ElemErtek(Const i,j:Byte; Const m:TSpecMat):TElem;

    {Ef: -

     Uf: ...}

 

    Procedure ElemModosit(Const i,j:Byte; Const e:TElem;

                          Var m:TSpecMat);

    {Ef: -

     Uf: ...}

 

  Implementation

    Uses

      Newdelay,Crt;

      {$i AltRutin.inc}

 

    Type {a "rádefiniáláshoz" segéd típus}

      TVektor = Array [0{az ismétlödö elem helye}..MaxN] of TElem;

      TMutVektor = ^TVektor;

 

    {RelatívCím-függvények: -------------------------------------------}

 

    Function CFvKons(Const i,j:Byte; Const m:TSpecMat[SzP1] ):Integer;

    {Ef: -

     Uf: ...}

    Begin

      CFvKons:=0

    End; {CFvKons}

 

    Function CFvDiag(Const i,j:Byte; Const m:TSpecMat):Integer;

    {Ef: -

     Uf: ...}

    Begin

      If i=j then CFvDiag:=i else CFvDiag:=0;

    End; {CFvDiag}

 

    Function CFvA3Szog(Const i,j:Byte; Const m:TSpecMat):Integer;

    {Ef: -

     Uf: ...}

    Begin

      {...}

    End; {CFvA3Szog}

 

    Function CFvF3Szog(Const i,j:Byte; Const m:TSpecMat):Integer;

    {Ef: -

     Uf: ...}

    Begin

      CFvF3Szog:=CFvA3Szog(j,i,m)

    End; {CFvF3Szog}

 

    Function CFvSzim(Const i,j:Byte; Const m:TSpecMat):Integer;

    {Ef: -

     Uf: ...}

    Begin

      {... A3Szog-re visszavezethető,

           az sem baj, ha az ism-re most semmi szükség ...}

      If i>=j then CFvSzim:=((i-1)*i div 2)+j

              else CFvSzim:=((j-1)*j div 2)+i

    End; {CFvSzim}

 

    Function CFvTeljes(Const i,j:Byte; Const m:TSpecMat):Integer;

    {Ef: -

     Uf: ...}

    Begin

      CFvTeljes:=(i-1)*m.n+j

    End; {CFvTeljes}

 

    {Fajta-eldöntö függvények: ----------------------------------------}

 

    Function KonsE(Const m:TSpecMat):Boolean;

    {Ef: –

     Uf: KonsE = BÁRMELY i=1..m.n*m.n-1 : m.elemek^[i]=m.elemek^[i+1]}

      Var

        i:Byte;

        lehet:Boolean;

        raDef{iniálás}:TMutVektor;

    Begin

      raDef:=m.elemek; {az m.elemek-re rádefiniáltuk, hogy vektorként lássuk}

      If m.fajta=Teljes then

      Begin

        Lehet:=True;

        i:=1;

        While (i<m.n*m.n) and lehet do

        Begin

          lehet:=raDef^[i]=raDef^[i+1]; inc(i)

        End;

        KonsE:=lehet

      End

        else

      Begin

        KonsE:=m.fajta=Kons

      End;

    End; {KonsE}

 

    Function DiagE(Const m:TSpecMat):Boolean;

    {Ef: -

     Uf: ...}

    Begin

      {...}

      DiagE:=False

    End; {}

 

    Function A3SzogE(Const m:TSpecMat):Boolean;

    {Ef: -

     Uf: ...}

    Begin

      {...}

      A3SzogE:=False

    End; {}

 

    Function F3SzogE(Const m:TSpecMat):Boolean;

    {Ef: -

     Uf: ...}

    Begin

      {...}

      F3SzogE:=False

    End; {}

 

    Function SzimE(Const m:TSpecMat):Boolean;

    {Ef: –

     Uf: ...}

      Var

        i,j:Byte;

        lehet:Boolean;

        raDef{iniálás}:TMutVektor;

    Begin

      raDef:=m.elemek; {az m.elemek-re rádefiniáltuk, hogy vektorként lássuk}

      If m.fajta=Teljes then

      Begin

        i:=1; lehet:=True;

        While (i<=m.n) and lehet do

        Begin

          j:=1;

          While (j<=m.n) and

                (raDef^[CFvTeljes(i,j,m)]=raDef^[CFvTeljes(j,i,m)]) do

          Begin

            Inc(j);

          End;

          If j<=m.n then lehet:=False

                    else Begin Inc(i); j:=1; end;

        End;

        SzimE:=lehet

      End

        else

      Begin

        SzimE:=m.fajta=Szim

      End;

    End; {SzimE}

 

    {Egyebek: ---------------------------------------------------------}

 

    Function ElemSzam(Const m:TSpecMat):Integer;

    Begin

      Case m.fajta of

        Kons   : ElemSzam:=1; {az ismétlődő elem}

        Diag   : ElemSzam:=1+m.n; {az ismétlődő elem + az átlóbeliek}

        A3Szog,

        F3Szog,

        Szim   : ElemSzam:=1+(m.n*(m.n+1) Div 2)+1; {az ismétlődő + … }

        Teljes : ElemSzam:=Sqr(m.n)

      End;

    End; {ElemSzam}

 

    {Operációk: -------------------------------------------------------}

 

    Procedure Letrehoz(Const n:Byte; ism:TElem; Var m:TSpecMat);

    {Ef: -

     Uf: m.n=n ÉS m.elemek^[0..0]=ism ÉS m.fajta=Kons ÉS m.siker}

      Var

        raDef{iniálás}:TMutVektor;

    Begin

      m.n:=n;

      m.fajta:=Kons; m.siker:=True;

      GetMem(m.elemek,ElemSzam(m)*SizeOf(TElem));

      raDef:=m.elemek; {az m.elemek-re rádefiniáltuk, hogy vektorként lássuk}

      raDef^[0]:=ism;

    End; {Letrehoz}

 

    Procedure Ki(Const cim:String; Const m:TSpecMat);

    {Ef: -

     Uf: ...}

      Var

        raDef{iniálás}:TMutVektor;

        i,j:Byte;

    Begin

      UjLap(cim +'('+FajtaToStr(m.fajta)+')',0);

      raDef:=m.elemek; {az m.elemek-re rádefiniáltuk, hogy vektorként lássuk}

      For i:=1 to m.n do

      Begin

        Writeln(i:3,'. sor:');

        For j:=1 to m.n do

        Begin

          Case m.fajta of

            Kons  : Write(raDef^[CFvKons(i,j,m)]:4);

            Diag  : Write(raDef^[CFvDiag(i,j,m)]:4);

            A3Szog: Write(raDef^[CfvA3Szog(i,j,m)]:4);

            F3Szog: Write(raDef^[CFvF3Szog(i,j,m)]:4);

            Szim  : Write(raDef^[CFvSzim(i,j,m)]:4);

            Teljes: Write(raDef^[CFvTeljes(i,j,m)]:4);

          End; {Case}

        End; {j}

        Writeln;

      End; {i}

      BillreVar;

    End; {Ki}

 

    Procedure Be(Const cim:String; Var m:TSpecMat);

    {Ef: -

     Uf: ...}

    Begin

      {Ötlet:

       * beolvasni a "teljes" mátrixot

       * megkeresni a legtömörebb, speciális ábrázolást (fajtát)

       * konvertáni a megfelelő speciális fajtájúvá...}

    End; {}

 

    Procedure Osszead(Const m1,m2:TSpecMat;

                      Var osszeg:TSpecMat);

    {Ef: -

     Uf: ...}

    Begin

      {...}

    End; {}

 

    Procedure Kivon(Const m1,m2:TSpecMat;

                    Var kulonbseg:TSpecMat);

    {Ef: -

     Uf: ...}

    Begin

      {...}

    End; {}

 

    Procedure Szoroz(Const m1,m2:TSpecMat;

                     Var szorzat:TSpecMat);

    {Ef: -

     Uf: ...}

    Begin

      {Ötlet:

       * szorozni a "teljes" mátrixba

       * megkeresni a legtömörebb, speciális ábrázolást (fajtát)

       * konvertáni a megfelelő speciális fajtájúvá...}

    End; {}

 

    Procedure SkalSzor(Const m:TSpecMat; Const skal:TElem;

                       Var szorzat:TSpecMat);

    {Ef: -

     Uf: ...}

    Begin

      {...}

    End; {}

 

    Function HibasE(Var m:TSpecMat):Boolean;

    {Ef: -

     Uf: HibasE(m) = NEM m.siker ÉS m.siker’}

    Begin

      HibasE:=not m.siker; m.siker:=True

    End; {HibasE}

 

    Function ElemErtek(Const i,j:Byte; Const m:TSpecMat):TElem;

    {Ef: -

     Uf: ...}

    Begin

      {...}

    End; {}

 

    Procedure ElemModosit(Const i,j:Byte; Const e:TElem;

                          Var m:TSpecMat);

    {Ef: -

     Uf: ...}

      Var

        ms:TSpecMat;

        raDef{iniálás}:TMutVektor;

        raDefms:TMutVektor;

        k,l:Byte;

    Begin

      {Ötlet:

       * konvertálni "teljes" mátrixszá

       * módosítani

       * megkeresni a legtömörebb, speciális ábrázolást (fajtát)

       * konvertáni a megfelelö speciális fajtájúvá...}

      ms.n:=m.n;

      ms.fajta:=Teljes;

      {ms elemeinek helyfoglalása:}

      GetMem(ms.elemek,ElemSzam(ms)*SizeOf(TElem));

      {m.elemek-re / ms.elemek-re rádefiniálás, hogy vektorként lássuk:}

      raDef:=m.elemek; raDefms:=ms.elemek;

      {a teljes ms létrehozása:}

      For k:=1 to m.n do

      Begin

        For l:=1 to m.n do

        Begin

          Case m.fajta of

            Kons  : raDefms^[CFvTeljes(k,l,ms)]:=raDef^[CFvKons(k,l,m)];

            Diag  : raDefms^[CFvTeljes(k,l,ms)]:=raDef^[CFvDiag(k,l,m)];

            A3Szog: {...};

            F3Szog: {...};

            Szim  : raDefms^[CFvTeljes(k,l,ms)]:=raDef^[CFvSzim(k,l,m)];

            Teljes: {...};

          End; {Case m.fajta}

        End; {For l}

      End; {For k}

      {ms(i,j) módosítása:}

      raDefms^[CFvTeljes(i,j,ms)]:=e;

      {a legtömörebb fajta megtalálása és m-be másolása:}

      If

        KonsE(ms) then

        Begin

          {...}

        End else if

        DiagE(ms) then

        Begin

          {...}

        End else if

        A3SzogE(ms) then

        Begin

          {...}

        End else if

        F3SzogE(ms) then

        Begin

          {...}

        End else if

        SzimE(ms) then

        Begin

          {m.elemek helyének felszabadítása:}

          FreeMem(m.elemek,ElemSzam(m)*SizeOf(TElem));

          m.fajta:=Szim;

          {m elemeinek helyfoglalása:}

          GetMem(m.elemek,ElemSzam(m)*SizeOf(TElem));

          {m.elemek-re rádefiniálás, hogy vektorként lássuk:}

          raDef:=m.elemek;

          For k:=1 to m.n do for l:=1 to k do

          Begin

            raDef^[CFvSzim(k,l,m)]:=raDefms^[CFvTeljes(k,l,ms)];

          End;

        End

          else {Teljes}

        Begin

          {m.elemek helyének felszabadítása:}

          FreeMem(m.elemek,ElemSzam(m)*SizeOf(TElem));

          {m.elemek <- ms.elemek:}

          m.elemek:=ms.elemek;

        End;

    End; {ElemModosit}

 

Begin

End.

 

  Egy szebb (?) megoldás a fajta-szerinti feldolgozása,

  pl. a kiírásra.

  {$f+ -- az implementation rész elején legyen ez a kapcsoló}

    Type

      TCFv = Function(Const i,j:Byte):Integer;

    Procedure Ki(Const cim:String; Const m:TSpecMat);

      Var

        raDef{iniálás}:TMutVektor;

        i,j:Byte;

        cFv:TCFv;

    Begin

      UjLap(cim,0);

      raDef:=m.elemek; {az m.elemek-re rádefiniáltuk, hogy vektorként lássuk}

      Case m.fajta of

        Kons: cFv:=CFvKons;

        Diag: cFv:=CFvDiag;

        {...}

      End;

      For i:=1 to m.n do

      Begin

        Writeln(i:3,'. sor:');

        For j:=1 to m.n do

        Begin

          Write(raDef^[cFv(i,j)]:4)

        End; {j}

        Writeln;

      End; {i}

      BillreVar;

    End; {Ki}

 

Minden kellék letöltése: Tomb1.zip.


[1] FreePascal-ban létezik dinamikus tömb. Tudnivalók röviden:

Var
  dm:Array of TElem;//dinamikus vektor
…
  SetLength(dm,N);//dm vektornak N eleme lesz
  For i:=0 to N-1 do dm[i]:=i;//0..N-1 közötti indexekkel

 [SzP1]Szükség lehet a mérete miatt.