N-ti čvor

Implementirati funkciju koja vraća pokazivač na n-ti čvor dvostruke povezane liste sa sentinel čvorom. N-ti čvor se broji sa početka liste ili od kraja liste u zavisnosti od znaka parametra n. Ako je n pozitivan, broji se od početka liste. Ako je n negativan, broji se od kraja liste. Ako n-ti čvor ne postoji, funkcija vraća NULL.

cvor *nti_cvor(cvor *sentinel, int n)

Ulaz

Sa standardnog ulaza se učitava ceo broj $n$, a zatim niz celih brojeva koji se smeštaju u dvostruku povezanu listu. Unos se završava kada se unese kraj ulaza (EOF).

Izlaz

Na standardni izlaz se ispisuje vrednost $n$-tog čvora ako postoji, ili NULL ako $n$-ti čvor ne postoji.

Primer

Ulaz

3
10 20 30 40 50

Izlaz

30

Primer

Ulaz

-2
10 20 30 40 50

Izlaz

40

Primer

Ulaz

10
10 20 30 40 50

Izlaz

NULL

Rešenje

lista.h

#ifndef DVOSTRUKO_POVEZANA_LISTA_H
#define DVOSTRUKO_POVEZANA_LISTA_H

typedef struct cvor {
    int podatak;
    struct cvor *prethodni;
    struct cvor *sledeci;
} cvor;

/* Kreira i inicijalizuje listu (sentinel-čvor). */
cvor *inicijalizuj_listu(void);

/* Kreira novi čvor povezan sa prethodnikom i sledbenikom. */
cvor *napravi_cvor(int x, cvor *pre, cvor *sli);

/* Briše dati čvor (pretpostavlja se da nije sentinel). */
void obrisi_cvor(cvor *cv);

/* Ubacivanje u odnosu na postojeći čvor. */
void ubaci_prethodni(cvor *cv, int x);
void ubaci_sledeci(cvor *cv, int x);

/* Ubacivanje na početak/kraj liste. */
void ubaci_na_pocetak(cvor *sentinel, int x);
void ubaci_na_kraj(cvor *sentinel, int x);

/* Provera praznine liste. */
int prazna(cvor *sentinel);

/* Ispis liste. */
void ispisi_listu(cvor *sentinel);

/* Brisanje svih elemenata (sentinel ostaje). */
void obrisi_listu(cvor *sentinel);

#endif

main.c

#include <stdio.h>
#include "lista.h"

cvor *nti_cvor(cvor *sentinel, int n)
{
	if (n > 0) {
		cvor *trenutni = sentinel->sledeci;

		for (int i = 1; i < n && trenutni != sentinel; i++) {
			trenutni = trenutni->sledeci;
		}

		if (trenutni == sentinel) {
			return NULL;
		}

		return trenutni;
	} else if (n < 0) {
		cvor *trenutni = sentinel->prethodni;

		for (int i = -1; i > n && trenutni != sentinel; i--) {
			trenutni = trenutni->prethodni;
		}

		if (trenutni == sentinel) {
			return NULL;
		}

		return trenutni;
	}
	
	return NULL; // n == 0 nije validan indeks
}

int main(void)
{
	cvor *lista = inicijalizuj_listu();
	if (lista == NULL) {
		fprintf(stderr, "Greska pri inicijalizaciji liste.\n");
		return 1;
	}

	int n;
	scanf("%d", &n);

	int x;
	while (scanf("%d", &x) == 1) {
		ubaci_na_kraj(lista, x);
	}

	cvor *rezultat = nti_cvor(lista, n);
	if (rezultat != NULL) {
		printf("%d\n", rezultat->podatak);
	} else {
		printf("NULL\n");
	}

	obrisi_listu(lista);

	return 0;
}

lista.c

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

cvor *inicijalizuj_listu(void)
{
    cvor *s = malloc(sizeof(cvor));
    if (s == NULL)
        return NULL;

    s->prethodni = s;
    s->sledeci   = s;
    return s;
}

/* Kreira novi čvor čije veze odmah postavljamo. */
cvor *napravi_cvor(int x, cvor *pre, cvor *sli)
{
    cvor *novi = malloc(sizeof(cvor));
    if (novi == NULL)
        return NULL;

    novi->podatak   = x;
    novi->prethodni = pre;
    novi->sledeci   = sli;
    return novi;
}

/* Briše čvor iz liste i oslobađa memoriju. */
void obrisi_cvor(cvor *cv)
{
    cv->prethodni->sledeci = cv->sledeci;
    cv->sledeci->prethodni = cv->prethodni;
    free(cv);
}

/* Ubacuje novi čvor pre cv. */
void ubaci_prethodni(cvor *cv, int x)
{
    cvor *novi = napravi_cvor(x, cv->prethodni, cv);
    if (novi == NULL)
        return;

    cv->prethodni->sledeci = novi;
    cv->prethodni          = novi;
}

/* Ubacuje novi čvor posle cv. */
void ubaci_sledeci(cvor *cv, int x)
{
    cvor *novi = napravi_cvor(x, cv, cv->sledeci);
    if (novi == NULL)
        return;

    cv->sledeci->prethodni = novi;
    cv->sledeci            = novi;
}

/* Ubacivanje na početak i kraj koriste sentinelu kao referencu. */
void ubaci_na_pocetak(cvor *sentinel, int x)
{
    ubaci_sledeci(sentinel, x);
}

void ubaci_na_kraj(cvor *sentinel, int x)
{
    ubaci_prethodni(sentinel, x);
}

/* Lista je prazna kada sentinel pokazuje samo na sebe. */
int prazna(cvor *sentinel)
{
    return sentinel->sledeci == sentinel;
}

/* Ispis svih elemenata, bez sentinela. */
void ispisi_listu(cvor *sentinel)
{
    printf("[");
    for (cvor *p = sentinel->sledeci; p != sentinel; p = p->sledeci) {
        printf("%d", p->podatak);
        if (p->sledeci != sentinel)
            printf(", ");
    }
    printf("]\n");
}

/* Brisanje svih pravih elemenata. */
void obrisi_listu(cvor *sentinel)
{
    while (!prazna(sentinel))
        obrisi_cvor(sentinel->sledeci);
}