Jazyk C 2013 – 13. cvičenie [CodeLite + Generický zásobník]

Posted on by

CodeLite

  • CodeLite je bezplatné prostredie pre vývoj C/C++ na Windows, Linux a MacOS X.
  • dostupné na http://codelite.org/
  • dostaneme editor + kompilátor GCC
  • nastavme v projektových vlastnostiach parametre pre kompilátor oddelené bodkočiarkami -ansi;-pedantic;-Wall;-Wextra

Generický zoznam

Vytvorme nástrel pre generický spojový zoznam ľubovoľného typu

Položka

Dáta budú generickým pointerom

struct polozka {
        void * data;
        struct polozka * dalsi;
};

“Konštruktor” [nešťastná verzia]

Vytvorme zlú funkciu pre alokáciu novej položky nad danými dátami.

/* nedokonalá verzia */
struct polozka * polozka_new(void * data) {
        struct polozka * nova = malloc(sizeof(struct polozka));
        if(nova == NULL) {
                perror("Malloc() polozky zlyhal");
                exit(EXIT_FAILURE);
        }

        nova->data = data;
        nova->dalsi = NULL;

        return nova;
}

Koľko bajtov treba pre položku? sizeof (struct polozka). Môže sa nám zdať, že zoznam doubleov potrebuje viac miesta než zoznam intov, lebo double zaberá viac miesta, ale samotné dáta sú reprezentované ako generický pointer. Pointer v C zaberá v pamäti rovnaké miesto bez ohľadu na dátový typ, na ktorý ukazuje. (Inak povedané sizeof(int *) = sizeof(void *) = sizeof(double *))

Inicializácia položky

Zlý nápad č.1:

struct polozka * p = polozka_new(42);

Funkcia potrebuje generický pointer void *, a 42 je int. Nesedia dátové typy: snažíme sa napchať číslo do adresy.

Zlý nápad č.2:

struct polozka * p = polozka_new((void *) 42);

Funkcia potrebuje generický pointer void *, a 42 je int. Nesedia dátové typy: snažíme sa napchať číslo do adresy a pretypovaním čísla na adresu nič nezachránime (prinajhoršom by sme mali prístup k adrese s offsetom 42).

Zlý nápad č.3:

struct polozka * p = polozka_new(&42);

Ampersand získava adresu z veci, ale 42 je konštanta, ktorá v pamäti nemá adresu. (Resp. v pamäti je zrejme viacero štyridsaťdvojek…). Operátor referencie & funguje len lvalue (lhodnoty). Zjednodušene ich môžeme chápať ako “veci, ktoré sa môžu ocitnúť na ľavej strane v priradení”, čo neplatí pre situáciu "42 = ...". Analógia je vec, ktorá má meno, čo pre “42” neplatí.

Dobrý nápad (s výhradami)

  • Vyrobíme premennú typu int.

  • Získame jej adresu, teda pointer na ňu a strčíme ju do funkcie

    int data = 42;
struct polozka * p = polozka_new(&data);

Toto tu pobeží pre veľmi jednoduché prípady, viď nižšie.

Ako vytlačiť položku?

Zlý nápad č. 1

printf("%d", p->data);

Premenná p->data je typu void *, ktorý chceme vytlačiť ako číslo, čo je blbosť.

Vieme však, že zoznam nesie celé čísla, presnejšie pointre na celé čísla, môžeme pretypovať:

Zlý nápad č. 2

printf("%d", (int *) p->data);

Zrazu sa snažíme vytlačiť pointer na int ako celé číslo: to je však adresa, ktorá nebude dávať zmysel.

Musíme dereferencovať premennú, a teda sa dostať k jej obsahu.

Dobrý nápad

printf("%d", *((int *) p->data));

Celý kód

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

struct polozka {
        void * data;
        struct polozka * dalsi;
};

struct polozka * polozka_new(void * data) {
        struct polozka * nova = malloc(sizeof(struct polozka));
        if(nova == NULL) {
                perror("Malloc() polozky zlyhal");
                exit(EXIT_FAILURE);
        }

        nova->data = data;
        nova->dalsi = NULL;

        return nova;
}

