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

R19rTjPwgVb121

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 programie użyj stosu zaimplementowanego za pomocą omówionego w sekcji „Przeczytaj” interfejsu Deque i klasy ArrayDeque.

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: (31 + 4) * 7
Wyrażenie postfiksowe: 31  4 +  7 *

R1OxMESwEG9GT

Linia 1. import java kropka util kropka Deque średnik. Linia 2. import java kropka util kropka ArrayDeque średnik. Linia 4. public class StosListaOnpJF otwórz nawias klamrowy. Linia 6. public static boolean czyOperator otwórz nawias okrągły String znak zamknij nawias okrągły otwórz nawias klamrowy. Linia 7. if otwórz nawias okrągły znak kropka equals otwórz nawias okrągły cudzysłów otwórz nawias okrągły cudzysłów zamknij nawias okrągły kreska pionowa kreska pionowa znak kropka equals otwórz nawias okrągły cudzysłów zamknij nawias okrągły cudzysłów zamknij nawias okrągły kreska pionowa kreska pionowa znak kropka equals otwórz nawias okrągły cudzysłów plus cudzysłów zamknij nawias okrągły kreska pionowa kreska pionowa. Linia 8. znak kropka equals otwórz nawias okrągły cudzysłów minus cudzysłów zamknij nawias okrągły kreska pionowa kreska pionowa znak kropka equals otwórz nawias okrągły cudzysłów asterysk cudzysłów zamknij nawias okrągły kreska pionowa kreska pionowa znak kropka equals otwórz nawias okrągły cudzysłów prawy ukośnik cudzysłów zamknij nawias okrągły kreska pionowa kreska pionowa. Linia 9. znak kropka equals otwórz nawias okrągły cudzysłów procent cudzysłów zamknij nawias okrągły kreska pionowa kreska pionowa znak kropka equals otwórz nawias okrągły cudzysłów kareta cudzysłów zamknij nawias okrągły zamknij nawias okrągły. Linia 10. return true średnik. Linia 11. return false średnik. Linia 12. zamknij nawias klamrowy. Linia 14. public static int priorytet otwórz nawias okrągły String znak zamknij nawias okrągły otwórz nawias klamrowy. Linia 15. if otwórz nawias okrągły znak kropka equals otwórz nawias okrągły cudzysłów otwórz nawias okrągły cudzysłów zamknij nawias okrągły zamknij nawias okrągły return 0 średnik. Linia 16. else if otwórz nawias okrągły znak kropka equals otwórz nawias okrągły cudzysłów plus cudzysłów zamknij nawias okrągły kreska pionowa kreska pionowa znak kropka equals otwórz nawias okrągły cudzysłów minus cudzysłów zamknij nawias okrągły zamknij nawias okrągły return 1 średnik. Linia 17. else if otwórz nawias okrągły znak kropka equals otwórz nawias okrągły cudzysłów asterysk cudzysłów zamknij nawias okrągły kreska pionowa kreska pionowa znak kropka equals otwórz nawias okrągły cudzysłów prawy ukośnik cudzysłów zamknij nawias okrągły kreska pionowa kreska pionowa znak kropka equals otwórz nawias okrągły cudzysłów procent cudzysłów zamknij nawias okrągły zamknij nawias okrągły return 2 średnik. Linia 18. else if otwórz nawias okrągły znak kropka equals otwórz nawias okrągły cudzysłów kareta cudzysłów zamknij nawias okrągły zamknij nawias okrągły return 3 średnik. Linia 19. return minus 1 średnik. Linia 20. zamknij nawias klamrowy. Linia 22. public static String konwertujDoOnp otwórz nawias okrągły String wyrazenie zamknij nawias okrągły otwórz nawias klamrowy. Linia 23. Deque otwórz nawias ostrokątny String zamknij nawias ostrokątny stos znak równości new ArrayDeque otwórz nawias ostrokątny zamknij nawias ostrokątny otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 24. String wynik znak równości cudzysłów cudzysłów średnik. Linia 25. String znak znak równości cudzysłów cudzysłów średnik. Linia 27. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny 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 28. znak znak równości String kropka valueOf otwórz nawias okrągły wyrazenie kropka charAt otwórz nawias okrągły i zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 29. if otwórz nawias okrągły znak kropka equals otwórz nawias okrągły cudzysłów cudzysłów zamknij nawias okrągły 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 30. wynik plus znak równości znak średnik. Linia 31. zamknij nawias klamrowy else if otwórz nawias okrągły znak kropka equals otwórz nawias okrągły cudzysłów otwórz nawias okrągły cudzysłów zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 32. stos kropka push otwórz nawias okrągły znak zamknij nawias okrągły średnik. Linia 33. zamknij nawias klamrowy else if otwórz nawias okrągły znak kropka equals otwórz nawias okrągły cudzysłów zamknij nawias okrągły cudzysłów zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 34. while otwórz nawias okrągły wykrzyknik stos kropka getFirst otwórz nawias okrągły zamknij nawias okrągły kropka equals otwórz nawias okrągły cudzysłów otwórz nawias okrągły cudzysłów zamknij nawias okrągły zamknij nawias okrągły. Linia 35. wynik plus znak równości cudzysłów cudzysłów plus stos kropka pop otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 36. stos kropka pop otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 37. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 38. while otwórz nawias okrągły wykrzyknik stos kropka isEmpty otwórz nawias okrągły zamknij nawias okrągły ampersant ampersant otwórz nawias okrągły priorytet otwórz nawias okrągły stos kropka getFirst 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 39. wynik plus znak równości stos kropka pop otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 40. stos kropka push otwórz nawias okrągły znak zamknij nawias okrągły średnik. Linia 41. zamknij nawias klamrowy. Linia 42. zamknij nawias klamrowy. Linia 44. while otwórz nawias okrągły wykrzyknik stos kropka isEmpty otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 45. wynik plus znak równości cudzysłów cudzysłów plus stos kropka pop otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 46. zamknij nawias klamrowy. Linia 48. return wynik średnik. Linia 49. zamknij nawias klamrowy. Linia 51. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 52. 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 53. System kropka out kropka println otwórz nawias okrągły cudzysłów Wyrażenie infiksowe dwukropek cudzysłów plus wyrazenie zamknij nawias okrągły średnik. Linia 54. String wynik znak równości konwertujDoOnp otwórz nawias okrągły wyrazenie zamknij nawias okrągły średnik. Linia 55. System kropka out kropka println otwórz nawias okrągły cudzysłów Wyrażenie postfiksowe dwukropek cudzysłów plus wynik zamknij nawias okrągły średnik. Linia 56. zamknij nawias klamrowy. Linia 57. zamknij nawias klamrowy.

