1. Homepage of Dr. Zoltán Porkoláb
    1. Home
    2. Archive
  2. Teaching
    1. Timetable
    2. Imperative programming (BSc)
    3. Multiparadigm programming (MSc)
    4. C programming (BSc for physicists)
    5. Project tools (BSc)
    6. Bolyai College
    7. C++ (for foreign studenst)
    8. Software technology lab
    9. BSc and MSc thesis
  3. Research
    1. Templight
    2. CodeChecker
    3. CodeCompass
    4. Projects
    5. Publications (up to 2011)
    6. PhD students
  4. Affiliations
    1. Dept. of Programming Languages and Compilers
    2. Ericsson Hungary Ltd

Imperatív programozás 9.

Összetett adatszerkezetek

A programozási nyelvekben gyakan van szükség összetett adatok kezelésére. Ezek közé tartozik a tömb (tömbök), ami azonos típusú elemek (egy- vagy többdimenziós) véges sorozatából áll, a rekord, ami különböző típusok rendezett N-ese, az únió, ami egy időben véges számú típus közül pontosan egyet tudj tárolni. Bár nem összetett adattípus, de itt tárgyaljuk a felsorolási típust is. Egyes imperatív nyelvekben további összetett típusok is létezhetnek, mint pl. a halmaz (set) típus Pascal-ban.

Az összetett típusok maguk is tartalmazhatnak beépített vagy összetett típusokat, így alkothatunk rekordokból vagy úniókból tömböket, rekordok és úniók tartalmazhatnak tömböket, rekordokat, úniókat, felsorolási értékeket.

Rekord típus

Programjainkban gyakran kell többféle adatot együtt kezelnünk: pl. egy dolgozó aznosítóját, nevét, beosztását, születési dátumát; egy előadás kódját, oktatóját, a hozzás tartozó gyakorlatok adatait (amik maguk is lehetnek összetett adatok). Ilyenkor kényelmes lenne, ha ezeket az adatokat egyetlen változóban tárolhatnánk, paraméterként átadhatnánk, egyetlen utasítással adhatnánk értéket. Ezt a fajta adatszerkezetet nevezzük rekord-nak, (record) vagy struktúrának (struct). Az R = (R1, R2, …, Rn) rekord a T1, T2, … Tn típusok direkt szorzata R = T1 x T2 x … x Tn.

A rekord típus összetevőit tag-nak (member) vagy mező-nek (field) nevezzük, minden tag egy névvel és típussal rendelkezik, és ez utóbbinak megfelelő műveleteket lehet elvégezni rajta. A rekord típus leggyakoribb implementációja, hogy az egyes tagok egymás után helyezkednek el a memóriában. Minden tag a rekord elejéhez képest saját távolsággal (offset) rendelkezik. Esetenként azonban a tagok között lehetnek “lyukak” (gap) is, itt nem tárolunk információt. Lyukak amiatt lehetnek, mert egyes fordítók bizonyos típusokat csak adott bájtcímekre helyezhetnek el. Ebből következően a rekord mérete nagyobb vagy egyenlő a mezők méreteinek összegével.

A rekord típussal rendszerint csak a legegyszerűbb műveleteket végezhetjük el, pl. értékadás, ide értve az érték szerinti paraméterátadást és függvényvisszatérést is, a rekord címének lekérdezése, és az egyes tagok (mezők) elérése. Miután a rekord egy mezőjét elértük, az adott mező típusának megfelelő műveleteket végezhetünk rajta.

Előfordul, hogy a rekord bizonyos része többféleképpen is lehet definiálva. Az ilyen variadic record-okat lentebb, az úniónál tárgyaljuk.

Az objektum-orientált nyelvekben az osztályt (class) tekinthetjük a rekordtípus olyan általánosításának, ahol az adattagok mellett a rajtuk végzett műveleteket (tagfüggvényeket) is definiálhatjuk, illetve megadhatjuk az egyes tagok hozzáférési jogait (public, private, …).

Struct C-ben

