Figure 23-1 Organization of a simple spreadsheet in Software

Maker Quick Response Code in Software Figure 23-1 Organization of a simple spreadsheet

Each new structure is placed in the list with the elements inserted in sorted order based on the array index The array is accessed by following the links For example, you can use the following structure as the basis of a sparse array in a spreadsheet program:

struct cell { char cell_name[9]; char formula[128]; struct cell *next; struct cell *prior; } ; /* /* /* /* cell name eg, A1, B34 */ info eg, 10/B2 */ pointer to next entry */ pointer to previous record */

The field cell_name holds a string that contains a cell name such as A1, B34, or Z19 The string formula holds the formula (data) that is assigned to each spreadsheet location An entire spreadsheet program would be far too large to use as an example Instead this chapter examines the key functions that support the linked-list sparse array Remember, there are many ways to implement a spreadsheet program The data structure and routines here are just examples of sparse-array techniques The following global variables point to the beginning and end of the linked-list array:

struct cell *start = NULL; /* first element in list */ struct cell *last = NULL; /* last element in list */

When you enter a formula into a cell in most spreadsheets, you are, in effect, creating a new element in the sparse array If the spreadsheet uses a linked list, that new cell is inserted into it via a function similar to dls_store( ), which was developed in 22 Remember that the list is sorted according to the cell name; that is, A12 precedes A13, and so on

/* Store cells in sorted order */ void dls_store(struct cell *i, /* pointer to new cell to insert */ struct cell **start, struct cell **last) { struct cell *old, *p; if(!*last) { /* first element in list */ i->next = NULL; i->prior = NULL; *last = i;

Page 567 *start = i; return; } p = *start; /* start at top of list */ old = NULL; while (p) { if(strcmp(p->cell_name, i->cell_name) < 0){ old = p; p = p->next; } else { if(p->prior) { /* is a middle element */ p->prior->next = i; i->next = p; i->prior = p->prior; p->prior = i; return; } i->next = p; /* new first element */ i->prior = NULL; p->prior = i; *start = i; return; } } old->next = i; /* put on end */ i->next = NULL; i->prior = old; *last = i; return; }

Here, the parameter i is a pointer to the new cell to insert The start and last parameters are pointers to pointers that point to the beginning and end of the list, respectively The deletecell( ) function, which follows, removes from the list the cell whose name is an argument to the function

void deletecell(char *cell_name, struct cell **start, struct cell **last)

Page 568 { struct cell *info; info = find(cell_name, *start); if(info) { if(*start==info) { *start = info->next; if(*start) (*start)->prior = NULL; else *last = NULL; } else { if(info->prior) info->prior->next = info->next; if(info != *last) info->next->prior = info->prior; else *last = info->prior; } free(info); /* return memory to system */ } }

The final function that you need in order to support a linked-list sparse array is find( ), which locates any specific cell The function requires a linear search to locate each item; and, as you saw in 21, the average number of comparisons in a linear search is n/2, where n is the number of elements in the list Here is find( ):

struct cell *find(char *cell_name, struct cell *start) { struct cell *info; info = start; while(info) { if(!strcmp(cell_name, info->cell_name)) return info; info = info->next; /* get next cell */ } printf(''Cell not found\n"); return NULL; /* not found */ }

Analysis of the Linked-List Approach The principal advantage of the linked-list approach to sparse arrays is that it makes efficient use of memory memory is used only for those elements in the array that