Učešljaj dve liste

Napisati funkciju koja učešljava dve jednostruko povezane liste naizmenično, počevši od prve liste. Ako su liste različitih dužina, preostali elementi duže liste se dodaju na kraj rezultujuće liste. Rezultat se smešta u prvu listu.

int ucesljaj(cvor* lista1, cvor* lista2);

Napomena: Konstantno dodatno memorijsko ograničenje.

Ulaz

Sa standardnog ulaza se učitavaju dve liste celih brojeva u formatu:

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

[b1, b2, b3, ..., bm]

pri čemu je $n$ ($0 \leq n \leq 10^5$) broj elemenata prve liste, a $m$ ($0 \leq m \leq 10^5$) broj elemenata druge liste. Elementi lista $a_i$ i $b_i$ su celi brojevi.

Izlaz

Na standardni izlaz ispisati učešljanu prvu listu u formatu:

[c1, c2, c3, ..., c(n+m)]

pri čemu je $n+m$ broj elemenata rezultujuće liste, a $c_i$ su celi brojevi.

U slučaju greške, na standardni izlaz za greške ispisati odgovarajuću poruku i prekinuti izvršavanje programa sa kodom neuspeha (1).

Primer

`stdin`

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

`stdout`

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

Primer

`stdin`

[10, 20, 30]
[]

`stdout`

[10, 20, 30]

Primer

`stdin`

[]
[5, 15, 25]

`stdout`

[5, 15, 25]

Primer

`stdin`

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

`stdout`

[1, 4, 2, 5, 3]

Primer

`stdin`

[,,,]
[1, 2, 3]

`stderr`

Greška: Neuspešno učitavanje liste.

Rešenje

`liste.h`

#ifndef LISTE_H
#define LISTE_H

#include <stddef.h>  /* za size_t */

/* Čvor jednostruko povezane liste. */
typedef struct cvor {
    int podatak;
    struct cvor *sledeci;
} cvor;

/* Statusni kodovi za operacije nad listom. */
typedef enum {
    OK,
    NEDOVOLJNO_MEMORIJE,
    NEMA_ELEMENATA
} status;

/* 
 * Kreiranje i uništavanje liste
 */

/* Kreira praznu listu sa sentinel-čvorom. Vraća pokazivač na sentinel ili NULL. */
cvor *inicijalizuj_listu(void);

/* Oslobađa sve "prave" elemente liste; sentinel ostaje. */
void obrisi_listu(cvor *sentinel);

/* Kao gore, ali održava i pokazivač na kraj liste. */
void obrisi_listu_sa_krajem(cvor *sentinel, cvor **pokazivac_na_kraj);

/* Oslobađa sve elemente i sentinel; poništava pokazivač na listu. */
void unisti_listu(cvor **psentinel);

/* 
 * Osnovne operacije ubacivanja
 */

/* Dodaje novi element na početak liste (iza sentinela). */
status dodaj_na_pocetak(cvor *sentinel, int podatak);

/* Dodaje novi element na kraj liste, složenosti O(n). */
status dodaj_na_kraj(cvor *sentinel, int podatak);

/* Dodaje novi element na kraj liste, uz održavanje pokazivača na kraj (O(1)). */
status dodaj_na_kraj_sa_krajem(cvor *sentinel,
                               cvor **pokazivac_na_kraj,
                               int podatak);

/* Umeće već alocirani čvor odmah iza zadatog elementa (bez provera). */
void ubaci_iza_elementa(cvor *element, cvor *novi);

/* Umeće već alocirani čvor "ispred" zadatog tako što se podaci zamene. */
void ubaci_ispred_elementa(cvor *element, cvor *novi);

/* 
 * Brisanje
 */

/* Briše prvi pravi element liste (iza sentinela) i vraća njegovu vrednost. */
status obrisi_sa_pocetka(cvor *sentinel, int *podatak);

/* Kao gore, ali održava i pokazivač na kraj liste. */
status obrisi_sa_pocetka_sa_krajem(cvor *sentinel,
                                   cvor **pokazivac_na_kraj,
                                   int *podatak);

/* Briše prvi element sa datom vrednošću; ako ne postoji, vraća NEMA_ELEMENATA. */
status obrisi_prvi_sa_vrednoscu(cvor *sentinel, int vrednost);

/* 
 * Pretraga
 */

/* Vraća pokazivač na prvi čvor sa datom vrednošću ili NULL ako takav ne postoji. */
cvor *nadji_prvi(cvor *sentinel, int vrednost);

/* Vraća prethodni čvor u odnosu na prvi čvor sa datom vrednošću, ili NULL. */
cvor *nadji_prethodni(cvor *sentinel, int vrednost);

/* 
 * Sortirano ubacivanje i učešljavanje (merge)
 */

/* Umeće novi element tako da lista ostane sortirana (neopadajuće). */
status ubaci_sortirano(cvor *sentinel, int podatak);

/* Objedinjava dve sortirane liste s1 i s2 u s1; s2 postaje prazna. */
void objedini(cvor *s1, cvor *s2);

/* 
 * Učitavanje
 */

/* Učita listu u formatu [1, 2, 3] sa stdin u zadatu povezanu listu. */
status ucitaj_listu(cvor *sentinel);

/* 
 * Ispis
 */

/* Ispisuje sve elemente liste (bez sentinela) u jednom redu. */
void ispisi_elemente_liste(cvor *sentinel);

#endif /* LISTE_H */

`main.c`

#include <stdio.h>
#include <stdlib.h>
#include "liste.h"

/* Funkcija koja učešljava dve liste naizmenično. */
static void ucesljaj(cvor* s1, cvor* s2)
{
    cvor *p = s1;
    cvor *a = s1->sledeci;
    cvor *b = s2->sledeci;

    while (a != NULL && b != NULL) {
        // Umeće element iz prve liste
        p->sledeci = a;
        a = a->sledeci;
        p = p->sledeci;

        // Umeće element iz druge liste
        p->sledeci = b;
        b = b->sledeci;
        p = p->sledeci;
    }

    if (a != NULL) {
        p->sledeci = a;  // Dodaje preostale elemente iz prve liste
    } else if (b != NULL) {
        p->sledeci = b;  // Dodaje preostale elemente iz druge liste
    }
}

int main(void)
{
    cvor *l1 = inicijalizuj_listu();
    if (l1 == NULL) {
        fprintf(stderr, "Greška: Neuspešna inicijalizacija liste.\n");
        exit(EXIT_FAILURE);
    }

    cvor *l2 = inicijalizuj_listu();
    if (l2 == NULL) {
        fprintf(stderr, "Greška: Neuspešna inicijalizacija liste.\n");
        unisti_listu(&l1);
        exit(EXIT_FAILURE);
    }

    status s = ucitaj_listu(l1);
    if (s != OK) {
        fprintf(stderr, "Greška: Neuspešno učitavanje liste.\n");
        unisti_listu(&l2);
        exit(EXIT_FAILURE);
    }

    s = ucitaj_listu(l2);
    if (s != OK) {
        fprintf(stderr, "Greška: Neuspešno učitavanje liste.\n");
        unisti_listu(&l1);
        exit(EXIT_FAILURE);
    }

    ucesljaj(l1, l2);

    ispisi_elemente_liste(l1);

    unisti_listu(&l1);
    // unisti_listu(&l2);  // l2 je sada prazna, nema šta da se uništi
    free(l2); // oslobodi samo sentinel

    exit(EXIT_SUCCESS);
}

`liste.c`

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include "liste.h"

/* Pročita jedan ceo broj iz niske, koristeći strtol. */
static int procitaj_int(const char **s, int *vrednost)
{
    char *kraj;
    long val = strtol(*s, &kraj, 10);
    if (kraj == *s) {
        return 0;  /* nije bilo broja */
    }
    *vrednost = (int)val;
    *s = kraj;
    return 1;
}

/* Pomoćna funkcija: kreira novi čvor sa datom vrednošću. */
static cvor *novi_cvor(int podatak)
{
    cvor *novi = malloc(sizeof(cvor));
    if (novi == NULL)
        return NULL;

    novi->podatak = podatak;
    novi->sledeci = NULL;
    return novi;
}

/* Kreira praznu listu sa sentinel-čvorom. */
cvor *inicijalizuj_listu(void)
{
    cvor *s = malloc(sizeof(cvor));
    if (s == NULL)
        return NULL;

    s->podatak = 0;        /* vrednost se ne koristi */
    s->sledeci = NULL;     /* prazna lista */
    return s;
}

