Υλοποίηση πινάκων

Πίνακες μιας διάστασης υλοποιούνται με τη διαδοχική φύλαξη των στοιχείων στη μνήμη.
Πίνακες δύο διαστάσεων υλοποιούνται με τη διαδοχική φύλαξη των στοιχείων κάθε γραμμής (C, Pascal) ή κάθε στήλης (Fortran) στη μνήμη.
Ανάλογα υλοποιούνται και πίνακες με περισσότερες από δύο διαστάσεις.
Έτσι το στοιχείο i,j ενός πίνακα Ν*Μ στοιχείων μεγέθους Κ βρίσκεται στη θέση μνήμης Κ * (i * M + j).
Πίνακες δύο και παραπάνω διαστάσεων μπορούν ακόμα να υλοποιηθούν με τη χρήση πινάκων μιας διάστασης και δεικτών (C).

Το παρακάτω παράδειγμα ορίζει έναν ΑΤΔ για πίνακα ακεραίων δύο διαστάσεων με δυναμικά οριζόμενες διαστάσεις. Ο υπολογισμός της θέσης ενός στοιχείου γίνεται με τη απεικόνιση των δύο διαστάσεων του πίνακα στη μία διάσταση της δυναμικής μνήμης.

Δηλώσεις: array2d.h

/*
 * Abstract Data Type Definition file array2d.h
 */

typedef struct s_array2d *array2d;

array2d new_array2d(int rows, int cols);
void array2d_set_value(array2d a, int row, int col, int val);
int array2d_get_value(array2d a, int row, int col);
void array2d_delete(array2d a);

Ορισμοί: array2d.c

/*
 * Abstract Data Type Implementation file array2d.c
 * 2D -> 1D mapping implementation
 */

#include <stdlib.h>
#include <assert.h>
#include "array2d.h"

struct s_array2d {
	int *values;		/* Value storage */
	int rows, cols;		/* Dimensions */
};

array2d
new_array2d(int rows, int cols)
{
	array2d a;

	a = (array2d)malloc(sizeof(struct s_array2d));
	assert(a != NULL);

	a->values = (int *)malloc(rows * cols * sizeof(int));
	assert(a->values != NULL);

	a->rows = rows;
	a->cols = cols;
}

void
array2d_set_value(array2d a, int row, int col, int val)
{
	assert(row > 0 && row < a->rows);
	assert(col > 0 && col < a->cols);
	a->values[row * a->cols + col] = val;
}

int
array2d_get_value(array2d a, int row, int col)
{
	assert(row > 0 && row < a->rows);
	assert(col > 0 && col < a->cols);
	return (a->values[row * a->cols + col]);
}

void
array2d_delete(array2d a)
{
	free(a->values);
	free(a);
}

Εναλλακτικά, μπορούμε να υλοποιήσουμε τον πίνακα δύο διαστάσεων με βάση έναν πίνακα από δείκτες σε πίνακες μιας διάστασης. Η τεχνική αυτή υλοποίησης μπορεί να είναι αποδοτικότερη σε αρχιτεκτονικές όπου ο πολλαπλασιασμός διαρκεί μεγαλύτερο χρόνο από την πρόσβαση στη μνήμη ή σε περιπτώσεις όπου οι διαστάσεις των γραμμών του πίνακα δεν είναι όλες ίσες.

Οι δηλώσεις του ΑΤΔ παραμένουν φυσικά οι ίδιες.

Ορισμοί: array2d.c

/*
 * Abstract Data Type Implementation file array2d.c
 * Array of pointer implementation
 */

#include <stdlib.h>
#include <assert.h>
#include "array2d.h"

struct s_array2d {
	int **values;		/* Value storage */
	int rows, cols;		/* Dimensions */
};

array2d
new_array2d(int rows, int cols)
{
	array2d a;
	int i;

	a = (array2d)malloc(sizeof(struct s_array2d));
	assert(a != NULL);

	a->values = (int **)malloc(rows * sizeof(int *));
	assert(a->values != NULL);

	for (i = 0; i < rows; i++) {
		a->values[i] = (int *)malloc(cols * sizeof(int));
		assert(a->values[i] != NULL);
	}

	a->rows = rows;
	a->cols = cols;
}

void
array2d_set_value(array2d a, int row, int col, int val)
{
	assert(row > 0 && row < a->rows);
	assert(col > 0 && col < a->cols);
	a->values[row][col] = val;
}

int
array2d_get_value(array2d a, int row, int col)
{
	assert(row > 0 && row < a->rows);
	assert(col > 0 && col < a->cols);
	return (a->values[row][col]);
}

void
array2d_delete(array2d a)
{
	int i;

	for (i = 0; i < a->rows; i++)
		free(a->values[i]);
	free(a->values);
	free(a);
}