10. labor: Sztringkezelés dinamikus tömbökkel

A mai óra célja kettős. Egyrészről újra sztringekkel (karaktertömbökkel) dolgozunk. Másrészről most ezek kezelését kiegészítjük úgy, hogy a számukra lefoglalt memóriát dinamikusan kezeljük. Minden megírt függvény a kijelölt művelet elvégzése előtt meghatározza, hogy az általa létrehozott sztring milyen hosszú lesz, és annak megfelelően foglal memóriát. Így soha nem kell majd aggódni attól, hogy egy előre meghatározott méretű tömb megtelik.

Írj függvényt, amely paraméterként vesz át két sztringet, amelyeket nem módosít. A visszatérési értéke legyen egy új sztring, amelyet dinamikusan foglalt le, és a két sztringet tartalmazza összefűzve! A függvény pontosan annyi bájt memóriát foglaljon le dinamikusan, amennyire szükség van! A string.h függvényeit ne használd.

Írj egyszerű főprogramot, amely meghívja a függvényt, és kiír egy összefűzött sztringet a képernyőre. Figyelj arra, hogy ne legyen memóriaszivárgás – azaz a lefoglalt memóriát szabadítsd is fel.

#include <stdio.h>
#include <stdlib.h>

char* osszefuz(char const* s1,char const *s2) {
    int len1=0, len2=0;
    int i;
    char *uj;
     /* Megmérjük mindkét sztring hosszát */
    while (s1[len1]) len1++;
    while (s2[len2]) len2++;
     /* Területfoglalás (+1 hely a lezáró 0 miatt) */
    uj = (char*) malloc((len1+len2+1)*sizeof(char));
     /* Ha nem sikerül :( */
    if(uj==NULL) return NULL;
     /* Különben másolunk */
    for (i=0;i<len1;i++) uj[i]=s1[i];       /* Első sztring */
    for (i=0;i<len2;i++) uj[len1+i]=s2[i];  /* A másodikat len1-től! */
    uj[len1+len2]='\0';  /* Lezárás */
    return uj;
}

int main() {
    char *elso="Hello ";
    char *masodik="world!";
    char *egyben;
    
    egyben = osszefuz(elso,masodik);
    if (egyben!=NULL) printf("%s", egyben);
    free(egyben);  /* Fontos hogy felszabadítsuk amit lefoglaltunk!!! */
    
    return 0;
}    

A fenti feladatból látszik, hogy minden paraméterként kapott sztringnek a művelet előtt meg kell határozni a hosszát. Ezt úgy lehet megkerülni, ha minden sztring mellé eltároljuk azt is. (Ilyenkor a lezáró nullára nincsen szükség, mert a hosszt ebből tudjuk.) Egy szöveghez így két adat tartozik: a hossz (egész szám) és a karaktereket tároló tömb (karakterre mutató pointer, hiszen dinamikus memóriáról van szó). A „helló, világ” szöveg például így lehet eltárolva:

Hozz létre egy új projektet. Definiálj DinSztring nevű struktúrát, amely egy szöveg adatait tárolja ilyen módon! Írj függvényeket:

• dinsztring_init(): paraméterként kap egy DinSztring-re mutató pointert és egy szokványos nullával lezárt C sztringet (karaktertömböt). Inicializálja a struktúrát úgy, hogy az a C sztring másolatát tárolja dinamikusan foglalt memóriaterületen!

  Mivel a másolat nem lesz nullával lezárt (és semelyik DinSztring-hez tartozó karaktertömb nem lesz az), ezért a string.h beépített függvények nem használhatóak.

  Ez lesz az egyetlen olyan függvény, amely inicializálatlan struktúrán dolgozik. Az összes többi már inicializált struktúrát kap majd, amelyet ez a függvény állított be!
• dinsztring_kiir(): paraméterként kap egy DinSztring-re mutató pointert, és képernyőre írja a tárolt szöveget.
• dinsztring_free(): paraméterként kap egy DinSztring pointert, és felszabadítja a hozzá tartozó dinamikus memóriaterületet.

