Dužina dvostruke liste

Implementirati funkciju koja računa dužinu dvostruke povezane liste sa sentinel čvorom.

size_t duzina_liste(cvor *sentinel)

Ulaz

Sa standardnog ulaza se učitava 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 dužina liste kao ceo broj.

Primer

Ulaz

1 2 3 4 5

Izlaz

Primer

Ulaz

Izlaz

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"

size_t duzina_liste(cvor *sentinel)
{
	size_t duzina = 0;
	for (cvor *p = sentinel->sledeci; p != sentinel; p = p->sledeci) {
		duzina++;
	}
	return duzina;
}

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

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

	printf("%zu\n", duzina_liste(lista));

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