import java.util.Deque;
import java.util.ArrayDeque;

public class StosListaOnpJF {

    public static boolean czyOperator(String znak) {
        if (znak.equals("(") || znak.equals(")") || znak.equals("+") ||
            znak.equals("-") || znak.equals("*") || znak.equals("/") ||
            znak.equals("%") || znak.equals("^"))
            return true;
        return false;
    }

    public static int priorytet(String znak) {
        if (znak.equals("(")) return 0;
        else if (znak.equals("+") || znak.equals("-")) return 1;
        else if (znak.equals("*") || znak.equals("/") || znak.equals("%")) return 2;
        else if (znak.equals("^")) return 3;
        return -1;
    }

    public static String konwertujDoOnp(String wyrazenie) {
        Deque<String> stos = new ArrayDeque<>();
        String wynik = "";
        String znak = "";

        for (int i=0; i < wyrazenie.length(); i++) {
            znak = String.valueOf(wyrazenie.charAt(i));
            if (znak.equals(" ") || !czyOperator(znak)) {
                wynik += znak;
            } else if (znak.equals("(")) {
                stos.push(znak);
            } else if (znak.equals(")")) {
                while (!stos.getFirst().equals("("))
                    wynik += " " + stos.pop();
                stos.pop();
            } else {
                while (!stos.isEmpty() && (priorytet(stos.getFirst()) >= priorytet(znak)))
                    wynik += stos.pop();
                stos.push(znak);
            }
        }

        while (!stos.isEmpty()) {
            wynik += " " + stos.pop();
        }

        return wynik;
    }