Ha helyesek a függvényeid, az alábbi programnak működnie kell:

int main() {
   DinSztring hv;
   
   dinsztring_init(&hv, "hello, vilag");
   dinsztring_kiir(&hv);
   dinsztring_free(&hv);
   
   return 0;
}

/* Fejlécfájl */
#ifndef DINSZTRING_H
#define DINSZTRING_H

/* Dinamikus sztringet tároló struktúra */
typedef struct {
	int hossz; /* Hossz */
	char *p;   /* Pointer a karakterekre */
} DinSztring;

/* Inicializálás */
int dinsztring_init(DinSztring *ds,char *s);

/* Kiírás */
void dinsztring_kiir(DinSztring *ds);

/* Felszabadítás */
void dinsztring_free(DinSztring *ds);

/* Hozzáfűzés */
int dinsztring_hozzafuz(DinSztring *ds1, DinSztring *ds2);

/* Értékadás */
int dinsztring_ertekad(DinSztring *ds1, DinSztring *ds2);

/* Részsztring kivágása */
int dinsztring_resz(DinSztring *ds,int mettol,int meddig);

#endif

/* Függvények kidolgozása */
#include "labor10_dinsztring.h"

#include <stdlib.h>
#include <stdio.h>

/* Inicializálás */
int dinsztring_init(DinSztring *ds,char *s) {
	int len=0,i;
	while (s[len]!='\0') len++;              /* Kiszámoljuk s hosszát */
	ds->hossz=len;                          /* Ez lesz a hossz */
	ds->p=(char*)malloc(len*sizeof(char));  /* Helyfoglalás */
	if (ds->p==NULL) return 0;               /* Ha nem sikerül :( */
	for (i=0;i<len;i++) ds->p[i]=s[i];       /* Másolás */
	return 1;                               /* Siker :) */
}

/* Kiírás */
void dinsztring_kiir(DinSztring *ds) {
	int i;
	for (i=0;i<ds->hossz;i++)
		putchar(ds->p[i]);
}

/* Felszabadítás */
void dinsztring_free(DinSztring *ds) {
	free(ds->p);
}

/* Hozzáfűzés */
int dinsztring_hozzafuz(DinSztring *ds1, DinSztring *ds2) {
	int i;
	char *uj = (char*)malloc((ds1->hossz+ds2->hossz)*sizeof(char));  /* Helyfoglalás ideiglenes tömbbe */
	if (uj==NULL) return 0;  /* Ha nem sikerül :( */
	for (i=0;i<ds1->hossz;i++) uj[i]=ds1->p[i];  /* Régi rész másolása */
	for (i=0;i<ds2->hossz;i++) uj[ds1->hossz+i] = ds2->p[i];  /* Új rész másolása */
	free(ds1->p);  /* Régi sztring törlése!!! */
	ds1->p=uj;  /* Új pointer */
	ds1->hossz+=ds2->hossz;  /* Új hossz */
	return 1;  /* Siker :) */
}

/* Értékadás */
int dinsztring_ertekad(DinSztring *ds1, DinSztring *ds2) {
	int i;
	free(ds1->p);  /* Régi sztring törlése!!! */
	ds1->p=(char*)malloc(ds2->hossz*sizeof(char));  /* Helyfoglalás */
	if (ds1->p==NULL) return 0;  /* Ha nem sikerül :( */
	for (i=0;i<ds2->hossz;i++) ds1->p[i]=ds2->p[i];  /* Másolás */
	ds1->hossz=ds2->hossz;  /* Hossz felülírása */
	return 1;  /* Siker :) */
}

/* Részsztring kivágása */
int dinsztring_resz(DinSztring *ds,int mettol,int meddig) {
	int i;
	char *uj;
	if (mettol<0) mettol=0;  /* Határok ellenőrzése */
	if (meddig>ds->hossz) meddig = ds->hossz;
	uj=(char*)malloc((meddig-mettol)*sizeof(char));  /* Helyfoglalás ideiglenes tömbbe */
	if (uj==NULL) return 0;  /* Ha nem sikerül :( */
	for (i=mettol;i<meddig;i++) uj[i-mettol] = ds->p[i];  /* Megfelelő rész bemásolása az újba */
	free(ds->p);  /* Régi törlése!!! */
	ds->p=uj;  /* Új pointer */
	ds->hossz=meddig-mettol;  /* Hossz felülírása */
	return 1;  /* Siker :) */
}

