Representation of a sparse array as an array of pointers in C

Suppose that a spreadsheet has a size of 26x100 (from A1 to Z100), that is, it consists of 2'600 elements. Theoretically, table elements can be stored in the following array of structures:

  struct cell {
   char cell_name [9];
   char formula [128];
 } list_entry [2600];  / * 2600 cells * /

Ho 2`600 multiplied by 137 bytes (the size of this structure in bytes) is 356`200 bytes of memory. This is too much memory to waste on an incompletely used array. Nevertheless, it is possible to create an array of pointers (pointer array) on structures of the type cell . It takes much less memory to store an array of pointers than an array of structures. Each time a cell is assigned a logical data array, memory is allocated for this data, and the address of the selection is assigned to the corresponding pointer in the array of pointers. This scheme allows to achieve higher performance than with a linked list or binary tree. The description of the array of pointers is as follows:

  struct cell {
   char cell_name [9]; 
   char formula [128];
 } list_entry;

 struct cell * sheet [2600];  / * array of 2600 pointers * /

This smaller memory array is used to store pointers to the data entered in the spreadsheet. When you enter the next entry in the appropriate cell of the array is entered a pointer to the entered data. In fig. Figure 23.2 shows what a sparse array looks like in memory, represented as an array of pointers.

  + - + - + - + - + - + - + - + - + - + - + - + - +
 |. |. | 0 | 0 |. | 0 | 0 | 0 |. | 0 | 0 | 0 |
 + | + | + - + - + | + - + - + - + | + - + - + - +
  |  |  |  |  + ---- +
  |  |  |  '-> | A [8] |
  |  |  |  + ---- +
  |  |  |  + ---- +
  |  |  '-> | A [4] |
  |  |  + ---- +
  |  |  + ---- +
  |  '-> | A [1] |
  |  + ---- +
  |  + ---- +
  '-> | A [0] |
     + ---- +

Before using an array of pointers, each of its elements must be initialized to zero ( NULL ), which means the absence of this entry. The following is the array initialization function:

  void init_sheet (void)
 {
   register int t;

   for (t = 0; t <2600; ++ t) sheet [t] = NULL;
 }

When a user enters a formula in a cell that occupies a certain position in the spreadsheet (and the position of the cell, as is known, is determined by its name), the index is calculated in the array of pointers sheet . This index is obtained by converting the string representation of the cell name into a number, as shown in the following listing:

  void store (struct cell * i)
 {
   int loc;
   char * p;

   / * calculate the index by the given name * /
   loc = * (i-> cell_name) - 'A';  / * column * /
   p = & (i-> cell_name [1]);
   loc + = (atoi (p) -1) * 26;  / * number of lines * line width +
                               column * /

   if (loc> = 2600) {
     printf ("Cell outside the array. \ n");
     return;
   }
   sheet [loc] = i;  / * put pointer into array * /
 }

When calculating the index in the store () function, it is assumed that all cell names begin with a capital letter followed by an integer, for example, B34, C19, etc. Therefore, as a result of calculations using the formula programmed in the store () function, the cell name A1 corresponds to index 0, the name B1 corresponds to index 1, A2 - 26, and so on. Since the cell names are unique, the indices are also unique and the pointer to each record is stored in the corresponding array position. If you compare this procedure with versions using a linked list or binary tree, it becomes clear how much simpler and shorter it is.

The deletecell () cell deletion function also becomes very short. When called, it simply resets the pointer to the element and returns the system memory.

  void deletecell (struct cell * i)
 {
   int loc;
   char * p;

   / * calculation of the index for a given cell name * /
   loc = * (i-> cell_name) - 'A';  / * column * /
   p = & (i-> cell_name [1]);
   loc + = (atoi (p) -1) * 26;  / * number of lines * line width + 
                               column * /

   if (loc> = 2600) {
     printf ("Cell outside the array. \ n");
     return;
   }
   if (! sheet [loc]) return;  / * do not free if pointer is zero
                              (null) * /

   free (sheet [loc]);  / * free up system memory * /
   sheet [loc] = NULL;
 }

This code is also much faster and easier than with the linked list version.

The process of finding a cell by name is simple, since the cell name uniquely identifies the index in the array of pointers. Therefore, the search function takes the following form:

  struct cell * find (char * cell_name)
 {
   int loc;
   char * p;

   / * calculation of the index for a given cell name * /
   loc = * (cell_name) - 'A';  / * column * /
   p = & (cell_name [1]);
   loc + = (atoi (p) -1) * 26;  / * number of lines * line width + 
                               column * /

   if (loc> = 2600 ||! sheet [loc]) {/ * this cell is empty * /
     printf ("Cell not found. \ n");
     return NULL;  / * search unsuccessful * /
   }
   else return sheet [loc];
 }

Analysis of the method of representing a sparse array as an array of pointers

The sparse array implementation method based on an array of pointers provides much faster access to elements than methods based on a linked list and binary tree. If the array is not very large, allocating memory for the array of pointers only slightly reduces the amount of free system memory. However, in the array of pointers, a certain amount of memory is allocated for each cell, regardless of whether it is used or not. In some applications this may be a limitation, although in general this is not a problem.