The first step in creating a program is to develop the algorithm that will produce the solution. The algorithm must detail operations that will be performed on the given data. A decision must also be made about how the data will be organized. Typically data is best split into distinct groups, or collections, based on the basic operations required for each collection. The data structure utilized for each collection can be tailored to the specific operations to be performed on it. Each collection, with its operations, can then be treated individually as a data abstraction.
A data abstraction is a collection of data upon which only a set of specific operations are allowed. The technique of data abstraction has been used in this text as a tool in creating programs that are understandable and maintainable. Insight is required to determine the particular collection to use and the operations to act upon it. The same collection may be useful in a number of different problems. This may be so with the same set of allowable operations or with different sets of operations. As an example, recall that the stack data abstraction was used in both towers and next with the same operations.
Once the data abstractions to be used in a solution are determined, a decision must be made on how to implement them. This requires deciding what data structure is to be used to store the collection and how the operations on it will be defined. In this text each operation has been incorporated in a function using the tool of functional modularization. Treating the collection and its operations as a data abstraction means that the program can only process the collection using those functions. This guarantees that the collection is accessed only when one of the functions is invoked. Proper packaging of the data abstraction can thus ensure that it is used appropriately. How this packaging is done is the topic of this chapter.
The discussion is presented only now for several reasons. First, preceding chapters have introduced a number of data abstractions that can serve as vehicles to present different approaches to packaging. Next, packaging introduces another level of abstraction, which can complicate the understanding of the basic material. Time was needed to absorb the beginning concepts. Finally, packaging is language-dependent, and the aim of this book is to be as language-independent as possible yet still present programs in the C programming language. Given the language-dependence of packaging and the belief that students should first concentrate on basics, the topic is confined to this chapter. This does not mean it is unimportant--only that it might cloud the other concepts presented. Consequently the material in this chapter may be skipped or, alternatively, imposed on the programs in the later chapters. The C approaches to packaging are straightforward; should you desire, the programs can be readily modified to the style presented here.
Consider the program below from Chapter 1 for calculating prime numbers.
This program is structured with the data abstraction collection and its operations set, insert, omit, and belongs placed together. This facilitates finding its data structure and function declarations and definitions, whenever modifications are desired. Changes to collection, set, insert, omit, and belongs may be made, as long as they still do their tasks correctly without changing any other part of the program.
The program, however, is more cluttered and longer than necessary. It is burdened with exhibiting details of the data abstraction that are irrelevant to it. One way to avoid this is to use the include capability of C. Using C's include statement, we can
Create a file called collection that contains all the statements specifying the data abstraction, and then
Insert these into the program with one statement--the include statement
This is done in the following version of the program.
When this program is compiled, the C preprocessor will replace the include "collection" statement in the program file with the source code from the file collection. Thus the object code produced by the compiler for this version will be identical to that produced by the first version.
The file collection, which can be stored separately, contains:
So far, the programs in this text have been written so that they are compiled as a single source code file. This is still true for the two versions of primes. The first was written as a single source file. In the second, the include statement causes the precompiler to incorporate collection into the program file, producing a single source code file.
It is also possible in C to locate the functions of a program in more than one file. Each file of source code can be separately compiled, producing a corresponding file of object code. This ability to allocate the functions of a program to different files is a tool that can be used to achieve another kind of modularity besides functional modularity. This new modularity, which we call file modularity, allocates functions to files, whereas functional modularity allocates tasks to functions. In keeping with this definition of file modularity, the term module will be used to mean one or more files, to be separately compiled, used for the implementation of a data abstraction. Before compilation they are source modules; after compilation they are object modules.
To create a module for collection, two files in addition to the program file will be needed. They are called collection.h and collection.c. Collection.h, the header file, contains all definitions needed for collection's data structure and all declarations for its functions. The header file must be included in any file using this data abstraction. Collection.c, which contains definitions of all the functions of the data abstraction that implement its operations, must also include the header file, as in the following example.
The two files are shown below. In collection.h a standard way of declaring a function is presented. It uses the extern declaration, as in the following example.
The extern declaration informs the compiler that the function is defined elsewhere, in another file. The comment /* int,collection */ identifies the parameters of the function--since it is a comment, it disappears in compilation.
With this version, the program file and collection are compiled separately into object modules. The linker must combine the two object modules to create an executable program.
The File collection.h
The File collection.c
Final Version: The File primestest.c
Although this third version may seem similar to the second, it differs in an important way. Its functions are distributed among three files. Two of these, collection.h and collection.c, are used by the module for collection, the data abstraction. This allows the details of the implementation to be hidden, removes the need for the program itself to change whenever the data abstraction implementation is changed, and also shortens the program. The second version does all this as well, but the third version is even better. It allows collection.c to be compiled separately from file primestest.c, the file containing main, primes, create, and so on. More precisely, primestest.c must be compiled, and then the object code for primestest.c, along with the object code from the separately compiled file collection.c, can be linked by the linker. Finally, the resultant executable file produced by the linker can be run.
Once collection.c has been successfully compiled and verified, its object module can be stored in a library for use in the creation of programs such as primes. In this way C fosters the building up of programs by putting together previous solutions. In the creation or modification of large programs, the use of already compiled modules can significantly reduce time for compiling and program development.
Whenever the implementation of the data abstraction collection changes, changes may occur in the source code of collection.h or of collection.c. When they occur in collection.h, any file that includes it must be recompiled. In our example, this means that collection.c and primestest.c must be recompiled. To run primestest.c, its compiled version, along with the compiled version of the new collection.c, must be linked; then the resultant executable program file can be run. The new object code produced by compiling the new version of collection.c should replace the old version in the library. When the changes occur in collection.c only, it must be recompiled followed by relinking with the object code for primestest.c before the new executable program file can be run.
As a second example of file modularization, consider the stable marriage program of Section 2.5.2. That program is structured with the data abstractions pairings, with its operations mate, read_mens_mates, and create_womens_mates placed together, and preferences, with its operations mostpreferred, nextpreferred, prefers, read_preferences, and create_priorities also placed together. Grouping each data abstraction facilitates finding its data structures, function declarations, and definitions, whenever modifications to them are required. Such changes will not necessitate changing any other part of the program, since it was written treating pairings and preferences as data abstractions. Also, changes to one data abstraction do not require changes in the other. The program in Section 2.5.2 is written as a single source file. We now place the two data abstractions in modules. The modules and the program file structure of the program using file modularization are printed below. The headers, operations and program file are, respectively, pairings.h, pairings.c, preferences.h, preferences.c, and stablemarriages.c.
The File pairings.h
The File pairings.c
The File preferences.h
The File preferences.c
The File stablemarriages.c
The include "pairings.h" and include "preferences.h" were put at the top of the program file because their contents are needed from that point in the file. In the program file for primestest.c, the include "collection.h" appears just before the primes function, since its contents are only needed from that point on in the file.
The files pairings.c, preferences.c, and stablemarriages.c can be compiled separately. To run stable marriages.c, they must first all be linked by the linker.
Any time changes are made in pairings.h, the files pairings.c and stablemarriages.c must be recompiled. Changes in pairings.c also require that pairings.c be recompiled . The same applies for preferences.h and preferences.c. However, changes to only one of pairings.c, preferences.c, or stablemarriages.c require only its individual recompilation. Relinking is always required before execution.
Let us look at another example of file modularization of a program. Consider the program of Section 3.6.1 that reads in, creates, and prints the information fields of each record on a list of stock records. That version is in a single file and is functionally modularized. The data abstraction list, with its operations next, setlink, setinfo, avail, getnextrecord, printrecord, and anotherrecord, appear together.
The version of the program that follows uses a module for the list data abstraction with the header file, list.h, and the operations file, list.c. The file, list.c, and the program file, listexample.c, are compiled separately.
The file list.h:
The File list.h
The File list.c
Finally, here is the program file to create a list and print its contents. It treats the list as a data abstraction and uses file modularization for the data abstraction.
The File listexample.c
The files list.h and list.c now embody the list data abstraction. Note that, should the format of the list change, these changes must be reflected in the header file and also in the operations file. In the later file, list.c, the changes would be localized to setinfo, getnextrecord, and printrecord. Instead, were the format to remain the same but the records stored in an array of records rather than the dynamic memory, more extensive changes would be required in both lists.h and list.c.
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.
Data abstraction and functional and file modularization are important concepts whose proper application to program development and program structure enhance program readability and maintainability. They aid the programmer in establishing libraries of useful functions that can be readily selected for use in creating new programs for new problems.
The ability to compile parts of a program separately can make debugging an easier task and can save time. In C this can be achieved by placing appropriate parts of a program in distinct files. When this is done it is necessary to keep track of which files must be compiled and linked in order to execute the program file.
1. Why is it not necessary to place the include "collection.h" before the primes function in primestest.c?
2. Why is primestest.c independent of the implementation of collection?
3. Why must primestest.c and collection.c be recompiled when changes are made in collection.h?
4. Change preferences.h and preferences.c so that the preferences and priorities arrays are implemented using a pointer array pointing to their rows, which are stored as row records in dynamic memory (see Section 2.3.3).
5. Run stablemarriages.c with your solution to Exercise 4.
6. What must be changed in list.h and list.c if you want to add another field (say, dividends) to the list records?
7. Change the files of Section 5.4 so that the name field of the stockrecords, instead of being an array, is a list. Treat that list as a data abstraction.
8. Write and compile a module for the queue data abstraction using the circular array implementation of Section 4.6.1.
9. Write and compile a module for the queue data abstraction using the list implementation of Section 4.6.3.
10. Create a program file ordlistexample.c. The program is to do what listexample.c does, except the list that is created is to have the records appear in alphabetical order by name. The list is to be treated as a data abstraction using list.h and list.c.
11. Compile, link, and run your program created in Exercise l0.
12. Define file list_record.h and list_record.c, and modify list.h and list.c to reflect these changes. The result should make list.h and list.c independent of details of the listrecords (as was done with the stack in Section 5.5). To accomplish this, you will have to remove and modify some operations from list.c, placing their modified versions in list_record.c, and some declarations from list.h, placing their modified versions in list_record.h.
13. Create a module for a data abstraction list of stacks.
1. Replace collection.h and collection.c with new files that implement collection as an array that contains the actual integers currently in the collection as its entries.
2. a. One of the two complete programs of Section 3.9.3 implements the configuration for the perfect shuffle as an array and the other implements it as a list. They do not treat the configuration as a data abstraction; write and run a single source file program that does.
b. Rewrite and run the program developed for (a) using file modularization to hide the details of the configuration's implementation and so that separate compilation can be done.
3. Change the stack implementation of Section 5.5 so that it is implemented as in Section 4.5.1. You can change only the files stack.h and stack.c; the program file, towerstest.c, cannot be changed.
4. Modify the implementation of the stack data abstraction in Section 5.5 so that instead of the stack containing records, it contains pointers to the records. Again, this should be achieved with changes only to stack.h and stack.c.
5.2: The Prime Example
#include <stdio.h>
main()
{int n;
printf("\n n = ?\n");scanf("%d",&n);primes(n);
}
#define TRUE 1
#define FALSE 0
#define MAXN 500
typedef int collection[MAXN];
set(n,c)
/* Sets c to empty */
int n;
collection c;
{int i;
for (i=1;i<=n;i++)
c[i] = FALSE;
}
insert(i,c)
/* Inserts i in c */
int i;
collection c;
{c[i] = TRUE;
}
omit(i,c)
/* Removes i from c */
int i;
collection c;
{c[i] = FALSE;
}
belongs(i,c)
/* Returns true only
if i is in c
*/
int i;
collection c;
{return(c[i]);
}
primes(n)
/* Prints all prime numbers between 2 and n */
int n;
{collection candidates;
create(n,candidates);
remove(n,candidates);
print(n,candidates);
}
create(n,c)
/* Creates a collection of integers between 2 and n */
int n;
collection c;
{int i;
set(n,c);
for (i=2;i<=n;i++)
insert(i,c);
}
remove(n,c)
/* Removes all nonprimes from c */
int n;
collection c;
{int firstprime;
int factor;
firstprime = 2;
factor = firstprime;
while (nonprimes(factor,n))
{delete(factor,n,c);
factor++;
}
}
nonprimes(factor,n)
/* Returns true only if non
primes may remain in c
*/
int factor,n;
double sqrt();
{return(factor <= sqrt((double)n));
}
delete(factor,n,c)
/* Deletes multiples of factor from c */
int factor,n;
collection c;
{int nextmultiple;
nextmultiple = 2 * factor;
while (nextmultiple <= n)
{omit(nextmultiple,c);
nextmultiple = nextmultiple + factor;
}
}
print(n,c)
/* Prints integers in c */
int n;
collection c;
{int i;
for (i=2;i<=n;i++)
if (belongs(i,c))
printf("\n %d\n",i);}
#include <stdio.h>
main()
{int n;
printf("\n n = ?\n");scanf("%d",&n);primes(n);
}
#include "collection"
primes(n)
/* Prints all prime numbers between 2 and n */
int n;
{collection candidates;
create(n,candidates);
remove(n,candidates);
print(n,candidates);
}
create(n,c)
/* Creates a collection of integers between 2 and n */
int n;
collection c;
{int i;
set(n,c);
for (i=2;i<=n;i++)
insert(i,c);
}
remove(n,c)
/* Removes all nonprimes from c */
int n;
collection c;
{int firstprime;
int factor;
firstprime = 2;
factor = firstprime;
while (nonprimes(factor,n))
{delete(factor,n,c);
factor++;
}
}
nonprimes(factor,n)
/* Returns true only if non
primes may remain in c
*/
int factor,n;
double sqrt();
{return(factor <= sqrt((double)n));
}
delete(factor,n,c)
/* Deletes multiples of factor from c */
int factor,n;
collection c;
{int nextmultiple;
nextmultiple = 2 * factor;
while (nextmultiple <= n)
{omit(nextmultiple,c);
nextmultiple = nextmultiple + factor;
}
}
print(n,c)
/* Prints integers in c */
int n;
collection c;
{int i;
for (i=2;i<=n;i++)
if (belongs(i,c))
printf("\n %d\n",i);}
/* The data abstraction collection
and its allowed operations */
#define TRUE 1
#define FALSE 0
#define MAXN 500
typedef int collection [MAXN];
set(n,c)
/* Sets c to empty */
int n;
collection c;
{int i;
for (i=1;i<=n;i++)
c[i] = FALSE;
}
insert(i,c)
/* Inserts i in c */
int i;
collection c;
{c[i] = TRUE;
}
omit(i,c)
/* Removes i from c */
int i;
collection c;
{c[i] = FALSE;
}
belongs(i,c)
/* Returns true only
if i is in c
*/
int i;
collection c;
{return(c[i]);
}
extern set(/* int,collection */);
/* header for collection of integers */
#define TRUE 1
#define FALSE 0
#define MAXN 500
typedef int collection[MAXN];
extern set(/* int,collection */);
/* Sets collection to empty */
extern insert(/* int,collection */);
/* Adds int to collection */
extern omit(/* int,collection */);
/* Takes int out of collection */
extern belongs(/*int,collection */);
/* Returns true only if int is in collection */
/* operations for collection of integers */
#include "collection.h"
set(n,c)
/* Sets c to empty */
int n;
collection c;
{int i;
for (i=1;i<=n;i++)
c[i] = FALSE;
}
insert(i,c)
/* Inserts i in c */
int i;
collection c;
{c[i] = TRUE;
}
omit(i,c)
/* Removes i from c */
int i;
collection c;
{c[i] = FALSE;
}
belongs(i,c)
/* Returns true only
if i is in c
*/
int i;
collection c;
{return(c[i]);
}
#include <stdio.h>
main()
{int n;
printf("\n n = ?\n");scanf("%d",&n);primes(n);
}
#nclude "collection.h"
primes(n)
/* Prints all prime numbers between 2 and n */
int n;
{collection candidates;
create(n,candidates);
remove(n,candidates);
print(n,candidates);
}
create(n,c)
/* Creates a collection of integers between
2 and n */
int n;
collection c;
{int i;
set(n,c);
for (i=2;i<=n;i++)
insert(i,c);
}
remove(n,c)
/* Removes all nonprimes from c */
int n;
collection c;
{int firstprime;
int factor;
firstprime = 2;
factor = firstprime;
while (nonprimes(factor,n))
{delete(factor,n,c);
factor++;
}
}
nonprimes(factor,n)
/* Returns true only if non
primes may remain in c
*/
int factor,n;
double sqrt();
{return(factor <= sqrt((double)n));
}
delete(factor,n,c)
/* Deletes multiples of factor from c */
int factor,n;
collection c;
{int nextmultiple;
nextmultiple = 2 * factor;
while (nextmultiple <= n)
{omit(nextmultiple,c);
nextmultiple = nextmultiple + factor;
}
}
print(n,c)
/* Prints integers in c */
int n;
collection c;
{int i;
for (i=2;i<=n;i++)
if (belongs(i,c))
printf("\n %d\n",i);}
5.3: Stable Marriages
/* header for pairings */
#define MAXN 50
typedef int mates[MAXN];
extern mate(/* int, pairings */);
/* Returns the mate of person int */
extern read_mens_mates(* int, pairings */);
/* Reads the mates of the men(int of them)
into pairings
*/
extern create_womens_mates(/* int,pairings_1,pairings_2 */);
/* Creates the pairings_2 of the
men(int of them), based on
the mens' mates specified by
pairings_1
*/
/* operations allowed on pairings */
#include "pairings.h"
mate (person,pairs)
/* Returns persons mate
as specified by pairs */
int person;
pairings pairs;
{return(pairs[person]);
}
read_mens_mates(n,pairs)
/* Reads the n wives into pairs */
int n;
pairings pairs;
{int i;
printf("\n mpairs = ? \n");for (i=1;i <=n;i++)
scanf("%d",&pairs[i]);}
create_womens_mates(n,pairs1,pairs2)
/* Pairs 1 specifies the n wives, one
for each man. Pairs2 is set to
specify the n men, one for each woman.
*/
int n;
pairings pair;
{int i,j;
for (i=1;i<=n;i++)
{for (j=1;pairs1[j] != i;j++)
;
pairs2 [i] = j;
}
}
/* header file for preferences */
#define MAXN 50
typedef int preferences[MAXN][MAXN];
extern mostpreferred(/* int,preferences */);
/* Returns the mate most preferred by
person int as specified by pref */
extern nextpreferred(/* int_1,int_2,pref */);
/* Returns the mate preferred most, after
the mate given by index int_2, by person
int_1 as specified by pref
*/
extern prefers(/* int_1,int_2,int_3,pref */);
/* Returns true if individual int_1 prefers
person int_2 to individualsmate int_3
as specified by pref
*/
extern read_preferences(/* int,pref */);
/* Reads int number of rows of
preferences into pref
*/
extern create_priorities(/* int,pref_1,pref_2 */);
/* Creates int number of individual
priorities in pref_2 based on the
individual preferences specified
by pref_1
*/
/* operations allowed on preferences */
#include "preferences.h"
mostpreferred (person,pref)
/* Returns the mate most preferred by
person as specified by pref */
int person;
preferences pref;
{return(pref[person][1]);
}
nextpreferred(person,index,pref)
/* Returns the mate preferred most, after
the mate given by index, by person
as specified by pref
*/
int person,index;
preferences pref;
{return(pref[person][index]);
}
prefers(individual,person,individualsmate,priority)
/* Returns true if individual prefers person to
individuals mate as specified by priority
*/
int individual,person,individualsmate;
preferences priority;
{return(priority[individual][person] <
priority [individual] [individualsmate]);
}
read_preferences (n,pref)
/* Reads n rows of
preferences into pref
*/
int n;
preferences pref;
{int i,j;
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
scanf ("%d",&pref[i][j]);}
create_priorities(n, pref, priority)
/* Creates n individual priorities
in priority based on the
individual preferences specified
by pref
*/
int n;
preferences pref,priority;
{int i,j;
for (i=1,i<=n;i++)
for (j=1;j<=n;j++)
priority[i][pref[i][j]] = j;
}
#include <stdio.h>
#include "pairings.h"
#include "preferences.h"
#define TRUE 1
#define FALSE 0
main()
{pairings mpairs,wpairs;
preferences mpref,wpref,mpriority,wpriority;
int i,j,n;
printf("\n n = ?\n");scanf("%d",&n);read_mens_mates(n,mpairs);
create_womens_mates(n,mpairs,wpairs);
printf("\n Enter mens preferences \n");read_preferences(n,mpref);
printf("\n Enter womens preferences \n");read_preferences(n,wpref);
create_priorities(n,mpref,mpriority);
create_priorities(n,wpref,wpriority);
if (stabilitycheck(n,mpairs,wpairs,mpref,wpref,mpriority,
wpriority))
printf(" The pairings are stable \n");else
printf(" The pairings are not stable \n");printf(" The pairings are: \n");printf(" man wife \n");for (i=1;i<=n;i++)
printf("%d %d \n",i,mate (i,mpairs));}
stabilitycheck(n,mpairs,wpairs,mpref,wpref,mpriority,wpriority)
int n;
pairings mpairs,wpairs
preferences mpref,wpref,mpriority,wpriority;
{int man,wife,individual,individualsmate,index,stable;
stable = TRUE;
for(man=1;(stable && man<=n);man++)
{wife = mate(man,mpairs);
individual = mostpreferred(man,mpref);
index = 1;
while (stable && (individual != wife))
{individualsmate = mate(individual, wpairs);
if(prefers(individual,man,individualsmate,
wpriority))
stable = FALSE;
else
{index++;
individual = nextpreferred(man,index,mpref);
}
}
individual = mostpreferred(wife,wpref);
index = 1;
while(stable && (individual != man))
{individualsmate = mate(individual,mpairs);
if(prefers(individual,wife,individualsmate,
mpriority))
stable = FALSE;
else
{index++;
individual = nextpreferred(wife,index,wpref);
}
}
}
return(stable);
}
5.4 : A List Example
/* header for list */
#define MAXSIZE 5
#define NULL 0
#define SENTINEL -1
typedef struct
{int month;
int day;
int year;
}date;
typedef struct
{char name[MAXSIZE];
int shares;
float value;
date datebought;
}infofield;
typedef struct listrecord
{infofield info;
struct listrecord *link;
}stockrecord,*listpointer;
extern listpointer next(/* listpointer */);
/* Returns a copy of listpointer in link field of
record pointed to by listpointer */
extern listpointer setnull();
/* Returns a null listpointer value */
extern setlink(/* listpointer_1,listpointer_2 */);
/* Sets the link field of the record pointed to
by listpointer_1 to the value of
listpointer_2
*/
extern setinfo(/* listpointer_1,listpointer_2 */);
/* Sets the info field of the record pointed to
by listpointer_1 to the contents of the
info field of the record pointed to by
listpointer_2
*/
extern listpointer avail();
/* Returns a pointer to storage for
a record of type struct stockrecord */
extern listpointer getnextrecord();
/* Returns a pointer to a record
containing the next input records'
information, or a null pointer if
the next input is the sentinel
*/
extern printrecord(/* listpointer */);
/* Prints the information in the record
pointed to by listpointer */
extern anotherrecord(/* listpointer */);
/* Returns true if there are no
more records and false otherwise */
/* operations allowed on a list */
#include "list.h"
listpointer next(pointer)
/* Returns a copy of the
link field in the record
pointed to by pointer
*/
listpointer pointer;
{return (pointer->link);
}
listpointer setnull()
/* Returns a null pointer */
{return(NULL);
}
setlink(pointer1,pointer2)
/* Sets the link field of the
record pointed to by pointer1
to the contents of pointer2
*/
listpointer pointer1, pointer2;
{pointer1->link = pointer2;
}
setinfo(pointer1,pointer2)
/* Sets the infofield of the record
pointed to by pointer1 to the
infofield of the record
pointed to by pointer2
*/
listpointer pointer1,pointer2;
{int i;
for (i=0;i<MAXSIZE;i++)
pointer1->info.name[i] = pointer2->info.name[i];
pointer1->info.shares = pointer2->info.shares;
pointer1->info.value = pointer2->info.value;
pointer1->info.datebought.month = pointer2->info.datebought.
month;
pointer1->info.datebought.day = pointer2->info.datebought.day;
pointer1->info.datebought.year = pointer2->info.datebought.year;
}
listpointer avail()
*/ Returns a pointer to storage
allocated for a record of type
stockrecord
*/
{listpointer malloc();
return(malloc(sizeof(stockrecord)));
}
anotherrecord(recordpointer)
/* Returns true if there is
another record
*/
listpointer recordpointer;
{listpointer setnull();
return(recordpointer != setnull());
}
listpointer getnextrecord()
/* Inputs the data for the new
record and returns a pointer
to a record containing the data
in its infofield, or, if there
are no new records, returns
a null pointer
*/
{listpointer setnull();
static stockrecord nextrecord;
printf(" Enter number of shares \n");scanf("%d",&(nextrecord.info.shares));if(nextrecord.info.shares != SENTINEL)
{printf(" Enter the stock name - less than %d characters\n",MAXSIZE);
scanf("%s",nextrecord.info.name);printf(" Enter the price of one share of the stock \n");scanf("%f",&(nextrecord.info.value));printf(" Enter the month day year of the stock purchase\n");
scanf("%d %d %d",&(nextrecord.info.datebought.month),&(nextrecord.info.datebought.day),
&(nextrecord.info.datebought.year));
return(&nextrecord);
}
else
return(setnull());
}
printrecord(recordpointer)
/* Prints the contents of the infofield
of the record pointed to by recordpointer
*/
listpointer recordpointer;
{printf(" The stock is %s \n",recordpointer->info.name);print(" The number of shares is %d \n",recordpointer->info.shares);
printf(" The value of a share is %f\n",recordpointer->info.value);
printf(" The date of purchase is %d %d %d\n\n",recordpointer->info.datebought.month,
recordpointer->info.datebought.day, recordpointer->
info.datebought.year);
}
#include "list.h"
#include <stdio.h>
#define TRUE 1
#define FALSE 0
main()
/* Inputs a series of stockrecords,
creates a list of the records, and
prints the contents of each list
record's infofield
*/
{listpointer stocks,recordpointer,next();
int done;
initialize(&stocks);
recordpointer = stocks;
done = FALSE;
while(!done&&anotherrecord(recordpointer))
{addrecord(&stocks,recordpointer,&done);
recordpointer = next(recordpointer);
}
recordpointer=stocks;
while (anotherrecord(recordpointer))
{printrecord(recordpointer);
recordpointer = next(recordpointer);
}
}
initialize(plistname)
/* Allocates storage for the first record
and sets listname to point to it
*/
listpointer *plistname;
{listpointer avail();
*plistname = avail();
}
addrecord(plistname,recordpointer,pdone)
/* Fills in the current record's data, and
allocates storage for the next record and
adds it to the list. If there is no data for
the current record it sets the link field of
the last list record to null, or the list
head, to null, and done to true.
*/
listpointer *plistname,recordpointer;
int *pdone;
{static listpointer predecessor;
listpointer setnull(),avail(),
getnextrecord(),pointer;
pointer = getnextrecord();
if (pointer != setnull())
{setinfo(recordpointer,pointer);
setlink(recordpointer,avail());
predecessor = recordpointer;
}
else if (*plistname != recordpointer)
{setlink(predecessor,setnull());
*pdone = TRUE;
}
else
{*plistname = setnull();
*pdone = TRUE;
}
}
5.5: A Stack Example
/* 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");}
5.6: Summary
Exercises
Suggested Assignments