Prezentacja multimedialna

Polecenie 1

Zapoznaj się z prezentacją przedstawiającą użycie stosu zaimplementowanego za pomocą listy jednokierunkowej niecyklicznej w realizacji algorytmu konwersji zapisu infiksowego na odwrotną notację polskąD8zD8PhYJodwrotną notację polską. Algorytm zapisany w pseudokodzie znajdziesz w e‑materiale Dynamiczne struktury danychDINsybcX5Dynamiczne struktury danych.

Specyfikacja problemu:

Dane:

wyrazenie – łańcuch znaków; zapis infiksowy wyrażenia arytmetycznego, w którym znak spacji występuje przed i po każdym operatorze

Wynik:

wyrażenie infiksowe wypisane w odwrotnej notacji polskiej

R13p9hcdavFI61

Polecenie 2

Na podstawie informacji z sekcji „Przeczytaj” oraz powyższej prezentacji napisz i uruchom program konwertujący podane wyrażenie infiksowe na postfiksowe. W implementacji do zdefiniowania węzłów listy użyj klasy Wezel zamiast struktury. W metodzie czyOperator() wykorzystaj metodę find() obiektu string.

Specyfikacja problemu:

Dane:

wyrazenie – łańcuch znaków; zapis infiksowy wyrażenia arytmetycznego, w którym znak spacji występuje przed i po każdym operatorze

Wynik:

wyrażenie infiksowe wypisane w odwrotnej notacji polskiej.

Działanie programu przetestuj dla następującego wyrażenia: (31 + 4) * 7.

Przykładowy wynik działania programu:

Wyrażenie infiksowe: 7 * (15 - 5)
Wyrażenie postfiksowe: 7  15  5 - *

