Učešljaj dvostruke liste

Implementirati funkciju koja učešljava drugu dvostruku listu u prvu. Učešljavanje se vrši tako što se naizmenično uzimaju čvorovi iz prve i druge liste, počevši od prve liste. Ako jedna lista ostane bez čvorova, preostali čvorovi iz druge liste se dodaju na kraj rezultujuće liste.

Ulaz

Sa standardnog ulaza se učitavaju dva niza celih brojeva koji se smeštaju u dve dvostruke povezane liste. Unos za svaku listu se završava kada se unese -1.

Izlaz

Na standardni izlaz se ispisuje učešljana lista u formatu:

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

Primer

Ulaz

1 3 5 7 -1
2 4 6 8 10 12 -1

Izlaz

[1, 2, 3, 4, 5, 6, 7, 8, 10, 12]

Primer

Ulaz

1 2 3 -1
4 5 6 -1

Izlaz

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

Primer

Ulaz

1 2 3 4 -1
-1

Izlaz

[1, 2, 3, 4]

Primer

Ulaz

-1
5 6 7 8 -1

Izlaz

[5, 6, 7, 8]

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"

void ucesljaj_liste(cvor *lista1, cvor *lista2)
{
	cvor *p1 = lista1->sledeci;
	cvor *p2 = lista2->sledeci;
	cvor *t = lista1;

	while (p1 != lista1 && p2 != lista2) {
		/* Ubaci iz prve liste */
		t->sledeci = p1;
		p1->prethodni = t;
		t = p1;
		p1 = p1->sledeci;

		/* Ubaci iz druge liste */
		t->sledeci = p2;
		p2->prethodni = t;
		t = p2;
		p2 = p2->sledeci;
	}

	if (p1 != lista1) {
		/* Preostali elementi iz prve liste */
		t->sledeci = p1;
		p1->prethodni = t;
		t = lista1->prethodni;
	} else if (p2 != lista2) {
		/* Preostali elementi iz druge liste */
		t->sledeci = p2;
		p2->prethodni = t;
		t = lista2->prethodni;
	}

	/* Zatvaranje liste */
	t->sledeci = lista1;
	lista1->prethodni = t;
}

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

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

	int x;
	while (scanf("%d", &x) == 1) {
		if (x == -1) {
			break;
		}
		ubaci_na_kraj(lista1, x);
	}

	while (scanf("%d", &x) == 1) {
		if (x == -1) {
			break;
		}
		ubaci_na_kraj(lista2, x);
	}

	ucesljaj_liste(lista1, lista2);

	ispisi_listu(lista1);

	obrisi_listu(lista1);
	free(lista2);

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