/* Oslobađa sve prave elemente liste; sentinel ostaje. */
void obrisi_listu(cvor *sentinel)
{
    cvor *tekuci = sentinel->sledeci;
    while (tekuci != NULL) {
        cvor *p = tekuci;
        tekuci  = tekuci->sledeci;
        free(p);
    }
    sentinel->sledeci = NULL;
}

/* Oslobađa sve prave elemente i resetuje pokazivač na kraj. */
void obrisi_listu_sa_krajem(cvor *sentinel, cvor **pokazivac_na_kraj)
{
    cvor *tekuci = sentinel->sledeci;
    while (tekuci != NULL) {
        cvor *p = tekuci;
        tekuci  = tekuci->sledeci;
        free(p);
    }
    sentinel->sledeci  = NULL;
    *pokazivac_na_kraj = sentinel;
}

/* Uništava čitavu listu, uključujući sentinel-čvor. */
void unisti_listu(cvor **psentinel)
{
    if (*psentinel == NULL)
        return;

    obrisi_listu(*psentinel);
    free(*psentinel);
    *psentinel = NULL;
}

/* Dodaje novi element na početak liste (iza sentinela). */
status dodaj_na_pocetak(cvor *sentinel, int podatak)
{
    cvor *novi = novi_cvor(podatak);
    if (novi == NULL)
        return NEDOVOLJNO_MEMORIJE;

    novi->sledeci      = sentinel->sledeci;
    sentinel->sledeci  = novi;
    return OK;
}

/* Dodaje novi element na kraj liste, složenosti O(n). */
status dodaj_na_kraj(cvor *sentinel, int podatak)
{
    cvor *novi = novi_cvor(podatak);
    if (novi == NULL)
        return NEDOVOLJNO_MEMORIJE;

    novi->sledeci = NULL;

    cvor *p = sentinel;
    while (p->sledeci != NULL)
        p = p->sledeci;

    p->sledeci = novi;
    return OK;
}

/* Dodaje novi element na kraj liste, uz održavanje pokazivača na kraj. */
status dodaj_na_kraj_sa_krajem(cvor *sentinel,
                               cvor **pokazivac_na_kraj,
                               int podatak)
{
    (void)sentinel;  /* sentinel je implicitno jednak *pokazivac_na_kraj na početku */

    cvor *novi = novi_cvor(podatak);
    if (novi == NULL)
        return NEDOVOLJNO_MEMORIJE;

    novi->sledeci = NULL;

    (*pokazivac_na_kraj)->sledeci = novi;
    *pokazivac_na_kraj = novi;

    return OK;
}

/* Umeće već alocirani čvor odmah iza zadatog elementa. */
void ubaci_iza_elementa(cvor *element, cvor *novi)
{
    if (element == NULL || novi == NULL)
        return;

    novi->sledeci  = element->sledeci;
    element->sledeci = novi;
}

/* Umeće novi čvor "ispred" datog elementa zamjenom podataka. */
void ubaci_ispred_elementa(cvor *element, cvor *novi)
{
    if (element == NULL || novi == NULL)
        return;

    /* Umećemo novi iza elementa, pa menjamo podatke. */
    novi->sledeci  = element->sledeci;
    element->sledeci = novi;

    int tmp            = element->podatak;
    element->podatak   = novi->podatak;
    novi->podatak      = tmp;
}

/* Briše prvi pravi element liste i vraća njegovu vrednost. */
status obrisi_sa_pocetka(cvor *sentinel, int *podatak)
{
    if (sentinel->sledeci == NULL)
        return NEMA_ELEMENATA;

    cvor *p        = sentinel->sledeci;
    *podatak       = p->podatak;
    sentinel->sledeci = p->sledeci;
    free(p);

    return OK;
}

/* Briše prvi element i održava pokazivač na kraj. */
status obrisi_sa_pocetka_sa_krajem(cvor *sentinel,
                                   cvor **pokazivac_na_kraj,
                                   int *podatak)
{
    if (sentinel->sledeci == NULL)
        return NEMA_ELEMENATA;

    cvor *p        = sentinel->sledeci;
    *podatak       = p->podatak;
    sentinel->sledeci = p->sledeci;
    free(p);

    if (sentinel->sledeci == NULL)
        *pokazivac_na_kraj = sentinel;

    return OK;
}