RnlE3UUWdnzGZ

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 2. kratka include otwórz nawias ostrokątny string zamknij nawias ostrokątny. Linia 4. using namespace std średnik. Linia 6. class Wezel otwórz nawias klamrowy. Linia 7. public dwukropek. Linia 8. string znak średnik. Linia 9. Wezel asterysk nastepny średnik. Linia 11. Wezel otwórz nawias okrągły zamknij nawias okrągły dwukropek znak otwórz nawias okrągły cudzysłów cudzysłów zamknij nawias okrągły przecinek nastepny otwórz nawias okrągły nullptr zamknij nawias okrągły otwórz nawias klamrowy zamknij nawias klamrowy. Linia 12. Wezel otwórz nawias okrągły string znak zamknij nawias okrągły otwórz nawias klamrowy. Linia 13. this minus zamknij nawias ostrokątny znak znak równości znak średnik. Linia 14. this minus zamknij nawias ostrokątny nastepny znak równości nullptr średnik. Linia 15. zamknij nawias klamrowy. Linia 16. zamknij nawias klamrowy średnik. Linia 18. class Stos otwórz nawias klamrowy. Linia 19. Wezel asterysk wierzcholek średnik. Linia 20. public dwukropek. Linia 21. Stos otwórz nawias okrągły zamknij nawias okrągły dwukropek wierzcholek otwórz nawias okrągły nullptr zamknij nawias okrągły otwórz nawias klamrowy zamknij nawias klamrowy. Linia 22. bool czyPusty otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 23. string pobierzW otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 24. void odloz otwórz nawias okrągły string zamknij nawias okrągły średnik. Linia 25. string zdejmij otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 26. void wypisz otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 27. zamknij nawias klamrowy średnik. Linia 29. bool Stos dwukropek dwukropek czyPusty otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 30. return wykrzyknik wierzcholek średnik. Linia 31. zamknij nawias klamrowy. Linia 33. string Stos dwukropek dwukropek pobierzW otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 34. if otwórz nawias okrągły czyPusty otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły return cudzysłów cudzysłów średnik. Linia 35. return wierzcholek minus zamknij nawias ostrokątny znak średnik. Linia 36. zamknij nawias klamrowy. Linia 38. void Stos dwukropek dwukropek odloz otwórz nawias okrągły string znak zamknij nawias okrągły otwórz nawias klamrowy. Linia 39. Wezel asterysk nowy znak równości new Wezel otwórz nawias okrągły znak zamknij nawias okrągły średnik. Linia 40. nowy minus zamknij nawias ostrokątny nastepny znak równości wierzcholek średnik. Linia 41. wierzcholek znak równości nowy średnik. Linia 42. zamknij nawias klamrowy. Linia 44. string Stos dwukropek dwukropek zdejmij otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 45. if otwórz nawias okrągły czyPusty otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły return cudzysłów cudzysłów średnik. Linia 46. Wezel asterysk pomocniczy znak równości wierzcholek średnik. Linia 47. string znak znak równości pomocniczy minus zamknij nawias ostrokątny znak średnik. Linia 48. wierzcholek znak równości wierzcholek minus zamknij nawias ostrokątny nastepny średnik. Linia 49. delete otwórz nawias okrągły pomocniczy zamknij nawias okrągły średnik. Linia 50. return znak średnik. Linia 51. zamknij nawias klamrowy. Linia 53. void Stos dwukropek dwukropek wypisz otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 54. if otwórz nawias okrągły czyPusty otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły return średnik. Linia 55. Wezel asterysk pomocniczy znak równości wierzcholek średnik. Linia 56. while otwórz nawias okrągły pomocniczy wykrzyknik znak równości nullptr zamknij nawias okrągły otwórz nawias klamrowy. Linia 57. pomocniczy znak równości pomocniczy minus zamknij nawias ostrokątny nastepny średnik. Linia 58. zamknij nawias klamrowy. Linia 59. zamknij nawias klamrowy. Linia 61. bool czyOperator otwórz nawias okrągły string znak zamknij nawias okrągły otwórz nawias klamrowy. Linia 62. string operatory znak równości cudzysłów otwórz nawias okrągły zamknij nawias okrągły plus minus asterysk prawy ukośnik procent kareta cudzysłów średnik. Linia 63. if otwórz nawias okrągły operatory kropka find otwórz nawias okrągły znak zamknij nawias okrągły wykrzyknik znak równości string dwukropek dwukropek npos zamknij nawias okrągły otwórz nawias klamrowy. Linia 64. return true średnik. Linia 65. zamknij nawias klamrowy. Linia 66. return false średnik. Linia 67. zamknij nawias klamrowy. Linia 69. int priorytet otwórz nawias okrągły string znak zamknij nawias okrągły otwórz nawias klamrowy. Linia 70. if otwórz nawias okrągły znak znak równości znak równości cudzysłów otwórz nawias okrągły cudzysłów zamknij nawias okrągły return 0 średnik. Linia 71. else if otwórz nawias okrągły znak znak równości znak równości cudzysłów plus cudzysłów kreska pionowa kreska pionowa znak znak równości znak równości cudzysłów minus cudzysłów zamknij nawias okrągły return 1 średnik. Linia 72. else if otwórz nawias okrągły znak znak równości znak równości cudzysłów asterysk cudzysłów kreska pionowa kreska pionowa znak znak równości znak równości cudzysłów prawy ukośnik cudzysłów kreska pionowa kreska pionowa znak znak równości znak równości cudzysłów procent cudzysłów zamknij nawias okrągły return 2 średnik. Linia 73. else if otwórz nawias okrągły znak znak równości znak równości cudzysłów kareta cudzysłów zamknij nawias okrągły return 3 średnik. Linia 74. return minus 1 średnik. Linia 75. zamknij nawias klamrowy. Linia 77. string konwertujDoOnp otwórz nawias okrągły string wyrazenie zamknij nawias okrągły otwórz nawias klamrowy. Linia 78. Stos stos znak równości Stos otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 79. string wynik przecinek znak znak równości cudzysłów cudzysłów średnik. Linia 81. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny otwórz nawias okrągły int zamknij nawias okrągły wyrazenie kropka length otwórz nawias okrągły zamknij nawias okrągły średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 82. znak znak równości wyrazenie otwórz nawias kwadratowy i zamknij nawias kwadratowy średnik. Linia 83. if otwórz nawias okrągły znak znak równości znak równości cudzysłów cudzysłów kreska pionowa kreska pionowa wykrzyknik czyOperator otwórz nawias okrągły znak zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 84. wynik plus znak równości znak średnik. Linia 85. zamknij nawias klamrowy else if otwórz nawias okrągły znak znak równości znak równości cudzysłów otwórz nawias okrągły cudzysłów zamknij nawias okrągły otwórz nawias klamrowy. Linia 86. stos kropka odloz otwórz nawias okrągły znak zamknij nawias okrągły średnik. Linia 87. zamknij nawias klamrowy else if otwórz nawias okrągły znak znak równości znak równości cudzysłów zamknij nawias okrągły cudzysłów zamknij nawias okrągły otwórz nawias klamrowy. Linia 88. while otwórz nawias okrągły stos kropka pobierzW otwórz nawias okrągły zamknij nawias okrągły wykrzyknik znak równości cudzysłów otwórz nawias okrągły cudzysłów zamknij nawias okrągły. Linia 89. wynik plus znak równości cudzysłów cudzysłów plus stos kropka zdejmij otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 90. stos kropka zdejmij otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 91. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 92. while otwórz nawias okrągły wykrzyknik stos kropka czyPusty otwórz nawias okrągły zamknij nawias okrągły ampersant ampersant. Linia 93. otwórz nawias okrągły priorytet otwórz nawias okrągły stos kropka pobierzW otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły zamknij nawias ostrokątny znak równości priorytet otwórz nawias okrągły znak zamknij nawias okrągły zamknij nawias okrągły zamknij nawias okrągły. Linia 94. wynik plus znak równości stos kropka zdejmij otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 95. stos kropka odloz otwórz nawias okrągły znak zamknij nawias okrągły średnik. Linia 96. zamknij nawias klamrowy. Linia 97. stos kropka wypisz otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 98. zamknij nawias klamrowy. Linia 100. while otwórz nawias okrągły wykrzyknik stos kropka czyPusty otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły. Linia 101. wynik plus znak równości cudzysłów cudzysłów plus stos kropka zdejmij otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 103. return wynik średnik. Linia 104. zamknij nawias klamrowy. Linia 106. int main otwórz nawias okrągły int argc przecinek char asterysk argv otwórz nawias kwadratowy zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 107. string wyrazenie znak równości cudzysłów otwórz nawias okrągły 31 plus 4 zamknij nawias okrągły asterysk 7 cudzysłów średnik. Linia 108. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Wyrażenie infiksowe dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny wyrazenie otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 109. string wynik znak równości konwertujDoOnp otwórz nawias okrągły wyrazenie zamknij nawias okrągły średnik. Linia 110. cout otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów Wyrażenie postfiksowe dwukropek cudzysłów otwórz nawias ostrokątny otwórz nawias ostrokątny wynik otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 111. return 0 średnik. Linia 112. zamknij nawias klamrowy.

