Strona główna » Kursy » Zadania » Napisy zestaw 6B/2014
 

Napisy zestaw 6B/2014

Zadanie

Oryginalna treść zadania

Rozwiązanie

Omówienie podpunktu 1 - podziel()

Przed omówieniem podpunktu warto przypomnieć sobie, że napis to lista liczb, które na koću ma znak specjalny \0.

Przyjrzyjmy się argumentom funkcji. Otrzymujemy napis s i znak c. Mamy zwrócić nowy dynamicznie alokowany napis. Czyli nie wolno nam modyfikować napisu wejściowego pod żadnym pozorem. Przed przejściem dalej ustalmy nagłówek funkcji:

  1. char* podziel(char* s, char c){

Przyjmijmy, że znak c występuje na pozycji 0. Przechowajmy to w zmiennej pozycja. Następnie sprawdźmy znak po znaku napis. Jeśli natrafimy na sprawdzanej pozycji znak c to zapisujemy w zmiennej pozycja nową pozycje. Kiedy natrafimy na znak końca linii czyli znak specjalny \0. Kod realizujący tę część:

  1.   int pozycja = 0, i = 0;
  2.   while(s[i]!='\0'){
  3.     if(s[i]==c)
  4.       pozycja = i;
  5.     i++;
  6.   }

W tym momencie zmienna pozycja + 1 przechowuje długość napisu, który mamy przepisać. Warto zastanowić się nad przypadkiem kiedy znaku nie znajdziemy w napisie. Wtedy pozycja będzie równa 0.

Kolejna część rozwiązania polega na deklaracji nowej listy i przepisanie części napisu. Warto pamiętać, że długość tekstu do przepisania wynosi pozycja + 1, ponieważ ostatni znak musi być znakiem \0.

  1.   char* s2 = new char[pozycja+1];
  2.   for(int i = 0; i < pozycja; i++)
  3.     s2[i]=s[i];
  4.   s2[pozycja]='\0';
  5.   return s2;
  6. }

Omówienie podpunktu 2 - czyUnikalne()

Odwołując się do wskazówki w zadaniu wykorzystamy funkcje strcmp(), która porównuje dwa napisy. Zgodnie z jej deklaracją:

  1. int strcmp(const char *s1, const char *s2)

podajemy jej dwa napisy, które mamy zagwarantowane, że nie zostaną zmienione. Funkcje znajdziemy w bibliotece string.h. Funkcja zwraca liczbę mniejszą od zera, gdy napis_1 < napis_2, 0 gdy napis_1 jest taki sam jak napis_2 oraz liczbę większą od zera gdy napis_1 > napis_2.

Zacznijmy od nagłówka. Funkcja ma na podstawie podanej listy napisów i jej rozmiaru zwrócić wartość logiczną:

  1. bool czyPosortowane(char** t, int n){

Wyrazy są w jakiś sposób ustawione. Naszym zadaniem jest sprawdzić czy są ustawione niemalejąco według porządku leksykograficznego. Warto wykorzystać tu z funkcji strcmp, która zwróci wartość dodatnią, gdy taki porządek będzie zachodził. Żeby sprawdzić czy t napisów jest unikalnych wykonamy tylko t - 1 porównań. Zadanie to realizuje poniższy kod:

  1.   for(int i = 1; i < n; i++)
  2.     if(strcmp(t[i-1], t[i]) > 0)
  3.       return false;
  4.   return true;
  5. }

Omówienie podpunktu 3 - Testy

Przykładowo funkcja main:

  1. int main (){
  2.   // Test funkcji podziel
  3.   char* s = new char[5];
  4.   s[0]='0';s[1]='1';s[2]='2';s[3]='1';s[4]='\0';
  5.   char* w = podziel(s,'1');
  6.   cout << s << endl << w << endl;
  7.   // Test funkcji czyPosortowane
  8.   int n = 4;
  9.   char* t_0 = new char[4];
  10.   t_0[0]='a';t_0[1]='l';t_0[2]='a';t_0[3]='\0';
  11.   char* t_1 = new char[6];
  12.   t_1[0]='a';t_1[1]='l';t_1[2]='a';t_1[3]='a';t_1[4]='a';t_1[5]='\0';
  13.   char* t_2 = new char[5];
  14.   t_2[0]='b';t_2[1]='a';t_2[2]='l';t_2[3]='a';t_2[4]='\0';
  15.   char* t_3 = new char[6];
  16.   t_3[0]='z';t_3[1]='e';t_3[2]='b';t_3[3]='r';t_3[4]='a';t_3[5]='\0';
  17.   char** t = new char* [4];
  18.   t[0]=t_0;t[1]=t_1;t[2]=t_2;t[3]=t_3;
  19.   cout << (czyPosortowane(t,n) ? "TAK" : "NIE");
  20.   system("pause");
  21.   return 0;
  22. }