Sprawdź się
Napisz program, który dla ciągu znaków wiadomosc
zliczy wystąpienia każdego znaku z tablicy ASCII, a następnie wyświetli, ile razy dany znak pojawił się w tym ciągu znaków. Program powinien pomijać te znaki, które nie pojawiły się ani razu. Swój program przetestuj dla podanego ciągu znaków:
wiadomosc = "Ardua prima via est"
Specyfikacja problemu:
Dane:
wiadomosc
– łańcuch znaków, w którym należy zliczyć wystąpienia znaków
Wynik:
liczba odpowiadająca każdemu znakowi z tablicy ASCII występującemu w łańcuchu znaków
wiadomosc
oraz liczba wskazująca, ile razy dany znak pojawił się w łańcuchu; informacja o każdym znaku powinna znaleźć się w oddzielnej linijce, a pomiędzy obiema liczbami powinien znaleźć się dwukropek
Przykładowe wyjście:
32:3
65:1
97:3
100:1
101:1
105:2
109:1
112:1
114:2
115:1
116:1
117:1
118:1
Przykładowe rozwiązanie zadania:
#include <iostream>
#include <string>
using namespace std;
void zlicz_znaki(string wiadomosc, int* tablica_zliczen) {
for (int i = 0; i <= 255; ++i) {
tablica_zliczen[i] = 0;
}
for (int i = 0; i < wiadomosc.length(); i++) {
tablica_zliczen[wiadomosc[i]]++;
}
}
int main() {
string wiadomosc = "Ardua prima via est";
int tablica_zliczen[256];
zlicz_znaki(wiadomosc, tablica_zliczen);
for (int i = 0; i <= 255; i++) {
if (tablica_zliczen[i] > 0) {
cout << i << ":" << tablica_zliczen[i] << endl;
}
}
return 0;
}
Napisz program, który zakoduje ciąg znaków wiadomosc
, a następnie wypisze zakodowany łańcuch znaków na standardowe wyjście. Ważne, by wykorzystana została książka kodowa. Przetestuj swój program dla podanego ciągu znaków:
wiadomosc = "Jestem przykladowym tekstem i nalezy mnie zakodowac"
Specyfikacja problemu:
Dane:
wiadomosc
– łańcuch znakówksiazka_kodowa
– tablica zawierająca strukturykod
z kodowanym znakiem i odpowiadającym mu słowem kodowymDLUGOSC_KSIAZKI_KODOWEJ
– stała całkowita zawarta w programie; długość tablicyksiazka_kodowa
Wynik:
zakodowana_wiadomosc
– zakodowany łańcuch znaków
Przykładowe rozwiązanie zadania:
#include <iostream>
#include <string>
using namespace std;
struct kod {
char znak;
string slowo_kodowe;
};
void zainicjalizuj_ksiazke_kodowa(kod* ksiazka_kodowa) {
ksiazka_kodowa[0].znak = 'z';
ksiazka_kodowa[0].slowo_kodowe = "0000";
ksiazka_kodowa[1].znak = 'y';
ksiazka_kodowa[1].slowo_kodowe = "0001";
ksiazka_kodowa[2].znak = 't';
ksiazka_kodowa[2].slowo_kodowe = "0010";
ksiazka_kodowa[3].znak = 'o';
ksiazka_kodowa[3].slowo_kodowe = "0011";
ksiazka_kodowa[4].znak = 'w';
ksiazka_kodowa[4].slowo_kodowe = "01000";
ksiazka_kodowa[5].znak = 's';
ksiazka_kodowa[5].slowo_kodowe = "01001";
ksiazka_kodowa[6].znak = 'r';
ksiazka_kodowa[6].slowo_kodowe = "010100";
ksiazka_kodowa[7].znak = 'p';
ksiazka_kodowa[7].slowo_kodowe = "010101";
ksiazka_kodowa[8].znak = 'n';
ksiazka_kodowa[8].slowo_kodowe = "01011";
ksiazka_kodowa[9].znak = 'm';
ksiazka_kodowa[9].slowo_kodowe = "0110";
ksiazka_kodowa[10].znak = 'l';
ksiazka_kodowa[10].slowo_kodowe = "01110";
ksiazka_kodowa[11].znak = 'i';
ksiazka_kodowa[11].slowo_kodowe = "01111";
ksiazka_kodowa[12].znak = 'k';
ksiazka_kodowa[12].slowo_kodowe = "100";
ksiazka_kodowa[13].znak = 'd';
ksiazka_kodowa[13].slowo_kodowe = "1010";
ksiazka_kodowa[14].znak = 'c';
ksiazka_kodowa[14].slowo_kodowe = "10110";
ksiazka_kodowa[15].znak = 'J';
ksiazka_kodowa[15].slowo_kodowe = "10111";
ksiazka_kodowa[16].znak = 'e';
ksiazka_kodowa[16].slowo_kodowe = "110";
ksiazka_kodowa[17].znak = 'a';
ksiazka_kodowa[17].slowo_kodowe = "1110";
ksiazka_kodowa[18].znak = ' ';
ksiazka_kodowa[18].slowo_kodowe = "1111";
}
string znajdz_slowo_kodowe(char znak, kod* ksiazka_kodowa, int dlugosc_ksiazki_kodowej) {
for (int i = 0; i < dlugosc_ksiazki_kodowej; ++i) {
if (ksiazka_kodowa[i].znak == znak) {
return ksiazka_kodowa[i].slowo_kodowe;
}
}
}
string zakoduj_wiadomosc(string wiadomosc, kod* ksiazka_kodowa, int dlugosc_ksiazki_kodowej) {
string zakodowana_wiadomosc = "";
for (int i = 0; i < wiadomosc.length(); ++i) {
zakodowana_wiadomosc += znajdz_slowo_kodowe(wiadomosc[i], ksiazka_kodowa, dlugosc_ksiazki_kodowej);
}
return zakodowana_wiadomosc;
}
int main() {
string wiadomosc = "Jestem przykladowym tekstem i nalezy mnie zakodowac";
const int DLUGOSC_KSIAZKI_KODOWEJ = 19;
kod ksiazka_kodowa[DLUGOSC_KSIAZKI_KODOWEJ];
zainicjalizuj_ksiazke_kodowa(ksiazka_kodowa);
string zakodowanaWiadomosc = zakoduj_wiadomosc(wiadomosc, ksiazka_kodowa, DLUGOSC_KSIAZKI_KODOWEJ);
cout << zakodowanaWiadomosc << endl;
return 0;
}
Napisz program, który korzystając z podanej książki kodowej, odkoduje ciąg znaków wiadomosc_zakodowana
zakodowany za pomocą algorytmu Huffmana. W celu zdekodowania wiadomości możesz utworzyć drzewo kodowe na podstawie książki lub wykorzystać fakt, że kodowanie Huffmana jest kodowaniem prefiksowym. Zdekodowaną wiadomość wypisz na standardowe wyjście. Swój program przetestuj dla ciągu znaków:
wiadomosc_zakodowana = "1110101001001011011001111010011010010000000010011011111101110001100100000011001111010110100110010010110110011110111011111000001100010010111010111110110011110000110010100110110110001100100011010111000001"
Specyfikacja problemu:
Dane:
wiadomosc_zakodowana
– łańcuch znaków (zer i jedynek) do odkodowaniaksiazka_kodowa
– tablica zawierająca strukturykod
z kodowanym znakiem i odpowiadającym mu słowem kodowymDLUGOSC_KSIAZKI_KODOWEJ
– stała całkowita zawarta w programie; długość tablicyksiazka_kodowa
Wynik:
wiadomosc_odkodowana
– odkodowany łańcuch znaków
Przykładowe rozwiązanie zadania:
#include <iostream>
#include <string>
using namespace std;
struct kod {
char znak;
string slowo_kodowe;
};
void zainicjalizuj_ksiazke_kodowa(kod* ksiazka_kodowa) {
ksiazka_kodowa[0].znak = 'z';
ksiazka_kodowa[0].slowo_kodowe = "0000";
ksiazka_kodowa[1].znak = 'y';
ksiazka_kodowa[1].slowo_kodowe = "0001";
ksiazka_kodowa[2].znak = 's';
ksiazka_kodowa[2].slowo_kodowe = "0010";
ksiazka_kodowa[3].znak = 'k';
ksiazka_kodowa[3].slowo_kodowe = "0011";
ksiazka_kodowa[4].znak = 'w';
ksiazka_kodowa[4].slowo_kodowe = "01000";
ksiazka_kodowa[5].znak = 'r';
ksiazka_kodowa[5].slowo_kodowe = "010010";
ksiazka_kodowa[6].znak = 'p';
ksiazka_kodowa[6].slowo_kodowe = "010011";
ksiazka_kodowa[7].znak = 't';
ksiazka_kodowa[7].slowo_kodowe = "0101";
ksiazka_kodowa[8].znak = 'o';
ksiazka_kodowa[8].slowo_kodowe = "0110";
ksiazka_kodowa[9].znak = 'n';
ksiazka_kodowa[9].slowo_kodowe = "011100";
ksiazka_kodowa[10].znak = 'i';
ksiazka_kodowa[10].slowo_kodowe = "011101";
ksiazka_kodowa[11].znak = 'l';
ksiazka_kodowa[11].slowo_kodowe = "01111";
ksiazka_kodowa[12].znak = 'm';
ksiazka_kodowa[12].slowo_kodowe = "100";
ksiazka_kodowa[13].znak = 'e';
ksiazka_kodowa[13].slowo_kodowe = "101";
ksiazka_kodowa[14].znak = 'd';
ksiazka_kodowa[14].slowo_kodowe = "1100";
ksiazka_kodowa[15].znak = 'a';
ksiazka_kodowa[15].slowo_kodowe = "1101";
ksiazka_kodowa[16].znak = 'J';
ksiazka_kodowa[16].slowo_kodowe = "1110";
ksiazka_kodowa[17].znak = ' ';
ksiazka_kodowa[17].slowo_kodowe = "1111";
}
char znajdz_znak(string slowo_kodowe, kod* ksiazka_kodowa, int dlugosc_ksiazki_kodowej) {
for (int i = 0; i < dlugosc_ksiazki_kodowej; ++i) {
if (ksiazka_kodowa[i].slowo_kodowe == slowo_kodowe) {
return ksiazka_kodowa[i].znak;
}
}
return '\0';
}
string odkoduj_wiadomosc(string wiadomosc, kod* ksiazka_kodowa, int dlugosc_ksiazki_kodowej) {
string wiadomosc_odkodowana = "";
string slowo_kodowe = "";
for (int i = 0; i < wiadomosc.length(); ++i) {
slowo_kodowe += wiadomosc[i];
char znak = znajdz_znak(slowo_kodowe, ksiazka_kodowa, dlugosc_ksiazki_kodowej);
if (znak != '\0') {
wiadomosc_odkodowana += znak;
slowo_kodowe = "";
}
}
return wiadomosc_odkodowana;
}
int main() {
string wiadomosc_zakodowana = "1110101001001011011001111010011010010000000010011011111101110001100100000011001111010110100110010010110110011110111011111000001100010010111010111110110011110000110010100110110110001100100011010111000001";
const int DLUGOSC_KSIAZKI_KODOWEJ = 18;
kod ksiazka_kodowa[DLUGOSC_KSIAZKI_KODOWEJ];
zainicjalizuj_ksiazke_kodowa(ksiazka_kodowa);
string wiadomosc_odkodowana = odkoduj_wiadomosc(wiadomosc_zakodowana, ksiazka_kodowa, DLUGOSC_KSIAZKI_KODOWEJ);
cout << wiadomosc_odkodowana << endl;
return 0;
}