    public static void main(String[] args) {
        String wyrazenie = "(31 + 4) * 7";
        System.out.println("Wyrażenie infiksowe: " + wyrazenie);
        String wynik = konwertujDoOnp(wyrazenie);
        System.out.println("Wyrażenie postfiksowe: " + wynik);
    }
}

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

R1aRyhAub6QD21

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

Rf6CTDDuJei2R

Linia 1. class Wezel otwórz nawias klamrowy. Linia 2. int pozycja średnik. Linia 3. Wezel nastepny średnik. Linia 4. Wezel poprzedni średnik. Linia 5. Wezel otwórz nawias okrągły int pozycja zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. this kropka pozycja znak równości pozycja średnik. Linia 7. this kropka nastepny znak równości null średnik. Linia 8. this kropka poprzedni znak równości null średnik. Linia 9. zamknij nawias klamrowy. Linia 10. zamknij nawias klamrowy. Linia 12. class Lista otwórz nawias klamrowy. Linia 13. Wezel glowa średnik. Linia 15. public Lista otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 16. glowa znak równości null średnik. Linia 17. zamknij nawias klamrowy. Linia 19. public Wezel przejdz otwórz nawias okrągły int o podkreślnik ile przecinek Wezel wezel zamknij nawias okrągły otwórz nawias klamrowy. Linia 20. Wezel pomocniczy znak równości wezel średnik. Linia 21. if otwórz nawias okrągły wezel znak równości znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 22. pomocniczy znak równości glowa średnik. Linia 23. zamknij nawias klamrowy. Linia 25. 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 26. pomocniczy znak równości pomocniczy kropka nastepny średnik. Linia 27. zamknij nawias klamrowy. Linia 29. return pomocniczy średnik. Linia 30. zamknij nawias klamrowy. Linia 32. public void dodaj otwórz nawias okrągły int pozycja zamknij nawias okrągły otwórz nawias klamrowy. Linia 33. Wezel nowy znak równości new Wezel otwórz nawias okrągły pozycja zamknij nawias okrągły średnik. Linia 35. if otwórz nawias okrągły glowa znak równości znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 36. glowa znak równości nowy średnik. Linia 37. glowa kropka nastepny znak równości glowa kropka poprzedni znak równości glowa średnik. Linia 38. return średnik. Linia 39. zamknij nawias klamrowy. Linia 41. Wezel ostatni znak równości glowa kropka poprzedni średnik. Linia 42. nowy kropka nastepny znak równości glowa średnik. Linia 43. nowy kropka poprzedni znak równości ostatni średnik. Linia 44. glowa kropka poprzedni znak równości nowy średnik. Linia 45. ostatni kropka nastepny znak równości nowy średnik. Linia 46. zamknij nawias klamrowy. Linia 48. public void usun otwórz nawias okrągły Wezel wezel zamknij nawias okrągły otwórz nawias klamrowy. Linia 49. wezel kropka nastepny kropka poprzedni znak równości wezel kropka poprzedni średnik. Linia 50. wezel kropka poprzedni kropka nastepny znak równości wezel kropka nastepny średnik. Linia 52. 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 53. if otwórz nawias okrągły glowa kropka nastepny wykrzyknik znak równości glowa zamknij nawias okrągły otwórz nawias klamrowy. Linia 54. glowa znak równości glowa kropka nastepny średnik. Linia 55. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 56. glowa znak równości null średnik. Linia 57. zamknij nawias klamrowy. Linia 58. zamknij nawias klamrowy. Linia 59. zamknij nawias klamrowy. Linia 61. public void wypisz otwórz nawias okrągły int n zamknij nawias okrągły otwórz nawias klamrowy. Linia 62. Wezel pomocniczy znak równości glowa średnik. Linia 63. while otwórz nawias okrągły n zamknij nawias ostrokątny 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 64. System kropka out kropka print otwórz nawias okrągły pomocniczy kropka pozycja plus cudzysłów cudzysłów zamknij nawias okrągły średnik. Linia 65. pomocniczy znak równości pomocniczy kropka nastepny średnik. Linia 66. n minus minus średnik. Linia 67. zamknij nawias klamrowy. Linia 68. System kropka out kropka println otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 69. zamknij nawias klamrowy. Linia 70. zamknij nawias klamrowy. Linia 72. public class Lista2Flawiusz otwórz nawias klamrowy. Linia 73. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 74. Lista lista znak równości new Lista otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 75. int n znak równości 8 średnik. Linia 76. int k znak równości 3 średnik. Linia 78. 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. Linia 79. lista kropka dodaj otwórz nawias okrągły i zamknij nawias okrągły średnik. Linia 81. Wezel wezel znak równości lista kropka przejdz otwórz nawias okrągły k minus 1 przecinek null zamknij nawias okrągły średnik. Linia 82. while otwórz nawias okrągły wezel kropka nastepny wykrzyknik znak równości wezel zamknij nawias okrągły otwórz nawias klamrowy. Linia 83. lista kropka wypisz otwórz nawias okrągły n minus minus zamknij nawias okrągły średnik. Linia 84. lista kropka usun otwórz nawias okrągły wezel zamknij nawias okrągły średnik. Linia 85. wezel znak równości lista kropka przejdz otwórz nawias okrągły k przecinek wezel zamknij nawias okrągły średnik. Linia 86. zamknij nawias klamrowy. Linia 88. System kropka out kropka println otwórz nawias okrągły wezel kropka pozycja zamknij nawias okrągły średnik. Linia 89. zamknij nawias klamrowy. Linia 90. zamknij nawias klamrowy.

class Wezel {
    int pozycja;
    Wezel nastepny;
    Wezel poprzedni;
    Wezel(int pozycja) {
        this.pozycja = pozycja;
        this.nastepny = null;
        this.poprzedni = null;
    }
}

class Lista {
    Wezel glowa;

    public Lista() {
        glowa = null;
    }

    public Wezel przejdz(int o_ile, Wezel wezel) {
        Wezel pomocniczy = wezel;
        if (wezel == null) {
            pomocniczy = glowa;
        }

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

        return pomocniczy;
    }

    public void dodaj(int pozycja) {
        Wezel nowy = new Wezel(pozycja);

        if (glowa == null) {
            glowa = nowy;
            glowa.nastepny = glowa.poprzedni = glowa;
            return;
        }

        Wezel ostatni = glowa.poprzedni;
        nowy.nastepny = glowa;
        nowy.poprzedni = ostatni;
        glowa.poprzedni = nowy;
        ostatni.nastepny = nowy;
    }

    public void 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 = null;
            }
        }
    }

    public void wypisz(int n) {
        Wezel pomocniczy = glowa;
        while (n > 0) {
            System.out.print(pomocniczy.pozycja + " ");
            pomocniczy = pomocniczy.nastepny;
            n--;
        }
        System.out.println();
    }
}

public class Lista2Flawiusz {
    public static void main(String[] args) {
        Lista lista = new Lista();
        int n = 8;
        int k = 3;

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

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

        System.out.println(wezel.pozycja);
    }
}

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

RVhSBiS8gUG7P1

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", "Java".

Przykładowy wynik działania programu:

dynamiczne Struktury danych Java 
danych dynamiczne Java Struktury

RdCGclP30zcav

Linia 1. class Wezel otwórz nawias klamrowy. Linia 2. String wyraz średnik. Linia 3. Wezel nastepny średnik. Linia 4. Wezel poprzedni średnik. Linia 5. Wezel otwórz nawias okrągły String wyraz zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. this kropka wyraz znak równości wyraz średnik. Linia 7. this kropka nastepny znak równości null średnik. Linia 8. this kropka poprzedni znak równości null średnik. Linia 9. zamknij nawias klamrowy. Linia 10. zamknij nawias klamrowy. Linia 12. class Lista otwórz nawias klamrowy. Linia 13. Wezel glowa średnik. Linia 14. Wezel ogon średnik. Linia 16. public Lista otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 17. glowa znak równości ogon znak równości null średnik. Linia 18. zamknij nawias klamrowy. Linia 20. public void dodaj otwórz nawias okrągły String wyraz zamknij nawias okrągły otwórz nawias klamrowy. Linia 21. Wezel nowy znak równości new Wezel otwórz nawias okrągły wyraz zamknij nawias okrągły średnik. Linia 23. if otwórz nawias okrągły glowa znak równości znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 24. glowa znak równości ogon znak równości nowy średnik. Linia 25. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 26. ogon kropka nastepny znak równości nowy średnik. Linia 27. nowy kropka poprzedni znak równości ogon średnik. Linia 28. ogon znak równości nowy średnik. Linia 29. zamknij nawias klamrowy. Linia 30. zamknij nawias klamrowy. Linia 32. public void usun otwórz nawias okrągły Wezel wezel zamknij nawias okrągły otwórz nawias klamrowy. Linia 33. if otwórz nawias okrągły wezel znak równości znak równości glowa ampersant ampersant glowa kropka nastepny wykrzyknik znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 34. glowa znak równości glowa kropka nastepny średnik. Linia 35. glowa kropka poprzedni znak równości null średnik. Linia 36. return średnik. Linia 37. zamknij nawias klamrowy. Linia 39. 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 40. wezel kropka poprzedni kropka nastepny znak równości null średnik. Linia 41. ogon znak równości wezel kropka poprzedni średnik. Linia 42. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 43. wezel kropka poprzedni kropka nastepny znak równości wezel kropka nastepny średnik. Linia 44. wezel kropka nastepny kropka poprzedni znak równości wezel kropka poprzedni średnik. Linia 45. zamknij nawias klamrowy. Linia 46. zamknij nawias klamrowy. Linia 48. public int porownaj otwórz nawias okrągły Wezel wezel podkreślnik 1 przecinek Wezel wezel podkreślnik 2 zamknij nawias okrągły otwórz nawias klamrowy. Linia 49. String wyraz podkreślnik 1 znak równości wezel podkreślnik 1 kropka wyraz kropka toLowerCase otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 50. String wyraz podkreślnik 2 znak równości wezel podkreślnik 2 kropka wyraz kropka toLowerCase otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 51. return wyraz podkreślnik 1 kropka compareTo otwórz nawias okrągły wyraz podkreślnik 2 zamknij nawias okrągły średnik. Linia 52. zamknij nawias klamrowy. Linia 54. public void sortuj otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 55. Wezel pomocniczy znak równości glowa średnik. Linia 56. int i znak równości 0 średnik. Linia 57. while otwórz nawias okrągły true zamknij nawias okrągły otwórz nawias klamrowy. Linia 58. if otwórz nawias okrągły pomocniczy kropka nastepny znak równości znak równości null zamknij nawias okrągły. Linia 59. break średnik. Linia 60. if otwórz nawias okrągły porownaj otwórz nawias okrągły pomocniczy przecinek pomocniczy kropka nastepny zamknij nawias okrągły zamknij nawias ostrokątny 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 61. usun otwórz nawias okrągły pomocniczy zamknij nawias okrągły średnik. Linia 62. wstaw otwórz nawias okrągły pomocniczy zamknij nawias okrągły średnik. Linia 63. pomocniczy znak równości glowa średnik. Linia 64. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 65. pomocniczy znak równości pomocniczy kropka nastepny średnik. Linia 66. zamknij nawias klamrowy. Linia 67. zamknij nawias klamrowy. Linia 68. zamknij nawias klamrowy. Linia 70. public void wstaw otwórz nawias okrągły Wezel wezel zamknij nawias okrągły otwórz nawias klamrowy. Linia 71. Wezel pomocniczy znak równości wezel kropka nastepny średnik. Linia 72. 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 kropka 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 73. pomocniczy znak równości pomocniczy kropka nastepny średnik. Linia 74. zamknij nawias klamrowy. Linia 76. 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 77. wezel kropka nastepny znak równości null średnik. Linia 78. wezel kropka poprzedni znak równości ogon średnik. Linia 79. ogon kropka nastepny znak równości wezel średnik. Linia 80. ogon znak równości wezel średnik. Linia 81. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 82. wezel kropka poprzedni znak równości pomocniczy średnik. Linia 83. wezel kropka nastepny znak równości pomocniczy kropka nastepny średnik. Linia 84. pomocniczy kropka nastepny kropka poprzedni znak równości wezel średnik. Linia 85. pomocniczy kropka nastepny znak równości wezel średnik. Linia 86. zamknij nawias klamrowy. Linia 87. zamknij nawias klamrowy. Linia 89. public void wypisz otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 90. Wezel pomocniczy znak równości glowa średnik. Linia 91. while otwórz nawias okrągły pomocniczy wykrzyknik znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 92. System kropka out kropka print otwórz nawias okrągły pomocniczy kropka wyraz plus cudzysłów cudzysłów zamknij nawias okrągły średnik. Linia 93. pomocniczy znak równości pomocniczy kropka nastepny średnik. Linia 94. zamknij nawias klamrowy. Linia 95. System kropka out kropka println otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 96. zamknij nawias klamrowy. Linia 97. zamknij nawias klamrowy. Linia 99. public class TesterkaSort otwórz nawias klamrowy. Linia 100. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 101. 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 Java cudzysłów zamknij nawias klamrowy średnik. Linia 103. Lista lista znak równości new Lista otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 104. for otwórz nawias okrągły int i znak równości 0 średnik i otwórz nawias ostrokątny dane kropka length średnik i plus plus zamknij nawias okrągły. Linia 105. 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 107. lista kropka wypisz otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 108. lista kropka sortuj otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 109. lista kropka wypisz otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 110. zamknij nawias klamrowy. Linia 111. zamknij nawias klamrowy.

