Iseci opseg

Implementirati funkciju koja seče opseg iz dvostruko povezane liste i dodaje ga na početak druge dvostruko povezane liste sa sentinel čvorom. Opseg je definisan čvorovima [pocetak, kraj), gde je pocetak uključen u opseg, a kraj nije. Ako su pocetak i kraj isti, ne radi se ništa.

void iseci_opseg(cvor *sentinel, cvor *pocetak, cvor *kraj)

Ulaz

Sa standardnog izlaza se učitavaju dva cela broja koja predstavljaju indekse čvorova pocetak i kraj, a zatim niz celih brojeva koji se smeštaju u dvostruku povezanu listu iz koje se seče opseg. Unos se završava kada se unese kraj ulaza (EOF). Druga lista, na koju se dodaje isečeni opseg, je inicijalno prazna.

Izlaz

Na standardni izlaz se ispisuju obe liste u formatu:

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

gde je prva lista ona iz koje je isečen opseg, a druga lista je ona na koju je opseg dodat.

Primer

Ulaz

2 4
1 2 3 4 5 6

Izlaz

[1, 2, 5, 6]
[3, 4]

Primer

Ulaz

0 3
10 20 30 40 50

Izlaz

[40, 50]
[10, 20, 30]

Primer

Ulaz

1 1
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"

/* 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;
}

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

	int start_idx, end_idx;
	scanf("%d %d", &start_idx, &end_idx);

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

	cvor *start = lista->sledeci;
	for (int i = 0; i < start_idx && start != lista; i++) {
		start = start->sledeci;
	}

	cvor *end = start;
	for (int i = start_idx; i < end_idx && end != lista; i++) {
		end = end->sledeci;
	}

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

	iseci_opseg(nova_lista, start, end);

	ispisi_listu(lista);
	ispisi_listu(nova_lista);

	obrisi_listu(lista);
	obrisi_listu(nova_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);
}