Projekty z programování na FIT VUT: Projekt 1 — Jednoduchá komprimace/dekomprimace

Programování v jazyce C mě baví. C je skvělý jazyk (obsahuje všechna písmena abecedy až do C 😉 ). Při studiu na fakultě informatiky se s Cčkem setkávám poměrně zblízka a důvěrně. Důvodem je předmět IZP — Základy programování, který je zaměřen na jazyk C. Navzdory slovu „základy“ ve svém jméně se předmět rozhodně nezabývá (jen) základy. V IZP je nutné pro zápočet vypracovat celkem čtyři projekty. Pokusím se zde ukázat, jak dle IZP vypadají projekty pro ty, kteří se s programováním setkali poprvé v životě.

V tomto článku poodhalím projekt první — jednoduchou komprimaci a dekompresi.

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.

Projekt 1 — Jednoduchá komprimace/dekomprimace
Zadání projektu bylo poměrně jednoduché — bylo nutné vytvořit algoritmus, který komprimuje data na standardním vstupu, případně je dekomprimuje. De/Komprimace mohla probíhat po znacích, nebo po N-tici znaků. Znakem se rozumí vše, krom čísla. Komprimace i dekomprimace bude řízena celočíselným parametrem N, jehož hodnota bude větší nebo rovna 1. Při komprimaci bude program hledat ve vstupním textu opakující se bloky znaků délky N. Dále program při nalezení minimálně 2 a maximálně 9 shodných bloků délky N za sebou zapíše tuto posloupnost na výstup jako číslo udávající počet opakování následované tímto blokem písmen délky N.

Nebudu psát a ukazovat main(), ale až tři podstatné funkce: compresones(), decompres() a compresmore(), které komprimují po znacích, dekomprimují a komprimují N-tice znaků.

compresones(void)

Poměrně jednoduchá záležitost. Algoritmus prochází vstup, srovná jej s předešlým znakem. Pokud je předešlý znak shodný s právě načteným, zvýší se počítadlo. Pokud jsou rozdílné, vypíše se počítadlo (v případě, že je různé od jedné) a vysází se znak v bufferu, se kterým se vše srovnává.

int compresones (void)
{
 int oldznak = (getc(stdin));
 int pocet=1;
 int znak= getc(stdin);

do
{
	if (isdigit(znak))
	{
		fprintf(stderr,"Chyba vstupu\n");
		return EXIT_FAILURE;
	}
	if (znak == oldznak)
	{
		pocet++;
		if ( pocet == 10 )
		{
			putc('9',stdout);
			putc(oldznak,stdout);
			pocet = 1;
		}
	}
	else
	{
		if (pocet > 1)
		{
			int printnum = pocet + '0';
			putc(printnum,stdout);
			putc(oldznak,stdout);
			pocet = 1;
		}
		else
		{
			putc(oldznak,stdout);
			pocet = 1;

		}
	}
	oldznak = znak;
} while ((znak = getc(stdin)) != EOF);

return (EXIT_SUCCESS);
}

decompres(int N)

Dekomprese je velice jednoduchý algoritmus — prochází vstup a pokud narazí na číslo, tak číslo-krát vypíše N-tici následujících znaků.

int decompres (int N)
{

char znak;
char opakuj[N];

while ((znak = getc (stdin)) != EOF)
{
	if (isdigit (znak))
	{
		int repeat = ((int) znak) - '0';
		for (int i = 0; i < N; i++)
		{
			opakuj[i] = getc (stdin);
		}
		for (int i = 1; i <= repeat; i++)
		{
			for (int j = 0; j < N; j++)
			{
				putc (opakuj[j], stdout);
			}
		}
	}
	else
	{
		fputc (znak, stdout);
	}
}//konec while cyklu - tohle dělej do zblbnutí
  return (EXIT_SUCCESS);
}

compresmore(int N)

Komprimace, pokud je N>1, je složitější záležitost. Nedělal jsem de fakto žádnou dekompozici — což mě stálo půl bodu, ale co se dá dělat.

Princip je stejný jako v případě, že N je jedna, ovšem buffer, který se srovnává, je jednorozměrné pole velikosti N.

Na začátku algoritmu se toto jednorozměrné pole naplní znaky, dále se znaky naplní i testovací pole.

Poté se spustí smyčka postupně srovnávají obě pole. Pokud jsou obě pole shodná, zvýší se počitadlo. Pokud jsou rozdílná a počitadlo je větší jak jedna, vypíše se referenční pole a znaky z testovacího se načtou do referenčního. Pokud jsou pole rozdílná, vytiskne se první znak referenčního pole, znaky se posunou o jeden. Poslední znak v referenčním poli se vyplní prvním znakem testovacího. To se také posune o jeden — a poslední znak se načte ze vstupu. Toto se provádí cyklem while, dokud se nedostane algoritmus na konec souboru.

