Zadanie dodatkowe

Za zadanie można otrzymać maksymalnie 5 punktów, którymi można zastąpić nieoddane/nisko ocenione prace domowe.

Kod rozwiązania proszę przesłać na mojego maila do 22 stycznia 23:59.

Treść zadania

Jedną strukturę danych można zaimplementować na różne sposoby. Przykładowo, tutaj zaimplementowaliśmy słownik z użyciem nieposortowanej tablicy. Ta implementacja ma swoje wady - szukanie danego klucza zajmuje czas liniowy względem liczby elementów w słowniku. Alternatywnym sposobem zaimplementowania słownika jest użycie posortowanej tablicy - i to jest celem tego zadania. W posortowanej tablicy możemy zastosować algorytm przeszukiwania binarnego, opisany poniżej - dzięki niemu czas szukania danego klucza jest logarytmiczny względem liczby elementów - czyli znacznie szybszy.

Polecam przeczytać opis algorytmu na wikipedii.

int binsearch(int x, int tab[], int size) { // szukamy liczby `x` w posortowanej rosnąco tablicy `tab` o długości `size`
    int left = 0;
    int right = size - 1;
    int mid;
    while (left <= right) {
        mid = (left + right) / 2; // patrzymy na element pośrodku między indeksami `left` oraz `right`
        if (x < tab[mid])
            right = mid - 1; // jeśli szukany element jest mniejszy od elementu na pozycji `mid`, to na pewno jest na lewo
        else if (x > tab[mid])
            left = mid + 1; // jeśli szukany element jest większy od elementu na pozycji `mid`, to na pewno jest na prawo
        else
            return 1; // jeśli znaleźliśmy dany element, to zwracamy `1`
    }
    return 0; // jeśli nie znaleźliśmy danego elementu, to zwracamy `0`
}

Żeby dodać nowy element, można na przykład dodać go na koniec tablicy i przesuwać go o 1 pozycję w lewo tak długo, aż znajdziemy jego prawidłową pozycję. Potem trzeba oczywiście zwiększyć dict_fill.

Żeby usunąć element, można na przykład znaleźć jego pozycję i przesuwać go o 1 pozycję w prawo tak długo, aż dotrzemy na koniec tablicy. Potem trzeba oczywiście zmniejszyć dict_fill.

Jako rozwiązanie proszę przesłać poniższy kod z uzupełnionymi sekcjami TODO. Można dodać pomocnicze funkcje, żeby uniknąć duplikowania kodu, ale nie jest to konieczne. Reszta kodu jest poprawna, proszę jej nie edytować - zależy mi na tym, żeby interfejs (czyli nagłówki funkcji i sposób ich użycia) tej struktury danych pozostał bez zmian.

Każde uzupełnione TODO jest warte 1 punkt, więc nawet jeśli nie macie całego rozwiązania, to nadal warto wysłać chociaż jego część.

#include <stdio.h>
#include <stdlib.h>

#define DICT_MAX_SIZE 100

/*
 * Definiujemy strukturę o nazwie `dictionary_element`, która zawiera dwa pola:
 * `key` - klucz, po którym będziemy szukali wpisów w słowniku
 * `value` - wartość, kóra jest przyporządkowana danemu kluczowi
 */
typedef struct {
    int key;
    float value;
} dictionary_element;

/*
 * Deklaracja to sam nagłówek funkcji zakończony średnikiem, tzn `typ_zwracany nazwa(lista argumentów);`
 *
 * Podział na deklaracje i definicje to podział na to CO dany program robi i JAK to robi.
 * Ten podział ułatwia czytanie i pisanie większych projektów - najpierw ustalamy interfejs,
 * czyli CO jakaś część programu robi, a dopiero później piszemy JAK to robi.
 *
 * Dużą zaletą tego rozwiązania jest wymuszenie na programistach, żeby polegali jedynie na tym CO dana funkcja robi.
 * Przykładowo używamy `scanf` i `printf`, a nie musimy wiedzieć, JAK one działają. Co więcej, ich implamentacja może
 * się zmieniać (np w zależności od systemu operacyjnego), a dla nas nie będzie to miało znaczenia. Tutaj jest podobnie,
 * tzn używając słownika nie musimy martwić się o to jak on działa, wystarczy, że znamy funkcje do jego obsługi.
 */

// Deklaracje funkcji do obsługi słownika

// Inicjalizuje nowy słownik
void dict_init(dictionary_element dict[], int *dict_fill);

// Dodaje element `elem` do słownika, jeśli element już istnieje, to wypisuje błąd
void dict_add(dictionary_element dict[], int *dict_fill, dictionary_element elem);

// Sprawdza, czy dany klucz `key` jest w słowniku, jeśli tak, to zwraca 1, w przeciwnym wypadku zwraca 0
int dict_contains(dictionary_element dict[], int *dict_fill, int key);

// Zwraca wartość przyporządkowaną danemu kluczowi `key`, lub 0.0, jeśli klucza nie ma w słowniku
float dict_get(dictionary_element dict[], int *dict_fill, int key);

// Usuwa wpis o danym kluczu `key` ze słownika
void dict_remove(dictionary_element dict[], int *dict_fill, int key);



// Definicje funkcji do obsługi słownika

void dict_init(dictionary_element dict[], int *dict_fill) {
    // TODO
}

void dict_add(dictionary_element dict[], int *dict_fill, dictionary_element elem) {
    // TODO
}

int dict_contains(dictionary_element dict[], int *dict_fill, int key) {
    // TODO
}

float dict_get(dictionary_element dict[], int *dict_fill, int key) {
    // TODO
}

void dict_remove(dictionary_element dict[], int *dict_fill, int key) {
    // TODO
}

int main() {
    dictionary_element dict[DICT_MAX_SIZE];
    int dict_fill;

    dict_init(dict, &dict_fill);

    dictionary_element elem1 = {.key = 5, .value = 6.5};
    dictionary_element elem2 = {.key = 123456789, .value = 1.23};
    dictionary_element elem3 = {.key = -13, .value = 1.0};
    dictionary_element elem4 = {.key = -13, .value = 2.0};

    dict_add(dict, &dict_fill, elem1); // dodajemy pierwszy element
    dict_add(dict, &dict_fill, elem2); // dodajemy drugi element
    dict_add(dict, &dict_fill, elem3); // dodajemy trzeci element
    dict_add(dict, &dict_fill, elem4); // tutaj próbujemy dodać element z kluczem, który już jest w słowniku - dostaniemy błąd

    // wartość przyporządkowana kluczowi `-13` to nadal `1.0`
    printf("Dictionary element: %d -> %f\n", -13, dict_get(dict, &dict_fill, -13));

    // w słowniku mamy klucz `5`
    printf("Dictionary element: %d -> %f\n", 5, dict_get(dict, &dict_fill, 5));

    // usuwamy klucz `5`
    dict_remove(dict, &dict_fill, 5);

    // teraz w słowniku nie ma już klucza `5` - przy próbie znalezienia go dostaniemy błąd
    printf("Dictionary element: %d -> %f\n", 5, dict_get(dict, &dict_fill, 5));

    return 0;
}