Baza znanjaIzpitno središče
SLSlovenščina
Izberi jezik13

CKTIS / C

Sklad LIFO z dinamično tabelo v C

Sklad LIFO najprej odstrani nazadnje dodani zapis. Ločite število elementov od zmogljivosti in povečajte medpomnilnik brez izgube podatkov, če dodelitev pomnilnika spodleti.

Različica: ISO C23; implementation support may vary

Sintaksa

/* Application-defined operations in ISO C23; not standard-library APIs. */
/* Inside main, after the application types and functions are defined. */
Stack s = { .data = NULL, .size = 0, .capacity = 0 };
Process p;
if (!push(&s, (Process){ .id = 42 }) ||
    !peek(&s, &p) ||
    !pop(&s, &p)) {
    free(s.data);
    return EXIT_FAILURE;
}
/* All three calls succeeded; p holds the record copied by pop. */
free(s.data);

Sklad LIFO deluje po načelu »zadnji noter, prvi ven«. push doda element na vrh, peek kopira vrhnji element, ne da bi ga odstranil, pop pa ga kopira in odstrani. To so funkcije v primeru, ne funkcije standardne knjižnice C. peek in pop potrebujeta veljaven kazalec na ločen objekt Process, v katerega je mogoče pisati. Pri praznem skladu vrneta false in izhodnega objekta ne spremenita.

Invarianta je 0 <= size <= capacity: size šteje shranjene zapise, capacity pa rezervirana mesta. Vrh je na indeksu size - 1 le, če velja size > 0. pop zmanjša size, ne da bi sprostil medpomnilnik. Začetni NULL pomeni, da medpomnilnika še ni. Makro NULL, ki je na voljo med drugim v <stdlib.h>, se razširi v konstanto ničelnega kazalca, ki jo določa implementacija.

Ko je sklad poln, push začne z enim mestom, nato pa podvaja zmogljivost največ do SIZE_MAX / sizeof *s->data. SIZE_MAX iz <stdint.h> je največja vrednost size_t, ne količina razpoložljivega pomnilnika. Meja prepreči prekoračitev pri izračunu zmogljivosti in števila bajtov. Rezultat klica realloc z neničelno velikostjo se shrani v začasni kazalec: NULL pomeni neuspeh, sklad pa ostane nespremenjen. Po uspešni ponovni dodelitvi ne uporabljajte starih kazalcev na medpomnilnik ali njegove elemente, tudi če se naslov ni spremenil.

Če zmogljivosti ni mogoče povečati ali če dodelitev spodleti, push vrne false. Funkcija main sporoči napako na stderr, sprosti medpomnilnik s free in vrne EXIT_FAILURE iz <stdlib.h>. S tem gostiteljskemu okolju sporoči neuspešen konec programa, ne da bi predpostavila določeno številsko kodo.

Sestavljeni literal (Process){ .id = 10 } ustvari neimenovan objekt Process; ne gre za pretvorbo tipa. Ta literal ima samodejno trajanje shranjevanja, push pa shrani vrednost zapisa, ne njegovega naslova. Primer je skladen z ISO C23; ta oblika literala je na voljo od C99, vendar je podpora načinu C23 odvisna od implementacije.

Primeri

#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct { int id; } Process;

typedef struct {
    Process *data;
    size_t size;
    size_t capacity;
} Stack;

static bool push(Stack *s, Process value)
{
    if (s->size == s->capacity) {
        const size_t limit = SIZE_MAX / sizeof *s->data;
        if (s->capacity == limit)
            return false;

        size_t next = s->capacity == 0 ? 1
                    : s->capacity > limit / 2 ? limit
                    : s->capacity * 2;
        Process *new_data = realloc(s->data, next * sizeof *s->data);
        if (new_data == NULL)
            return false;
        s->data = new_data;
        s->capacity = next;
    }
    s->data[s->size] = value;
    ++s->size;
    return true;
}

static bool peek(const Stack *s, Process *out)
{
    if (s->size == 0)
        return false;
    *out = s->data[s->size - 1];
    return true;
}

static bool pop(Stack *s, Process *out)
{
    if (!peek(s, out))
        return false;
    --s->size;
    return true;
}

int main(void)
{
    Stack s = { .data = NULL, .size = 0, .capacity = 0 };
    if (!push(&s, (Process){ .id = 10 }) ||
        !push(&s, (Process){ .id = 20 })) {
        fputs("Cannot grow stack\n", stderr);
        free(s.data);
        return EXIT_FAILURE;
    }

    Process p;
    if (peek(&s, &p))
        printf("peek: %d\n", p.id);
    while (pop(&s, &p))
        printf("pop: %d\n", p.id);
    puts("empty");

    free(s.data);
    return EXIT_SUCCESS;
}

Rezultat

peek: 20
pop: 20
pop: 10
empty

Dve vstavljanji povečata zmogljivost z 1 na 2. Po uspešnem klicu `peek` program izpiše identifikator `20`. Prva dva klica `pop` vrneta `true` in prek kazalca `out` zapišeta najprej zapis z identifikatorjem `20`, nato zapis z identifikatorjem `10`. Naslednji klic `pop` vrne `false`, ker je sklad prazen.

Povezane lekcije

  • C · Lekcija 87 · Napredna · Različica: 3

Viri