Advertisement
KonaJjr

NAISP_LV4

Jan 16th, 2025
41
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 3.93 KB | None | 0 0
  1.  #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4.  
  5. #define MAX 10 // Maksimalna visina skip liste
  6.  
  7. // Struktura za povezanu listu
  8. typedef struct cvor {
  9.     int x;
  10.     struct cvor *sljedeci;
  11. } cvor;
  12.  
  13. // Funkcija za dodavanje elementa u povezanu listu
  14. void dodajUListu(cvor **glava, int vrijednost) {
  15.     cvor *novi = (cvor *)malloc(sizeof(cvor));
  16.     novi->x = vrijednost;
  17.     novi->sljedeci = *glava;
  18.     *glava = novi;
  19. }
  20.  
  21. // Funkcija za pretraživanje u povezanoj listi
  22. int pretraziListu(cvor *glava, int vrijednost) {
  23.     while (glava) {
  24.         if (glava->x == vrijednost)
  25.             return 1;
  26.         glava = glava->sljedeci;
  27.     }
  28.     return 0;
  29. }
  30.  
  31. // Struktura za skip listu
  32. typedef struct skipCvor {
  33.     int x;
  34.     int visina;
  35.     struct skipCvor *sljedeci[MAX];
  36. } skipCvor;
  37.  
  38. typedef struct skipLista {
  39.     skipCvor *header;
  40.     int razine;
  41. } skipLista;
  42.  
  43. // Funkcija za stvaranje novog cvora u skip listi
  44. skipCvor *noviSkipCvor(int vrijednost, int visina) {
  45.     skipCvor *novi = (skipCvor *)malloc(sizeof(skipCvor));
  46.     novi->x = vrijednost;
  47.     novi->visina = visina;
  48.     for (int i = 0; i < MAX; i++) {
  49.         novi->sljedeci[i] = NULL;
  50.     }
  51.     return novi;
  52. }
  53.  
  54. // Funkcija za stvaranje skip liste
  55. skipLista *stvaranjeSkipListe() {
  56.     skipLista *lista = (skipLista *)malloc(sizeof(skipLista));
  57.     lista->header = noviSkipCvor(-1, MAX);
  58.     lista->razine = 0;
  59.     return lista;
  60. }
  61.  
  62. // Funkcija za generiranje visine za čvor
  63. int generirajVisinu() {
  64.     int visina = 1;
  65.     while (rand() % 2 == 0 && visina < MAX) {
  66.         visina++;
  67.     }
  68.     return visina;
  69. }
  70.  
  71. // Funkcija za dodavanje elementa u skip listu
  72. void dodajUSkipListu(skipLista *lista, int vrijednost) {
  73.     skipCvor *trenutni = lista->header;
  74.     skipCvor *put[MAX];
  75.     for (int i = lista->razine - 1; i >= 0; i--) {
  76.         while (trenutni->sljedeci[i] && trenutni->sljedeci[i]->x < vrijednost) {
  77.             trenutni = trenutni->sljedeci[i];
  78.         }
  79.         put[i] = trenutni;
  80.     }
  81.  
  82.     int visina = generirajVisinu();
  83.     if (visina > lista->razine) {
  84.         for (int i = lista->razine; i < visina; i++) {
  85.             put[i] = lista->header;
  86.         }
  87.         lista->razine = visina;
  88.     }
  89.  
  90.     skipCvor *novi = noviSkipCvor(vrijednost, visina);
  91.     for (int i = 0; i < visina; i++) {
  92.         novi->sljedeci[i] = put[i]->sljedeci[i];
  93.         put[i]->sljedeci[i] = novi;
  94.     }
  95. }
  96.  
  97. // Funkcija za pretraživanje u skip listi
  98. int pretraziSkipListu(skipLista *lista, int vrijednost) {
  99.     skipCvor *trenutni = lista->header;
  100.     for (int i = lista->razine - 1; i >= 0; i--) {
  101.         while (trenutni->sljedeci[i] && trenutni->sljedeci[i]->x < vrijednost) {
  102.             trenutni = trenutni->sljedeci[i];
  103.         }
  104.     }
  105.     trenutni = trenutni->sljedeci[0];
  106.     return (trenutni && trenutni->x == vrijednost);
  107. }
  108.  
  109. int main() {
  110.     srand(time(NULL));
  111.  
  112.     int N = 100000; // Broj elemenata
  113.     cvor *glava = NULL;
  114.     skipLista *skip = stvaranjeSkipListe();
  115.  
  116.     time_t t1, t2;
  117.  
  118.     // Formiranje povezane liste
  119.     t1 = clock();
  120.     for (int i = 0; i < N; i++) {
  121.         dodajUListu(&glava, rand() % (N * 10));
  122.     }
  123.     t2 = clock();
  124.     printf("Formiranje povezane liste: %ldms\n", (t2 - t1));
  125.  
  126.     // Formiranje skip liste
  127.     t1 = clock();
  128.     for (int i = 0; i < N; i++) {
  129.         dodajUSkipListu(skip, rand() % (N * 10));
  130.     }
  131.     t2 = clock();
  132.     printf("Formiranje skip liste: %ldms\n", (t2 - t1));
  133.  
  134.     // Pretraživanje u povezanoj listi
  135.     t1 = clock();
  136.     for (int i = 0; i < 1000; i++) {
  137.         pretraziListu(glava, rand() % (N * 10));
  138.     }
  139.     t2 = clock();
  140.     printf("Pretraživanje u povezanoj listi: %ldms\n", (t2 - t1));
  141.  
  142.     // Pretraživanje u skip listi
  143.     t1 = clock();
  144.     for (int i = 0; i < 1000; i++) {
  145.         pretraziSkipListu(skip, rand() % (N * 10));
  146.     }
  147.     t2 = clock();
  148.     printf("Pretraživanje u skip listi: %ldms\n", (t2 - t1));
  149.  
  150.     return 0;
  151. }
  152.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement