Strukture podataka i algoritmi: Nizovi

Strukture podataka i algoritmi

3 Strukture podataka

U ovoj glavi cemo proucavati neke osnovne strukture podataka: nizove, liste i stekove.

3.1 Nizovi

Najjednostavniji nacin za implementaciju naseg skupa je koriscenjem niza za cuvanje njegovih elemenata. Tada implementacija niza postaje:


/* Implementacija apstraktnog tipa skup pomocu niza */
#include <assert.h>		/* Zbog funkcija "assert" */
#include "collection.h"	/* ucitava specifikaciju */

struct t_collection {
	int item_cnt;
	int max_cnt;	/* Nije apsolutno neophodno */
	int item_size;	/* Potrebno zbog FindInCollection */
	void *items[];
	};

Stvari koje treba primetiti:

Ucitali smo specifikaciju ovog objekta u njegovu implementaciju - sto omogucava kompajleru da proveri da implementacija i specifikacija odgovaraju jedna drugoj. Iako ucitavanje specifikacije nije strogo neophodno, mnogo je sigurnije uraditi tako, jer to omogucava kompajleru da uoci neke uobicajene greske i osigurava da specifikacija i implementacija ostaju u saglasnosti kada se promeni objekat.
items je navedeno kao niz void * pointera u definiciji strukture. To je niz objekata koji su, u stvari, pointeri - ali, setimo se da mi to pokusavamo da sakrijemo od korisnika klase. Mnogi C programeri bi ovde napisali ekvivalentnu definiciju sa void **.

Pitanje:

Zasto atributmax_cnt nije apsolutno neophodan?
Uputstvo: razlog je u vezi sa pre- i post-uslovima specificiranim za metode ovog objekta.

Implementacija metoda je data u:
Ucitaj collection.c

Stvari koje treba primetiti:

Metod ConsCollection koristi funkciju za alociranje memorije calloc da bi dinamicki alociro memoriju za skup sa programskog heap-a. Neophodna su dva poziva - jedan da bi alocirao memoriju za "zaglavlje" same strukture i drugi da bi alocirao memoriju za niz pointera.
Pozivi metoda assert su dodati zbog pre-uslova (videti pun opis assert funkcije). Primetimo da su pre-uslovi ovde izrazeni kao posebni uslovi povezani sa &&. Posto assert funkcija prihvata samo proizvoljan logicki izraz kao svoj argument, jedna assert funkcija bi bila dovoljna. Medjutim, izabrali smo da svaki uslov implementiramo kao posebnu assert funkciju. Ovo je uradjeno da bi smo olaksali debagiranje: ako pre-uslovi nisu zadovoljeni, veoma je korisno znati tacno koji od pre-uslova nije bio zadovoljen!
Funkcija memcmp je standardna bibliotecka funkcija koja poredi dva bloka memorije bajt po bajt [Unix man strana za memcmp].
Koriscenje memcmp i ItemKey dosta ogranicava oblik kljuca - on se mora nalaziti u uzastopnom nizu karaktera u objektu. Postoje nacini za obezbedjivanje fleksibilnijih kljuceva (npr. koji imaju vise polja u item ili koji se izracunavaju na osnovu item). Ovo se zasniva na mogucnostima C-a, o kojima ce kasnije biti reci.
Ne postoji tretman gresaka, npr. ako nema dovoljno memorije na programskom heap-u prilikom poziva funkcije calloc.
Ovo je veoma ozbiljan nedostatak.
Nijedan program bez saglasne strategije za otkrivanje, prijavljivanje i oporavljanje od gresaka ne moze se smatrati dobro konstruisanim. Takve programe je tesko debagovati i oni su podlozni pucanju zbog gresaka koje je tesko ispraviti, jer nema pokazatelja na uzrok greske.

Kljucni pojmovi