Χρήστος Κοίλιας Δομές Δεδομένων και Οργανώσεις Αρχείων. Εκδόσεις Νέων Τεχνολογιών, 1993.
/* * Abstract Data Type Definition file point.h */ typedef struct s_point *point; point new_point(void); int get_x_point(point p); int get_y_point(point p); void set_point(point p, int x, int y); void delete_point(point p);
/*
* Abstract Data Type Implementation file point.c
*/
#include <stdlib.h>
#include "point.h"
struct s_point {
int x, y; /* Point coordinates */
};
point
new_point(void)
{
return (point)malloc(sizeof(struct s_point));
}
int
get_x_point(point p)
{
return (p->x);
}
int
get_y_point(point p);
{
return (p->y);
}
void
set_point(point p, int x, int y)
{
p->x = x;
p->y = y;
}
void
delete_point(point p)
{
free(p);
}
Σημείωση: στη γλώσσα C++ οι μέθοδοι new και delete παρέχονται από τη γλώσσα, ενώ στις υπόλοιπες συναρτήσεις ο δείκτης p μεταφέρεται αυτόματα
Το παρακάτω παράδειγμα ορίζει έναν ΑΤΔ για πίνακα ακεραίων δύο διαστάσεων με δυναμικά οριζόμενες διαστάσεις. Ο υπολογισμός της θέσης ενός στοιχείου γίνεται με τη απεικόνιση των δύο διαστάσεων του πίνακα στη μία διάσταση της δυναμικής μνήμης.
/* * 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);
/*
* 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);
}
Εναλλακτικά, μπορούμε να υλοποιήσουμε τον πίνακα δύο διαστάσεων με βάση έναν πίνακα από δείκτες σε πίνακες μιας διάστασης. Η τεχνική αυτή υλοποίησης μπορεί να είναι αποδοτικότερη σε αρχιτεκτονικές όπου ο πολλαπλασιασμός διαρκεί μεγαλύτερο χρόνο από την πρόσβαση στη μνήμη ή σε περιπτώσεις όπου οι διαστάσεις των γραμμών του πίνακα δεν είναι όλες ίσες.
Οι δηλώσεις του ΑΤΔ παραμένουν φυσικά οι ίδιες.
/*
* 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);
}
/*
* Abstract Data Type Implementation file array2d.c
* Array of pointer implementation
* Special case for symmetric arrays
*/
#include <stdlib.h>
#include <assert.h>
#include "sym.h"
struct s_array2d {
int **values; /* Value storage */
int rows, cols; /* Dimensions */
};
/*
* Given a pointer to a symmetric array and the coordinates of an
* an element return a pointer to its location. Elements on the left
* and below the diagonal are mapped using the diagonal as the axis of
* symmetry
*/
static int *
value_position(array2d a, int row, int col)
{
assert(row >= 0 && row < a->rows);
assert(col >= 0 && col < a->cols);
if (row > col)
return (&(a->values[col][row]));
else
return (&(a->values[row][col]));
}
array2d
new_array2d(int rows, int cols)
{
array2d a;
int i;
assert(rows == cols); /* Must be symmetric */
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((i + 1) * sizeof(int));
assert(a->values[i] != NULL);
}
a->rows = rows;
a->cols = cols;
return (a);
}
void
set_val_array2d(array2d a, int row, int col, int val)
{
*value_position(a, row, col) = val;
}
int
get_val_array2d(array2d a, int row, int col)
{
return (*value_position(a, row, col));
}
void
delete_array2d(array2d a)
{
int i;
for (i = 0; i < a->rows; i++)
free(a->values[i]);
free(a->values);
free(a);
}
$rental_price{"Car category A"} = 12000;
$rental_price{"Car category B"} = 14000;
$rental_price{"Car category D"} = 16000;
$rental_price{"Car category R"} = 20000;
print $rental_price{"Car category R"};
Τελευταία αλλαγή: Δευτέρα, 2 Αυγούστου 2004 12:26 πμ
Εκτός αν αναφέρεται κάτι διαφορετικό, όλο το πρωτότυπο υλικό της σελίδας αυτής
του οποίου δημιουργός είναι ο Διομήδης Σπινέλλης παρέχεται σύμφωνα με τους
όρους της άδειας
«Creative Commons Attribution-Share Alike 3.0 Greece License».