A C programozási nyelvben a rekord (struktúra) típust a struct konstrukció valósítja meg. A struct kulcsszó része a struktúra típusnevének, azaz a változó deklarációjából nem hagyhatjuk el. A következő példában egy dátum int számhármassal történő lehetséges megvalósítása szerepel:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct date
{
  int year;
  int month;
  int day;   
};

void f(void)
{
  struct date exam = { 2018, 12, 17}; /* mezőnkénti inicializálás  */
  struct date *ep = &exam;            /* ep a vizsgára mutat       */ 
  ++exam.day;               /* egy nappal elhalasztva              */
  (*ep).day += 2;           /* még két nap halasztás               */
  ep->day += 3;             /* ep->day ugyanaz, mint az (*ep).day  */
  assert(ep == &ep->year);  /* struct címe azonos első tag címével */

  struct date y2019 = {2019};   /* csak a year mezőt inicializálja */
  struct date xmas  = { .month = 12, .day = 24 };  /* csak C99 óta */ 
}

A tagok elérését a pont (dot, member access) operátor teszi lehetővé. A struktúra típusú változó címét a szokásos címoperátorral (&) kérhetjük le, ennek a C-ben azonosnak kell lennie az első adattag (itt a year) címével. Mivel nagyon gyakori, hogy egy struktúrát a rá mutató pointeren keresztül érünk el, a (*ptr).field kifejezés helyett használhatjuk a rövidebb ptr->field jelölést. A struktúrát a tömböknél megszokott listával { … } inicializálhatjuk, illetve C99-től használhatunk inicializálást csak egyes mezőkre is.

Fontos megérteni, hogy a fenti példában az 1-6 sorok egy struktúra típust definiálnak. Ez nem egy változó, nem konkrét adatterület, nem lehet bele írni. Ez csak a dátum típus leírása, hogyan kell értelmezni a date összetett adatszerkezetet. Értékeket csak változókba írhatunk, azt létre kell hoznunk, pl. a 10. sorban található definicióval.

A következő példában egy alakzat típust definiálunk.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct square 
{ 
  int centerX; 
  int centerY; 
  int side; 
};

struct square move( struct square s, int deltaX, int deltaY);

void f(void)
{
  struct square mySquare = { 0, 0, 10 };   /* inicializáció */

  mySquare.centerX += 20;    /* mozgassuk el mySquare-t */ 
  mySquare.centerY += 30;    /* a (+20,+30) vektorral   */ 

  mySquare = move(mySquare, 20, 30);  /* függvénnyel */
}

Egy C struct változóit értékül adhatjuk hasonló típusú változóknak, ilyenkor az összes adattag átmásolódik. Ahogy a fenti példa mutatja, struct-okat átadhatunk paraméterként függvényeknek, és azok vissza is adhatnak struct-okat.Ilyenkor az érték szerinti paraméterátadás szerint a teljes struct másolódik (ellentétben a tömbökkel, ahol az első elemre mutató pointer adódik át). Ha sok adattagból álló nagyméretű struct-ot használunk, néha hatékonysági okokból a címűket adjuk át paraméterként. Struktúrákra a relációs műveletek, mint pl. az == és != nem értelmezett.

Struktúrák tartalmazhatnak további struktúrákat. Egy személy például rendelkezik születési dátummal:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct person
{
  char         name[40];
  struct date  birthday;
};

int ask(void);
void f(void)
{
  struct person dean;
  strncpy( dean.name, "Horvath Zoltan", 40);
  dean.name[39] = '\0';
  dean.birthday.year = ask();
}

Mivel a pont operátor balról asszociatív (operátorok), ezért a dátum adattagjai eléréséhez nem kell zárójelezni.

Előfordul, hogy önhivatkozó adatszerkezeteket szeretnénk létrehozni. Egy személynek pl. lehetnek szülei és gyermekei is, akik szintén emberek. Ilyenkor a személy struktúra fizikailag nem tartalmazhatja önnmagát, de a logikai kapcsolatokat kifejezhetjük pointerekkel.

1
2
3
4
5
6
7
8
struct person
{ 
  char           name[20]; 
  struct date    birthday;
  struct person *father;
  struct person *mother;
  struct person *children[10];
};

Még az a helyzet is előfordulhat, hogy két struktúra kölcsönösen egymásra hivatkozik. Mivel a C fordító feltételezi, hogy egy típus definíciójában a meghivatkozott nevek már definiáltak, a hivatkozási kört egy előzetes deklarációval (forard declaration) tudjuk feloldani:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct manager;

struct staffmember
{
  struct person   pers;
  struct manager *boss;
};

struct manager
{ 
  struct person       pers;
  struct manager     *boss;
  struct staffmember *staff[10];
};

A legmagasabb pozícióban dolgozó főnök boss pointere NULL lesz.

Felsorolási típus C-ben

A C felsorolási típus valójában egy egész értékekből álló halmaz, aminek értékeit szimbolikus nevekkel jelölhetjük.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
enum color { WHITE, GREEN = 5, YELLOW, RED, BLACK};

void f(void)
{
  enum color traffic_light = RED;
  enum color *cptr = &traffic_light;

  switch( *cptr )
  {
  case RED:    puts("stop!");  break;
  case YELLOW: puts("break!"); break; 
  default:     puts("go!");    break;
  }
  if ( *cptr < YELLOW )   puts("go!");
  *cptr += 1;                    
  assert ( *cptr == BLACK );
}

A felsorolási típus értékei a { } közötti felsorolásból kerülnek ki. Ha a felsorolóban egy névnél szerepel a = jel, akkor az a felsoroló azt az értéket veszi fel. Ha ilyen nem szerepel, akkor az előző felsorolónál egyel nagyobb lesz. Az első felsoroló értéke, ha explicit mást nem rendelünk hozzá a nulla lesz. Az értékeknek egyedieknek kell lennie, ezt a fordító ellenőrzi.

A felsolási értékek valamely egész típusra képződnek le, mint a char signed vagy unsigned int. Ennek megfelelően a felsorolási értékek úgy viselkednek, mint az egészek, rézst vesznek konverziókban és alkalmazhatóak rájuk az aritmetikai operátorok is.

Únió típus

Egy másik összetett adatszerkezet, az únió (union), ami a halmazok úniójához hasonló konstrukció. Az U = (U1, U2, …, Un) únió, a _T1, T2, …, Tn típuok úniója _U = T1 u T2 u … u Tn. Amíg a rekordban a tagokat egy időben egyszerre, egymás után tároljuk, addig az únióban csak egyetlen típust tárolhatunk egy időben, de később ezt felülírhatjuk egy másik típussal. Ebből következően az únió mérete legalább akkora, mint a legnagyobb komponense (néha technikai okokból annál hosszabb).

Az únió tagjait úgy is tekinthetjük, mint típusbiztos interfészt, amelyen keresztül beírhatunk és kiolvashatunk az únióba. Amennyiben nem a megfelelő tagot használjuk kiolvasáshoz, akkor az eredmény hibás lehet.

Statikus típusrendszer esetén azt, hogy mi volt a legutolsó értékadás típusa, vagy a programozó kell számontartsa, vagy tudhatja maga az únió típusú változó. Ez utóbbi esetben ún. címkézett únió-ról (tagged union) vagy variáns (variant record) típusról beszélünk. Ilyen tagged union létezik számos funkcionális és imperatív nyelvben, pl. a Pascal-ban, Modula-2-ben, az Ada-ban, a Scala-ban, Rust-ban. A C++-ban a C++17-es szabványtól az std::variant típus valósítja meg.

1
2
3
4
5
6
7
8
9
10
(* Pascal variant record *)
type shapeKind = (square, rectangle, circle);
 shape = record
    centerx : integer;
    centery : integer;
    case kind : shapeKind of
      square : (side : integer);
      rectangle : (lenA, lenB : integer);
      circle : (radius : integer)
end;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
-- Ada variant record (discriminated type) 
type Shape_Kind is (Square, Rectangle, Circle);
type Shape (Kind : Shape_Kind) is record
   Center_X : Integer;
   Center_Y : Integer;
   case Kind is
      when Square =>
         Side : Integer;
      when Rectangle =>
         LenA, LenB : Integer;
      when Circle =>
         Radius : Integer;
   end case;
end record;
1
2
3
4
5
6
// C++ variant típus C++17-től, korábban használható a boost::variant
class Square { ... };
class Rectangle { ... };
class Circle { ... };

use Shape = std::variant<Square, Rectangle, Circle>;

Az objektum-orientált nyelvekben a tagged union-t gyakran örökléssel valósítjuk meg: az únió egy interfész vagy ha vannak közös adatok, akkor egy bázisosztály és ez egyes “variánsok” pedig a származtatott típusban valósíthatóak meg.

A dinamikus típusrendszerű nyelvekben nincsen szükség variant-ra, hiszen maguk az objektumok “ismerik” saját típusukat. Pythonban például írhatunk ilyet:

1
2
def f(x):
    return 2 if x else "s"

Ugyanakkor a Python 3.5 által bevezetett type hint-ek segítségével az únió használatot explicitté lehet tenni, ami sokat segíthet külső eszközök, pl. szintaxis ellenőrzők vagy editorok használatakor.

1
2
3
4
5
6
7
8
from typing import Union,TypeVar

T = TypeVar('T')
def f(x: T) -> Union[int, str]:
    if x:
        return 2
    else:
        return "s"

Unió C-ben

A C-ben az únió típust a union kulcsszóval hozzuk létre. Akárcsak a struct-nál, a union kulcsszó is része a típus nevének. A union-t képzelhetjük egy olyan struct-nak, ahol az összes adattag az únió kezdőcímén kezdődik, így atagok lényegében “átfedik” egymást.

A C nyelv nem rendelkezik tagged union típussal, az úniók tartalmának éppen aktuális típusát a programozónak kell számon tartania. Ezt gyakran úgy valósítjuk meg, hogy együttesen használjuk a struct és union konstrukciókat és esetleg a felsorolási típust is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
struct square { int centerX; int centerY; int side; };
struct rectangle { int centerX; int centerY; int lenA; int lenB; };
struct circle { int centerX; int centerY; int radius; };

enum shape_tag_t { square_tag, rectangle_tag, circle_tag };

struct shape
{
  enum shape_tag_t tag;
  union shapeKind
  {
    struct square    s;
    struct rectangle r;
    struct circle    c;
  }   u;
};

void f(void)
{
  struct circle cir = { 0, 0, 100 };
  
  struct shape  s; 
  s.tag = circle_tag;
  s.u.c = cir;

  printf( "%d %d %d\n", s.u.c.centerX, s.u.c.centerY, s.u.c.radius);
}

Látszik, hogy a shapeKind únió nevet sehol sem használjuk a programban. Valójában el is hagyhatjuk, így egy név nélküli (anonym) úniót hozunk létre u tagnévvel. Mivel az s, r és c tagnevek csak az u union tagban fordulnak elő, ezért használatukkor az u el is hagyható:

1
2
3
4
5
6
7
8
9
10
void f(void)
{
  struct circle cir = { 0, 0, 100 };
  
  struct shape  s; 
  s.tag = circle_tag;
  s.c = cir;

  printf( "%d %d %d\n", s.c.centerX, s.c.centerY, s.c.radius);
}

Ahogy korábban volt róla szó, a tag-ek lényegében “típusbiztos kapuk”, amelyen keresztül elérjük az únióban eltárolt valamely értéket. Ha nem az a tagot használjuk olvasásra, amin keresztül legutóbb írtunk az únió értékét, hibát kaphatunk. Néha mégis szándékosan csinálunk ilyet, pl. ha egy tpus értékét a bitek megváltoztatása nélkül egy másik típusban akarunk tárolni. Ilyen eset lehet, pl. ha egy bináris adatot akarunk hálózaton átküldeni, és az únió egyik tagja egy kellően hosszú karaktertömb, amit a hálózati függvény fog továbbítani.

Vigyázat!, ez nem egy klasszikus értelemben vett típuskonverzió, hiszen a bitek értéke nem változik meg. Ha pl. egy double és int adattagú únióba beírunk egy double számot és egészként olvassuk ki, akkor a lebegőpontos ábrázolás első pár bájtját próbálnánk (valószínűleg értelmetlen) egész számként értelmezni.

Dinamikus memóriakezelés

A C programok statikus, automatikus és dinamikus élettartamú tárterületeket hozhatnak létre (Élettartam). A globális és lokális statikus változók élettartama a program elejétől a végéig tart. A nem statikus lokálisak a veremben jönnek létre az őket deklaráló blokkba való belépéskor és felszámolódnak, amikor kilépünk a blokkból. Lehetséges azonban, hogy ad-hc módon kell tárterületet foglalnunk, vagy előre nem ismerjük a szükséges méretet. Ilyenkor használjuk a dinamikus élettartamot.

A dinamikus élettartamú objektumokat a szabad memóriában (free store, heap) foglaljuk le. Majdnem minden imperatív nyelv rendelkezik szabad memóriával, de annak használata erősen változó.

Java-ban, C#-ban objektumokat csak a szabad memóriában tudunk létrehozni a new segítségével. Ami lokális változó(nak) látszik, az is csak egy referencia (valójában egy pointer), maga az objektum a heap-ben jön létre. A C nyelvben minden objektum (egyszerű vagy összetett típusú) létrejöhet a statikus, az automatikus és a dinamikus tárterületen is.

A tárterület lefoglalása a malloc(size_t sz) függvénnyel történik, melynek a lefoglalandó bájtok számát adjuk meg. Hasznos, ha a paramétert a sizeof operátoron keresztül adjuk meg, nem pedig “beégetjük” a programba. A visszatérő érték típusa void *, amit a kívánt típusra mutató pointerré kell konvertálnunk. A malloc garantálja, hogy a lefoglalt tárterületen tetszőleges típusú objektum tárolható. Viszont a tárterület nem lesz inicializálva, lényegében “memória-szemetet” fog tartalmazni. Ha a tárterületet csupa nulla bitre szeretnénk inicializálni, a calloc(size_t num, size_t sz) függvényt használjuk, ami num darab sz méretű objektumnak foglal helyet és a területet nullára inicializálja.

A tárterület lefoglalva marad, amíg azt a free(ptr) függvénnyel vissza nem adjuk a szabad memória számára. A ptr mindenképpen egy malloc(), calloc(), vagy realloc() függvény által adott kell legyen. Ha a tárterület visszaadásáról megfeledkezünk, akkor elfogyhat a szabad memória. Ilyenkor amalloc(), calloc(), realloc() függvények NULL pointerat adnak vissza. Mindig ellenőrizzük ezen függvények visszatérő értékét!

Ellentétben más programozási nyelvekkel, a C-ben (és C++-ban) nincsen automatikus szemétgyűjtés (garbage collection), azaz a már nem használt, akár már hivatkozás hiányában el sem érhető tárterületek sem szabadulnak fel automatikusan. Ehhez mindig a free() függyvény meghívása kell. Azt a jelenséget, amikor az elérhetetlen tárterület a programozó hibájából lefoglalva marad, nevezzük memória elszivárgásnak (memory leak). Hosszan futó programok esetében (pl. egy szerver program vagy maga az operációs rendszer) a memoriaelszivárgás súlyos gondokat okozhat.

A dinamikusan lefoglalt tárterületet a realloc(void *ptr, size_t newsize) függvénnyel tudjuk átméretezni. A ptr az egy előzőleg lefoglalt tárterület, newsize pedig a kívánt új méret. A realloc() megpróbálja helyben megnövelni a tárterületet, ha ez nem sikerül, akkor más helyen foglalja azt le, odamásolja a régi terület tartalmát, majd felszabadítja azt. Ha nem sikerül az új helyfoglalás, akkor NULL poinrter tér vissza és a régi terület megőrződik, siker esetén az aktuális (akár új) területre mutató pointer tér vissza. A realloc() elvileg alkalmas a lefoglalt terület csökkentésére is, azonban implementáció függő, hogy valóban visszaad-e memóriát.

