Minimum i maksimum liste
Napisati dve funkcije koje vraćaju minimum i maksimum jednostruko povezane liste.
status minimum_liste(cvor* sentinel, int* min);
status maksimum_liste(cvor* sentinel, int* max);Ulaz
Sa standardnog ulaza se učitava lista celih brojeva u formatu:
[a1, a2, a3, ..., an]
pri čemu je
Izlaz
Na standardni izlaz ispisati dva cela broja odvojena razmakom: minimum i maksimum liste.
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
[3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
stdout
1 9
Primer
stdin
[-10, 0, 10, -20, 20]
stdout
-20 20
Primer
stdin
[]
stderr
Greška: Lista je prazna.
Primer
stdin
stderr
Greška: Neuspešno učitavanje liste.
Primer
stdin
[10, 20,,, 30,,]
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 pronalazi minimum u listi. */
static status minimum_liste(cvor *sentinel, int *min)
{
if (sentinel->sledeci == NULL) {
return NEMA_ELEMENATA;
}
*min = sentinel->sledeci->podatak;
// for varijanta
for (cvor *p = sentinel->sledeci->sledeci; p != NULL; p = p->sledeci) {
if (*min > p->podatak) {
*min = p->podatak;
}
}
return OK;
}
/* Funkcija koja pronalazi maksimum u listi. */
static status maksimum_liste(cvor *sentinel, int *max)
{
if (sentinel->sledeci == NULL) {
return NEMA_ELEMENATA;
}
*max = sentinel->sledeci->podatak;
// while varijanta
cvor *p = sentinel->sledeci->sledeci;
while (p != NULL) {
if (*max < p->podatak) {
*max = p->podatak;
}
p = p->sledeci;
}
return OK;
}
int main(void)
{
cvor *l = inicijalizuj_listu();
if (l == NULL) {
fprintf(stderr, "Greška: Neuspešna inicijalizacija liste.\n");
exit(EXIT_FAILURE);
}
status s = ucitaj_listu(l);
if (s != OK) {
fprintf(stderr, "Greška: Neuspešno učitavanje liste.\n");
exit(EXIT_FAILURE);
}
int min, max;
s = minimum_liste(l, &min);
if (s != OK) {
fprintf(stderr, "Greška: Lista je prazna.\n");
exit(EXIT_FAILURE);
}
s = maksimum_liste(l, &max);
if (s != OK) {
fprintf(stderr, "Greška: Lista je prazna.\n");
exit(EXIT_FAILURE);
}
printf("%d %d\n", min, max);
unisti_listu(&l);
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");
}