#include <iostream>
#include <string>

using namespace std;

class Wezel {
public:
    string znak;
    Wezel *nastepny;

    Wezel(): znak(""), nastepny(nullptr) {}
    Wezel(string znak) {
        this->znak = znak;
        this->nastepny = nullptr;
    }
};

class Stos {
    Wezel* wierzcholek;
public:
    Stos(): wierzcholek(nullptr) {}
    bool czyPusty();
    string pobierzW();
    void odloz(string);
    string zdejmij();
    void wypisz();
};

bool Stos::czyPusty() {
    return !wierzcholek;
}

string Stos::pobierzW() {
    if (czyPusty()) return "";
    return wierzcholek->znak;
}

void Stos::odloz(string znak) {
    Wezel* nowy = new Wezel(znak);
    nowy->nastepny = wierzcholek;
    wierzcholek = nowy;
}

string Stos::zdejmij() {
    if (czyPusty()) return "";
    Wezel* pomocniczy = wierzcholek;
    string znak = pomocniczy->znak;
    wierzcholek = wierzcholek->nastepny;
    delete(pomocniczy);
    return znak;
}

void Stos::wypisz() {
    if (czyPusty()) return;
    Wezel* pomocniczy = wierzcholek;
    while (pomocniczy != nullptr) {
      pomocniczy = pomocniczy->nastepny;
    }
}

bool czyOperator(string znak) {
    string operatory = "()+-*/%^";
    if (operatory.find(znak) != string::npos) {
        return true;
    }
    return false;
}

int priorytet(string znak) {
    if (znak == "(") return 0;
    else if (znak == "+" || znak == "-") return 1;
    else if (znak == "*" || znak == "/" || znak == "%") return 2;
    else if (znak == "^") return 3;
    return -1;
}

string konwertujDoOnp(string wyrazenie) {
    Stos stos = Stos();
    string wynik, znak = "";

    for (int i=0; i < (int)wyrazenie.length(); i++) {
        znak = wyrazenie[i];
        if (znak == " " || !czyOperator(znak)) {
            wynik += znak;
        } else if (znak == "(") {
            stos.odloz(znak);
        } else if (znak == ")") {
            while (stos.pobierzW() != "(")
                wynik += " " + stos.zdejmij();
            stos.zdejmij();
        } else {
            while (!stos.czyPusty() &&
                   (priorytet(stos.pobierzW()) >= priorytet(znak)))
                wynik += stos.zdejmij();
            stos.odloz(znak);
        }
        stos.wypisz();
    }

    while (!stos.czyPusty())
        wynik += " " + stos.zdejmij();

    return wynik;
}

int main(int argc, char *argv[]) {
    string wyrazenie = "(31 + 4) * 7";
    cout << "Wyrażenie infiksowe: " << wyrazenie << endl;
    string wynik = konwertujDoOnp(wyrazenie);
    cout << "Wyrażenie postfiksowe: " << wynik << endl;
    return 0;
}

Polecenie 3

Zapoznaj się z prezentacją przedstawiającą użycie jednokierunkowej listy cyklicznej w symulacji problemu Flawiusza. Algorytm zapisany w pseudokodzie znajdziesz w e‑materiale Dynamiczne struktury danychDINsybcX5Dynamiczne struktury danych.

Specyfikacja problemu:

Dane:

n – liczba naturalna; liczba elementów kręgu
k – liczba naturalna; liczba oznaczająca pierwszy eliminowany element oraz liczbę przejść do następnego eliminowanego elementu

Wynik:

wypisany numer elementu, który pozostał w kręgu

RGtd7JexkLhGp1

Polecenie 4

Przyjmijmy, że do symulacji problemu Flawiusza używamy dwukierunkowej listy cyklicznej o znanym rozmiarze n. Zaimplementuj metody dodaj(), usun() oraz wypisz() uwzględniające dwukierunkowość listy. Po uruchomieniu program powinien wypisywać zawartość listy przed każdym usunięciem węzła, a na końcu pozycję węzła, który pozostał na liście.

Specyfikacja problemu:

Dane:

n – liczba naturalna; rozmiar listy cyklicznej
k – liczba naturalna; liczba oznaczająca pierwszy eliminowany element oraz liczbę przejść do następnego eliminowanego elementu

Wynik:

zawartość listy przed każdym usunięciem węzła oraz pozycja węzła, który pozostał na liście

Działanie programu przetestuj dla n = 8 i k = 3.

Przykładowy wynik działania programu:

1 2 3 4 5 6 7 8 
1 2 4 5 6 7 8 
1 2 4 5 7 8 
2 4 5 7 8 
2 4 7 8 
4 7 8 
4 7 
7