class Wezel {
    String wyraz;
    Wezel nastepny;
    Wezel poprzedni;
    Wezel(String wyraz) {
        this.wyraz = wyraz;
        this.nastepny = null;
        this.poprzedni = null;
    }
}

class Lista {
    Wezel glowa;
    Wezel ogon;

    public Lista() {
        glowa = ogon = null;
    }

    public void dodaj(String wyraz) {
        Wezel nowy = new Wezel(wyraz);

        if (glowa == null) {
            glowa = ogon = nowy;
        } else {
            ogon.nastepny = nowy;
            nowy.poprzedni = ogon;
            ogon = nowy;
        }
    }

    public void usun(Wezel wezel) {
        if (wezel == glowa && glowa.nastepny != null) {
            glowa = glowa.nastepny;
            glowa.poprzedni = null;
            return;
        }

        if (wezel == ogon) {
            wezel.poprzedni.nastepny = null;
            ogon = wezel.poprzedni;
        } else {
            wezel.poprzedni.nastepny = wezel.nastepny;
            wezel.nastepny.poprzedni = wezel.poprzedni;
        }
    }

    public int porownaj(Wezel wezel_1, Wezel wezel_2) {
        String wyraz_1 = wezel_1.wyraz.toLowerCase();
        String wyraz_2 = wezel_2.wyraz.toLowerCase();
        return wyraz_1.compareTo(wyraz_2);
    }

    public void sortuj() {
        Wezel pomocniczy = glowa;
        int i = 0;
        while (true) {
            if (pomocniczy.nastepny == null)
                break;
            if (porownaj(pomocniczy, pomocniczy.nastepny) > 0) {
                usun(pomocniczy);
                wstaw(pomocniczy);
                pomocniczy = glowa;
            } else {
                pomocniczy = pomocniczy.nastepny;
            }
        }
    }

    public void wstaw(Wezel wezel) {
        Wezel pomocniczy = wezel.nastepny;
        while (pomocniczy != ogon && porownaj(wezel, pomocniczy.nastepny) >= 0) {
            pomocniczy = pomocniczy.nastepny;
        }

        if (pomocniczy == ogon) {
            wezel.nastepny = null;
            wezel.poprzedni = ogon;
            ogon.nastepny = wezel;
            ogon = wezel;
        } else {
            wezel.poprzedni = pomocniczy;
            wezel.nastepny = pomocniczy.nastepny;
            pomocniczy.nastepny.poprzedni = wezel;
            pomocniczy.nastepny = wezel;
        }
    }

    public void wypisz() {
        Wezel pomocniczy = glowa;
        while (pomocniczy != null) {
            System.out.print(pomocniczy.wyraz + " ");
            pomocniczy = pomocniczy.nastepny;
        }
        System.out.println();
    }
}

public class TesterkaSort {
    public static void main(String[] args) {
        String dane[] = {"dynamiczne", "Struktury", "danych", "Java"};

        Lista lista = new Lista();
        for (int i = 0; i < dane.length; i++)
            lista.dodaj(dane[i]);

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

Przeczytaj

Sprawdź się