2.3.3 Pointer Array Representation

The second technique for representing a two-dimensional array in terms of one-dimensional arrays uses a pointer array p. Pointer arrays have pointers as their entries. The entries of the pointer array point to the rows of a, which may be stored in one of two ways: in data (a one-dimensional array) or in the dynamic memory. The number of rows, r, of a must be known. Then p, data, and r represent a when the array is used, and p and r represent a when dynamic memory is used. In the array case, p is of integer type, as in Section 2.2.1. In fact, this is just an application of that method.

Clearly, there is no need to store the rows one after another in data; they can be anywhere in the array as long as they do not overlap. This feature provides considerable flexibility in the use of storage.

A variation of the array technique would treat the rows stored in data as row records. In the dynamic memory case, p is of type pointer, and the row records are stored in dynamic memory. Selection and traversal are thus both easily achieved. The corresponding versions (storing rows in data, storing row records in data, storing row records in dynamic memory) of the function check would appear as follows.

Version 1?/FONT>Storing Rows in Data

#define TRUE 1

#define FALSE 0

>Comment

typedef int pointerarray[50];

typedef int dataarray[2500];

check(p,data,r) /* storing rows in data */

/* Returns true only if the rxr

two-dimensional array, whose rows

are stored in data and are pointed to

by pointers stored in p, is symmetric.

*/

>Comment

pointerarray p;

dataarray data;

int r;

{

>Comment

int i,j,ck;

ck = TRUE;

for(i=1;i<r && ck;i++)

for(j=0;j<i && ck;j++)

>Comment

if(data [p[i]+j]! = data[p[j]+i])

ck = FALSE;

return (ck);

}

Version 2?/FONT>Storing Row Records in Data

#define TRUE l

#define FALSE 0

>Comment

typedef struct

{

int row[50];

}rowrecord;

typedef int pointerarray[50];

typedef rowrecord dataarray[50];

check (p, data, r) /* storing row records in data */

/* Returns true only if the rxr

two-dimensional array, whose rows

are stored in row records in data and

are pointed to by pointers stored

in p, is symmetric.

*/

>Comment

pointerarray p;

dataarray data;

int r;

{

>Comment

int i,j,ck;

ck = TRUE;

for(i=1;i<r && ck;i++)

for(j=0;j<i && ck;j++)

>Comment

if(data[p[i]].row[j] !=

data[p[j]].row[i])

ck=FALSE;

return(ck);

}

The third version (storing row records in dynamic memory) is a complete program with a driver for check(p,r). It illustrates reading and printing of r and the array represented by r and p. The input and output from its execution might appear as follows.

Typical Input and Output

Enter an integer between 1 and 50 for r

4

Enter the next rowrecord

  3   4  -67   8

Enter the next rowrecord

  4   5   23  57

Enter the next rowrecord

-67  23   -6   4

Enter the next rowrecord

  8  57    4   0

r is 4

The row records are:

  3   4  -67   8

  4   5   23  57

-67  23   -6   4

  8  57    4   0

The array is symmetric

The program reads the two-dimensional input array, represents it, checks it for symmetry, and outputs the result.

Version 3?/FONT>Storing Row Records in Dynamic Memory

#include <stdio.h>

#define TRUE 1

#define FALSE 0

>Comment

typedef struct

{

int row[50];

}rowrecord, *rowpointer;

typedef rowpointer pointerarray[50];

main()

/* Driver for check(p,r) */

{

>Comment

pointerarray p;

int r;

>Comment

int i,j;

>Comment

rowpointer malloc();

printf("Enter an integer between 1 and 50 for r\n");

scanf("%d",&r);

for(i=0;i<r;i++)

{

>Comment

p[i]=malloc(sizeof(rowrecord));

printf("Enter the next rowrecord\n");

>Comment

for(j=0;j<r;j++)

scanf("%d",&(p[i]->row[j]));

}

printf("\n r is %d \n",r);

printf("The row records are: \n");

for (i=0;i<r;i++)

{

printf("\n");

>Comment

for (j=0;j<r;j++)

printf("%3d",p[i]->row[j]);

}

if(check(p,r))

printf("\n The array is symmetric \n");

else

printf("\n The array is not symmetric \n");

}

check(p,r) /* Storing row records in dynamic memory */

/* Returns true only if the rxr

two-dimensional array, whose rows

are stored in row records in dynamic

memory and are pointed to by pointers

stored in p, is symmetric.

*/

pointerarray p;

int r;

{

>Comment

int i,j,ck;

ck=TRUE;

for(i=1;i<r && ck;i++)

for(j=0;j<i && ck;j++)

>Comment

if (p[i]->row[j] != p[j]->row[i])

ck=FALSE;

return (ck);

}

The pointer array technique may be used storing columns instead of rows. Then p's entries point to the column records.

Example 2.7

It is often desirable to store information in an array in a specific order. Algorithms to rearrange the information to achieve the order may require repeated interchange of rows. Suppose the programmer wants to interchange the ith and jth rows of the array a when it is represented using the pointer array p. This can be accomplished quickly, taking advantage of the pointers, by executing

temp = p[i];

p[i] = p[j];

p[j] = temp;

Note that the data in each row are not moved; only the pointers change. The time it takes the computer to switch rows is independent of their length. Contrast this with the processing involved for the rowwise method of representing a (Section 2.3.1). Even if a actually is available directly as a two-dimensional array, the pointer array representation is more efficient. Swapping columns, of course, is a much more involved task, unless the programmer has chosen to store columns rather than rows. n

The pointer array method offers the advantage of convenience in storing rows of different lengths. Thus it can be used to construct arrays with rows of different lengths easily. Also, if many rows of a are the same, they need not be duplicated in data or in dynamic memory. Their pointer entries in pointer array p need merely point to the same record, resulting in significant storage savings. The means should fit the ends as much as possible! In programming, the ends (the desired operations) determine the means (the data structures to be used).