Szöveg; néhány jellegzetes tömbös/szöveges feladatfajta

1. A szöveg

A korábbi leckékhez hasonlóan ezt a típust is a definiálás és a felhasználás szintaktikai, szemantikai tudnivalóinak a megadásával mutatjuk be.

1.1. A szövegtípus

Strukturálás

Annak ellenére, hogy egy nyilvánvalóan összetett típusról van szó, nincs értelme strukturálásról beszélni, mivel ez teljesen kötött, alig ad valami szabadságot a programozónak; csak annyit, hogy jogában áll a maximális karakterszámot előre meghatározni:

Szövegtípus = Szöveg(MaxHossz).

Értékhalmaz

MaxHossz-nyi karaktersorozatok halmaza (karaktertípus MaxHossz-szoros direktszorzata).

Műveletek

Hossz, + (egymásután írás), Balrész, Jobbrész, Jele (adottadik jele), Üres ("" = szövegkonstans).

Megjegyzés: Implementációnként eltérő műveletkészletet definiálnak.

Relációk

<, ≤, ≥, > (alfabetikus rendezés), =, ≠.

Alfabetikus rendezés

(1) Az a szó van ábécében előbb, amelyik első különböző betűje előbb van;

(2) az ∅ üres szó (="") minden szónál előbb van.

Példák a rendezési axiómák alkalmazására:

1.2. A szöveg és a tömb

Vegyük észre, hogy vannak a tömbök és a „szövegek” közt hasonlatosságok, de lényeges eltérések is! Mindkettő azonos típusú elemeket egyesít egyetlen – bár összetett – elemmé. Amíg a tömb esetében ez az elemtípus szabadon megválasztható, addig a szövegtípus esetében rögzített: karakter. Tehát a tömb valójában nem típus, hanem egy eszköz típusok „gyártásához”. Ezért helyesebb a tömböt egy ún. típuskonstrukciónak nevezni.

A tömb is a szöveg is indexelhető, így elemeik külön-külön elérhetők. A szövegeket azonban elemeinél nagyobb „egységekben” és kezelhetjük. Például valamekkora kezdő-, vagy végszeletét „egyben” is vizsgálhatjuk. (L. Balrész, Jobbrész műveleteket.)

Amíg a tömb létrejöttekor (statikus deklaráció esetén) fix méretű, addig a szöveg „lényegéhez tartozik” a méret dinamikus változása is, hiszen a fent definiált + művelettel (konkatenáció) az operandusainak össz hosszával megegyező hosszúságú szöveg keletkezik.

Érdemes tudatosítani a + művelet nem kommutativitását. Ezt szemléltethetjük az alábbi feladat kétféle megoldásával.

Feladat

Megoldás – 1

Csak a lényeget, nem a precíz algoritmust adjuk meg. (Gyakorlásképpen a tisztelt olvasó oldja meg úgy is!) A fordított sorozat kezdetben legyen az üres szöveg. Ehhez jobbról illesszük az eredeti szöveg jeleit hátulról előrefelé haladva. Például: a „körte” szövegből a fordított szöveg alakulása lépésről-lépésre ez lesz: „e”, „et”, „etr”, „etrö”, „etrök”.

Megoldás – 2

A második megoldásban balról illesztjük az eredeti szöveg jeleit (elölről haladva), tehát a félig kész elé. Ez esetben a készülő fordított szöveg állapotai ezek lesznek: „k”, „ök”, „rök”, „trök”, „etrök”.

Érdemes rápillantani az alábbi animációra, amelyben körüljárjuk a fentieket.

További problémák

Meglepő, de nehézségeket rejt a rendezési reláció. A probléma forrása az, hogy az ún. alfabetikus rendezés lényege az, hogy a két összehasonlítandó szöveg azonos indexű jeleit vetjük össze, és az (1.-vel kezdve) elsőként eltérő jelpár határozza meg a sorrendet. Például „alfa”<„alma”, mert az „f” előbb van az ABC-ben, mint az „m”. Úgy is mondhatnánk: „f”<„m”, így világosan kiderül, hogy valójában visszavezetjük a karaktertípusnál értelmezett rendezési relációra.

Első probléma: a magyar nyelvben az ABC-ben vannak többjelű betűk is, jól meghatározott helyre illesztve, azaz a jelenkénti hasonlítás fals eredményre vezethet. Például: a „csacsi” és a „cumi” sorrendje: „csacsi”, „cumi”, mivel az összes „cs”-vel kezdődőt meg előzi bármely „c”-vel kezdődő szó.

A második probléma: a magyar nyelvben lévő ékezetes betűket az addigra már definiált karakterkészletekben a „fölöslegesnek” vélt jelek helyére illesztették, így a karakterek rendezési elvére addig alkalmazott „az a jel van előbb, amelyik kódja kisebb” elv nem működik. Például: az „alá” és az „alul” sorrendje „alul” < „alá” lesz, mert „á” > „u”, a helyes „alá” < „alul” helyett.

Vissza a tartalomjegyzékhez

2. Feladatfajták

A megismert összetett adattípusaink (a tömb és a szöveg) már lehetővé teszik, hogy elidőzzünk általában is bizonyos jellegzetes feladatfajták elemzésén.

Figyelje meg az alábbi animációban: a feladat specifikációból hogyan alkotjuk meg a megoldás algoritmusát!

Az alábbi animációban érdekes, összetettebb feladatok alkalmazását láthatja a tömböknek.

Vissza a tartalomjegyzékhez