Rotiraj dvostruku listu za k mesta u levo

Napisati funkciju koja rotira dvostruku povezanu listu sa sentinel čvorom za $k$ mesta u levo. Rotacija za jedno mesto u levo podrazumeva da se prvi čvor liste premesti na kraj liste.

void rotiraj_k(cvor *sentinel, int k)

Ulaz

Sa standardnog ulaza se učitava ceo broj $k$, 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 rotirana lista u formatu:

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

Primer

Ulaz

2
1 2 3 4 5

Izlaz

[3, 4, 5, 1, 2]

Primer

Ulaz

8
10 20 30 40 50

Izlaz

[40, 50, 10, 20, 30]

Primer

Ulaz

4

Izlaz

[]

Primer

Ulaz

0
5 10 15 20

Izlaz

[5, 10, 15, 20]

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 <stdlib.h>
#include "lista.h"

/* Vraća dužinu dvostruko povezane liste sa sentinelom. */
size_t duzina_liste(cvor *sentinel)
{
	size_t duzina = 0;
	for (cvor *p = sentinel->sledeci; p != sentinel; p = p->sledeci) {
		duzina++;
	}
	return duzina;
}

/* Iseci opseg iz dvostruko povezane liste sa sentinelom.
   Opseg je definisan čvorovima [pocetak, kraj). 
   Opseg dodati na pocetak liste na koju pokazuje sentinel.
   Sentinel moze pokazivati na istu ili drugu listu od one u kojoj su pocetak i kraju. */
void iseci_opseg(cvor *sentinel, cvor *pocetak, cvor *kraj)
{
	if (pocetak == kraj) {
		return;
	}

	cvor *pre_pocetka = pocetak->prethodni;
	cvor *pre_kraja = kraj->prethodni;

	/* Povezivanje krajeva liste iz koje se seče opseg */
	pre_pocetka->sledeci = kraj;
	kraj->prethodni = pre_pocetka;

	/* Ubacivanje opsega na početak nove liste */
	cvor *prvi = sentinel->sledeci;
	sentinel->sledeci = pocetak;
	pocetak->prethodni = sentinel;
	pre_kraja->sledeci = prvi;
	prvi->prethodni = pre_kraja;
}

/* Rotira dvostruko povezanu listu sa sentinelom za k mesta u levo. */
void rotiraj_k(cvor *sentinel, int k)
{
	size_t n = duzina_liste(sentinel);
	if (n == 0) {
		return; // prazna lista
	}

	k = k % n;
	if (k == 0) {
		return; // nema potrebe za rotacijom
	}

	cvor *trenutni = sentinel->sledeci;
	for (int i = 0; i < k; i++) {
		trenutni = trenutni->sledeci;
	}

	iseci_opseg(sentinel, trenutni, sentinel);
}

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

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

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

	rotiraj_k(lista, k);

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