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;
}