R1JDbF289Bbls

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 3. using namespace std średnik. Linia 5. typedef struct Wezel otwórz nawias klamrowy. Linia 6. int pozycja średnik. Linia 7. Wezel asterysk nastepny średnik. Linia 8. Wezel asterysk poprzedni średnik. Linia 9. Wezel otwórz nawias okrągły int pozycja zamknij nawias okrągły otwórz nawias klamrowy. Linia 10. this minus zamknij nawias ostrokątny pozycja znak równości pozycja średnik. Linia 11. this minus zamknij nawias ostrokątny nastepny znak równości nullptr średnik. Linia 12. this minus zamknij nawias ostrokątny poprzedni znak równości nullptr średnik. Linia 13. zamknij nawias klamrowy. Linia 14. zamknij nawias klamrowy Wezel średnik. Linia 16. class Lista otwórz nawias klamrowy. Linia 17. Wezel asterysk glowa średnik. Linia 18. public dwukropek. Linia 19. Lista otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy glowa znak równości nullptr średnik zamknij nawias klamrowy. Linia 20. void dodaj otwórz nawias okrągły int pozycja zamknij nawias okrągły średnik. Linia 21. void usun otwórz nawias okrągły Wezel asterysk zamknij nawias okrągły średnik. Linia 22. Wezel asterysk przejdz otwórz nawias okrągły int przecinek Wezel asterysk zamknij nawias okrągły średnik. Linia 23. void wypisz otwórz nawias okrągły int zamknij nawias okrągły średnik. Linia 24. zamknij nawias klamrowy średnik. Linia 26. Wezel asterysk Lista dwukropek dwukropek przejdz otwórz nawias okrągły int o podkreślnik ile przecinek Wezel asterysk wezel zamknij nawias okrągły otwórz nawias klamrowy. Linia 27. Wezel asterysk pomocniczy znak równości wezel średnik. Linia 28. if otwórz nawias okrągły wezel znak równości znak równości nullptr zamknij nawias okrągły otwórz nawias klamrowy. Linia 29. pomocniczy znak równości glowa średnik. Linia 30. zamknij nawias klamrowy. Linia 32. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny o podkreślnik ile średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 33. pomocniczy znak równości pomocniczy minus zamknij nawias ostrokątny nastepny średnik. Linia 34. zamknij nawias klamrowy. Linia 36. delete otwórz nawias okrągły wezel zamknij nawias okrągły średnik. Linia 37. return pomocniczy średnik. Linia 38. zamknij nawias klamrowy. Linia 40. void Lista dwukropek dwukropek dodaj otwórz nawias okrągły int pozycja zamknij nawias okrągły otwórz nawias klamrowy. Linia 41. Wezel asterysk nowy znak równości new Wezel otwórz nawias okrągły pozycja zamknij nawias okrągły średnik. Linia 43. if otwórz nawias okrągły glowa znak równości znak równości nullptr zamknij nawias okrągły otwórz nawias klamrowy. Linia 44. glowa znak równości nowy średnik. Linia 45. glowa minus zamknij nawias ostrokątny nastepny znak równości glowa średnik. Linia 46. glowa minus zamknij nawias ostrokątny poprzedni znak równości glowa średnik. Linia 47. return średnik. Linia 48. zamknij nawias klamrowy. Linia 49. Wezel asterysk ostatni znak równości glowa minus zamknij nawias ostrokątny poprzedni średnik. Linia 50. nowy minus zamknij nawias ostrokątny nastepny znak równości glowa średnik. Linia 51. nowy minus zamknij nawias ostrokątny poprzedni znak równości ostatni średnik. Linia 52. glowa minus zamknij nawias ostrokątny poprzedni znak równości nowy średnik. Linia 53. ostatni minus zamknij nawias ostrokątny nastepny znak równości nowy średnik. Linia 54. zamknij nawias klamrowy. Linia 56. void Lista dwukropek dwukropek usun otwórz nawias okrągły Wezel asterysk wezel zamknij nawias okrągły otwórz nawias klamrowy. Linia 57. wezel minus zamknij nawias ostrokątny nastepny minus zamknij nawias ostrokątny poprzedni znak równości wezel minus zamknij nawias ostrokątny poprzedni średnik. Linia 58. wezel minus zamknij nawias ostrokątny poprzedni minus zamknij nawias ostrokątny nastepny znak równości wezel minus zamknij nawias ostrokątny nastepny średnik. Linia 60. if otwórz nawias okrągły wezel znak równości znak równości glowa zamknij nawias okrągły otwórz nawias klamrowy. Linia 61. if otwórz nawias okrągły glowa minus zamknij nawias ostrokątny nastepny wykrzyknik znak równości glowa zamknij nawias okrągły otwórz nawias klamrowy. Linia 62. glowa znak równości glowa minus zamknij nawias ostrokątny nastepny średnik. Linia 63. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 64. glowa znak równości nullptr średnik. Linia 65. zamknij nawias klamrowy. Linia 66. zamknij nawias klamrowy. Linia 67. zamknij nawias klamrowy. Linia 69. void Lista dwukropek dwukropek wypisz otwórz nawias okrągły int n zamknij nawias okrągły otwórz nawias klamrowy. Linia 70. Wezel asterysk pomocniczy znak równości glowa średnik. Linia 71. while otwórz nawias okrągły n minus minus zamknij nawias okrągły otwórz nawias klamrowy. Linia 72. cout otwórz nawias ostrokątny otwórz nawias ostrokątny pomocniczy minus zamknij nawias ostrokątny pozycja otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów cudzysłów średnik. Linia 73. pomocniczy znak równości pomocniczy minus zamknij nawias ostrokątny nastepny średnik. Linia 74. zamknij nawias klamrowy. Linia 75. cout otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 76. zamknij nawias klamrowy. Linia 78. int main otwórz nawias okrągły int argc przecinek char asterysk argv otwórz nawias kwadratowy zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 79. int n znak równości 8 średnik. Linia 80. int k znak równości 3 średnik. Linia 81. Lista lista średnik. Linia 83. for otwórz nawias okrągły int i znak równości 1 średnik i otwórz nawias ostrokątny n plus 1 średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 84. lista kropka dodaj otwórz nawias okrągły i zamknij nawias okrągły średnik. Linia 85. zamknij nawias klamrowy. Linia 87. Wezel asterysk wezel znak równości lista kropka przejdz otwórz nawias okrągły k minus 1 przecinek nullptr zamknij nawias okrągły średnik. Linia 88. while otwórz nawias okrągły wezel minus zamknij nawias ostrokątny nastepny wykrzyknik znak równości wezel zamknij nawias okrągły otwórz nawias klamrowy. Linia 89. lista kropka wypisz otwórz nawias okrągły n minus minus zamknij nawias okrągły średnik. Linia 90. lista kropka usun otwórz nawias okrągły wezel zamknij nawias okrągły średnik. Linia 91. wezel znak równości lista kropka przejdz otwórz nawias okrągły k przecinek wezel zamknij nawias okrągły średnik. Linia 92. zamknij nawias klamrowy. Linia 94. cout otwórz nawias ostrokątny otwórz nawias ostrokątny wezel minus zamknij nawias ostrokątny pozycja otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 96. return 0 średnik. Linia 97. zamknij nawias klamrowy.