/* Pronalaženje prvog elementa sa datom vrednošću. */
cvor *nadji_prvi(cvor *sentinel, int vrednost)
{
    for (cvor *p = sentinel->sledeci; p != NULL; p = p->sledeci)
        if (p->podatak == vrednost)
            return p;
    return NULL;
}

/* Pronalaženje prethodnog elementa u odnosu na prvi sa datom vrednošću. */
cvor *nadji_prethodni(cvor *sentinel, int vrednost)
{
    cvor *prev = sentinel;
    cvor *curr = sentinel->sledeci;

    while (curr != NULL) {
        if (curr->podatak == vrednost)
            return prev;
        prev = curr;
        curr = curr->sledeci;
    }
    return NULL;
}

/* Briše prvi element sa zadatom vrednošću. */
status obrisi_prvi_sa_vrednoscu(cvor *sentinel, int vrednost)
{
    cvor *prev = nadji_prethodni(sentinel, vrednost);
    if (prev == NULL)
        return NEMA_ELEMENATA;

    cvor *za_brisanje = prev->sledeci;
    prev->sledeci     = za_brisanje->sledeci;
    free(za_brisanje);

    return OK;
}

/* Umeće element u sortiranu listu (neopadajući poredak). */
status ubaci_sortirano(cvor *sentinel, int podatak)
{
    cvor *novi = novi_cvor(podatak);
    if (novi == NULL)
        return NEDOVOLJNO_MEMORIJE;

    cvor *prev = sentinel;
    cvor *curr = sentinel->sledeci;

    while (curr != NULL && curr->podatak < podatak) {
        prev = curr;
        curr = curr->sledeci;
    }

    novi->sledeci = curr;
    prev->sledeci = novi;

    return OK;
}

/* Učešljava dve sortirane liste u prvu (s1); s2 postaje prazna. */
void objedini(cvor *s1, cvor *s2)
{
    cvor *p = s1;
    cvor *a = s1->sledeci;
    cvor *b = s2->sledeci;

    while (a != NULL && b != NULL) {
        if (a->podatak <= b->podatak) {
            p->sledeci = a;
            a = a->sledeci;
        } else {
            p->sledeci = b;
            b = b->sledeci;
        }
        p = p->sledeci;
    }

    p->sledeci = (a != NULL) ? a : b;

    s2->sledeci = NULL;  /* druga lista je sada prazna */
}

/* Učita listu u formatu [1, 2, 3] sa stdin u zadatu povezanu listu. */
status ucitaj_listu(cvor *sentinel)
{
    char linija[1024];

    if (fgets(linija, sizeof(linija), stdin) == NULL)
        return NEMA_ELEMENATA;  /* ili tretirati kao OK-prazno */

    const char *p = linija;

    /* lokalni pokazivač na kraj liste – na početku je to sentinel */
    cvor *kraj = sentinel;

    /* Preskoči beline i očekuj '[' */
    while (isspace((unsigned char)*p)) p++;
    if (*p != '[') {
        return NEMA_ELEMENATA;
    }
    p++;  /* preko '[' */

    /* Prazna lista '[]'? */
    while (isspace((unsigned char)*p)) p++;
    if (*p == ']') {
        return OK;
    }

    /* Inače čitamo brojeve odvojene zarezima. */
    for (;;) {
        int x;
        while (isspace((unsigned char)*p)) p++;

        if (!procitaj_int(&p, &x)) {
            return NEMA_ELEMENATA;
        }

        if (dodaj_na_kraj_sa_krajem(sentinel, &kraj, x) != OK) {
            return NEDOVOLJNO_MEMORIJE;
        }

        while (isspace((unsigned char)*p)) p++;

        if (*p == ',') {
            p++;  /* preko zareza, ide sledeći broj */
            continue;
        } else if (*p == ']') {
            break;  /* kraj liste */
        } else {
            return NEMA_ELEMENATA;
        }
    }

    return OK;
}

/* Ispis svih elemenata liste (bez sentinela). */
void ispisi_elemente_liste(cvor *sentinel)
{
    printf("[");
    for (cvor *p = sentinel->sledeci; p != NULL; p = p->sledeci) {
        printf("%d", p->podatak);
        if (p->sledeci != NULL)
            printf(", ");
    }
    printf("]\n");
}