This last example involves a stack and its application in the nonrecursive towers program of Section 4.5.3. The stack is implemented as a list. The program treats the stack as a data abstraction and is structured so the stack and its operations appear together.
We give the header file, stack.h, the operations file, stack.c, and the program file, towerstest.c, that can be used to achieve file modularization and separate compilation.
The File stack.h
The File stack.c
The File towerstest.c
Notice that the operations push and pop in stack.c have been written under the assumption that the C compiler allows the entire contents of one record to be copied into another record of the same type using just one assignment statement. In order to achieve greater portability, these operations could be written so that they do not depend on this assumption by using individual assignment statements for each field of the records. However, this can also be accomplished by restructuring the program. Moreover, restructuring can also achieve another level of data abstraction with respect to the stack records and their operations (in this example only one will be needed). This will require changes to stack.h and stack.c but will make the new stack module independent of the implementation of the stack records. The current stack module, consisting of the files stack.h and stack.c, must be changed and recompiled whenever the records being stacked have a different format from that which is represented by whatever. After the restructuring this will not be necessary. Any changes in the stack record format will be localized to the stack record module.
To do the restructuring, first create a module for the data abstraction stackrecord and its operations. The module consists of the files stack_record.h and stack_record.c.
The File stack_record.h
The File stack_record.c
Here is the new stack module.
The File stack.h
File stack.c
As promised, the new stack modules are not dependent on the details of the stack records. The program file, towerstest.c, does not need to be changed from its original version. To run it, stack_record.c and stack.c must be compiled. Their object files, along with the previously generated object file for towerstest.c, can be linked, and then towerstest.c can be run. Any future changes in stack_record.h mean that stack_record.c, stack.c, and towerstest.c must be recompiled, but changes to only stack_record.c or stack.c will require just their recompilation. Similarly, changes to just towerstest.c require only its recompilation.
Using this technique it is possible, as demonstrated, to structure programs so that modules for data abstractions can be built using modules for other data abstractions. The examples presented, for the sake of simplicity, have dealt with small to moderate-sized programs. With programs of this size the overall impact of file modularity and modules may not appear to be great. The real power of the technique becomes quickly apparent when large programs are written by teams of programmers. The efficiency and control gained through modularity in such cases is significant.
/* header for stack */
#define NULL 0
typedef struct
{int n;
int i;
int a;
int f;
}whatever;
typedef struct record
{whatever info;
struct record *link;
}stackrecord,*stack;
extern setstack(/* pstack */);
/* Sets stack to empty */
extern empty (/* pstack */);
/* Returns true only if
the stack is empty */
extern push(/* pstackrecord,pstack */);
/* Makes stackrecord the new
top entry on stack*/
extern pop(/* pstack,pstackrecord */);
/* Removes the top entry from
stack and returns with its
contents in stackrecord
*/
extern overflow(/* pstack */);
/* Prints a warning when
the stack overflows */
extern underflow(/* pstack */);
/* Prints a warning when the stack underflows */
/* operations for the stack */
#include "stack.h"
setstack(ps)
/* Sets stack s to empty */
stack *ps;
{*ps = NULL;
}
empty(ps)
/* Returns true only if
the stack s is empty */
stack *ps;
{return(*ps == NULL);
}
push(pnewrecord,ps)
/* Makes stackrecord the new
top entry on stack s */
stackrecord *pnewrecord;
stack *ps;
{stackrecord *newentry;
newentry = malloc(sizeof(stackrecord));
newentry->info = pnewrecord->info;
newentry->link = *ps;
*ps = newentry;
}
pop(ps,pvalue)
/* Removes the top entry from
stack s and returns with its
contents in stackrecord
*/
stack *ps;
stackrecord *pvalue;
{if(!empty(ps))
{pvalue->info = (*ps)->info;
*ps = (*ps)->link;
}
else
underflow(ps);
}
overflow(ps);
/* Prints a warning when
the stack overflows */
stack *ps;
{printf (" The stack has overflowed /n");}
underflow(ps);
/* Prints a warning when
the stack underflows */
stack *ps;
{printf(" The stack has underflowed /n");}
#include <stdio.h>
main()
{int n;
printf("\n enter a value for n \n");scanf("%d",&n);towers(n,1,2,3);
}
#include "stack.h"
towers(n,i,a,f)
/* Moves the top n disks
from peg i to peg f
*/
int n,i,a,f;
{stack s;
int done
setstack(&s);
done = FALSE;
while(!done)
{while(n > 1)
{s_tack(n,i,a,f,&s);
setvar 1(&n,&i,&a,&f);
}
printf("\n %d -> %d\n",i,f);if(!empty(&s))
{restore(&n,&i,&a,&f,&s);
printf("\n %d -> %d\n",i,f);setvar2(&n,&i,&a,&f);
}
else
done = TRUE;
}
setvar1(pn,pi,pa,pf)
/* Sets n to n - 1 and
interchanges f and a
*/
int *pn,*pi,*pa,*pf;
{int t;
*pn = *pn - 1;
t = *pf;
*pf = *pa;
*pa = t;
}
setvar2(pn,pi,pa,pf)
/* Sets n to n - 1 and
interchanges a and i
*/
int *pn,*pi,*pa,*pf;
{int t;
*pn = *pn - 1;
t = *pa;
*pa = *pi;
*pi = t;
}
s_tack(n,i,a,f,ps)
/* Creates a record containing
n, i, a, and f and inserts it
on stack s
*/
int n,i,a,f;
stack *ps;
{stackrecord newrecord;
newrecord.info.n = n;
newrecord.info.i = i;
newrecord.info.a = a;
newrecord.info.f = f;
push(&newrecord,ps);
}
restore(pn,pi,pa,pf,ps)
/* Removes the top record from
stack s and copies its contents into n,i,a,f
*/
int *pn,*pi,*pa,*pf;
stack *ps;
{stackrecord value;
pop(ps,&value);
*pn = value.info.n;
*pi = value.info.i;
*pa = value.info.a;
*pf = value.info.f;
}
/* header for stackrecord */
typedef struct
{int n;
int i;
int a;
int f;
}whatever;
typedef struct record
{whatever info;
struct record *link;
}stackrecord,*stackrecordpointer;
extern setinfo(/* stackrecordpointer_1,stackrecordpointer_2 */);
/* Sets the info field of the record pointed to
by stackrecordpointer_1 to the contents of the
info field of the record pointed to by stackrecordpointer_2
*/
/* operations for stackrecord */
#include "stack_record.h"
setinfo(pointer1,pointer2)
/* Copies the contents of the record
pointed to by pointer 1 into
the record pointed to by pointer2
*/
stackrecordpointer pointer1,pointer2;
{pointer1->info.retrn = pointer2->info.retrn;
pointer1->info.n = pointer2->info.n;
pointer1->info.i = pointer2->info.i;
pointer1->info.a = pointer2->info.a;
pointer1->info.f = pointer2->info.f;
}
/* header for stack */
#include "stack_record.h"
#define NULL 0
stackrecord *stack;
extern setstack(/* pstack */);
/* Sets stack to empty */
extern empty(/* pstack */);
/* Returns true only if the stack is empty */
extern push(/* pstackrecord,pstack */);
/* Makes stackrecord the new top entry on stack*/
extern pop(/* pstack,pstackrecord */);
/* Removes the top entry from
stack and returns with its
contents in stackrecord
*/
extern overflow(/* pstack */);
/* Prints a warning when
the stack overflows */
extern underflow(/* pstack */);
/* Prints a warning when
the stack underflows */
/* operations for the stack */
#include "stack.h"
setstack(ps)
/* Sets stack to empty */
stackrecordpointer *ps;
{*ps = NULL;
}
empty(ps)
/* Returns true only if
the stack is empty */
stackrecordpointer *ps;
{return(*ps == NULL);
}
push(pnewrecord,ps)
/* Makes stackrecord the new
top entry on stack*/
stackrecord *pnewrecord;
stackrecordpointer *ps;
{stackrecord *newentry;
newentry = malloc(sizeof
(stackrecord));
setinfo(newentry,pnewrecord);
newentry->link = *ps;
*ps = newentry;
}
pop(ps,pvalue)
/* Removes the top entry from
stack and returns with its
contents in stackrecord
*/
stackrecordpointer *ps;
stackrecord *pvalue;
{if(!empty(ps))
{setinfo(pvalue,(*ps));
*ps = (*ps)->link;
}
else
underflow(ps);
}
overflow(ps);
/* Prints a warning when
the stack overflows */
stackrecordpointer *ps;
{printf (" The stack has overflowed /n");}
underflow(ps);
/* Prints a warning when
the stack underflows */
stackrecordpointer *ps;
{printf (" The stack has underflowed /n");}