Tömb-típuskonstrukció
(hiányos mátrixok)

A feladat

Hiányosan kitöltött mátrixok láncolt ábrázolás melletti 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 …

A láncolás „receptje”

A láncolt tömb egy lehetséges ábrázolása:

Algoritmikusan

Pascal-ul

Típus
TMutMatElem=TMatElem’Mutató;

TMatElem=Rekord

(ert:TElem;
i,j:Byte;

    sKov[sorban következö],
    oKov[oszlopban következö]:
                   TMutMatElem
          [növekvően rendezve]

);

THianyMat=Rekord

(n:Byte;

ism:TElem;

      sFej,oFej:Tömb(1..MaxN:
                  TMutMatElem)
             [lehetne olcsóbban]

siker:Boolean;

);

Type
TMutMatElem = ^TMatElem;

TMatElem = Record

ert:TElem;
i,j:Byte;

    sKov{sorban következö},
    oKov{oszlopban következö}:
                 TMutMatElem
        {növekvően rendezve}

End;

THianyMat = Record

n:Byte;

ism:TElem;

    sFej,oFej:Array [1..MaxN] of
                  TMutMatElem;
             {lehetne olcsóbban}

siker:Boolean;

End;

Kezelési minimum:

Algoritmikusan	Pascal-ul
Változó mut:TMatElem’Mutató … Lefoglal(mut) [ha nincs hely: mut=Sehova] …	Var mut:^TMatElem; … New(mut); {egy TMatElem típusúnak foglal helyet} …
Felszabadít(mut) [mut=Sehova]	Dispose(mut); {mut változatlan!} …
L. még: Létrehoz-nál, HolVan-nál, ElemMódosít-nál, Tomorit-nél!

A főprogram

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

Program HianyosMatrixok;

A teszteléshez, a feltételes fordításhoz:

- fordítási kapcsolók (f/b)

- feltételes fordítás kapcsolói ("változói", most TESZT)

- s ezek be-/kikapcsolás direktívái: {$DEFINE TESZT}/{$UNDEF TESZT}

{$f+ $b-}

{$DEFINE TESZT}

Uses

HianyMat,Newdelay,Crt;

{$i AltRutin.inc}

Const

cim ='Hiányos mátrix -- Próba';

Var

m,m1,m2:THianyMat;

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); {m1[i,i]:=i}

End;

Ki('szimmetrikus m1',m1);

{konstans mátrixból alsó-háromszög mátrix létrehozás:}

Letrehoz(N,0,m);

For i:=1 to N do

Begin

For j:=1 to i do

Begin

ElemModosit(i,j,i*10+j,m); {m[i,j]:=i*10+j}

{$IFDEF TESZT}

Ki('nyomkövetés m',m);

{$ENDIF};

End;

Tomorit(m);

Ki('alsó-3-szög (0) m',m);

{0 elem cseréje 1-re:}

For i:=1 to N do

Begin

For j:=1 to N do

Begin

If ElemErtek(i,j,m)=0 then

Begin

ElemModosit(i,j,1,m);

{$IFDEF TESZT}

Ki('nyomkövetés m',m);

{$ENDIF};

End;

Tomorit(m);

Ki('alsó-3-szög (1) m',m);

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 Pascal unit-tal

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

Unit HianyMat;

Hiányosan kitöltött négyzetes mátrixok láncolt ábrázolás melletti

megvalósítása.

Asszociált müveletek:

* Letrehoz {konstans mátrixot}

* Ki

* Be

* Osszead

* Kivon

* Szoroz

* SkalSzor

* HibasE

* ElemErtek

* ElemModosit

* Tomorit

A teszteléshez, a feltételes fordításhoz:

- fordítási kapcsolók (f/b)

- feltételes fordítás kapcsolói ("változói", most TESZT)

- s ezek be-/kikapcsolás direktívái: {$DEFINE TESZT}/{$UNDEF TESZT}

{$f+ $b-}

{$DEFINE TESZT}

Interface

Const

MaxN = 100;

Type

TElem = Integer;

TMutMatElem = ^TMatElem;

TMatElem = Record

ert:TElem; i,j:Byte;

sKov{sorban következö},oKov{oszlopban következö}:TMutMatElem

End;

THianyMat = Record

n:Byte;

ism:TElem;

sFej,oFej:Array [1..MaxN] of TMutMatElem;{olcsóbban!!!}

{növekvően rendezve}

siker:Boolean;

End;

Procedure Tomorit(Var m:THianyMat);

{Ef: -

Uf: m’^.ism=m leggyakoribb elemének értéke ES
m’ elemei ELEME m-nek ES elemei<>m’.ism}

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

{Ef: -

Uf: m.n=n ES m.ism=ism ES m.sFej=Nil ES m.oFej=Nil ES m.siker}

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

{Ef: -

Uf: ...}

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

{Ef: -

Uf: ...}

Procedure Osszead(Const m1,m2:THianyMat;

Var osszeg:THianyMat);

{Ef: -

Uf: ...}

Procedure Kivon(Const m1,m2:THianyMat;

Var kulonbseg:THianyMat);

{Ef: -

Uf: ...}

Procedure Szoroz(Const m1,m2:THianyMat;

Var szorzat:THianyMat);

{Ef: -

Uf: ...}

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

Var szorzat:THianyMat);

{Ef: -

Uf: ...}

Function HibasE(Const m:THianyMat):Boolean;

{Ef: -

Uf: ...}

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

{Ef: -

Uf: ...}

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

Var m:THianyMat);

{Ef: -

Uf: ...}

Implementation

Uses

Newdelay,Crt;

{$i AltRutin.inc}

{Elem-keresö függvény: -------------------------------------------}

Function HolVan(Const i,j:Byte; Const m:THianyMat):TMutMatElem;

{Ef: (i,j)-szerint növekedöen rendezett

Uf: LETEZIK (i,j) ELEME m.(i,j) => Holvan^.(i,j)=(i,j)

NEM LETEZIK (i,j) ELEME m.(i,j) => Holvan=Nil}

Var

mut:TMutMatElem;

Begin

mut:=m.sFej[i];

While (mut<>Nil) and (mut^.j<j) do

Begin

mut:=mut^.sKov;

End;

If (mut=Nil) or (mut^.j>j) then HolVan:=Nil

else HolVan:=mut;

End; {HolVan}

Function SorbanElozo(Const i,j:Byte; Const m:THianyMat):TMutMatElem;

{Ef: (i,j)-szerint növekedöen rendezett

Uf: ...}

Var

mut,emut:TMutMatElem;

Begin

mut:=m.sFej[i];

If mut=Nil then {nincs az i. sorban még elem}

Begin

SorbanElozo:=Nil

End

Else

Begin

emut:=Nil;

While (mut<>Nil) and (mut^.j<j) do

Begin

emut:=mut; mut:=mut^.skov;

End;

SorbanElozo:=emut

End;

End; {SorbanElozo}

Function OszlopbanElozo(Const i,j:Byte; Const m:THianyMat):TMutMatElem;

{Ef: (i,j)-szerint növekedöen rendezett

Uf: ...}

Var

mut,emut:TMutMatElem;

Begin

mut:=m.oFej[j];

If mut=Nil then {nincs a j. oszlopban még elem}

Begin

OszlopbanElozo:=Nil

End

Else

Begin

emut:=Nil;

While (mut<>Nil) and (mut^.i<i) do

Begin

emut:=mut; mut:=mut^.skov;

End;

OszlopbanElozo:=emut

End;

End; {OszlopbanElozo}

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

Function ElemSzam(Const m:THianyMat):Integer;

{Ef: -

Uf: ElemSzam(m)=a láncolt elemek száma}

Var

i,j:Byte;

db:Integer;

Begin

db:=0;

For i:=1 to m.n do

Begin

For j:=1 to m.n do

Begin

If HolVan(i,j,m)<>Nil then Inc(db);

End;

ElemSzam:=db

End; {ElemSzam}