Je-li soubor u konce, překontrolují se obě načtená pole, jestli nejsou shodná, případně se vypíší dle pravidel popsaných výše.

int compresmore (int N)
{

int refer[N];
int test[N];
int tmpchar;

for (int i=0; i < N; i++)
{
	refer[i] = getc(stdin);
	if (refer[i] == EOF)
		{return EXIT_SUCCESS;}
	if ( isdigit(refer[i]))
		{
			fprintf(stderr,"Chyba vstupu\n");
			return EXIT_FAILURE;
		}
}

for ( int i=0; i < (N); i++)
  {
	test[i] = getc(stdin);
	if (refer[i] == EOF)
		{return EXIT_FAILURE;}
  }

int stejny=0;
int komprim = 1;
int posun = N;

do {
	for (int i=0; i < N; i++ )
	{
		if ( refer[i] == test[i] )
		{
			stejny++;
		}
		else
		{
			stejny = 0;
			break;
		}
	}

	if (stejny == N )
	{
		komprim++;
		posun = N;
		stejny=0;

		if (komprim == 9)
		{
			putc('9',stdout);
			for (int j=0; j < N; j++)
			{
				putc(test[j],stdout);
			}
			komprim = 0;
		}

	}
	else
	{
		if ( ( stejny == 0 ) && ( ( komprim > 1 ) ))
		{
			if (komprim > 1)
			{
				komprim = komprim + '0';
				putc(komprim,stdout);
			}

			for (int j=0; j < N; j++)
			{
				putc(refer[j],stdout);
			}
			posun = N;
			komprim = 1;
		}
		else
		{
			putc(refer[0],stdout);
			komprim = 1;
			posun = 1;
		}
	}
	if (posun == N)
	{
		for (int i = 0; i < N ; i++)
		{
			refer[i] = test[i];
		}

		for (int i = 0; i < N; i++)
		{
		if ((tmpchar = getc(stdin)) != EOF )
			{
				if (isdigit(tmpchar))
				{
					fprintf(stderr,"Chyba vstupu\n");
					return EXIT_FAILURE;
				}
				else
				{
					test[i] = tmpchar;
				}
			}
			else
			{
				if (isdigit(tmpchar))
				{
					fprintf(stderr,"Chyba vstupu\n");
					return EXIT_FAILURE;
				}
				else
				{
					for (int j = i; j < N; j++)
					{
						test[j] = EOF;
					}
					break;
				}
			}
		}
	}

	if (posun == 1)
	{
		for (int i = 0; i < (N-1); i++)
		{
			refer[i] = refer[i+1];
		}

		refer[N-1] = test[0];
		for (int i = 0; i < (N); i++)
		{
			test[i] = test[i+1];
		}
		test[N-1] = getc(stdin);
		if (isdigit(test[N-1]))
		{
			fprintf(stderr,"Chyba vstupu\n");
			return EXIT_FAILURE;
		}
	}
}
while( test[N-1] != EOF);
/** While smyčka výše pracuje, dokud není konec souboru a nebo dokud
 * není program ukončen s [Ctrl+D].
 */

/** Nyní vytiskneme zbývající znaky, které jsou v polích.
 */
if (komprim > 0)
{
	if (komprim > 1)
	{
		komprim = komprim + '0';
		putc(komprim,stdout);
	}
	for (int i = 0; i < N; i++ )
	{
		putc(refer[i],stdout);
	}
}

	stejny = 0;
	for (int i=0; i < (N-1); i++ )
	{
		if ( refer[i] == test[i] )
		{ stejny++; }
		else
		{
			stejny = 0;
			break;
		}
	}
	if (stejny == 0)
	{
		for (int i=0; i<N;i++)
		{ // sázej, dokud nebude test[i] == EOF
			if (test[i] == EOF)
				{break;}
			putc(test[i],stdout);
		}
	}

return (EXIT_SUCCESS);
}

Komplet zdrojáky jsou ke stažení z mého webu pod tímto odkazem. Zde na webu byly odstraněny všechny komentáře, naopak zdrojáky v archivu jsou komentovány poměrně bohatě. Překládejte prosím příkazem $make, který všechny záležitosti s překladem programu.

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

1 komentář u „Projekty z programování na FIT VUT: Projekt 1 — Jednoduchá komprimace/dekomprimace“

Napsat komentář

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