Dynamická alokácia pamäti (riešené príklady)

Algoritmy a programovanie - zbierka úloh

---

Štruktúry

Rekurzia

Dynamická alokácia pamäti

Vyhľadávanie

Triedenie

Lineárny zoznam

Binárny strom

Numerické algoritmy

Filtrovanie textu

Zadanie úlohy

Zostavte program na filtrovanie textu - vyhľadávanie riadkov s hľadaným slovom. Program z klávesnice načíta hľadané slovo (nebude mať viac ako 100 znakov). Ďalej bude čítať z klávesnice riadky textu (reťazce ukončené ENTERom), až kým nenačíta prázdny riadok. Môžeme predpokladať, že žiaden riadok nebude dlhší ako 1000 znakov a že riadkov nebude viacej ako 1000.

Po načítaní prázdneho riadku program začne na obrazovku vypisovať výsledky (do tohoto okamihu NESMIE nič písať na obrazovku) v tvare:

V prvom riadku bude text "nachadza N:", kde N je počet riadkov, v ktorých sa nachádza hľadané slovo.

• Pod týmto riadkom budú vypísané všetky riadky, v ktorých sa nachádza hľadané slovo.
• Pod nimi bude prázdny riadok a ďalej riadok s textom "nenachadza N:", kde N je počet riadkov, v ktorých sa hľadané slovo nenachádza.
• Pod týmto riadkom budú vypísané všetky riadky, v ktorých sa nenachádza hľadané slovo.

Vzorový príklad

Príklad vstupu

slovo
Program bude hladat riadky s urcitym slovom.
V tomto riadku sa nenachadza.
A ani v tomto dalsom

Príklad výstupu:

nachadza 1:
Program bude hladat riadky s urcitym slovom.
nenachadza 2:
V tomto riadku sa nenachadza.
A ani v tomto dalsom.

Netreba zabúdať na to, že každý textový reťazec je ukončený znakom '\0', preto musíme rezervovať miesto aj preň.

Pre načítavanie hľadaného slova je vhodné použiť príkaz cez cin.getline, pretože cin>> akosi necháva ENTER za slovom nepovšimnutý a prvý cin.getline je potom prázdny.

Analýza riešenia

Keďže v tejto úlohe vopred nevieme, koľko riadkov bude obsahovať, je vhodné pole riadkov vytvoriť staticky – je ich, podľa zadania, nanajvýš 1000. Riadky samotné by však statickébyť nemali – je zbytočné mať maticu 1000×1001 znakov (čo predstavuje 1 MB dát), keď väčšina riadkov bude oveľa kratších. Riadok preto najskôr načítame do pomocnej premennej (textový reťazec dostatočnej dĺžky), „zmeriame“ jeho dĺžku a dynamicky vytvoríme riadok, do ktorého sa vojde (pozor, musíme dať dĺžku o jedno väčšiu).

Úlohu je možné riešiť použitím jedného poľa riadkov, no potom je problém s určením, v ktorom riadku sa hľadané slovo nachádza a v ktorom nie – dá sa to riešiť dvojako:

1. hneď pri čítaní vstupu budeme počítať riadky s hľadaným slovom a riadky bez neho, aby sme toto mohli vopred vypísať, potom druhýkrát musíme prechádzať poľom a vypisovať riadky, v ktorých sa hľadané slovo nachádza a nakoniec tretíkrát ním prechádzať a opäť hľadať riadky, v ktorom sa slovo nenachádza – toto riešenie nie je veľmi efektívne, keďže 3-krát hľadáme to isté (a hľadanie slova v reťazci je relatívne náročná operácia),
2. do pomocného poľa si budeme hneď pri čítaní vstupu zapisovať, či v danom riadku je alebo nie je hľadané slovo (hodnotou 1 alebo 0) a zároveň ich počítať zvlášť do počítadiel – pri vypisovaní stačí pozerať do tohto poľa a netreba znovu hľadať slovo v reťazcoch.

Praktickejšie však bude ukladať si riadky do dvoch polí – zvlášť tie, v ktorých sa hľadané slovo nachádza a zvlášť tie, kde nie. Keďže ale nevieme, koľko ktorých je, musíme počítať s najhoršou možnosťou pre obe polia – že riadkov bude plný počet (1000). Či sa hľadané slovo v riadku nachádza, nám pomôže zistiť funkcia strstr, na kopírovanie textu použijeme funkciu strcpy. V žiadnom prípade nemôžeme použiť len jednoduché priradenie, lebo by sa skopíroval len ukazovateľ na reťazec a nie reťazec samotný!. Keď už dynamicky vytvorené reťazce nepotrebujeme, je vhodné ich zmazať – po skončení programu sa síce vymažú automaticky, no je dobré zvyknúť si "upratať po sebe".

Riešenie v jazyku C

#include <iostream.h>
#include <string.h>
#include <conio.h>
int main()
{
   char text[1001], hladane[101], *najdene[1000], *nenajdene[1000];
   int pocet_najdenych = 0, pocet_nenajdenych = 0;
   cin.getline(hladane, 100);
   cin.getline(text, 1000);
   int dlzka = strlen(text);
   while (dlzka)
   {
      if (strstr(text, hladane)) // nachadza sa
      {
         najdene[pocet_najdenych] = new char[dlzka + 1];
         strcpy(najdene[pocet_najdenych], text);
         pocet_najdenych++;
      }
      else // nenachadza sa
      {
         nenajdene[pocet_nenajdenych] = new char[dlzka + 1];
         strcpy(nenajdene[pocet_nenajdenych], text);
         pocet_nenajdenych++;
      }
      cin.getline(text, 1000);
      dlzka = strlen(text);
   }
   int i;
   cout << "nachadza " << pocet_najdenych << ":\n";
   for (i = 0; i < pocet_najdenych; i++)
   {
      cout << najdene[i] << endl;
      delete[] najdene[i];
   }
   cout << "\nnenachadza " << pocet_nenajdenych << ":\n";
   for (i = 0; i < pocet_nenajdenych; i++)
   {
      cout << nenajdene[i] << endl;
      delete[] nenajdene[i];
   }
   getch();
}