Zadania

  1. (2025-04-14) bst.c, bst.h - stwórz implementację binarnego drzewa przeszukiwań, które wspiera następujące operacje:

    1. bst* bst_search(bst *node, int key) - wyszukiwanie metodą iteracyjną klucza w drzewie

    2. bst* bst_insert(bst* node, int value) - wstawianie wartości do drzewa

    3. void bst_free(bst* node); - dealokuje całe drzewo

    4. int bst_depth(bst* node); - zwraca głębokość drzewa

    5. void bst_print(bst* node); - wypisuje klucze metodą in-order

  2. (2025-04-14) bst_demo.c - stwórz program, który demonstruje stworząną bibliotekę bst.h poprzez:

    1. Pobiera wartość n, będącej górną granicą wartości dla których będzie program badał zachowanie drzewa

    2. Losuje n/2 wartości od 0 do n i zapisuje je w tablicy test (mogą się powtarzać)

    3. Następnie dla kolejności rosnącej, malejącej i losowej:

      1. Tworzy nowe drzewo, dodaje do niego liczby od 0 do n według wybranej kolejności i mierzy czas jaki zajęło dodanie wszystkich liczb do drzewa

      2. Wyszukuje wszystkie wartości z test i mierzy czas jaka zajęła ta operacja

      3. Dealokuje drzewo i mierzy czas jaki zajęła ta operacja

  3. stack.c - stwórz dwie implementacje stosu (listowa i tablicowa) i porównaj ich wydajność (stworzenie testu wykazującego wyższość jednej z implementacji nad drugą pozostawione osobie studenckiej)

Przykład wywołania bst_demo.c
$ ./bst_demo
test with values from 0 to: 100

Order: increasing
Insertion took: 214214213 ms
Search took: 4213213 ms
Deallocation took: 123213 ms

Order: decreasing
Insertion took: 214214213 ms
Search took: 4213213 ms
Deallocation took: 123213 ms

Order: random
Insertion took: 214214213 ms
Search took: 4213213 ms
Deallocation took: 123213 ms

Liczby pseudolosowe

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

int main()
{
  srand(time(NULL));

  for (int i = 0; i < 10; ++i) {
    printf("%d\n", rand());
  }

  return 0;
}

Pomiar czasu

#include <stdio.h>
#include <time.h>
#include <unistd.h>

int main()
{
  struct timespec start, finish;

  if (clock_gettime(CLOCK_MONOTONIC, &start) < 0) {
    printf("couldn't measure time\n");
    return 1;
  }

  sleep(3);

  if (clock_gettime(CLOCK_MONOTONIC, &finish) < 0) {
    printf("couldn't measure time\n");
    return 1;
  }

  int seconds = finish.tv_sec - start.tv_sec;
  int nanoseconds = finish.tv_nsec - start.tv_nsec;
  double miliseconds = seconds * 1000.0 + nanoseconds / 1000000.0;

  printf("sleep(3) took: %.3fms\n", miliseconds);
  return 0;
}

Dlaczego nie time_t time(time_t *tloc):

  • słaba rozdzielczość przy dzisiejszej prędkości obliczeń - sekundy

  • wrażliwy na zmiany czasu systemowego (zmiany na czas letni/zimowy, strefy czasowej czy zmiany przez użytkownika)

Wskaźnikowe struktury danych

Lista jednokierunkowa:

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

typedef struct node {
  int value;
  struct node *next;
} node_t;

node_t* init(int *xs, int n)
{
  if (n == 0) {
    return NULL;
  }

  node_t *root, *p;
  root = p = malloc(sizeof(node_t));

  for (int i = 0; i < n; ++i) {
    p->value = xs[i];
    if (i+1 < n) {
      p->next = malloc(sizeof(node_t));
      p = p->next;
    }
  }

  p->next = NULL;
  return root;
}

void print(node_t *head)
{
  for (node_t *p = head; p != NULL; p = p->next) {
    printf("%d\n", p->value);
  }
}

void deinit(node_t *list)
{
  for (node_t *p = list; p != NULL;) {
    node_t *next = p->next;
    free(p);
    p = next;
  }
}

int main()
{
  int xs[] = {1,2,3,4,5,6};

  node_t *list = init(xs, sizeof(xs) / sizeof(xs[0]));
  print(list);
  deinit(list);

  return 0;
}