Procedure Tomorit(Var m:THianyMat);

{Ef: -

Uf: m’^.ism=m leggyakoribb elemének értéke ES
m’ elemei ELEME m-nek ES elemei<>m’.ism}

Var

i,j,k,db,max:Byte;

mut,emut:TMutMatElem;

maxe,e:TElem;

gyak:Array [1..MaxN*MaxN] of

Record ert:TElem; db:Integer End;

Begin

{teljessé tétel -- m.ism értéküekkel kiegészítés:}

For i:=1 to m.n do

Begin

For j:=1 to m.n do

Begin

mut:=HolVan(i,j,m);

If mut=Nil then {m.ism értékü elem}

Begin

New(mut);

mut^.ert:=m.ism; mut^.i:=i; mut^.j:=j;

mut^.sKov:=Nil; mut^.oKov:=Nil;

emut:=SorbanElozo(i,j,m);

If emut=Nil then {fej-hez láncolandó}

Begin

mut^.sKov:=m.sFej[i]; m.sFej[i]:=mut;

End

else {elemhez láncolandó}

Begin

mut^.sKov:=emut^.sKov; emut^.sKov:=mut;

End; {emut}

emut:=OszlopbanElozo(i,j,m);

If emut=Nil then {fej-hez láncolandó}

Begin

mut^.oKov:=m.oFej[j]; m.oFej[j]:=mut;

End

else {elemhez láncolandó}

Begin

mut^.oKov:=emut^.oKov; emut^.oKov:=mut;

End; {emut}

End; {mut}

End; {j}

End; {i}

{$IFDEF TESZT}

Ki('ellenörzés -- teljes',m);

{$ENDIF};

{gyakoriság-számlálás:}

db:=0;

For i:=1 to m.n do

Begin

For j:=1 to m.n do

Begin

e:=HolVan(i,j,m)^.ert;

k:=1;

While (k<=db) and (e<>gyak[k].ert) do Inc(k);

If k>db then

Begin

Inc(db); gyak[db].ert:=e; gyak[db].db:=1;

End

else

Begin

Inc(gyak[k].db)

End;

End; {j}

End; {i}

{a leggyakoribb kiválasztása:}

max:=gyak[1].db; maxe:=gyak[1].ert;

For i:=2 to m.n do

Begin

If gyak[i].db>max then

Begin

max:=gyak[i].db; maxe:=gyak[i].ert;

End;

{a leggyakoribb adminisztrálása, kifüzése:}

m.ism:=maxe;

For i:=1 to m.n do

Begin

For j:=1 to m.n do

Begin

mut:=HolVan(i,j,m); e:=mut^.ert;

If e=maxe then {kifüzendö}

Begin

emut:=SorbanElozo(i,j,m);

If emut=Nil then {sor elejéröl}

Begin

m.sFej[i]:=mut^.sKov; {még nem dobjuk el}

End

else {sor belsejéböl}

Begin

emut^.sKov:=mut^.sKov; {még nem dobjuk el}

End;

emut:=OszlopbanElozo(i,j,m);

If emut=Nil then {oszlop elejéröl}

Begin

m.oFej[j]:=mut^.oKov; Dispose(mut);

End

else {oszlop belsejéböl}

Begin

emut^.oKov:=mut^.oKov; Dispose(mut);

End; {emut}

End; {e}

End; {j}

End; {i}

{$IFDEF TESZT}

Ki('ellenörzés -- tömörített',m);

{$ENDIF};

End; {Tomorit}

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

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

{Ef: -

Uf: m.n=n ES m.ism=ism ES m.sFej=Nil ES m.oFej=Nil ES m.siker}

Var

i,j:Byte;

Begin

m.n:=n;

m.ism:=ism;

For i:=1 to MaxN do

Begin

m.sFej[i]:=Nil; m.oFej[i]:=Nil

End;

m.siker:=True;

End; {Letrehoz}

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

{Ef: -

Uf: ...}

Var

i,j:Byte;

Begin

UjLap(cim,0);

For i:=1 to m.n do

Begin

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