int main(void)
{
        int number = 42;
        struct polozka * p = polozka_new(&number);

        printf("%d", *( (int *) p->data));

        return EXIT_SUCCESS;
}

Problémy

  • Musíme dať pozor, aby pointre v zozname ukazovali na odlišné položky.
  • Ak by sa premenná number menila (napríklad v cykle), menila by sa aj hodnota položky v zozname
    • odovzdávanie pointerov = odovzdávanie balónikov.

Demonštrácia:

int main(void)
{
    int i;

    struct polozka * p = NULL;
    struct polozka * z = NULL;

    /*===================*/ 

    for(i = 0; i < 10; i++) {
            p = polozka_new(&i);
            p->dalsi = z;
            z = p;
    }

    /*===================*/


    p = z;
    while(p != NULL) {
            printf("%d ", *( (int *) p->data));
            p = p->dalsi;
    }


    return EXIT_SUCCESS;
}

Výsledok bude: 10 10 10 10 10 10 10 10 10, hoci by mal byť zoznam čísiel od 1 po 10.

Dôvod je, že do zoznamu pridávame pointer na premennú i v cykle. Adresa je stále rovnaká a pridá sa na každú položku zoznamu, aj keď jej obsah sa mení. V konečnom dôsledku bude adresa v zozname obsahovať poslednú položku cyklu, čiže 10.

Riešenie?

  • Zoznam si musí skopírovať hodnotu k sebe.
  • Musí si alokovať sám pamäť pre dáta v položke.
  • Z premennej dodanej do funkcie skopíruje dáta do položky.

Predtým ale potrebujeme dodať do funkcie ďalší parameter s veľkosťou dát (lebo potrebujeme vedieť, že int zaberá v atribúte data viac pamäte ako taký double).

struct polozka * polozka_new(void * data, size_t velkost)

Ak je položka alokovaná:

nova->data = malloc(velkost);

vieme do nej skopírovať údaje doslova bit po bite, bajt po bajte. Na to slúži funkcia memcpy, ktorá je zovšeobecnením kopírovania reťazcov. Potrebuje tri veci:

  • cieľové miesto v pamäti: reprezentované ako generický pointer
  • zdrojové miesto v pamäti: reprezentované ako generický pointer
  • počet bajtov, ktoré sa majú skopírovať: zistíme ho z veľkosti dát.

Kód?

struct polozka * polozka_new(void * data, size_t velkost) {
        struct polozka * nova = malloc(sizeof(struct polozka));
        if(nova == NULL) {
                perror("Malloc() polozky zlyhal");
                exit(EXIT_FAILURE);
        }

        /* alokujeme pamat pre data v polozke */
        nova->data = malloc(velkost);
        if(nova->data == NULL) {
            perror("Malloc() dat zlyhal");
            exit(EXIT_FAILURE);
        }
        /* skopirujeme bajty do polozky */
        memcpy(nova->data, data, velkost);
        nova->dalsi = NULL;

        return nova;
}

Použitie?

p = polozka_new(&i, sizeof(int));

Kompletný kód [korektná verzia]

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

struct polozka {
        void * data;
        struct polozka * dalsi;
};

struct polozka * polozka_new(void * data, size_t velkost) {
        struct polozka * nova = malloc(sizeof(struct polozka));
        if(nova == NULL) {
                perror("Malloc() polozky zlyhal");
                exit(EXIT_FAILURE);
        }

        nova->data = malloc(velkost);
        if(nova->data == NULL) {
            perror("Malloc() dat zlyhal");
            exit(EXIT_FAILURE);
        }
        memcpy(nova->data, data, velkost);
        nova->dalsi = NULL;

        return nova;
}

int main(void)
{
    int i;

    struct polozka * p = NULL;
    struct polozka * z = NULL;

    for(i = 0; i < 10; i++) {
            p = polozka_new(&i, sizeof(int));
            p->dalsi = z;
            z = p;
    }

    /*===================*/


    p = z;
    while(p != NULL) {
            printf("%d ", *( (int *) p->data));
            p = p->dalsi;
    }


    return EXIT_SUCCESS;
}

Pridaj komentár

Vaša e-mailová adresa nebude zverejnená. Vyžadované polia sú označené *