Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #include <time.h>
- #define MAX 10 // Maksimalna visina skip liste
- // Struktura za povezanu listu
- typedef struct cvor {
- int x;
- struct cvor *sljedeci;
- } cvor;
- // Funkcija za dodavanje elementa u povezanu listu
- void dodajUListu(cvor **glava, int vrijednost) {
- cvor *novi = (cvor *)malloc(sizeof(cvor));
- novi->x = vrijednost;
- novi->sljedeci = *glava;
- *glava = novi;
- }
- // Funkcija za pretraživanje u povezanoj listi
- int pretraziListu(cvor *glava, int vrijednost) {
- while (glava) {
- if (glava->x == vrijednost)
- return 1;
- glava = glava->sljedeci;
- }
- return 0;
- }
- // Struktura za skip listu
- typedef struct skipCvor {
- int x;
- int visina;
- struct skipCvor *sljedeci[MAX];
- } skipCvor;
- typedef struct skipLista {
- skipCvor *header;
- int razine;
- } skipLista;
- // Funkcija za stvaranje novog cvora u skip listi
- skipCvor *noviSkipCvor(int vrijednost, int visina) {
- skipCvor *novi = (skipCvor *)malloc(sizeof(skipCvor));
- novi->x = vrijednost;
- novi->visina = visina;
- for (int i = 0; i < MAX; i++) {
- novi->sljedeci[i] = NULL;
- }
- return novi;
- }
- // Funkcija za stvaranje skip liste
- skipLista *stvaranjeSkipListe() {
- skipLista *lista = (skipLista *)malloc(sizeof(skipLista));
- lista->header = noviSkipCvor(-1, MAX);
- lista->razine = 0;
- return lista;
- }
- // Funkcija za generiranje visine za čvor
- int generirajVisinu() {
- int visina = 1;
- while (rand() % 2 == 0 && visina < MAX) {
- visina++;
- }
- return visina;
- }
- // Funkcija za dodavanje elementa u skip listu
- void dodajUSkipListu(skipLista *lista, int vrijednost) {
- skipCvor *trenutni = lista->header;
- skipCvor *put[MAX];
- for (int i = lista->razine - 1; i >= 0; i--) {
- while (trenutni->sljedeci[i] && trenutni->sljedeci[i]->x < vrijednost) {
- trenutni = trenutni->sljedeci[i];
- }
- put[i] = trenutni;
- }
- int visina = generirajVisinu();
- if (visina > lista->razine) {
- for (int i = lista->razine; i < visina; i++) {
- put[i] = lista->header;
- }
- lista->razine = visina;
- }
- skipCvor *novi = noviSkipCvor(vrijednost, visina);
- for (int i = 0; i < visina; i++) {
- novi->sljedeci[i] = put[i]->sljedeci[i];
- put[i]->sljedeci[i] = novi;
- }
- }
- // Funkcija za pretraživanje u skip listi
- int pretraziSkipListu(skipLista *lista, int vrijednost) {
- skipCvor *trenutni = lista->header;
- for (int i = lista->razine - 1; i >= 0; i--) {
- while (trenutni->sljedeci[i] && trenutni->sljedeci[i]->x < vrijednost) {
- trenutni = trenutni->sljedeci[i];
- }
- }
- trenutni = trenutni->sljedeci[0];
- return (trenutni && trenutni->x == vrijednost);
- }
- int main() {
- srand(time(NULL));
- int N = 100000; // Broj elemenata
- cvor *glava = NULL;
- skipLista *skip = stvaranjeSkipListe();
- time_t t1, t2;
- // Formiranje povezane liste
- t1 = clock();
- for (int i = 0; i < N; i++) {
- dodajUListu(&glava, rand() % (N * 10));
- }
- t2 = clock();
- printf("Formiranje povezane liste: %ldms\n", (t2 - t1));
- // Formiranje skip liste
- t1 = clock();
- for (int i = 0; i < N; i++) {
- dodajUSkipListu(skip, rand() % (N * 10));
- }
- t2 = clock();
- printf("Formiranje skip liste: %ldms\n", (t2 - t1));
- // Pretraživanje u povezanoj listi
- t1 = clock();
- for (int i = 0; i < 1000; i++) {
- pretraziListu(glava, rand() % (N * 10));
- }
- t2 = clock();
- printf("Pretraživanje u povezanoj listi: %ldms\n", (t2 - t1));
- // Pretraživanje u skip listi
- t1 = clock();
- for (int i = 0; i < 1000; i++) {
- pretraziSkipListu(skip, rand() % (N * 10));
- }
- t2 = clock();
- printf("Pretraživanje u skip listi: %ldms\n", (t2 - t1));
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement