6.4: Implementing List-structures

The graphic depictions of list-structures mirror the conceptual image of them. To implement list-structures in a language such as C, you may store their records in dynamic memory or in an array of records. Wherever the records are stored, it must be possible to distinguish simple records from complex ones. The main difference in the format of the records, compared to those of a chain, is that an additional field becomes necessary for the sublist pointer when the record is complex. We also assume that the record contains a field whose value will establish whether the record is simple or complex. The actual implementation of a list-structure record may be done in three ways:

1. Declare two types of records:

one to be used for simple records

another to be used for complex records

2. Declare one record type that consists of a fixed part and a union, which has

one format for simple records

another format for complex records

3. Declare one record type, used for both simple and complex records, but containing a kind or tag field to indicate whether the record stored is simple or complex

The first way is undesirable because it requires that a program deal with two distinct pointer types, one for simple records and another for complex records, so we dismiss it. The second method is feasible and also requires a kind field, which we can put in the fixed part. However, even though the two distinct union formats may have significant differences in the amount of storage they require, C will always allocate the larger amount. Thus this method does not save storage over the third way, which we now choose to use.

To implement the accounts list-structure of Figure 6.1(a), the following definitions could be used when the records are to be stored in dynamic memory.

>Comment

typedef struct record

{

int kind;

int info;

struct record *sublist;

struct record *link;

}listrecord, *liststructurepointer;

When the records are to be stored in an array of records, the implementation should be changed to

>Comment

typedef struct record

{

int kind;

int info;

>Comment

int sublist;

>Comment

int link;

}listrecord;

>Comment

typedef int liststructurepointer;

This change is needed because now listpointer, link, and sublistptr will each be an integer index into the array of records rather than a pointer variable containing an absolute memory address.

As a second illustration, consider the records for the polynomials of Figure 6.1(e). Notice that a complex record in that list-structure has two possible formats, depending on whether the record is a header or not. If it is a header record, the second field contains a character; otherwise it contains a sublist pointer. Using a union, the polynomial records can be implemented as follows.

>Comment

typedef union

{

char unknown;

polyrecord *sublist;

int value;

}varying;

typedef struct record

{

int tag;

varying secondfield;

int exponent;

struct record *nextterm;

}polyrecord, *liststructurepointer;

The tag field indicates whether the record is simple or complex. In this implementation the union allows the same storage to be used to hold the unknown (for a header record) or a sublist pointer. It was used here because a complex record has two distinct possible second fields and the union allows them to share the same storage. The alternative is to avoid the use of the union and keep separate fields for both the unknown and the sublist pointer in each record. This just wastes storage.

When the records are to be stored in an array of records, the implementation should be changed to

>Comment

typedef union

{

char unknown;

>Comment

int sublist;

int value;

}varying;

typedef struct

{

int tag;

varying secondfield;

int exponent;

>Comment

int nextterm;

}polyrecord;

>Comment

typedef liststructurepointer;

It is also possible to implement the main list and sublists of a list-structure as two-way lists. This is convenient, just as for chains, when it is necessary to go back and forth during the processing of a list-structure or to make the predecessor of any record easily accessible. In this case an additional field would be needed for the backward pointer.

The following program creates and prints the records of a list-structure to illustrate its implementation with records stored in dynamic memory. It also demonstrates two applications of the traverse function. The input consists, first, of an integer to indicate whether the list being created is null, and, second, a sequence of data for each record. This sequence is assumed to be in the order in which the records are accessed in a traversal of the liststructure. For example, input corresponding to accounts of Figure 6.1(a), would be as follows. (Program output is not shown, nor are program prompts for input.)

1    --  indicates a nonnull list-structure

175  --  information field value

1    --  indicates record is complex

11   --  indicates the link and sublist fields are not null

0    --  information field value

1    --  indicates record is complex

11   --  indicates the link and sublist fields are not null

100  --  information field value

0    --  indicates record is simple

0    --  indicates the link field is null

75   --  information field value

0    --  indicates record is simple

0    --  indicates the link field is null

450  --  information field value

1    --  indicates record is complex

11   --  indicates the link and sublist fields are not null

200  --  information field value

1    --  indicates record is complex

10   --  indicates the link field is not null but the sublist field is

250  --  information field value

0    --  indicates record is simple

0    --  indicates the link field is null

-46  --  information field value

0    --  indicates record is simple

0    --  indicates the link field is null

The Program

Reads in list-structure records,

Creates the list-structure, and

Prints all its records.

#include <stdio.h>

>Comment

typedef struct record

{

int info;

int kind;

struct record *sublistptr;

struct record *link;

}examplerecord,*liststructurepointer;

>Comment

#define NULL 0

>Comment

liststructurepointer next(p)

/* Returns a copy of the link field

value of record pointed to by p.

*/

liststructurepointer p;

{

return(p->link);

}

liststructurepointer sublist(p)

/* Returns a copy of the sublistpointer

field value of record pointed to by p.

*/