#include <iostream>

using namespace std;

typedef struct Wezel {
    int pozycja;
    Wezel *nastepny;
    Wezel *poprzedni;
    Wezel(int pozycja) {
        this->pozycja = pozycja;
        this->nastepny = nullptr;
        this->poprzedni = nullptr;
    }
} Wezel;

class Lista {
    Wezel *glowa;
  public:
    Lista() { glowa = nullptr; }
    void dodaj(int pozycja);
    void usun(Wezel*);
    Wezel* przejdz(int, Wezel*);
    void wypisz(int);
};

Wezel* Lista::przejdz(int o_ile, Wezel* wezel) {
    Wezel* pomocniczy = wezel;
    if (wezel == nullptr) {
       pomocniczy = glowa;
    }

    for (int i=0; i < o_ile; i++) {
        pomocniczy = pomocniczy->nastepny;
    }

    delete(wezel);
    return pomocniczy;
}

void Lista::dodaj(int pozycja) {
    Wezel* nowy = new Wezel(pozycja);

    if (glowa == nullptr) {
        glowa = nowy;
        glowa->nastepny = glowa;
        glowa->poprzedni = glowa;
        return;
    }
    Wezel* ostatni = glowa->poprzedni;
    nowy->nastepny = glowa;
    nowy->poprzedni = ostatni;
    glowa->poprzedni = nowy;
    ostatni->nastepny = nowy;
}

void Lista::usun(Wezel* wezel) {
    wezel->nastepny->poprzedni = wezel->poprzedni;
    wezel->poprzedni->nastepny = wezel->nastepny;

    if (wezel == glowa) {
        if (glowa->nastepny != glowa) {
            glowa = glowa->nastepny;
        } else {
            glowa = nullptr;
        }
    }
}

void Lista::wypisz(int n) {
    Wezel* pomocniczy = glowa;
    while (n--) {
        cout << pomocniczy->pozycja << " ";
        pomocniczy = pomocniczy->nastepny;
    }
    cout << endl;
}

int main(int argc, char *argv[]) {
  int n = 8;
  int k = 3;
  Lista lista;

  for (int i=1; i<n+1; i++) {
    lista.dodaj(i);
  }

  Wezel* wezel = lista.przejdz(k - 1, nullptr);
  while (wezel->nastepny != wezel) {
    lista.wypisz(n--);
    lista.usun(wezel);
    wezel = lista.przejdz(k, wezel);
  }

  cout << wezel->pozycja << endl;

  return 0;
}

Polecenie 5

Zapoznaj się z prezentacją przedstawiającą użycie niecyklicznej listy dwukierunkowej w algorytmie leksykograficznego sortowania wyrazów. Algorytm zapisany w pseudokodzie znajdziesz w e‑materiale Dynamiczne struktury danychDINsybcX5Dynamiczne struktury danych.

Specyfikacja problemu:

Dane:

wyrazy – tablica lub lista zawierająca ciągi znaków – wyrazy do uporządkowania

Wynik:

wypisane w porządku leksykograficznym wyrazy

R14RVWMBYUYki1

Polecenie 6

Metoda wstaw() zaimplementowana w prezentacji dotyczącej sortowania leksykograficznego wykonuje w pętli while jedno porównanie, które wcześniej wykonywane jest w metodzie sortuj().

Zaimplementuj taką wersję tej metody, która nie wykona zbędnego porównania.

Specyfikacja problemu:

Dane:

wyrazy – tablica lub lista zawierająca ciągi znaków – wyrazy do uporządkowania

Wynik:

wyrazy wypisane przed posortowaniem i po sortowaniu w porządku leksykograficznym

Działanie programu przetestuj dla wyrazów: "dynamiczne", "Struktury", "danych", "cpp".

Przykładowy wynik działania programu:

dynamiczne Struktury danych cpp 
cpp danych dynamiczne Struktury

R16NvNhyBvgET

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 2. kratka include otwórz nawias ostrokątny algorithm zamknij nawias ostrokątny. Linia 3. kratka include otwórz nawias ostrokątny string zamknij nawias ostrokątny. Linia 5. using namespace std średnik. Linia 7. typedef struct Wezel otwórz nawias klamrowy. Linia 8. string wyraz średnik. Linia 9. Wezel asterysk nastepny średnik. Linia 10. Wezel asterysk poprzedni średnik. Linia 11. Wezel otwórz nawias okrągły string wyraz zamknij nawias okrągły otwórz nawias klamrowy. Linia 12. this minus zamknij nawias ostrokątny wyraz znak równości wyraz średnik. Linia 13. this minus zamknij nawias ostrokątny nastepny znak równości nullptr średnik. Linia 14. this minus zamknij nawias ostrokątny poprzedni znak równości nullptr średnik. Linia 15. zamknij nawias klamrowy. Linia 16. zamknij nawias klamrowy Wezel średnik. Linia 18. class Lista otwórz nawias klamrowy. Linia 19. Wezel asterysk glowa średnik. Linia 20. Wezel asterysk ogon średnik. Linia 22. public dwukropek. Linia 23. Lista otwórz nawias okrągły zamknij nawias okrągły dwukropek glowa otwórz nawias okrągły nullptr zamknij nawias okrągły przecinek ogon otwórz nawias okrągły nullptr zamknij nawias okrągły otwórz nawias klamrowy zamknij nawias klamrowy. Linia 24. void dodaj otwórz nawias okrągły string zamknij nawias okrągły średnik. Linia 25. void usun otwórz nawias okrągły Wezel asterysk zamknij nawias okrągły średnik. Linia 26. int porownaj otwórz nawias okrągły Wezel asterysk przecinek Wezel asterysk zamknij nawias okrągły średnik. Linia 27. void wstaw otwórz nawias okrągły Wezel asterysk zamknij nawias okrągły średnik. Linia 28. void sortuj otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 29. void wypisz otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 30. zamknij nawias klamrowy średnik. Linia 32. void Lista dwukropek dwukropek dodaj otwórz nawias okrągły string wyraz zamknij nawias okrągły otwórz nawias klamrowy. Linia 33. Wezel asterysk nowy znak równości new Wezel otwórz nawias okrągły wyraz zamknij nawias okrągły średnik. Linia 34. if otwórz nawias okrągły glowa znak równości znak równości nullptr zamknij nawias okrągły otwórz nawias klamrowy. Linia 35. glowa znak równości ogon znak równości nowy średnik. Linia 36. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 37. ogon minus zamknij nawias ostrokątny nastepny znak równości nowy średnik. Linia 38. nowy minus zamknij nawias ostrokątny poprzedni znak równości ogon średnik. Linia 39. ogon znak równości nowy średnik. Linia 40. zamknij nawias klamrowy. Linia 41. zamknij nawias klamrowy. Linia 43. void Lista dwukropek dwukropek usun otwórz nawias okrągły Wezel asterysk wezel zamknij nawias okrągły otwórz nawias klamrowy. Linia 44. if otwórz nawias okrągły wezel znak równości znak równości glowa ampersant ampersant glowa minus zamknij nawias ostrokątny nastepny wykrzyknik znak równości nullptr zamknij nawias okrągły otwórz nawias klamrowy. Linia 45. glowa znak równości glowa minus zamknij nawias ostrokątny nastepny średnik. Linia 46. glowa minus zamknij nawias ostrokątny poprzedni znak równości nullptr średnik. Linia 47. return średnik. Linia 48. zamknij nawias klamrowy. Linia 50. if otwórz nawias okrągły wezel znak równości znak równości ogon zamknij nawias okrągły otwórz nawias klamrowy. Linia 51. wezel minus zamknij nawias ostrokątny poprzedni minus zamknij nawias ostrokątny nastepny znak równości nullptr średnik. Linia 52. ogon znak równości wezel minus zamknij nawias ostrokątny poprzedni średnik. Linia 53. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 54. wezel minus zamknij nawias ostrokątny poprzedni minus zamknij nawias ostrokątny nastepny znak równości wezel minus zamknij nawias ostrokątny nastepny średnik. Linia 55. wezel minus zamknij nawias ostrokątny nastepny minus zamknij nawias ostrokątny poprzedni znak równości wezel minus zamknij nawias ostrokątny poprzedni średnik. Linia 56. zamknij nawias klamrowy. Linia 57. zamknij nawias klamrowy. Linia 59. int Lista dwukropek dwukropek porownaj otwórz nawias okrągły Wezel asterysk wezel podkreślnik 1 przecinek Wezel asterysk wezel podkreślnik 2 zamknij nawias okrągły otwórz nawias klamrowy. Linia 60. string wyraz podkreślnik 1 znak równości wezel podkreślnik 1 minus zamknij nawias ostrokątny wyraz średnik. Linia 61. string wyraz podkreślnik 2 znak równości wezel podkreślnik 2 minus zamknij nawias ostrokątny wyraz średnik. Linia 63. transform otwórz nawias okrągły wyraz podkreślnik 1 kropka begin otwórz nawias okrągły zamknij nawias okrągły przecinek wyraz podkreślnik 1 kropka end otwórz nawias okrągły zamknij nawias okrągły przecinek wyraz podkreślnik 1 kropka begin otwórz nawias okrągły zamknij nawias okrągły przecinek. Linia 64. otwórz nawias kwadratowy zamknij nawias kwadratowy otwórz nawias okrągły unsigned char c zamknij nawias okrągły otwórz nawias klamrowy return tolower otwórz nawias okrągły c zamknij nawias okrągły średnik zamknij nawias klamrowy zamknij nawias okrągły średnik. Linia 66. transform otwórz nawias okrągły wyraz podkreślnik 2 kropka begin otwórz nawias okrągły zamknij nawias okrągły przecinek wyraz podkreślnik 2 kropka end otwórz nawias okrągły zamknij nawias okrągły przecinek wyraz podkreślnik 2 kropka begin otwórz nawias okrągły zamknij nawias okrągły przecinek. Linia 67. otwórz nawias kwadratowy zamknij nawias kwadratowy otwórz nawias okrągły unsigned char c zamknij nawias okrągły otwórz nawias klamrowy return tolower otwórz nawias okrągły c zamknij nawias okrągły średnik zamknij nawias klamrowy zamknij nawias okrągły średnik. Linia 69. return wyraz podkreślnik 1 kropka compare otwórz nawias okrągły wyraz podkreślnik 2 zamknij nawias okrągły średnik. Linia 70. zamknij nawias klamrowy. Linia 72. void Lista dwukropek dwukropek sortuj otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 73. Wezel asterysk pomocniczy znak równości glowa średnik. Linia 74. while otwórz nawias okrągły true zamknij nawias okrągły otwórz nawias klamrowy. Linia 75. if otwórz nawias okrągły pomocniczy minus zamknij nawias ostrokątny nastepny znak równości znak równości nullptr zamknij nawias okrągły. Linia 76. break średnik. Linia 77. if otwórz nawias okrągły porownaj otwórz nawias okrągły pomocniczy przecinek pomocniczy minus zamknij nawias ostrokątny nastepny zamknij nawias okrągły zamknij nawias ostrokątny 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 78. usun otwórz nawias okrągły pomocniczy zamknij nawias okrągły średnik. Linia 79. wstaw otwórz nawias okrągły pomocniczy zamknij nawias okrągły średnik. Linia 80. pomocniczy znak równości glowa średnik. Linia 81. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 82. pomocniczy znak równości pomocniczy minus zamknij nawias ostrokątny nastepny średnik. Linia 83. zamknij nawias klamrowy. Linia 84. zamknij nawias klamrowy. Linia 85. zamknij nawias klamrowy. Linia 87. void Lista dwukropek dwukropek wstaw otwórz nawias okrągły Wezel asterysk wezel zamknij nawias okrągły otwórz nawias klamrowy. Linia 88. Wezel asterysk pomocniczy znak równości wezel minus zamknij nawias ostrokątny nastepny średnik. Linia 89. while otwórz nawias okrągły pomocniczy wykrzyknik znak równości ogon ampersant ampersant porownaj otwórz nawias okrągły wezel przecinek pomocniczy minus zamknij nawias ostrokątny nastepny zamknij nawias okrągły zamknij nawias ostrokątny znak równości 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 90. pomocniczy znak równości pomocniczy minus zamknij nawias ostrokątny nastepny średnik. Linia 91. zamknij nawias klamrowy. Linia 93. if otwórz nawias okrągły pomocniczy znak równości znak równości ogon zamknij nawias okrągły otwórz nawias klamrowy. Linia 94. wezel minus zamknij nawias ostrokątny nastepny znak równości nullptr średnik. Linia 95. wezel minus zamknij nawias ostrokątny poprzedni znak równości ogon średnik. Linia 96. ogon minus zamknij nawias ostrokątny nastepny znak równości wezel średnik. Linia 97. ogon znak równości wezel średnik. Linia 98. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 99. wezel minus zamknij nawias ostrokątny poprzedni znak równości pomocniczy średnik. Linia 100. wezel minus zamknij nawias ostrokątny nastepny znak równości pomocniczy minus zamknij nawias ostrokątny nastepny średnik. Linia 101. pomocniczy minus zamknij nawias ostrokątny nastepny minus zamknij nawias ostrokątny poprzedni znak równości wezel średnik. Linia 102. pomocniczy minus zamknij nawias ostrokątny nastepny znak równości wezel średnik. Linia 103. zamknij nawias klamrowy. Linia 104. zamknij nawias klamrowy. Linia 106. void Lista dwukropek dwukropek wypisz otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 107. Wezel asterysk pomocniczy znak równości glowa średnik. Linia 108. while otwórz nawias okrągły pomocniczy wykrzyknik znak równości nullptr zamknij nawias okrągły otwórz nawias klamrowy. Linia 109. cout otwórz nawias ostrokątny otwórz nawias ostrokątny pomocniczy minus zamknij nawias ostrokątny wyraz otwórz nawias ostrokątny otwórz nawias ostrokątny cudzysłów cudzysłów średnik. Linia 110. pomocniczy znak równości pomocniczy minus zamknij nawias ostrokątny nastepny średnik. Linia 111. zamknij nawias klamrowy. Linia 112. cout otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 113. zamknij nawias klamrowy. Linia 115. int main otwórz nawias okrągły int argc przecinek char asterysk argv otwórz nawias kwadratowy zamknij nawias kwadratowy zamknij nawias okrągły otwórz nawias klamrowy. Linia 116. string dane otwórz nawias kwadratowy zamknij nawias kwadratowy znak równości otwórz nawias klamrowy cudzysłów dynamiczne cudzysłów przecinek cudzysłów Struktury cudzysłów przecinek cudzysłów danych cudzysłów przecinek cudzysłów cpp cudzysłów zamknij nawias klamrowy średnik. Linia 117. int n znak równości sizeof otwórz nawias okrągły dane zamknij nawias okrągły prawy ukośnik sizeof otwórz nawias okrągły dane zamknij nawias okrągły otwórz nawias kwadratowy 0 zamknij nawias kwadratowy średnik. Linia 119. Lista lista średnik. Linia 120. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny n średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 121. lista kropka dodaj otwórz nawias okrągły dane otwórz nawias kwadratowy i zamknij nawias kwadratowy zamknij nawias okrągły średnik. Linia 122. zamknij nawias klamrowy. Linia 124. lista kropka wypisz otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 125. lista kropka sortuj otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 126. lista kropka wypisz otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 128. return 0 średnik. Linia 129. zamknij nawias klamrowy.

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