A realloc() veszélyes lehet, ha az átméretezendő tárterületünkre más mutatók hivatkoznak. Ilyenkor elmozgatva a hivatkozott tárterületet a mutatók érvénytelenné válnak.

Megjegyzések

  1. A szabad memória számon tartja, hogy mekkora területet foglaltunk le, ezt a free()-nek nem kell megadnia. Az információ a heap-ben, a ptr környékén tárolódik, ha nem helyes pointerrel akarunk felszabadítani, az futási idejű hibát fog okozni.

  2. Vannak platformok, ahol a programban több heap is létezik, pl. a főprogramban és egyes dinamikus library-kben (.DLL, .so) is. Ilyenkor fontos, hogy ugyanaz a programrész szabadítsa fel a memóriát, aki lefoglalta, különben esetleg a free függvény rossz heap-be próbálná visszaadni a tárterületet. Ez futási idejű hibához vezethet.

  3. Úgy is elfogyhat a memória, ha a különböző méretű lefoglalások és felszabadítások során feldarabolódik a heap. Ilyenkor lenne még elég szabad bájt, csak nincsen elég egyetlen összefüggő területen. A mai modern szabad memória implementációk számos módon próbálják ennek a lehetőségét csökkenteni. Érdekes megoldás a .NET framework-é, ott a managed heap feltömöríti a használt területet, így eltüntetve a lyukakat, egy összefüggő memóriaterületet hoz létre a szabad területből. Ilyenkor azonban az átmozgatott területre mutató pointerek értékeit is módosítani kell, ami komoly hatékonyságcsökkentő tevékenység.

  4. Ha egy területet felszabadítottunk, akkor tilos ismételten felszabadítani. Ilyen hibát akkor szoktunk kapni, ha egy pointert lemásolunk és mindkét helyen fel akarjuk szabadítani a mutatott tárterületet. Ez gyakran az ún. sekély másolás (shallow copy) eredménye, amikor a pointert másoljuk a mutatott tárterület helyett.

  5. A felszabadított memóriára tilos hivatkozni. Az indirekció (*) operátor használata ilyenkor futási idejű hibát okozhat.

  6. A free() függvénynek átadhatunk NULL pointert, ilyenkor a hatása az üres utasítással ekvivalens. A free() viszont nem állítja NULL-ra az átadott pointer értékét.

  7. A heap műveletek szálbiztosak, azaz többszálú programban is biztonsággal használhatjuk őket. Viszont ez azt jelenti, hogy a heap használata a háttérben lock-olásokkal jár, ami csökkenti a hatékonyságot.

  8. Gyakori hiba, hogy egy C string másolása számára akarunk helyet foglalni az strlen függvény visszatérő értéke alapján. Azonban ha pont annyi helyet foglalunk le, akkor nem marad hely a lezáró bináris NUL karakterre. Ezt a hibát hívják off by one (OBOE, OB1) errornak. Helyesen használjuk a malloc(strlen(source)+1) kifejezést.

  9. A dinamikus élettartammal kapcsolatos függvények az <stdlib.h> headerben vannak deklarálva.

Egy példa összetett adatszerkezetek dinamikus kezelésére

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include <stdio.h>
#include <stdlib.h>

struct square { int centerX; int centerY; int side; };
struct rectangle { int centerX; int centerY; int lenA; int lenB; };
struct circle { int centerX; int centerY; int radius; };

typedef struct square    square_t;
typedef struct rectangle rectangle_t;
typedef struct circle    circle_t;

enum shape_tag_t { square_tag, rectangle_tag, circle_tag };

typedef
struct shape /* a shape on canvas */
{
  int               id;
  enum shape_tag_t tag;
  union shapeKind
  {
    square_t    s;
    rectangle_t r;
    circle_t    c;
  }   u;
} shape_t;

typedef
struct elem  /* one node in object ist */
{
  shape_t     *shp;
  struct elem *next;
} elem_t;