liststructurepointer p;

{

return(p->sublistptr);

}

liststructurepointer setnull()

/* Returns a null pointer */

{

return(NULL);

}

liststructurepointer avail()

/* Returns a pointer to storage allocated

for a liststructure record of type

examplerecord.

*/

{

return(malloc(sizeof(examplerecord)));

}

complex(p)

/* Returns true only if the record pointed

to by p is complex.

*/

liststructurepointer p;

{

>Comment

return(p->kind == 1);

}

createrecord(l,ptr)

/* Reads in the data for the current record

and sets its fields appropriately.

*/

liststructurepointer 1,ptr;

{

int link,subptr,value,kind;

liststructurepointer setnull(),avail();

printf("\n enter info \n");

>Comment

scanf("%d",&value);

printf("\n enter 0 for simple 1

for complex \n");

>Comment

scanf("%d",&kind);

>Comment

if (kind == 0)

{

printf("\n enter link \n");

>Comment

scanf("%d",&link);

>Comment

if (link == 0)

>Comment

ptr->link = setnull();

>Comment

else

>Comment

ptr->link = avail();

}

>Comment

else

{

printf("\n enter link & subptr \n");

>Comment

scanf("%d %d",&link,&subptr);

>Comment

if (link == 0)

>Comment

ptr->link = setnull();

>Comment

else

>Comment

ptr->link = avail();

>Comment

if (subptr == 0)

>Comment

ptr->sublistptr = setnull();

>Comment

else

>Comment

ptr->sublistptr = avail(); 

}

>Comment

ptr->info = value;

>Comment

ptr->kind = kind:

}

printrecord(pls,ptr)

/* Prints the contents of the info field

of the record pointed to by ptr.

*/

liststructurepointer *pls,ptr;

{

printf("\n %d \n",ptr->info);

}

main()

/* Reads in liststructure records, creates

the liststructure, and prints all its records.

*/

{

int n;

>Comment

liststructurepointer l,avail();

printf("\n enter liststructure: 0 for\

null list 1 otherwise \n");

scanf("%d",&n);

printf("\n remember - the data for the\

records must be in traversal order\

\n");

>Comment

if (n == 0)

>Comment

l = NULL;

>Comment

else

{

>Comment

l = avail()

>Comment

create(1);

}

>Comment

traverse(&l);

>Comment

if (l == NULL)

printf("\n The list is null \n");

}

>Comment

#define LIMIT 50

typedef liststructurepointer whatever;

typedef struct

{

whatever stackarray[LIMIT];

int top;

}stack;

>Comment

setstack(ps)

/* Sets stack s to empty */

stack *ps;

{

(*ps).top = -1;

}

empty(ps)

/* Returns true only if

stack s is empty.

*/

stack *ps;

{

return((*ps).top == -1);

}

push(value,ps)

/* Inserts contents of value as

top entry of stack s.

*/

whatever value;

stack *ps;

{

if ((*ps).top == (LIMIT - 1))

overflow(ps);

else

{

(*ps).top = (*ps).top + 1;

(*ps).stackarray[(*ps).top] = value;

}

}

pop(ps,pvalue)

/* Removes the top entry of stack s

and places its contents in value.

*/

stack *ps;

whatever *pvalue;

{

if (empty(ps))

underflow(ps);

else

{

*pvalue = (*ps).stackarray[(*ps).top];

(*ps).top = (*ps).top - 1;

}

}

overflow(ps)

/* Prints a message when

the stack overflows.

*/

stack *ps;

{

printf("\n stack overflow \n");

}

underflow(ps)

/* Prints a message when

the stack underflows.

*/

stack *ps;

{

printf("\n stack underflow \n");

}

>Comment

traverse(pls)

/* Prints the info fields of all

records of the liststructure l.

*/

liststructurepointer *pls;

{

liststructurepointer ptr,null,setnull(),

next(),sublist();

stack s1;

null = setnull();

ptr = *pls;

setstack(&s1);

while ((ptr != null)||(!empty(&s1)))

if (ptr != null)

{

>Comment

printrecord(pls,ptr);

if (complex(ptr))

{

push(next(ptr),&s1);

ptr = sublist(ptr);

}

else

ptr = next(ptr);

}

else

pop(&s1,&ptr);

}

>Comment

create(l)

/* Inputs records and creates the list l */

liststructurepointer l;

{

liststructurepointer ptr,null,setnull(),

next(),sublist();

stack s2;

null = setnull();

ptr = l;

setstack(&s2);

while ((ptr != null)||(!empty(&s2)))

if (ptr != null)

{

>Comment

createrecord(l,ptr);

if (complex(ptr))

{

push(next(ptr),&s2);

ptr = sublist(ptr);

}

else

ptr = next(ptr);

}

else

pop(&s2,&ptr);

}

Although the stacks have been given distinct names, since s1 is local to create and s2 is local to traverse, they could have both been named s. Note that either create or traverse could be replaced by recursive versions.

6.4.1 Sharing Storage