#include <stdio.h>
#include "dinsztring.h"

int main() {
	DinSztring s1,s2,s3;
 
	dinsztring_init(&s1, "hello, ");
	dinsztring_init(&s2, "vilag");
	dinsztring_init(&s3, "ez felul lesz irva");
	dinsztring_hozzafuz(&s1,&s2);
	dinsztring_kiir(&s1); putchar('\n');
	dinsztring_ertekad(&s3,&s1);
	dinsztring_kiir(&s3); putchar('\n');
	dinsztring_resz(&s3,3,9);
	dinsztring_kiir(&s3); putchar('\n');
	dinsztring_free(&s1);
	dinsztring_free(&s2);
	return 0;
}

Az alábbiakban további függvényeket fogsz létrehozni. Érdemes a DinSztring típushoz tartozó függvényeket egy külön forrásmodulba tenni. Szedd szét ezért az eddig keletkezett programot három fájlra:

1. dinsztring.h, amelyben a típus megadása és a függvények deklarációi vannak. Ez tartalmazzon include őrszemet, azaz a többszörös beépítést megakadályozó makrót!
2. dinsztring.c, amelyben a függvények definíciói.
3. main.c, amelyben pedig a tesztelő programrészek lesznek (mint pl. a fenti main() függvény).

Forrásfájlt és fejlécfájlt a Code::Blocks-ban az alábbi lépésekkel tudsz hozzáadni a projekthez:

1. Válaszd ki aktívnak a projektedet, ha esetleg több projekt van nyitva. Ehhez a projekt nevére kattints a jobb gombbal, és a menüből Activate project.
2. A fenti menüből File, New, File pontot kell kiválasztani, a fájl típusának pedig a C/C++ source-t (forrásfájlhoz) vagy a C/C++ header-t. A nyelv legyen C. A következő ablakban be kell állítani a fájl elérési útját és nevét; legyen ez most dinsztring.c (dinsztring.h). Ugyanabba a mappába kell tenni, mint a projekt többi fájljának a helye. Jelezni kell azt is, hogy az ebből a forrásfájlból keletkező tárgykódot a futtatható .exe-hez kell majd linkelni, ezért be kell pipálni az „Add file to active project in build targets” résznél mindent:
   

   
3. Fejlécfájl esetén a Code::Blocks automatikusan létrehozza az ún. include guard-okat, amelyek a többszörös beillesztés ellen védenek. (Ettől függetlenül ilyet tudni kell írni a vizsgán. :D) A main.c-ben és a dinsztring.c-ben is be kell illeszteni ezt a fejlécfájlt; ezt tedd is meg:

   #include "dinsztring.h"

A többi feladatot már ennek megfelelően dolgozd ki!

Írj függvényt, amely egy meglévő DinSztring-hez fűz hozzá egy másikat. Figyelj arra, hogy ehhez a módosított DinSztring memóriaterületét újra kell foglalni (hiszen megnő a mérete). Példaprogram:

DinSztring s1, s2;

dinsztring_init(&s1, "hello, ");
dinsztring_init(&s2, "vilag");
dinsztring_hozzafuz(&s1, &s2);
dinsztring_kiir(&s1); // hello, vilag

Tedd hozzá a példához a felszabadításukat is!

Írj függvényt, amely egy paraméterként kapott DinSztring-et felülír, és abba egy másik paraméterként kapottat másol. A fenti példát folytatva:

dinsztring_ertekad(&s1, &s2);
dinsztring_kiir(&s1); // vilag

Írj függvényt, amely egy DinSztringet úgy módosít, hogy kivágja abból a paraméterként kapott két index közötti részt. Az első index az első karakterre mutasson, ami már kell, a második index pedig arra az első karakterre, ami már nem kell. Pl. így:

Ha az első index kisebb 0-nál, akkor vegye a függvény 0-nak azt; ha a második nagyobb a sztring hosszánál, akkor pedig azzal megegyezőnek.

Írj teszt programrészt is – próbáld ki a függvényt különböző bemenetekre!

Egyébként az első ami már igen, utolsó ami már nem konvenció éppen megegyezik azzal, amit a tömböknél is használunk: for i=0; i<méret stb., azaz i=0 már igen, i=méret már nem. Itt is az intervallum alulról zárt, felülről nyílt.

Csináld meg a fentit fordítva: az indexekkel jelzett részt a függvény vágja ki, a többi maradjon!

Írj függvényt, amely:

1. Nulla hosszúságúra állít egy DinSztring-et.
2. Hozzáfűz egy DinSztring-hez egy paraméterként kapott karaktert.

Írj ezek segítségével függvényt, amely tetszőlegesen hosszú szöveget (sort) képes beolvasni a szabványos bemenetről. A sor végét újsor karakter (\n) vagy fájlvége jel jelzi.

dinsztring_beolvas(&s);
puts("Ezt irtad be:");
dinsztring_kiir(&s);

Dinamikusan foglalt struktúra

A gyakorlat halmaz struktúrájához hasonlóan csináld meg azt, hogy maga a sztring struktúra is dinamikusan legyen foglalva, ne csak a tárolt adat. A létrehozó függvény itt is térjen vissza a lefoglalt struktúrára mutató pointerrel. Sztring használatához így nem struktúrát, hanem pointert kell majd definiálni:

DinSztring *sz;

sz=dinsztring_letrehoz("hello, vilag");
dinsztring_kiir(sz);
dinsztring_felszabadit(sz);

Természetesen a felszabadításnak ilyenkor a struktúrát és fel kell szabadítania majd.

Sztring létrehozása másolatként

Írj függvényt, amely paraméterként kap egy DinSztring-et, és létrehoz egy másikat, amely másolata annak. Ez is az újra mutató pointerrel térjen vissza, mint az előbbi. Mi a különbség eközött, és az értékadás között? Használható a fent megírt értékadás függvény a dinamikusan foglalt struktúrák esetében?

Beszúrás

Írj függvényt, amely egy DinSztring-be egy adott helyen beszúrja a másik tartalmát. Pl. a „hellóvilág” szövegbe az ötödik indexnél beszúrt sztring:

További, nagyobb feladat: a malloc()–free() hívások számának csökkentése

A fenti megoldásban elég gyakran hívódik a malloc() és free() függvény. Akár egy karakter hozzáfűzése miatt is másolódik a sztring. Alakítsd át a sztringkezelő függvényeket ezért úgy, hogy mindig egy kicsivel több memóriát foglaljanak, mint amennyi szükséges. Így pedig csak akkor foglaljanak újra, ha az is betelik. Ehhez vegyél fel a struktúrába egy új integert (kapacitás), amely a lefoglalt terület nagyságát tárolja. Természetesen méret≤kapacitás minden esetben, hiszen a tárolt szöveg nem lehet nagyobb a lefoglalt területnél. Az összes függvényt ehhez újra kell írni, hogy figyelembe vegyék a kapacitás adattagot is.

A függvények kidolgozása előtt találj ki egy stratégiát: hogyan viszonyuljon a kapacitás a szöveg hosszához. Vagyis ha növelni kell, akkor mennyivel nőjön a terület nagysága; ha pedig feleslegesen nagy a terület, akkor mennyivel csökkenjen. Itt kompromisszumra van szükség: ha nagy a szabadon tartott terület, akkor ritkán kell újrafoglalni, de sok az elpocsékolt memória. Ezt a stratégiát építsd be egy függvénybe (pl. olyan módon, hogy ez egy függvényként jelenik meg, amely megadja, mekkora a foglalt terület a sztring hossza szerint). Ez a függvény a sztring modulnak egy „láthatatlan” része legyen, a sztring modul használói elől legyen elrejtve!