typedef struct Wezel {
    string wyraz;
    Wezel *nastepny;
    Wezel *poprzedni;
    Wezel(string wyraz) {
        this->wyraz = wyraz;
        this->nastepny = nullptr;
        this->poprzedni = nullptr;
    }
} Wezel;

class Lista {
    Wezel* glowa;
    Wezel* ogon;

public:
    Lista(): glowa(nullptr), ogon(nullptr) {}
    void dodaj(string);
    void usun(Wezel*);
    int porownaj(Wezel*, Wezel*);
    void wstaw(Wezel*);
    void sortuj();
    void wypisz();
};

void Lista::dodaj(string wyraz) {
    Wezel* nowy = new Wezel(wyraz);
    if (glowa == nullptr) {
        glowa = ogon = nowy;
    } else {
        ogon->nastepny = nowy;
        nowy->poprzedni = ogon;
        ogon = nowy;
    }
}

void Lista::usun(Wezel* wezel) {
    if (wezel == glowa && glowa->nastepny != nullptr) {
        glowa = glowa->nastepny;
        glowa->poprzedni = nullptr;
        return;
    }

    if (wezel == ogon) {
        wezel->poprzedni->nastepny = nullptr;
        ogon = wezel->poprzedni;
    } else {
        wezel->poprzedni->nastepny = wezel->nastepny;
        wezel->nastepny->poprzedni = wezel->poprzedni;
    }
}

