Projekty z programování na FIT VUT: Projekt 4 — České řazení

Řetězce jsou v jazyce C opravdu peklem. A stejně tak je i čeština (obecně) dost velké zlo. Čtvrtý projekt z IZP byl zaměřen právě na jazyk C ve spojení s jazykem Českým a ještě hůř, na řazení dle české normy. Hlavní váha projektu 4 byla v naprogramování funkce int strcmp(char *s1, char *s2), která srovná dva vstupní řetězce s1 a s2, přičemž návratová hodnota je rovna nule, pokud jsou oba řetězce shodné, návratová hodnota je kladná, pokud je řetěz s1 za řetězem s2. Pokud je s1 před s2, poté je návratová hodnota záporná. Druhá váha projektu spočívala na řadícím algoritmu — tedy setřídí pole dle kritérií (v tomto případě se jednalo právě o podmínku českého řazení — s užitím mého strcmp() 🙂

Dobrá rada ze začátku zdarma: NEOPISUJTE!!! Studujete-li FIT na VUT v Brně a řešíte projekt, neopisujte můj kód. Ačkoli je program licencován GPLv3+, tak nedoporučuji opisovat. Prvně — já již projekt odevzdal a pokud vím, tak ten FIŤácký soft pro odhalování plagiátů má ten „můj“ vzorek již uložen. A dále — pokud sami nebudete programovat, nenaučíte se to.

České porovnání stringů — trocha teorie

Jak již bylo napsáno v perexu, hlavní váha projektu spočívala v naprogramování českého srovnávacího algoritmu. České porovnání (řazení) je dost nepříjemné. Problém je, že norma je definována dosti nešťastně — dvou-průchodově navržené a řešené. V prvním průchodě jsou považovány všechna česká písmena (s výjimkou ř a š) shodné s neháčkovanými/nečárkovanými základy písmene — tedy  například e,é,ě,E,É,Ě mají stejnou řadící váhu, stejně tak i velká a malá písmena. Háčky a čárky (případně u Slováků vokáň (ať je to cokoli)) mají až sekundární řadící prioritu, tedy se k nim přihlédne až v případě, že první průchod nerozhodl.

Například tedy bude:

  • Lis
  • líska
  • Liška
  • list

Povšimněte si, že list je až za liškou (neboli že nerozhodlo s|š, ale až k|t

Aby toho nebylo málo, máme v Češtině ještě „ch“, které je psáno dvěmi znaky. Proto se při znaku c|C musí vždy kontrolovat, není-li následováno h|H — tedy CH a dle toho se případně zařídit.

Jak na algorismus

Jak je asi patrné z výše napsaného, nepomůže klasická strcmp() — funkce pouze porovnává hodnoty znaků v řetězci. Nedíval jsem se strcmp do střev, ale základ té funkce bude:

int porovnej_znak(char prvni_znak, char druhy_znak)
{
	int stav = 0;

	if ((int) prvni_znak > (int) druhy_znak ) stav= 1;
	else if ((int) prvni_znak == (int) druhy_znak) stav= 0;
	else if ((int) prvni_znak < (int) druhy_znak) stav= -1;
	return stav;
}

int porovnej_retezce(char *s1, char *s2)
{
	int prvni_lng = strlen(s1);
	int druhy_lng = strlen(s2);
	int kratsi;
	kratsi = ( prvni_lng >= druhy_lng ) ? druhy_lng : prvni_lng;

	for (int prvek=0; prvek < kratsi; prvek++)
	{
		rozhodnuto = porovnej_znak(s1[znak],s2[znak]);

		if (rozhodnuto != 0) return rozhodnuto;
	}

	if (prvni_lng == druhy_lng) return 0;
	else if (prvni_lng > druhy_lng) return 1;
	else return -1;
}

Prvně tedy zjistíme délku obou řetězců a určíme, který je kratší. Poté porovnáváme postupně jednotlivé znaky, dokud jsou stejné. V případě, že se liší, vrátí +1 nebo -1. Pokud dojde až na konec kratšího řetězce, tak se dle délky těch dvou řetězců rozhodne, jestli vrátí nulu — jsou oba stejné, +1, (pokud první je delší než druhý) a nebo -1.

Ačkoli se to nemusí na první pohled zdát, ve funkci porovnej_retezce máme základ pro český řadící algoritmus. Pro začátek uděláme jednoprůchodový, který nebude podporovat sice češtinu plně, ale bude zanedbávat velká a malá písmena. Napíšeme funkci int pretupuj(char znak) , která načte znak a v návratové hodnotě vrátí jeho novou hodnotu.

int pretypuj(char znak)
{
	switch( (unsigned int) znak)
	{
		//mezera
		case ' ': novy_znak=0; break;

		case 'a': novy_znak = 1; break;
		case 'A': novy_znak = 1; break;

		case 'b': novy_znak = 2; break;
		case 'B': novy_znak = 2; break;

		case 'c': novy_znak = 3; break;
		case 'C': novy_znak = 3; break;

		case 'd': novy_znak = 5; break;
		case 'D': novy_znak = 5; break;

		case 'e': novy_znak = 6; break;
		case 'E': novy_znak = 6; break;

		case 'f': novy_znak = 7; break;
		case 'F': novy_znak = 7; break;

		case 'g': novy_znak = 8; break;
		case 'G': novy_znak = 8; break;

		case 'h': novy_znak = 9; break;
		case 'H': novy_znak = 9; break;

		//tady je ch,CH, Ch,cH... s cislem 10
		case '?': novy_znak = 10; break;

		case 'i': novy_znak = 11; break;
		case 'I': novy_znak = 11; break;

		//takto bude pro vsechna ostatní pismena
		defalt: novy_znak = 33
	}
	return novy_znak;
}

A v routině porovnej_retezce() bude pouze několik změn, které vytvoří dvě pole typu int jménem s1int, s2int o velikostech prvni_lng, resp. druhy_lng a budou dvě smyčky:

for (int i = 0; i < prvni_lng; i++)
{
	s1int = pretypuj(s1[i];
}

for (int i = 0; i < druhy_lng; i++)
{
	s2int = pretypuj(s2[i];
}

A u smyčky rozhodnuto nebude na vstupu funkce porovnej_znak() znaky pole s1,s2, ale s1int a s2int. Také se změní přetypování ve funkci porovnej_znak, které samozřejmě zmizí. Přidání českých znaků do přetypovávací funkce není zas až tak náročné, stačí dopsat ty správné konstanty a dát jim vhodné „nové“ hodnoty.

Jak na písmeno ‚ch‘

Ch je mrcha — zabírá 2 znaky. Proto je třeba toto pořešit jinak, než vlastní přetypovávací funkcí. Jistě jste si všimli, že v přetypovávací funkci je místo CH napsán otazník. A to je právě hlavní myšlenka. Na vstup na místě, kde by bylo očekáváno CH, vložíte JINOU konstantu — nejlépe takovou, aby nedělala problém jiným znakům. Já zvolil otazník, ačkoli místo toho jsem mohl zvolit něco jiného, lepšího (0x00 mi nyní oproti otazníku připadá ideální, ale co se dá dělat).

int prvek = 0;
for (int znak = 0; znak< prvni_lng; znak++)
{
	if ( s1[znak] == 'c' || s1[znak] == 'C')
	{
		if ( s1[znak+1] == 'h' || s1[znak+1] == 'H')
		{
			znak++;
			s[znak] = '?';
		}
	}
	s1int[prvek++] = pretypuj(s[znak],params);
}

Porovnání dvou českých řetězů

CH jsme vyřešili, máme funkci pro přetypování, takže nyní celou funkci, ovšem pouze krátce:

int porovnej_retez(char *s1, char *s2)
{
	int prvni_lng = strlen(s1);
	int druhy_lng = strlen(s2);
	int kratsi;
	kratsi = ( prvni_lng >= druhy_lng ) ? druhy_lng : prvni_lng;

	pretypuj_poprve(s1);
	pretypuj_poprve(s2);

	for (int prvek=0; prvek < kratsi; prvek++)
	{
		rozhodnuto = porovnej_znak(s1int[znak],s2int[znak]);

		if (rozhodnuto != 0) return rozhodnuto;
	}

	pretypuj_podruhe(s1);
	pretypuj_podruhe(s2);

	for (int prvek=0; prvek < kratsi; prvek++)
	{
		rozhodnuto = porovnej_znak(s1int[znak],s2int[znak]);

		if (rozhodnuto != 0) return rozhodnuto;
	}
	if (prvni_lng == druhy_lng) return 0;
	else if (prvni_lng > druhy_lng) return 1;
	else return -1;
}

kde funkce pretypuj_poprve() a pretypuj_podruhe() přetypovávají v prvním průchodu diakritická znaménka na váhu písmene bez diaktiritiky, po druhém průchodu ovšem již těmto dávají jinou váhu.

Bohužel můj algoritmus má jednu chybu — pokud je v prvním znaku diakritika, tak řetězec blbě zařadí:

Ďas
Rezac
Safar
Řezáč
Řezač
Zavrek

seřadí:

Rezac
Safar
Zavrek
Ďas
Řezač
Řezáč

Je vidět, že problém je pouze u prvních písmen. Zbytek (Řezáč|Řezač) seřadí správně, ale umístí je na špatné místo. Nechápu proč. Fakt jsem na to nepřišel…

Seřazení pole

Zbytek projektu není zase až tak zajímavý. Řadící algoritmus jsem použil include sort, který porovnává pole řetězců. Já mu předávám celou strukturu, ale de fakto mu stačí na vstupu 2 informace: ukazatel na pole, které má seřadit, a počet řádků v poli. Výsledek bude:

void serad_ins(char *serazene_slupce,int pocet_serazenych_radku)
{
	char index[MAX_CHARS];
	int i, j;
	for (i = 1; i < pocet_serazenych_radku+1; ++i)
	{
		strcpy(index,serazene_slupce[i]);
		for (j = i; j > 0 && porovnej_data(serazene_slupce[j-1],index) > 0; j--)
			strcpy(serazene_slupce[j],serazene_slupce[j-1]);
		strcpy(serazene_slupce[j],index);
	}
}

To je prosím celý zázrak. Algoritmus má jednu nevýhodu — tou je kvadratická náročnost na obecně neseřazeném poli. Pokud ovšem máme téměř seřazené pole, je náročnost pouze lineární — čehož s úspěchem využívám a pole (rychle) seřadím při každém přidání nové položky. Dále je algoritmus stabilní (nemá problém se dvěma shodnými řetězci) a ultra-jednoduchý — jako ovšem většina chytrých věcí (ovšem ne všechny).

A to je vše. Ostatní byly již jen implementační drobnosti — unique-sort, který vynechává duplicity, podpora krom Latin2 i CP1250 byla jen podmínka v přetypování a podobně. To vše jsou jen drobnosti. Bohužel chyba se špatným zařazením prvních písmen je poměrně kritická. Ale co už, nepřišel jsem na to.

V případě, že byste rádi použili některou část, dodržte prosím licenci GPL verze 3 a nebo pozdější.

Jako obvykle jsou ke stažení zdrojové kódy, tentokrát takřka bez komentářů… Začínám jimi šetřit 😀 Pořád platí varování ohledně plagiátorství ze začátku článku!

Napsat komentář

Vaše emailová adresa nebude zveřejněna. Vyžadované informace jsou označeny *