For j:=1 to m.n do

Begin

Write(ElemErtek(i,j,m):4)

End; {j}

Writeln;

End; {i}

Writeln('Tárolt elemek száma:',ElemSzam(m));

BillreVar;

End; {Ki}

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

{Ef: -

Uf: ...}

Begin

{Ötlet:

* beolvasni a "teljes" mátrixot

* és tömöríteni...}

End; {}

Procedure Osszead(Const m1,m2:THianyMat;

Var osszeg:THianyMat);

{Ef: -

Uf: ...}

Begin

{...}

End; {}

Procedure Kivon(Const m1,m2:THianyMat;

Var kulonbseg:THianyMat);

{Ef: -

Uf: ...}

Begin

{...}

End; {}

Procedure Szoroz(Const m1,m2:THianyMat;

Var szorzat:THianyMat);

{Ef: -

Uf: ...}

Begin

{...}

End; {}

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

Var szorzat:THianyMat);

{Ef: -

Uf: ...}

Begin

{...}

End; {}

Function HibasE(Const m:THianyMat):Boolean;

{Ef: -

Uf: ...}

Begin

{...}

End; {}

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

{Ef: -

Uf: m-nek nem tárolt eleme az (i,j) => ElemErtek(i,j,m)=m.ism ES

m-nek tárolt eleme az (i,j) => ElemErtek(i,j,m)=tárolt érték}

Var

mut:TMutMatElem;

Begin

mut:=HolVan(i,j,m);

If mut=Nil then ElemErtek:=m.ism

else ElemErtek:=mut^.ert

End; {ElemErtek}

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

Var m:THianyMat);

{Ef: -

Uf: BARMELY ii<>i,jj<>j ELEME [1..m.n]: m’ elemei = m elemei ES

m’ (i,j) eleme = e}

Var

emut,mut:TMutMatElem;

Begin

If m.ism<>e then {tárolandó elem esete}

Begin

mut:=HolVan(i,j,m);

If mut<>Nil then {van ilyen elem tárolva}

Begin

mut^.ert:=e

End

else {nincs tárolva ez az elem}

Begin

{MatElem létrehozás:}

New(mut); mut^.ert:=e; mut^.i:=i; mut^.j:=j;

{láncolások:}

emut:=SorbanElozo(i,j,m);

If
m.sFej[i]=Nil then {üres még a sor}

Begin

m.sFej[i]:=mut; mut^.sKov:=Nil;

End else if

emut=Nil then {sorelsőként illesztendő be}

Begin

mut^.sKov:=m.sFej[i]; m.sFej[i]:=mut;

End

else

Begin

mut^.sKov:=emut^.sKov; emut^.sKov:=mut;

End;

{EndIf}

emut:=OszlopbanElozo(i,j,m);

m.oFej[j]=Nil then {üres még az oszlop}

Begin

m.oFej[j]:=mut; mut^.oKov:=Nil;

End else if

emut=Nil then {oszlopelsőként illesztendő be}

Begin

mut^.oKov:=m.oFej[j]; m.oFej[j]:=mut;

End

else

Begin

mut^.oKov:=emut^.oKov; emut^.oKov:=mut;

End;

{EndIf}

End; {mut}

End

else {nem tárolandó elem esete}

Begin

mut:=HolVan(i,j,m);

If mut<>Nil then {most már fölöslegesen tárolt elem: törlendö}

Begin

emut:=SorbanElozo(i,j,m);

If emut=Nil then m.sFej[i]:=mut^.sKov

else emut^.sKov:=mut^.sKov;

emut:=OszlopbanElozo(i,j,m);

If emut=Nil then m.oFej[j]:=mut^.oKov

else emut^.oKov:=mut^.oKov;

Dispose(mut);

End;

End; {m.ism}

End; {ElemModosit}

Begin

End.

Tömb-típuskonstrukció (hiányos mátrixok)

A feladat

Műveletek a mátrixokkal

A láncolás „receptje”

A főprogram

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

Tömb-típuskonstrukció
(hiányos mátrixok)