int Lista::porownaj(Wezel* wezel_1, Wezel* wezel_2) {
    string wyraz_1 = wezel_1->wyraz;
    string wyraz_2 = wezel_2->wyraz;

    transform(wyraz_1.begin(), wyraz_1.end(), wyraz_1.begin(),
        [](unsigned char c){ return tolower(c); });

    transform(wyraz_2.begin(), wyraz_2.end(), wyraz_2.begin(),
        [](unsigned char c){ return tolower(c); });

    return wyraz_1.compare(wyraz_2);
}

void Lista::sortuj() {
    Wezel* pomocniczy = glowa;
    while (true) {
        if (pomocniczy->nastepny == nullptr)
            break;
        if (porownaj(pomocniczy, pomocniczy->nastepny) > 0) {
            usun(pomocniczy);
            wstaw(pomocniczy);
            pomocniczy = glowa;
        } else {
            pomocniczy = pomocniczy->nastepny;
        }
    }
}

void Lista::wstaw(Wezel* wezel) {
    Wezel* pomocniczy = wezel->nastepny;
    while (pomocniczy != ogon && porownaj(wezel, pomocniczy->nastepny) >= 0) {
        pomocniczy = pomocniczy->nastepny;
    }

    if (pomocniczy == ogon) {
        wezel->nastepny = nullptr;
        wezel->poprzedni = ogon;
        ogon->nastepny = wezel;
        ogon = wezel;
    } else {
        wezel->poprzedni = pomocniczy;
        wezel->nastepny = pomocniczy->nastepny;
        pomocniczy->nastepny->poprzedni = wezel;
        pomocniczy->nastepny = wezel;
    }
}

void Lista::wypisz() {
    Wezel* pomocniczy = glowa;
    while (pomocniczy != nullptr) {
        cout << pomocniczy->wyraz << " ";
        pomocniczy = pomocniczy->nastepny;
    }
    cout << endl;
}

int main(int argc, char *argv[]) {
    string dane[] = {"dynamiczne", "Struktury", "danych", "cpp"};
    int n = sizeof(dane)/sizeof(dane)[0];

    Lista lista;
    for(int i = 0; i < n; i++) {
        lista.dodaj(dane[i]);
    }

    lista.wypisz();
    lista.sortuj();
    lista.wypisz();

    return 0;
}

Przeczytaj

Sprawdź się