Obrni dvostruku listu

Implementirati funkciju koja obrće dvostruku povezanu listu sa sentinel čvorom.

void obrni_listu(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 obrnuta lista u formatu:

[a1, a2, a3, ..., an]

Primer

Ulaz

1 2 3 4 5

Izlaz

[5, 4, 3, 2, 1]

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"

/* Obrće dvostruku povezanu listu sa sentinelom. */
void obrni_listu(cvor *sentinel)
{
	cvor *trenutni = sentinel->sledeci;
	cvor *sledeci = NULL;

	while (trenutni != sentinel) {
		sledeci = trenutni->sledeci;
		trenutni->sledeci = trenutni->prethodni;
		trenutni->prethodni = sledeci;
		trenutni = sledeci;
	}

	/* Promena veza sentinela */
	sledeci = sentinel->sledeci;
	sentinel->sledeci = sentinel->prethodni;
	sentinel->prethodni = sledeci;
}

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

	obrni_listu(lista);

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