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.
When the records are to be stored in an array of records, the implementation should be changed to
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.
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
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.)
The Program
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.
typedef struct record
{
int kind;
int info;
struct record *sublist;
struct record *link;
}listrecord, *liststructurepointer;
typedef struct record
{
int kind;
int info;
int sublist;
int link;
}listrecord;
typedef int liststructurepointer;
typedef union
{
char unknown;
polyrecord *sublist;
int value;
}varying;
typedef struct record
{
int tag;
varying secondfield;
int exponent;
struct record *nextterm;
}polyrecord, *liststructurepointer;
typedef union
{
char unknown;
int sublist;
int value;
}varying;
typedef struct
{
int tag;
varying secondfield;
int exponent;
int nextterm;
}polyrecord;
typedef liststructurepointer;
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
Reads in list-structure records,
Creates the list-structure, and
Prints all its records.
#include <stdio.h>
typedef struct record
{
int info;
int kind;
struct record *sublistptr;
struct record *link;
}examplerecord,*liststructurepointer;
#define NULL 0
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;
{
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");
scanf("%d",&value);
printf("\n enter 0 for simple 1
for complex \n");
scanf("%d",&kind);
if (kind == 0)
{
printf("\n enter link \n");
scanf("%d",&link);
if (link == 0)
ptr->link = setnull();
else
ptr->link = avail();
}
else
{
printf("\n enter link & subptr \n");
scanf("%d %d",&link,&subptr);
if (link == 0)
ptr->link = setnull();
else
ptr->link = avail();
if (subptr == 0)
ptr->sublistptr = setnull();
else
ptr->sublistptr = avail();
}
ptr->info = value;
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;
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");
if (n == 0)
l = NULL;
else
{
l = avail()
create(1);
}
traverse(&l);
if (l == NULL)
printf("\n The list is null \n");
}
#define LIMIT 50
typedef liststructurepointer whatever;
typedef struct
{
whatever stackarray[LIMIT];
int top;
}stack;
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");
}
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)
{
printrecord(pls,ptr);
if (complex(ptr))
{
push(next(ptr),&s1);
ptr = sublist(ptr);
}
else
ptr = next(ptr);
}
else
pop(&s1,&ptr);
}
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)
{
createrecord(l,ptr);
if (complex(ptr))
{
push(next(ptr),&s2);
ptr = sublist(ptr);
}
else
ptr = next(ptr);
}
else
pop(&s2,&ptr);
}