typedef
struct canvas  /* the canvas for shapes */
{
  int     count;
  elem_t *first;
} canvas_t;

int genId()
{
  static int i = 0;
  return i++;
}

shape_t *createSquare( int x, int y, int side)
{
  shape_t *sp = (shape_t *)malloc(sizeof(shape_t));
  if ( NULL == sp )
    return NULL;
  sp->id        = genId();
  sp->tag       = square_tag;
  sp->u.s.centerX = x; 
  sp->u.s.centerY = y; 
  sp->u.s.side    = side;
  return sp; 
}

shape_t *createRectangle( int x, int y, int a, int b)
{
  shape_t *sp = (shape_t *)malloc(sizeof(shape_t));
  if ( NULL == sp )
    return NULL;
  sp->id        = genId();
  sp->tag       = rectangle_tag;
  sp->u.r.centerX = x; 
  sp->u.r.centerY = y; 
  sp->u.r.lenA    = a;
  sp->u.r.lenB    = b;
  return sp; 
}

shape_t *createCircle( int x, int y, int r)
{
  shape_t *sp = (shape_t *)malloc(sizeof(shape_t));
  if ( NULL == sp )
    return NULL;
  sp->id        = genId();
  sp->tag       = circle_tag;
  sp->u.c.centerX = x; 
  sp->u.c.centerY = y; 
  sp->u.c.radius  = r;
  return sp; 
}

char *sShapeKind(enum shape_tag_t tg)
{
  switch( tg )
  {
  case    square_tag: return "square";
  case rectangle_tag: return "rectangle"; 
  case    circle_tag: return "circle";
  default           : return "unknown";
  }
}
 
void printShape(shape_t *sp)
{
  printf("id = %d, type = %s\n", sp->id, sShapeKind(sp->tag));
}

void initCanvas( canvas_t *cp)
{
  cp->count = 0;
  cp->first = NULL;
}

void addCanvas( canvas_t *cp, shape_t *sp)
{
  elem_t *newElem = (elem_t *)malloc(sizeof(elem_t));
  newElem->shp = sp; 
  newElem->next = NULL;
  if ( 0 == cp->count )
    cp->first = newElem; 
  else
  {
    elem_t *p = cp->first;
    while ( NULL != p->next )
      p = p->next;
    p->next = newElem;
  }
  ++cp->count;
}
void deleteCanvas( canvas_t *cp)
{
  elem_t *ep = cp->first;
  while ( NULL != ep )
  {
    elem_t *ptrToDel = ep;
    ep = ep->next;

    free( ptrToDel->shp);
    free( ptrToDel); 
  }
}

void printCanvas( canvas_t *cp)
{
  elem_t *ep = cp->first;
  printf( "num of shapes = %d\n", cp->count);
  
  while ( NULL != ep )
  {
    printShape(ep->shp);
    ep = ep->next;
  }
}

int main()
{
  canvas_t cvs;

  initCanvas( &cvs);

  addCanvas( &cvs, createCircle( 10, 10, 20));
  addCanvas( &cvs, createRectangle( 14, 20, 10, 30)); 

  printCanvas( &cvs);
  deleteCanvas( &cvs);

  return 0;
}
$ ./a.out 
num of shapes = 2
id = 0, type = circle
id = 1, type = rectangle

A program futását ellenőrizhetjük valamely dinamikus analízis eszközzel, pl. a google memory sanitizer-rel vagy a valgrind-al.

valgrind ./a.out
==30117== Memcheck, a memory error detector
==30117== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==30117== Using Valgrind-3.10.1 and LibVEX; rerun with -h for copyright info
==30117== Command: ./a.out
==30117== 
num of shapes = 2
id = 0, type = circle
id = 1, type = rectangle
==30117== 
==30117== HEAP SUMMARY:
==30117==     in use at exit: 0 bytes in 0 blocks
==30117==   total heap usage: 4 allocs, 4 frees, 80 bytes allocated
==30117== 
==30117== All heap blocks were freed -- no leaks are possible
==30117== 
==30117== For counts of detected and suppressed errors, rerun with: -v
==30117== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)