02-Chap 02-ARRAYS AND STRUCTURES

CHAPTER 2
ARRAYS AND STRUCTURES
2.1 THE ARRAY AS AN ABSTRACT DATA TYPE
We begin our discussion by considering an array as an ADT. This is not the usual per
spective since many programmers view an array only as "a consecutive set of memory
locations." This is unfortunate because it clearly shows an emphasis on implementation
issues. Thus, although an array is usually implemented as a consecutive set of memory
locations, this is not always the case. Intuitively an array is a set of pairs, <index,
value>, such that each index that is defined has a value associated with it. In mathemati
cal terms, we call this a correspondence or a mapping. However, when considering an
ADT we are more concerned with the operations that can be performed on an array.
Aside from creating a new array, most languages provide only two standard operations
for arrays, one that retrieves a value, and a second that stores a value. Structure 2.1
shows a definition of the array ADT.
The Creaie(j, list) function produces a new, empty array of the appropriate size.
All of the items are initially undefined. Retrieve accepts an array and an index. It
returns the value associated with the index if the index is valid, or an error if the index is
invalid. Store accepts an array, an index, and an item, and returns the original array aug
mented with the new <index, value> pair. The advantage of this ADT definition is that it
clearly points out the fact that the array is a more general structure than "a consecutive
set of memory locations."
49
50 Arrays And Structures
structure Array is
objects: A set of pairs <mdex, value> where for each value of index there is a value
from the set item. Index is a finite ordered set of one or more dimensions, for example,
{0, • • ■ , n-1} for one dimension, {(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2,
1), (2, 2)) for two dimensions, etc.
functions:
for all A G Array, i g index, x g item, j, size g integer
Array Create(7, list) return an array of j dimensions where list
is a y-tuple whose zth element is the the size of
the zth dimension. Items are undefined.
Item Retrieve(A, /) if (z G index) return the item associated
with index value z in array A
else return error
Array Store(A,z,x) if (z in index)
return an array that is identical to array
A except the new pair <z, x> has been
inserted else return error.
end Array
Structure 2.1: Abstract Data Type Array
Now let’s examine arrays in C. We restrict ourselves initially to one-dimensional

arrays. A one-dimensional array in C is declared implicitly by appending brackets to the
name of a variable. For example,
int list [5], *plist[5];
declares two arrays each containing five elements. The first array defines five integers,
while the second defines five pointers to integers. In C all arrays start at index 0, so
/z5?[0], ZZ^rfl], /z5r[2], /z5Z[3], and /z\f[4] are the names of the five array elements, each of
which contains an integer value. Similarly, plist[Q], plist[}.], plistl?.], plist[3], and
plist[4] are the names of five array elements, each of which contains a pointer to an
integer.
We now consider the implementation of one-dimensional arrays. When the com
piler encounters an array declaration such as the one used above to create list, it allocates
five consecutive memory locations. Each memory location is large enough to hold a sin
gle integer. The address of the first element /z5Z[0], is called the base address. If the size
of an integer on your machine is denoted by sizeofiint), then we get the following
memory addresses for the five elements of list[]-.
The Array As An Abstract Data Type 51
Variable Memory Address

to[0] base address = a
Z^dl] a + sizeof( int)
/Z5?[2] a + 2-sizeof(int)
/Z5?[3] a + 3'sizeof(int)
/wr[4] a + 4-sizeof(mt)
In fact, when we write list[i] in a C program, C interprets it as a pointer to an integer

whose address is the one in the table above. Observe that there is a difference between a
declaration such as
★
int listl;
and
int list2 [5];
The variables list\ and list'2 are both pointers to an int, but in the second case five
memory locations for holding integers have been reserved, list'2 is a pointer to /z5r2[0]
and list2+i is a pointer to Ust2[i]. Notice that in C, we do not multiply the offset i with
the size of the type to get to the appropriate element of the array. Thus, regardless of the
type of the array list2, it is always the case that (to2 + /) equals &list2[i}. So,
*({ist2 + z) equals list2[i ].
It is useful to consider the way C treats an array when it is a parameter to a func
tion. All parameters of a C function must be declared within the function. However, the
range of a one-dimensional array is defined only in the main program since new storage
for an array is not allocated within a function. If the size of a one-dimensional array is
needed, it must be either passed into the function as an argument or accessed as a global
variable.
Consider Program 2.1. When sum is invoked, input = &input [0] is copied into a
temporary location and associated with the formal parameter list. When /z5r[zj occurs on
the right-hand side of the equals sign, a dereference takes place and the value pointed at
by (list + z) is returned. If list[i} appears on the left-hand side of the equals sign, then the
value produced on the right-hand side is stored in the location (list 4- z). Thus in C, array
parameters have their values altered, despite the fact that the parameter passing is done
using call-by-value.
Example 2.1 [One-dimensional array addressing}’. Assume that we have the following
declaration:
int one[] {0, 1, 2, 3 , 4} ;
We would like to write a function that prints out both the address of the zth ele
ment of this array and the value found at this address. To do this, print\ {Program 2.2)
uses pointer arithmetic. The function is invoked as print}(&one |()],5). As you can see
#define MAX-SIZE 100

float sum(float [], int);
float input[MAX —SIZE], answer;
int i;
void main(void)
for (i 0; i < MAX-SIZE; i++)

input[i] 1;
answer sum(input, MAX—SIZE);

printf("The sum is: %f\n", answer);
}
float sum(float list[], int n)
{
int i ;
float tempsum = 0;
for (i = 0; i < n;
tempsum += list[i];
return tempsum;
}
Program 2.1: Example array program
from the printf statement, the address of the ith element is simply ptr + i. To obtain the
value of the /th element, we use the dereferencing operator, *. Thus, "^{ptr + /) indicates
that we want the contents of the ptr 4- i position rather than the address.
void printl(int *ptr, int rows)

{
/■^ print out a one-dimensional array using a pointer */
int i;
printf("Address Contents\n");
for (i = 0; i < rows; i + +)
II Q. *
printf(%8u%5d\n'', ptr + i, (ptr + i));
printf("\n") ;
}
Program 2.2: One-dimensional array accessed by address
Figure 2.1 shows the results we obtained when we ran print1. Notice that the
Structures And Unions 53
Address Contents
1228 0
1230 1
1232 2
1234 3
4
Figure 2.1: One-dimensional array addressing
addresses increase by two. This is what we would expect on an Intel 386 machine. □
2.2 STRUCTURES AND UNIONS
2.2.1 Structures
Arrays are collections of data of the same type. In C there is an alternate way of group
ing data that permits the data to vary in type. This mechanism is called the struct, short
for structure. A structure (called a record in many other programming languages) is a
collection of data items, where each item is identified as to its type and name. For exam
ple,
struct {
char name[10];
int age;
float salary;
} person;
creates a variable whose name is person and that has three fields:
a name that is a character array

an integer value representing the age of the person
a float value representing the salary of the individual
We may assign values to these fields as below. Notice the use of the . as the structure
member operator. We use this operator to select a particular member of the structure.
strcpy(person.name,"james") ;
person.age 10;
person.salary = 35000;
We can create our own structure data types by using the typedef statement as
below:
typedef struct human—being { or typedef struct {

char name[10 3; char name[10];
int age; int age;
float salary; float salary;
}; } human-being;
This says that human-being is the name of the type defined by the structure definition,
and we may follow this definition with declarations of variables such as:
human—being personl, person2;
We might have a program segment that says:
if (strcmp(personl.name, person2.name))
printf{"The two people do not have the same nameXn");
else
printf("The two people have the same name\n");
It would be nice if we could write if (personl == person2 ) and have the entire
structure checked for equality, or if we could write personl = person2 and have
that mean that the value of every field of the structure of person! is assigned as the
value of the corresponding field of person 1. ANSI C permits structure assignment, but
most earlier versions of C do not. For older versions of C, we are forced to write the
more detailed form:
strcpy(personl.name, person2.name);
personl.age = person2.age;
personl.salary = person2.salary;
While structures cannot be directly checked for equality or inequality, we can

write a function (Program 2.3) to do this. We assume that TRUE and FALSE are defined
as:
ttdefine FALSE 0
ttdefine TRUE 1
A typical function call might be:
int humans—equal(human—being personl,

human—being person2)
{
*
/ return TRUE if personl and person2 are the same human
being otherwise return FALSE */
if (strcmp(personl.name, person2.name))
return FALSE;
if (personl.age != person2.age)
return FALSE;
if (personl.salary 1= person2.salary)
return FALSE;
return TRUE;
}
Program 2.3: Function to check equality of structures
if (humans—equal(personl,person2))
printf("The two human beings are the same\n");
else
printf{"The two human beings are not the same\n");
We can also embed a structure within a structure. For example, associated with
our human-being structure we may wish to include the date of his or her birth. We can
do this by writing:
typedef struct {
int month;
int day;
int year;
} date;
typedef struct human—being {

char name[10];
int age;
float salary;
date dob;
};
A person born on February 11, 1944, would have the values for the date struct set as:
personl.dob.month = 2;
personl.dob.day = 11;
personl.dob.year = 1944;
2.2.2 Unions
Continuing with our human-being example, it would be nice if we could distinguish

between males and females. In the case of males we might ask whether they have a
beard or not. In the case of females we might wish to know the number of children they
have borne. This gives rise to another feature of C called a union. A union declaration
is similar to a structure, but the fields of a union must share their memory space. This
means that only one field of the union is "active" at any given time. For example, to add
different fields for males and females we would change our definition of human-being
to:
typedef struct sex—type {

enum tag—field {female, male} sex;
union {
int children;
int beard ;
} u;
};
typedef struct human—being {
char name[10];
int age;
float salary;
date dob;
sex—type sex—info;
};
human—being personl, person2;
We could assign values to person! and person2 as:
personl.sex—info.sex = male;
personl.sex—info.u.beard = FALSE;
and
person2.sex—info.sex = female;
person2.sex—info.u.children - 4;
Notice that we first place a value in the tag field. This allows us to determine which field
in the union is active. We then place a value in the appropriate field of the union. For
example, if the value of sex-info.sex was male, we would enter a TRUE or a FALSE in
the sex-info.u.beard field. Similarly, if the person was a female, we would enter an
integer value in the sex-info.u.children field. C does not check to make sure that we use
the appropriate field. For instance, we could place a value of female in the sex-info.sex
field, and then proceed to place a value of TRUE in the sex-info.u.beard field. Although
we know that this is not appropriate, C does not check to make sure that we have used
the correct fields of a union.
2.2.3 Internal Implementation of Structures
In most cases you need not be concerned with exactly how the C compiler will store the
fields of a structure in memory. Generally, if you have a structure definition such as:
struct {int i,j; float a, b;};

or
struct {int i; int j; float a; float b; };
these values will be stored in the same way using increasing address locations in the
order specified in the structure definition. However, it is important to realize that holes
or padding may actually occur within a structure to permit two consecutive components
to be properly aligned within memory.
The size of an object of a struct or union type is the amount of storage necessary
to represent the largest component, including any padding that may be required. Struc
tures must begin and end on the same type of memory boundary, for example, an even
byte boundary or an address that is a multiple of 4, 8, or 16.
2.2.4 Self-Referential Structures
A self-referential structure is one in which one or more of its components is a pointer to

itself. Self-referential structures usually require dynamic storage management routines
(malloc and free) to explicitly obtain and release memory. Consider as an example:
typedef struct list {

char data;
list ★ link ;
} ;
Each instance of the structure list will have two components, data and link, data is a sin
gle character, while link is a pointer to a list structure. The value of link is either the
address in memory of an instance of list or the null pointer. Consider these statements,
which create three structures and assign values to their respective fields:
list iteml/ item2, item3;

iteml.data 'Si' ;
item2.data
item3.data 'c' ;
iteml.link item2.link item3.link NULL ;
Structures item 1, item 2, and z7em3 each contain the data item a, b, and c, respectively,
and the null pointer. We can attach these structures together by replacing the null link
field in item 2 with one that points to item 3 and by replacing the null link field in item 1
with one that points to item 2.
iteml.link &i tem2;

iteml.link = &:item3;
We will see more of this linking in Chapter 4.
EXERCISES
1. Develop a structure to represent the planets in the solar system. Each planet has
fields for the planet’s name, its distance from the sun (in miles), and the number of
moons it has. Place items in each the fields for the planets: Earth and Venus.
2. Modify the human-being structure so that we can include different information
based on marital status. Marital status should be an enumerated type with fields:
single, married, widowed, divorced. Use a union to include different information
based on marital status as follows:
• Single. No information needed.
• Married. Include a marriage date field.
• Widowed. Include marriage date and death of spouse date fields.
• Divorced. Include divorce date and number of divorces fields.
Assign values to the fields for some person of type human-being.

3. Develop a structure to represent each of the following geometric objects:
• rectangle
• triangle
• circle.
2.3 THE POLYNOMIAL ABSTRACT DATA TYPE
Arrays are not only data structures in their own right, we can also use them to implement
other abstract data types. For instance, let us consider one of the simplest and most com
monly found data structures: the ordered, or linear, list. We can find many examples of
this data structure, including:
• Days of the week: (Sunday, Monday, Tuesday, Wednesday, Thursday, Friday,

Saturday)
♦ Values in a deck of cards: (Ace, 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, King)
• Floors of a building: (basement, lobby, mezzanine, first, second)
• Years the United States fought in World War II: (1941, 1942, 1943, 1944, 1945)
• Years Switzerland fought in World War II: ()
Notice that the years Switzerland fought in World War II is different because it
contains no items. It is an example of an empty list, which we denote as ( ). The other
lists all contain items that are written in the form (itemQ, item j, • • • , itemn-i).
We can perform many operations on lists, including:
♦ Finding the length, n, of a list.
♦ Reading the items in a list from left to right (or right to left).
• Retrieving the /th item from a list, 0 < i < n.
• Replacing the item in the /th position of a list, 0 < / n.
• Inserting a new item in the /th position of a list, 0 < i < n. The items previously num
bered /, i 4-1, • • • , n-1 become items numbered / 4-1,/4-2, ••• , n.
• Deleting an item from the /th position of a list, 0 < / <n. The items numbered / 4-1,
• • • , «-l become items numbered /, /4-1, • • • , n~2.
Rather than state the formal specification of the ADT list, we want to explore
briefly its implementation. Perhaps, the most common implementation is to represent an
ordered list as an array where we associate the list element, itemj, with the array index i.
We call this a sequential mapping because, assuming the standard implementation of an
array, we are storing itenti, itemj + \ into consecutive slots i and i + 1 of the array. Sequen
tial mapping works well for most of the operations listed above. Thus, we can retrieve
an item, replace an item, or find the length of a list, in constant time. We also can read
the items in the list, from either direction, by simply changing subscripts in a controlled
way. Only insertion and deletion pose problems since the sequential allocation forces us
to move items so that the sequential mapping is preserved. It is precisely this overhead
that leads us to consider nonsequential mappings of ordered lists in Chapter 4.
Let us jump right into a problem requiring ordered lists, which we will solve by
using one-dimensional arrays. This problem has become the classical example for
motivating the use of list processing techniques, which we will see in later chapters.
Therefore, it makes sense to look at the problem and see why arrays offer only a partially
adequate solution. The problem calls for building a set of functions that allow for the
manipulation of symbolic polynomials. Viewed from a mathematical perspective, a poly
nomial is a sum of terms, where each term has a form ax^, where x is the variable, a is
the coefficient, and e is the exponent. Two example polynomials are:
A (x) = + + 4 and B (x) = + lOx^ + 3x^ + 1
The largest (or leading) exponent of a polynomial is called its degree. Coefficients that
are zero are not displayed. The term with exponent equal to zero does not show the vari
able since x raised to a power of zero is 1. There are standard mathematical definitions
for the sum and product of polynomials. Assume that we have two polynomials, A (x) =
and B(x) = J^h/x' then:
A (x) + B (x) = '^(ai + bi)x'
A (x) • B(x') =
Similarly, we can define subtraction and division on polynomials, as well as many other
operations.
We begin with an ADT definition of a polynomial. The particular operations in
part are a reflection of what will be needed in our subsequent programs to manipulate
polynomials. The definition is contained in Structure 2.2.
We are now ready to make some representation decisions. A very reasonable first
decision requires unique exponents arranged in decreasing order. This requirement con
siderably simplifies many of the operations. Using our specification and this stipulation,
we can write a version of Add that is closer to a C function (Program 2.4), but is still
representation-independent.
This algorithm works by comparing terms from the two polynomials until one or
both of the polynomials becomes empty. The switch statement performs the comparis
ons and adds the proper term to the new polynomial, d. If one of the polynomials
becomes empty, we copy the remaining terms from the nonempty polynomial into d.
With these insights, suppose we now consider the representation question more care
fully.
One way to represent polynomials in C is to use typedef to create the type polyno
mial as below:
#define MAX—DEGREE 101 Max

*
/ degree of polynomial + 1
/
*
typedef struct {
int degree;
The Polynomial Abstract Data Type 61
structure Polynomial is
a„x en a set of ordered pairs of <ej, ai> where fly in
fl
objects: /?(x) = a^x^' + •- •- •' + a„x^'';
Coefficients and c, in Exponents, e^ are integers >= 0
functions:
for all poly,poly\, poly2 e Polynomial, coefe Coefficients, expon e Exponents
Polynomial Zero() return the polynomial,

p(%) = 0
Boolean }.s7.QXQ{poly} if (poly) return FALSE
else return TRUE
Coefficient Coef{poly,expon) if {expon e poly) return its
coefficient else return zero
Exponent Lead-Exp(po/y) return the largest exponent in
po/y
Polynomial Attach(pe>/y, coef, expon) if {expon e poly) return error
else return the polynomial poly
with the term <coef, expon>
inserted
Polynomial Remove(p<?Zy, expon) if {expon e poly)
return the polynomial poly with
the term whose exponent is
expon deleted
else return error
Polynomial SingleMult(p<9/y, coef, expon) return the polynomial
poly -coef-x^^P^^
Polynomial Add(p<?Zyl, poly2) return the polynomial
polyi + poly2
Polynomial Mult(poZyl» poly2) return the polynomial
poly\ • poly2
end Polynomial
Structure 2.2: Abstract data type Polynomial
float coef[MAX-DEGREE];
} polynomial;
n
Now if fl is of type polynomial and n < MAX-DEGREE, the polynomial A (x) = âix'
i=0
would be represented as:
a.degree = n
*
/ d a + b, where a, b, and d are polynomials */
d Zero()
while (! IsZero(a) && ! IsZero(b)) do {
switch COMPARE(Lead —Exp(a), Lead—Exp(b)) {
case -1: d -
Attach(d,Coef(b,Lead—Exp(b) ) ,Lead—Exp(b)) ;
b = Remove(b,Lead—Exp(b));
break;
case 0:
0: sum Coef ( a, Lead—Exp(a)) + Coef(b.
Lead—Exp(b));
if (sum) {
Attach(d,sum,Lead—Exp(a));
a = Remove(a,Lead—Exp(a));
b = Remove(b,Lead—Exp(b));
}
break;
case 1: d =
Attach(d,Coef(a,Lead—Exp(a)), Lead—Exp(a));
a - Remove(a,Lead—Exp(a));
}
}
insert any remaining terms of a or b into d
Program 2.4: Initial version of padd function
a . coef[1] = 0 < z <n
In this representation, we store the coefficients in order of decreasing exponents,

such that a . coef [z ] is the coefficient of x n—i provided a term with exponent n-i exists;
otherwise, a . coef [z ] = 0. Although this representation leads to very simple algorithms
for most of the operations, it wastes a lot of space. For instance, if a. degree «
MAX-DEGREE, (the double "less than" should be read as "is much less than"), then we
will not need most of the positions in a. coef [MAX-DEGREE]. The same argument
applies if the polynomial is sparse, that is, the number of terms with nonzero coefficient
is small relative to the degree of the polynomial. To preserve space we devise an alter
nate representation that uses only one global array, terms, to store all our polynomials.
The C declarations needed are:
MAX—TERMS 100 size

*
/ of terms array
/
*
typedef struct {
float coef;
int expon;
} polynomial;
polynomial terms[MAX—TERMS];
int avail 0;
Consider the two polynomials A (x) = 2x'^^ + 1 and B(x) = + 10%^ + 3x^ + 1.
Figure 2.2 shows how these polynomials are stored in the array terms. The index of the
first term of A and B is given by starta and startb, respectively, while finisha and finishb
give the index of the last term of A and B. The index of the next free location in the
array is given by avail. For our example, starta = 0, finisha = 1, startb = 2, finishb = 5,
and avail = 6.
starta finisha startb finishb avail

4. 4 4 4
1 1 1 10 3 1
exp 1000 0 4 3 2 0
0 1 1 3 4 5 6
Figure 2.2: Array representation of two polynomials
This representation does not impose any limit on the number of polynomials that
we can place in terms. The only stipulation is that the total number of nonzero terms
must be no more than MAX-TERMS. It is worth pointing out the difference between our
specification and our representation. Our specification used poly to refer to a polyno
mial, and our representation translated poly into a <start, finish > pair. Therefore, to use
A (x) we must pass in starta and finisha. Any polynomial A that has n nonzero terms has
starta and finisha such that finisha = starta + n - 1.
Before proceeding, we should evaluate our current representation. Is it any better
than the representation that uses an array of coefficients for each polynomial? It cer
tainly solves the problem of many zero terms since A (x) = 2x 4- 1 uses only six units
of storage: one for starta, one for finisha, two for the coefficients, and two for the
exponents. However, when all the terms are nonzero, the current representation requires
about twice as much space as the first one. Unless we know before hand that each of our
polynomials has few zero terms, our current representation is probably better.
We would now like to write a C function that adds two polynomials, A and B,
represented as above to obtain D = A 4- B. To produce D(x), padd (Program 2.5) adds
A (x) and B(x) term by term. Starting at position avail, attach (Program 2.6) places the
term.s of D into the array, terms. If there is not enough space in terms to accommodate
D, an error message is printed to the standard error device and we exit the program with
an error condition.
void padd(int starta,int finisha,int startb, int finishb,

int * startd,int *finishd)
{
/* add A(x) and B(x) to obtain D(x) */
float coefficient ;
*startd = avail;
while (starta <= finisha && startb <= finishb)
switch(COMPARE(terms[starta].expon,
terms[startb].expon)) {
★
-1: *
/ a expon < b expon
attach(terms[startb].coef,terms[startb].expon) ;
startb++;
break;
case 0: /
* equal exponents
coefficient terms[starta].coef +
terms[startb].coef;
if (coefficient)
attach(coefficient,terms[starta].expon) ;
starta++;
startb++;
break;
case 1: *
/ a expon > b expon
attach(terms[starta].coef,terms[starta].expon);
starta++;
}
1^ add in remaining terms of A(x)
for(; starta <= finisha; starta++)
attach(terms[starta].coef,terms[starta].expon);
/* add in remaining terms of B{x) ■^ /
for( ; startb <= finishb; startb++)
attach(terms[startb].coef, terms[startb].expon) ;
*
finishd = avail-1;
}
Program 2.5: Function to add two polynomials
Analysis of padd-. Since the number of nonzero terms in A and in B are the most impor
tant factors in the time complexity, we will carry out the analysis using them. Therefore,
let tn and n be the number of nonzero terms in A and B, respectively. If tn > 0 and n > 0,
the while loop is entered. Each iteration of the loop requires 0(1) time. At each
void attach(float coefficient, int exponent)

{
*
/ add a new term to the polynomial */
if (avail = MAX-TERMS) {
fprintf(stderr,"Too many terms in the polynomial\n");
exit(1};
}
terms[avail1.coef = coefficient;
terms[avail++ ].expon = exponent;
}
Program 2.6: Function to add a new term
iteration, we increment the value of starta or startb or both. Since the iteration ter
minates when either starta or startb exceeds finisha or finishb, respectively, the number
of iterations is bounded by m + n - 1. This worst case occurs when:
n n
2Z + 1
A(x) = 2 X 2i and S(x) = x
z=o i=Q
The time for the remaining two loops is bounded by O(n + m) because we cannot
iterate the first loop more than m times and the second more than n times. So, the asymp
totic computing time of this algorithm is O(a2 +m). □
Before proceeding let us briefly consider a few of the problems with the current
representation. We have seen that, as we create polynomials, we increment avail until it
equals MAX-TERMS. When this occurs, must we quit? Given the current representa
tion, we must unless there are some polynomials that we no longer need. We could write
a compaction function that would remove the unnecessary polynomials and create a
large, continuous available space at one end of the array. However, this requires data
movement which takes time. In addition, we also must change the start and end indices
for each polynomial moved, that is, we change the values of starti and finishi for all
polynomials moved. In Chapter 3, we let you experiment with some "simple" compact
ing routines.
EXERCISES
1. Write functions readpoly and printpoly that allow the user to create and print poly
nomials.
2. Write a function, pmult, that multiplies two polynomials. Figure out the comput
ing time of your function.
3. Write a function, peval, that evaluates a polynomial at some value, xq. Try to
minimize the number of operations.
4. Let A(x) = -I- 2«-2
”^ -i- • • • + x^ -i- x® and B(x) = *x^" -i- + x^
+ x^"
X ^ X -h
+ x^" + •■ •* •' -i- X -t- x.
For these polynomials, determine the exact number of times each statement of
padd is executed.
5. The declarations that follow give us a third representation of the polynomial ADT.
terms [/ ][0].expon gives the number of nonzero terms in the /th polynomial. These
terms are stored, in descending order of exponents, in positions /emw[Z][l],
terms . Create the functions readpoly. printpoly, padd, and pmult for
this representation. Is this representation better or worse than the representation
used in the text? (You may add declarations as necessary.)
ttdefine MAX-TERMS 101 / *■ maximum number of terms + 1

/
*
ttdefine MAX-POLYS 15 / * maximum number of
/
*
polynomials
typedef struct {
float coef;
int expon;
} polynomial;
polynomial terms[MAX—POLYS] [MAX—TERMS];
2.4 THE SPARSE MATRIX ABSTRACT DATA TYPE
2.4.1 Introduction
We now turn our attention to a mathematical object that is used to solve many problems
in the natural sciences, the matrix. As computer scientists, our interest centers not only
on the specification of an appropriate ADT, but also on finding representations that let us
efficiently perform the operations described in the specification.
In mathematics, a matrix contains m rows and n columns of elements as illustrated
in Figure 2.3. In this figure, the elements are numbers. The first matrix has five rows and
three columns; the second has six rows and six columns. In general, we write m x n
(read "m by n") to designate a matrix with m rows and n columns. The total number of
elements in such a matrix is mn. If m equals n, the matrix is square.
The standard representation of a matrix in computer science is a two-dimensional
array defined as a[MAX~ROWS][MAX-COLS]. With this representation, we can locate
quickly any element by writing a[Z][y], where i is the row index and j is the column
index. However, there are some problems with the standard representation. For
The Sparse Matrix Abstract Data Type 67
col 0 col 1 col 2 col 0 col 1 col 2 col 3 col 4 col 5

row 0 -27 3 4 row 0 15 0 0 22 0 -15
row 1 6 82 -2 row 1 0 11 3 0 0 0
row 2 109 -64 11 row 2 0 0 0 -6 0 0
row 3 12 8 9 row 3 0 0 0 0 0 0
row 4 48 27 47 row 4 91 0 0 0 0 0
row 5 0 0 28 0 0 0
(a) (b)
Figure 2.3; Two matrices
instance, if you look at Figure 2.3(b), you notice that it contains many zero entries. We
call this a sparse matrix. Although it is difficult to determine exactly whether a matrix is
sparse or not, intuitively we can recognize a sparse matrix when we see one. In Figure
2.3(b), only 8 of 36 elements are nonzero and that certainly is sparse.
Since a sparse matrix wastes space, we must consider alternate forms of represen
tation. The standard two-dimensional array implementation simply does not work when
the matrices are large since most compilers impose limits on array sizes. For example,
consider the space requirements necessary to store a 1000 x 1000 matrix. If this matrix
contains mostly zero entries we have wasted a tremendous amount of space. Therefore,
our representation of sparse matrices should store only nonzero elements.
Before developing a particular representation, we first must consider the opera
tions that we want to perform on these matrices. A minimal set of operations includes
matrix creation, addition, multiplication, and transpose. Structure 2.3 contains our
specification of the matrix ADT.
Before implementing any of these operations, we must establish the representation
of the sparse matrix. By examining Figure 2.3, we know that we can characterize
uniquely any element within a matrix by using the triple <row, col, value >. This means
that we can use an array of triples to represent a sparse matrix. Since we want our tran
spose operation to work efficiently, we should organize the triples so that the row indices
are in ascending order. We can go one step further by also requiring that all the triples
for any row be stored so that the column indices are in ascending order. In addition, to
ensure that the operations terminate, we must know the number of rows and columns,
and the number of nonzero elements in the matrix. Putting all this information together
suggests that we implement the Create operation as below:
structure Sparse-Matrix is
objects: a set of triples, <row, column, value>, where row and column are integers and
form a unique combination, and value comes from the set item.
functions:
for all a,be Sparse-Matrix, x e item, i, j, max-col, max-row g index
Sparse-Matrix Crcate(max-row, max-col) ::=

return a Sparse-Matrix that can hold up to
max—items = max—row x max-col and whose
maximum row size is max-row and whose
maximum column size is max-col.
Sparse-Matrix Transpose(a) ::=
return the matrix produced by interchanging
the row and column value of every triple.
Sparse-Matrix Add(fl, b} ::=
if the dimensions of a and b are the same
return the matrix produced by adding
corresponding items, namely those with
identical row and column values.
else return error
Sparse-Matrix Multiply(a, b)
if number of columns in a equals number of
rows in b
return the matrix d produced by multiplying o
by b according to the formula: t/[/][7] =
5^(13 [/][/:]• ^ ]) where d{i, j) is the (/, 7)th
element
else return error.
Structure 2.3: Abstract data type Sparse-Matrix
Sparse-Matrix CreatQ^max-row, max-cot)
^define MAX-TERMS 101 *

/ /
*
maximum number of terms +1
typedef struct {
int col;
int row;
int value;
} term;
term a[MAX-TERMS];
Since MAX-TERMS is greater than eight, these statements can be used to

represent the second sparse matrix from Figure 2.3. Figure 2.4(a) shows how this matrix
is represented in the array a. Thus, a [0].row contains the number of rows; a [Oj.coZ con
tains the number of columns; and a [0].vaZwe contains the total number of nonzero
entries. Positions 1 through 8 store the triples representing the nonzero entries. The row
index is in the field row\ the column index is in the field col\ and the value is in the field
value. The triples are ordered by row and within rows by columns.
row col value row col value
fl[0] 6 6 8 h[0] 6 6 8
[1] 0 0 15 [1] 0 0 15
[2] 0 3 22 [2] 0 4 91
[3] 0 5 -15 [3] 1 1 11
[4] 1 1 11 [4] 2 1 3
[5] 1 2 3 [5] 2 5 28
[6] 2 3 -6 [6] 3 0 22
[7] 4 0 91 [7] 3 2 -6
[8] 5 2 28 [8] 5 0 -15
(a) (b)
Figure 2.4: Sparse matrix and its transpose stored as triples
2.4.2 Transposing a Matrix
Figure 2.4(b) shows the transpose of the sample matrix. To transpose a matrix we must
interchange the rows and columns. This means that each element <2[Z][y] in the original
matrix becomes element A>L/][/] in the transpose matrix. Since we have organized the
original matrix by rows, we might think that the following is a good algorithm for tran
sposing a matrix:
for each row i

take element <1, j, value> and store it
as element <j
j /, i,,
i value> of the transpose;
value
Unfortunately, if we process the original matrix by the row indices we will not
know exactly where to place element <7, /, value> in the transpose matrix until we have
processed all the elements that precede it. For instance, in Figure 2.4, we have:
(0,0, 15), which becomes (0,0, 15)

(0, 3, 22), which becomes (3, 0, 22)
(0,5,-15), which becomes (5, 0,-15)
If we place these triples consecutively in the transpose matrix, then, as we insert

new triples, we must move elements to maintain the correct order. We can avoid this data
movement by using the column indices to determine the placement of elements in the
transpose matrix. This suggests the following algorithm:
for all elements in column j

place element <i,
1, j, value in
element <j, i, value>
The algorithm indicates that we should "find all the elements in column 0 and store
them in row 0 of the transpose matrix, find all the elements in column 1 and store them in
row 1, etc." Since the original matrix ordered the rows, the columns within each row of
the transpose matrix will be arranged in ascending order as well. This algorithm is
incorporated in transpose (Program 2.7). The first array, a, is the original array, while
the second array, b, holds the transpose.
It is not too difficult to see that the function works correctly. The variable,
currentb, holds the position in b that will contain the next transposed term. We generate
the terms in b by rows, but since the rows in b correspond to the columns in a, we collect
the nonzero terms for row i of b by collecting the nonzero terms from column i of a.
Analysis of transpose: Determining the computing time of this algorithm is easy since
the nested for loops are the decisive factor. The remaining statements (two if statements
and several assignment statements) require only constant time. We can see that the outer
for loop is iterated a [0].cc»/ times, where a [0].co/ holds the number of columns in the
original matrix. In addition, one iteration of the inner for loop requires a [Oj.vaZwe time,
where a [Q].value holds the number of elements in the original matrix. Therefore, the
total bme for the nested for loops is columns • elements. Hence, the asymptotic time
complexity is Q(columns • elements). □
We now have a matrix transpose algorithm with a computing time of

O(columns • elements). This time is a little disturbing since we know that if we
represented our matrices as two-dimensional arrays of size rows x columns, we could
obtain the transpose in O(rows • columns) time. The algorithm to accomplish this has the
simple form:
void transpose(term a[], term b[])

b is set to the transpose of a */
{
int n,i,j, currentb;
n = a[0].value; /* total number of elements */
b[0].row - a[0].col; / ★
rows in b = columns in a * /
b[0] .col = a[0].row; / *
columns in b = rows in a */
b[0].value = n;
if (n 0 ) { / ★ non zero matrix */
currentb = 1;
for (i = 0; i < a[01.col; i++)
/* transpose by the columns in a */
for (j = 1;<= n;
j
/* find elements from the current column */
if (a.[ j ] .col == i) {
*
/ element is in current column, add it to b */
b[currentb] .row = a[j].col;
b[currentb].col = a[j].row;
b[currentb].value = a[j].value;
currentb++;
}
}
}
Program 2.7: Transpose of a sparse matrix
for (j 0;
=0; j < columns; j++)
for (i = 0; i < rows; i++)
b[j ] [i] - a [i] [j ] ;
The O{columns • elements) time for our transpose function becomes

O(columns^ • rows) when the number of elements is of the order columns ■ rows.
Perhaps, to conserve space, we have traded away too much time. Actually, we can
create a much better algorithm by using a little more storage. In fact, we can transpose a
matrix represented a.s a sequence of triples in O{columns + elements) time. This algo
rithm, fast-transpose (Program 2.8), proceeds by first determining the number of ele
ments in each column of the original matrix. This gives us the number of elements in
each row of the transpose matrix. From this information, we can determine the starting
position of each row in the transpose matrix. We now can move the elements in the origi
nal matrix one by one into their correct position in the transpose matrix. We assume that
MAX-COL is defined as follows, and that the number of columns in the original matrix
never exceeds it.
Arrays And Structures
ttdefine MAX—COL 50 *
/
maximum number of columns + 1
/
*
void fast—transpose(term a[], term b[])

{
the transpose of a is placed in b
int row—terms[MAX—COL], starting—pos[MAX—COL];
int i,j, num—cols = a[0].col, num—terms = a[0].value;
b[0] .row = num—cols; b [ 0] .col a[0].row;
b [ 0] .value num—terms;
if (num—terms >0) { / nonzero matrix */
for {i 0; i < num—cols; i++)
row—terms[i] 0;
for (i = 1; i <= num—terms; i++)
row—terms [a [i] .col] 4-+;
starting—pos[Q] = 1;
for {i 1; i
num—cols ; i++)
starting—pos[i] =
starting—pos[i-1] + row—terms[i-1];
for (i = 1; i <= num—terms;
terms; i-n-) {
j = starting—pos [a [ i ]. col ]-n-;
b[j].row = a[i].col; b[j].col = a[i].row;
b[j].value = a[i].value;
}
}
}
Program 2.8: Fast transpose of a sparse matrix
Analysis offast-transpose: We can verify fast-transpose works correctly from the

preceding discussion and the observation that the starting point of row i, i > 1 of the tran
spose matrix is row-terms[i—l] + where row-rerw5[z-l] is the
number of elements in row z-1 and starting-pos[i-l] is the starting point of row z-1.
The first two for loops compute the values for row-terms, the third for loop carries out
the computation of starting-pos, and the last for loop places the triples into the tran
spose matrix. These four loops determine the computing time of fast-transpose. The
bodies of the loops are executed num-cols, num-terms, num-cols - 1, and num-terms
times, respectively. Since the statements within the loops require only constant time, the
computing time for the algorithm is O(columns + elements). The time becomes
O(columns • rows) when the number of elements is of the order columns • rows. This
time equals that of the two-dimensional array representation, although fast-transpose
has a larger constant factor. However, when the number of elements is sufficiently small
compared to the maximum of columns • rows, fast-transpose is much faster. Thus, in
this representation we save both time and space. This was not true of transpose since the
number of elements is usually greater than m£Lx[columns, rows} and columns • elements
is always at least columns ■ rows. In addition, the constant factor for transpose is bigger
than that found in the two-dimensional array representation. However, transpose
requires less space than fast-transpose since the latter function must allocate space for
the row-terms and starting-pos arrays. We can reduce this space to one array if we put
the starting positions into the space used by the row terms as we calculate each starting
position. □
If we try the algorithm on the sparse matrix of Figure 2.4(a), then after the execu
tion of the third for loop, the values of row-terms and starting-pos are:
[0] [11 [21 [3] [41 [5]

row-terms = 1 2 2 2 0 1
starting-pos = 1 2 4 6 8 8
The number of entries in row i of the transpose is contained in row-terms[i\. The start
ing position for row i of the transpose is held by starting-pos[i].
2.4.3 Matrix Multiplication
A second operation that arises frequently is matrix multiplication, which is defined

below.
Definition: Given A and B where A is m x n and B is n x p, the product matrix D has

dimension m xp. Its <i, j> element is :
zi-l
~ S îk ^kj
k=()
for 0 < i < m and 0 < j < p. □
The product of two sparse matrices may no longer be sparse, as Figure 2.5 shows.
n 0 01 fl 1 11 n 1 11
1 0 0 0 0 0 1 1 1
1 0 0 0 0 0 1 1 1
Figure 2.5: Multiplication of two sparse matrices

Arrays And Structures
We would like to multiply two sparse matrices represented as an ordered list (Fig
ure 2.4). We need to compute the elements of D by rows so that we can store them in
their proper place without moving previously computed elements. To do this we pick a
row of A and find all elements in column j of B for j = 0, 1, • • • , cols-b - 1. Normally,
we would have to scan all of B to find all the elements in column j. However, we can
avoid this by first computing the transpose of B. This puts all column elements in con
secutive order. Once we have located the elements of row i of A and column j of B we
just do a merge operation similar to that used in the polynomial addition of Section 2.2.
(We explore an alternate approach in the exercises at the end of this section.)
To obtain the product matrix D, mmult (Program 2.9) multiplies matrices A and B
using the strategy outlined above. We store the matrices A, B, and D in the arrays a, b,
and d, respectively. To place a triple in d and to reset sum to 0, mmult uses storesum
(Program 2.10). In addition, mmult uses several local variables that we will describe
briefly. The variable row is the row of A that we are currently multiplying with the
columns in B. The variable row-begin is the position in a of the first element of the
current row, and the variable column is the column of B that we are currently multiplying
with a row in A. The variable totald is the current number of elements in the product
matrix D. The variables i and j are used to examine successively elements from a row of
A and a column of B. Finally, the variable new-b is the sparse matrix that is the tran
spose of b. Notice that we have introduced an additional term into both a
(a[foZaZfl-i-l].row = rows-a;) and new-b (new-b[totalb+i].TO'w = cols-b;). These
dummy terms serve as sentinels that enable us to obtain an elegant algorithm.
void mmult{term a[], term b[], term d[])

*
/ multiply two sparse matrices */
{
int i, j, column, totalb = bLO].value, totald 0;
int rows a[0].row, cols—a = a[0].col,
totala - a[0].value; int cols—b = b[0].col,
int row-begin - 1, row = a[1].row, sum = 0;
int new-b[MAX-TERMS][3];
if (cols—a != b[0].row) {
fprintf(stderr,"Incompatible matrices\n");
exit(1);
}
fast—transpose(b,new —b);
/* set boundary condition */
a[totala+l].row = rows-a;
new—b[totalb+1].row = cols—b;
new—b [totalb+1] .col 0;
for (i = 1; i <= totala; ) {
column = new—b[1].row;
for (j = 1; j <= totalb+1;) {
multiply row of a by column of b

if (a[i].row != row) {
storesum(d,&totald,row,column,&sum);
i = row—begin;
for {; new—b[j].row == column; j++)
column = new—b[j].row;
}
else if (new—b[j].row != column) {
storesum (d, Sctotald, row, column, &sum) ;
1 = row—begin;
column = new—b[j].row;
}
else switch (COMPARE(a[i] .col, new—b[j] .col)) {
case -1: /'^ go to next term in a *
/
i + +; break;
case 0: *
/ add terms, go to next term in a and b
/
*
sum + = ( a[i++].value ■k new—b[j++].value);
break;
case 1 : /
* advance to next term in b
D++;
}
} / •jk end of for j
/
* totalb+1 */
for {; a[i].row == row; i + +)
row—begin = i; row = a [ i ] .
} end of for i<=totala
d[0].row = rows
d[0].col cols—b; d[0].value totald;
}
Program 2.9: Sparse matrix multiplication
Analysis of mmult: We leave the correctness proof of mmult as an exercise and consider
only its complexity. Besides the space needed for a, /?, d, and a few simple variables, we
also need space to store the transpose matrix new-b. We also must include the addi
tional space required by fast-transpose. The exercises explore a strategy for mmult that
does not explicitly compute new-h.
We can see that the lines before the first for loop require only O{cols-b + totalb)
time, which is the time needed to transpose b. The outer for loop is executed totala
times. At each iteration either i or j or both increase by 1, or i and column are reset. The
maximum total increment in j over the entire loop is totalb + 1. If termsrow is the total
number of terms in the current row of A, then i can increase at most termsrow times
before i moves to the next row of A. When this happens, we reset / to row-begin, and. at
void storesum(term d[], int *totald, int row, int column,

★
int sum)
*
{
/
* if *
sum I -
!= 0, then it along with its row and column
position is stored as the *totald+l entry in d */
if sum)
*
(
if totald
*
( MAX-TERMS) {
totald]
*
d[++ .row = row;
d[
totaldl.col
* - column;
t
*
d[otald].value sum;
= *
*sum 0;
}
else {
fprintf(stderr,"Numbers of terms in product
exceeds %d\n",MAX-TERMS) ;
exit(1);
}
}
Program 2.10: storesum function
the same time, advance column to the next column. Thus, this resetting takes place at
most cols-b time, and the total maximum increment in i is cols-b^termsrow. There
fore, the maximum number of iterations of the outer for loop is cols-b +
cols -b^termsrow + totalb. The time for the inner loop during the multiplication of the
current row is O{cols-b^termsrow -I- totalb}, and the time to advance to the next row is
Q){termsrow}. Thus, the time for one iteration of the outer for loop is
Q{cols-b'^termsrow -I- totalb}. The overall time for this loop is:
O('^(cols-b ■ termsrow + totalb}} = O{cols^b • total-a + rows-a • totalb) □
row
Once again we can compare this time with the computing time required to multi
ply matrices using the standard array representation. The classic multiplication algo
rithm is:
for (i = 0; i < rows—a; i++)

for (j - 0; j < cols—b; j++} {
sum = 0;
for {k 0; k cols—a; k++)
sum += (a[i][k] ★ b[k] [3 ] ) ;
a[i] [j] sum;
}
This algorithm takes O(r67W5-<3 • cols-a - cols~b) time. Since totala < cols~a ■ rows-a
and totalb < cols~a ■ cols-b, the time for mmult is at most:
Q{rows-a ■ cols-a • cols-b)
However, its constant factor is greater than that of the classic algorithm. In the worst
case, when totala = cols-a ■ rows-a or totalb = cols-a • cols-b, mmult is slower by a
constant factor. However, when totala and totalb are sufficiently smaller than their max
imum value, that is, A and 3 are sparse, mmult outperforms the classic algorithm. The
analysis of mmult is not trivial. It introduces some new concepts in algorithm analysis
and you should make sure that you understand the analysis.
This representation of sparse matrices permits us to perform operations such as
addition, transpose, and multiplication efficiently. However, there are other considera
tions that make this representation undesirable in certain applications. Since the number
of terms in a sparse matrix is variable, we would like to represent all our sparse matrices
in one array as we did for polynomials in Section 2.2. This would enable us to make
efficient utilization of space. However, when this is done we run into difficulties in allo
cating space from the array to any individual matrix. These difficulties also occur with
the polynomial representation and will become even more obvious when we study a
similar representation for multiple stacks and queues in Section 3.4.
EXERCISES
1. Write C functions read-matrix, print-matrix, and search that read triples into a
new sparse matrix, print out the terms in a sparse matrix, and search for a value in
a sparse matrix. Analyze the computing time of each of these functions.
2. Rewrite fast-transpose so that it uses only one array rather than the two arrays
required to hold row-terms and starting-pos.
3. Develop a correctness proof for the mmult function.
4. Analyze the time and space requirements of fast-transpose. What can you say
about the existence of a faster algorithm?
5. Use the concept of an array of starting positions found va fast-transpose to rewrite

mmult so that it multiplies sparse matrices A and B without transposing B. What is
the computing time of your function?
6. As an alternate sparse matrix representation we keep only the nonzero terms in a
one-dimensional array, value, in the order described in the text. In addition, we
also maintain a two-dimensional array, bits [raw }[columns ], such that bits[i][j]
= 0 if «[/][/■] - 0 and ^zV^Cz'lL/] = 1 if «[/][/] 0. Figure 2.6 illustrates the
representation for the sparse matrix of Figure 2.4(b).
151
r1 0 0 1 0 11 22
0 110 0 0 -15
0 0 0 10 0 11
0 0 0 0 0 0 3
1 0 0 0 0 0 -6
0 0 1 0 0 0 91
28
Figure 2.6: Alternate representation of a sparse matrix
(a) On a computer with w bits per word, how much storage is needed to
represent a sparse matrix. A, with t nonzero terms?
(b) Write a C function to add two sparse matrices A and B represented as in Fig
ure 2.6 to obtain D - A + B. How much time does your algorithm take?
(c) Discuss the merits of this representation versus the one used in the text.
Consider the space and time requirements for such operations as random
access, add, multiply, and transpose. Note that we can improve the random
access time by keeping another array, ra, such that ra [/ ] = number of
nonzero terms in rows 0 through z - 1.
2.5 REPRESENTATION OF MULTIDIMENSIONAL ARRAYS
The internal representation of multidimensional arrays requires more complex address

ing formulas. If an array is declared a [upper<^}[upperJ • • • [uppern^^}, then it is easy
to see that the number of elements in the array is:
rt-i
/=0
where H is the product of the upperi's. For instance, if we declare a as a [10][ 10][ 10],
then we require 10 • 10 ■ 10 = 1000 units of storage to hold the array. There are two
Representation Of Multidimensional Arrays 79
common ways to represent multidimensional arrays: row major order and column major
order. We consider only row major order here, leaving column major order for the exer
cises.
As its name implies, row major order stores multidimensional arrays by rows. For
instance, we interpret the two-dimensional array A [upperQ][upperi ] as upper^ rows,
row-’o, raw J, • • • , raWypp^^Q_i, each row containing upper y elements.
If we assume that a is the address of A [0][0], then the address of A [Z ][0] is oc +
i • upper X because there are Z rows, each of size upper j, preceding the first element in
the Zth row. Notice that we haven’t multiplied by the element size. This follows C con
vention in which the size of the elements is automatically accounted for. The address of
an arbitrary element, a [Zfij], is a + Z • upper j + j.
To represent a three-dimensional array, A[upperQ\[uppery}[upper2}. we interpret
the array as upper0 two-dimensional arrays of dimension upper 1 y. upper2- To locate
u [Z ][7 J[^ ], we first obtain a -1- i • upper 1 • upper! as the address of a [Z ][0][0] because
there are i two-dimensional arrays of size upper 1 • upper2 preceding this element. Com
bining this formula with the formula for addressing a two-dimensional array, we obtain:
a + i • upper I • upper 2 + j ‘ upper 2 + k
as the address of a [z ] [7 ] .
Generalizing on the preceding discussion, we can obtain the addressing formula
for any element A [ZolU i ] • • • [Z„_i ] in an n-dimensional array declared as:
A [upperQ][upperx} . . . [upper^.^]
If a is the address forX [0J[0]. . . [0] then the address of a [/o](O][O]... [0] is:
a+ z'o upperupper2 . . upper n-i
The address of a • • • [0] is:

a+z'o upper \ upper2 • . ■ upper^-] + z'l upper2 upper3 . . . upper^-}
Repeating in this way the address for A [/o][/1 ]. . . [Z„_i ] is:
a + iQupper iupper2 ■ • ■ upper^-i

+ i\upper2upper2 . . . upper„_\
+ i2Upper2Upper^ . . . uppern_i
+ i„_2upper^-i
+
n-l
"y = n upper,, 0<j<n-\

= a-i- ijaj where: k=i+ \
j=() ' Un-\ = 1
Notice that aj may be computed from 0 < j < «-!, using only one multiplication as
■ ^7 + 1 • Thus, a compiler will initially take the declared bounds
upper0 , .. . , upperfi-\ and use them to compute the constants using n-2
multiplications. The address of a [zq] ■ • ■ cnn be computed using the formula,
requiring n-1 more multiplications and n additions and n subtractions.
EXERCISES
1. Assume that we have a one-dimensional array, a[MAX-SlZE\. Normally, the sub

scripts for this array vary from 0 to MAX-SIZE - 1. However, by using pointer
arithmetic we can create arrays with arbitrary bounds. Indicate how to create an
array, and obtain subscripts for an array, that has bounds between -10 to 10. That
is, we view the subscripts as having the values -10, -9, -8, • • • , 8, 9, 10.
2. Extend the results from Exercise 1 to create a two-dimensional array where row
and column subscripts each range from -10 to 10.
3. Obtain an addressing formula for the element a [/’olCG] • • • in nn array
declared as a [uppers]. .. a Assume a column major representation of
the array with one word per element and a the address of a [0] [0]... [0]. In
column major order, the entries are stored by columns first. For example, the array
a [3][3] would be stored as a [0][0], a [l][0], a [2][0], a [0][l], a [1][1], a [2][1],
a[0][2], a[l][2], a [2][2].
2.6 THE STRING ABSTRACT DATA TYPE
2.6.1 Introduction
Thus far, we have considered only ADTs whose component elements were numeric. For
example, we created a sparse matrix ADT and represented it as an array of triples
<row, col, value >. In this section, we turn our attention to a data type, the string, whose
component elements are characters. As an ADT, we define a string to have the form, 5 =
5o, .. . , where Si are characters taken from the character set of the programming
language. If n = 0, then S is an empty or null string.
There are several useful operations we could specify for strings. Some of these
operations are similar to those required for other ADTs: creating a new empty string,
reading a string or printing it out, appending two strings together (called concatenation),
or copying a string. However, there are other operations that are unique to our new
ADT, including comparing strings, inserting a substring into a string, removing a sub
string from a string, or finding a pattern in a string. We have listed the essential opera
tions in Structure 2.4, which contains our specification of the string ADT. Actually there
are many more operations on strings, as we shall see when we look at part of C’s string
library in Figure 2.7.
The String Abstract Data Type 81
structure String is
objects: a finite set of zero or more characters.
functions:
for all 5, t G String, i, j, m E non-negative integers
String Null(m) return a string whose maximum length is
m characters, but is initially set to NULL
1111
We write NULL as
Integer Compare(5, z) if 5 equals t
return 0
else if .y precedes t
return -1
else return +1
Boolean IsNull(5) if (Compare(5, NULL))
return FALSE
else return TRUE
Integer Length(5) if (Compare(5, NULL))
return the number of characters in 5
else return 0.
String Concat(5, t) if (Compare(z, NULL))
return a string whose elements are those
of 5 followed by those of t
else return 5.
String Substr(s, z, 7) if ({7 > 0) && (z +7-I) < Length(5))
return the string containing the characters
of 5 at positions z, i + 1, • • • , z +7-I.
else return NULL.
Structure 2.4: Abstract data type String
In C, we represent strings as character arrays terminated with the null character \0.
For instance, suppose we had the strings:
#define MAX—SIZE 100 maximum

*
/ size of string */
char s[MAX-SIZE] {"dog"};
char t[MAX-SIZE] {"house"};
Figure 2.8 shows how these strings would be represented internally in memory.
Notice that we have included array bounds for the two strings. Technically, we could
have declared the arrays with the statements:
char s[] {"dog"};

Function Description
char ^strcat(char ^dest, char *src) concatenate dest and strings;
return result in dest
stmcat(char ^'dest, char *src, intn)
char * concatenate dest and « characters
from 5rc; return result in dest
strl, char *str2)
char ^strcmp(char * compare two strings;
return < 0 if strl < str2\
if 5Zr7 = str2-,
> 0 if 5rr7 > str2
strncmp(char *
char * strl, char ^str2, int n) compare first n characters
return < 0 if 5Zr7 < str2;
0 if 5Zr7 = str2‘,
> 1 if strl > str2
char ^strcpy(char "^dest, char "^src) copy src into dest; return
char '^strncpy(char "^dest, char ^src, int n) copy n characters from src
string into dest; return Jc^z;
size~-t strlen(char 5*) return the length of a 5
char '^strchr(char *5, intc) return pointer to the first
occurrence of c in s;
return NULL if not present
char '^strrchr(char *5, int c) return pointer to last occurrence of
c in 5; return NULL if not present
char '^strtok(char *5, char ^delimiters) return a token from s; token is
surrounded by delimiters
char ^strstr(char *5, char *pat) return pointer to start of
pat in 5
size—tstrspn(char *s, char ^spanset) scan 5 for characters in spanset;
return length of span
spanset)
size-t strcspn(char *s, char * scan 5 for characters not in spanset;
return length of span
char "^strpbrkichar *5, char ^spanset) scan 5 for characters in spanset;
return pointer to first occurrence
of a character from spanset
Figure 2.7: C string functions

sEO] sEl] sEZ] sE31 tEOl tElJ tEZl trai t[4] tE51
a o 9 \0 h o u s e \0
Figure 2.8: String representation in C
char t[] {"house"}
Using these declarations, the C compiler would have allocated just enough space to hold
each word including the null character. Now suppose we want to concatenate these
strings together to produce the new string, "doghouse." To do this we use the C function
strcat (See Figure 2.7). Two strings are joined together by strcat {s, t}, which stores the
result in 5. Although 5 has increased in length by five, we have no additional space in 5
to store the extra five characters. Our compiler handled this problem inelegantly: it sim
ply overwrote the memory to fit in the extra five characters. Since we declared t immedi
ately after 5, this meant that part of the word "house" disappeared.
We have already seen that C provides a built-in function to perform concatenation.
In addition to this function, C provides several other string functions which we access
through the statement ttinclude <string.h>. Figure 2.7 contains a brief summary of these
functions (we have excluded string conversion functions such as atoi). For each func
tion, we have provided a generic function declaration and a brief description. Rather
than discussing each function separately, we next look at an example that uses several of
them. For further information on string functions, including examples, look at the books
by Keminghan and Ritchie or Harbison and Steele cited in the References and Selected
Readings section.
Example 2.2 [String insertion]: Assume that we have two strings, say string i and
string 2, and that we want to insert string 2 into string 1 starting at the /th position of
string 1. We begin with the declarations:
ttinclude string.h>
#define MAX-SIZE 100 size
*
/ of largest string
/
*
*
char stringl[MAX-SIZE], s = stringl;
★
char Strings[MAX-SIZE], t = string2;
In addition to creating the two strings, we also have created a pointer for each string.
Now suppose that the first string contains "amobile" and the second contains "uto"
(Figure 2.9). We want to insert "uto" starting at position 1 of the first string, thereby pro
ducing the word "automobile." We can accomplish this using only three function calls,
as Figure 2.9 illustrates. Thus, in Figure 2.9(a), we assume that we have an empty string
that is pointed to by temp. We use strncpy to copy the first / characters from 5 into temp.
Since i = 1, this produces the string "a." In Figure 2.9(b), we concatenate temp and t to
produce the string "auto." Finally, we append the remainder of 5 to temp. Since strncat
copied the first i characters, the remainder of the string is at address (5 + /). The final
result is shown in Figure 2.9(c).
5 a m o b i 1 e \0
t u t \0
temp \0
initially
temp a \0
(a) after strncpy {temp,s,i)
temp u t o \Q
(b) after strcat (temp.t)
temp a u t o m 0 b i 1 e \0
(c) after strcat {temp, {s
Figure 2.9: String insertion example
Program 2.11 inserts one string into another. This particular function is not nor
mally found in <string.h.>. Since either of the strings could be empty, we also include
statements that check for these conditions. It is worth pointing out that the call
strnins{s, t, 0) is equivalent to strcat {t, 5). Program 2.11 is presented as an example of
manipulating strings. It should never be used in practice as it is wasteful in its use of
time and space. Try to revise it so the string temp is not required. □
2.6.2 Pattern Matching
Now let us develop an algorithm for a more sophisticated application of strings. Assume
that we have two strings, string and pat, where pat is a pattern to be searched for in
string. The easiest way to determine if pat is in string is to use the built-in function strstr.
If we have the following declarations:
void strnins(char *s, char *t. int i)

{
*
/ insert string t into string s at position i */
★
char string[MAX-SIZE] , temp = string;
if (i 0 && i > strlen(s)) {

fprintf(stderr,"Position is out of bounds \n");
exit(1);
}
if (!strlen(s))
strcpy(s,t);
else if {strlen(t)) {
strncpy(temp, s,i);
strcat(temp,t);
strcat(temp, (s+i));
strcpy(s, temp);
}
}
Program 2.11: String insertion function
char pat[MAX—SIZE], string[MAX—SIZE], *t ;
then we use the following statements to determine if pat is in string:
if (t = strstr(string,pat))
printf("The string from strstr is: %s\n",t);
else
printfC’The pattern was not found with strstr\n");
The call (t = strstr (string,pat)) returns a null pointer if pat is not in string. If pat is in
string, t holds a pointer to the start of pat in string. The entire string beginning at posi
tion t is printed out.
Although strstr seems ideally suited to pattern matching, there are two reasons
why we may want to develop our own pattern matching function:
(1) The function strstr is new to ANSI C. Therefore, it may not be available with the
compiler we are using.
(2) There are several different methods for implementing a pattern matching function.
The easiest but least efficient method sequentially examines each character of the
string until it finds the pattern or it reaches the end of the string. (We explore this
approach in the Exercises.) If pat is not in string, this method has a computing
time of O(n ■ m) where n is the length of pat and w is the length of string. We can
do much better than this, if we create our own pattern matching function.
We can improve on an exhaustive pattern matching technique by quitting when

strlen {pat} is greater than the number of remaining characters in the string. Checking
the first and last characters of pat and string before we check the remaining characters is
a second improvement. These changes are incorporated in nfind (Program 2.12).
int nfind(char *string, pat)

char *
{
/ match the last character of pattern first,
* and
then match from the beginning */
int i,j,start = 0;
int lasts strlen(string)-1;
int lastp = strlen(pat)-1;
int endmatch = lastp;
for (i - 0; endmatch <= lasts; endmatch++, start++) {

if (string[endmatch] == pat[lastp])
for (j = 0, i = start; j < lastp &&
string[i] == pat[j]; i + +,j-i--i-)
if (j == lastp)
return start; / *
successful */
}
return —1;
}
Program 2.12: Pattern matching by checking end indices first
Example 2.3 [Simulation of nfind} *. Suppose pat = "aab" and string = "ababbaabaa."
Figure 2.10 shows how nfind compares the characters from pat with those of string. The
end of the string and pat arrays are held by lasts and lastp, respectively. First nfind com
pares string [endmatch} and pat [lastp}. If they match, nfind uses i and 7 to move
through the two strings until a mismatch occurs or until all of pat has been matched. The
variable start is used to reset i if a mismatch occurs. □
Analysis of nfind-. If we apply nfind to string = "aa • • • a" and pat = "a • • • ab", then the
computing time for these strings is linear in the length of the string O(m), which is cer
tainly far better than the sequential method. Although the improvements we made over
the sequential method speed up processing on the average, the worst case computing
time is still O(« • m). n
a a b
T
y lastp
(a) pattern
a b a b b a a b a a
T" T T’
endmatch lasts
(b) no match
a b a b b a a b a a
'T' T nr
endmatch lasts
(c) no match
a b a b b a a b a a
T" T T”
Start endmatch lasts
(d) no match
a b a b b a a b a a
T T"
start endmatch lasts
(e) no match
a b a b b a a b a a
“T T rr
(f) no match
a b a b b a a b a a
t T rr
match
Figure 2.10: Simulation of nftnd

Ideally, we would like an algorithm that works in O(strlen (string) + strlen(pat))

time. This is optimal for this problem as in the worst case it is necessary to look at all
characters in the pattern and string at least once. We want to search the string for the
pattern without moving backwards in the string. That is, if a mismatch occurs we want
to use our knowledge of the characters in the pattern and the position in the pattern
where the mismatch occurred to determine where we should continue the search. Knuth,
Morris, and Pratt have developed a pattern matching algorithm that works in this way
and has linear complexity. Using their example, suppose
pat = 'abcabcacab'
Let 5 = 5o 52 • • • 5^-1 be the string and assume that we are currently determining
whether or not there is a match beginning at 5/. If s^â then, clearly, we may proceed by
comparing and a. Similarly if 5/ = a and 5j + | b then we may proceed by compar
ing and a. If 5,-5,+ i = ab and Si+2 then we have the situation:
5= a b ? 9 9 ?’
pat = 'a b c a b c a c a Z?’
The ? implies that we do not know what the character in 5 is. The first ? in 5 represents
5,-+2 and 5j+2 c. At this point we know that we may continue the search for a match by
comparing the first character in pat with 5,-+2- There is no need to compare this character
of pat with 5,+i as we already know that 5, + i is the same as the second character of pat,
b, and so 5,+i a. Let us try this again assuming a match of the first four characters in
pat followed by a nonmatch, i.e., 5^+4 b. We now have the situation:
5 = a b c a 9 7 ?’
pat - "a b c a b c a c a h’
We observe that the search for a match can proceed by comparing 5,-+4 and the second
character in pat, b. This is the first place a partial match can occur by sliding the pattern
pat towards the right. Thus, by knowing the characters in the patterm and the position in
the pattern where a mismatch occurs with a character in 5 we can determine where in the
pattern to continue the search for a match without moving backwards in 5. To formalize
this, we define a failure function for a pattern.
Definition: If p = pop j ■ • ■ p„_| is a pattern, then its failure function, f is defined as:
largest i < j such that PoPi " ' Pi- Pj-iPj-i+2 '' ' Pj if such an Z > 0 exists
/(/■) = □
-1 otherwise
For the example pattern, pat - abcabcacab, we have:
J 0 1 1 3 4 5 6 1 8 9
pat tz b c a b c tz c a b
f -1 -1 -1 0 1 1 3 -1 0 1
From the definition of the failure function, we arrive at the following rule for pat
tern matching; If a partial match is found such that Si^j • • • ’ Pj-\
Si Pj then matching may be resumed by comparing s^ and if j 0. If j =
then we may continue by comparing azzt/ po. This pattern matching rule translates
into function pmatch (Program 2.13). The following declarations are assumed:
linclude <stdio.h>
#include <string.h>
#define max_string_size 100
#define max_pattern_si2e 100
int pmatch();
void fail{);
int failure[max_pattern_size];
char string[max_string_size]t
char pat[max_pattern_size] ;
int pmatch(char *string, char *

pat)
{
*
/ Knuth, Morris, Pratt string matching algorithm */
int i 0, j = 0;
int lens = strlen(string) ;
int lenp = strlen(pat);
while ( i < lens && j < lenp ) {
if (stringli] == pat[j]) {
i++ ; j++; }
else if (j == 0) i++;
else j = fallure[j-1]+1;
}
return { (j == lenp) ? (i-lenp) : -1);
}
Program 2.13: Knuth, Morris, Pratt pattern matching algorithm

Note that we do not keep a pointer to the start of the pattern in the string. Instead
we use the statement:
return ( (j == lenp) ? (i - lenp) : -1);
This statement checks to see whether or not we found the pattern. If we didn’t find the
pattern, the pattern index index j is not equal to the length of the pattern and we return
-1. If we found the pattern, then the starting position is / - the length of the pattern.
Analysis of pmatch: The while loop is iterated until the end of either the string or the
pattern is reached. Since i is never decreased, the lines that increase i cannot be exe
cuted more than m = strlen (string) times. The resetting of j to failure[j~l] + l decreases
the value of j. So, this cannot be done more times than j is incremented by the statement
j ++ as otherwise, j falls off the pattern. Each time the statement j ++ is executed, i is
also incremented. So, j cannot be incremented more than m times. Consequently, no
statement of Program 2.13 is executed more than m times. Hence the complexity of
function pmatch is O(m) = O(strlen (string)). □
From the analysis of pmatch, it follows that if we can compute the failure function
in O(strlen (pat)) time, then the entire pattern matching process will have a computing
time proportional to the sum of the lengths of the string and pattern. Fortunately, there is
a fast way to compute the failure function. This is based upon the following restatement
of the failure function:
-1 if 7 = 0
f<J) = f” (j - 1) + 1 where m is the least integer k for which = pj
-1 if there is no k satisfying the above
(note that f' (j) = f (j) and /"O') (j}}')-
This definition yields the function in Program 2.14 for computing the failure function of
a pattern.
Analysis of fail: In each iteration of the while loop the value of i decreases (by the
definition of/). The variable i is reset at the beginning of each iteration of the for loop.
However, it is either reset to -1 (initially or when the previous iteration of the for loop
goes through the last else clause) or it is reset to a value 1 greater than its terminal value
on the previous iteration (i.e., when the statement failure[j] = Z + 1 is executed). Since
the for loop is iterated only n-[ (n is the length of the pattern) times, the value of i has a
total increment of at most n-1. Hence it cannot be decremented more than n~l times.
Consequently the while loop is iterated at most n-\ times over the whole algorithm and
the computing time onfall is O(n) = O(strlen (pat)}. □
void fail(char *
pat)
{
/* ■ compute the pattern's failure function */
int n = strlen(pat);
failure[0] -1;
for (j=l; j n; j++) {
i = failure[j-1] ;
while ((patlj] != pat[i+1]) && (i 0) )
i failure[i];
if (pat[j] == pat[i+1])
failure[j] i + 1;
else failure[j] = -1;
}
}
Program 2.14: Computing the failure function
Note that when the failure function is not known in advance, the time to first compute
this function and then perform a pettern match is 0{strlen (pat) + strlen (string)).
EXERCISES
1. Write a function that accepts as input a string and determines the frequency of
occurrence of each of the distinct characters in string. Test your function using
suitable data.
2. Write a function, strndel, that accepts a string and two integers, start and length.
Return a new string that is equivalent to the original string, except that length
characters beginning at start have been removed.
3. Write a function, strdeh that accepts a string and a character. The function returns
string with the first occurrence of character removed.
4. Write a function, strpos}, that accepts a string and a character. The function
returns an integer that represents the position of the first occurrence of character
in string. If character is not in string, it returns -1. You may not use the function
strpos which is part of the traditional <string.h> library, but not the ANSI C one.
5. Write a function, strchr 1, that does the same thing as strpos 1 except that it returns
a pointer to character. If character is not in the list it returns NULL. You may not
use the built-in function strchr.
6. Modify Program 2.11 so that it does not use a temporary string temp. Compare the
complexity of your new function with that of the old one.
7. Write a function, strsearch, that uses the sequential method for pattern matching.
That is, assuming we have a string and a pattern, strsearch examines each charac
ter in string until it either finds the pattern or it reaches the end of the string.
8. Show that the computing time for nfind is O(/i • w) where n and m are, respec
tively, the lengths of the string and the pattern. Find a string and a pattern for
which this is true.
9. Compute the failure function for each of the following patterns:
(a) aaaab
(b) ababa a
(c) ab aab aab
10. Show the equivalence of the two definitions for the failure function.
2.7 REFERENCES AND SELECTED READINGS
Several texts discuss array representation in C, including T. Plum, Reliable Data Struc
tures in C, Plum Hall, Cardiff, N.J., 1985 (Chapter 3), and R. Jaesche, Solutiofis in C,
Addison-Wesley, Reading, Mass., 1986 (Chapter 2). The Jaesche text includes a detailed
discussion of array bounds, including altering array bounds, and pointer addressing.
Strings are discussed in B. Kemighan and K. Ritchie, The C Programming
Language, ANSI C, Second Edition, Prentice-Hall, Englewood Cliffs, N.J., 1988, and S.
Harbison and G. Steele, C: A Reference Manual, Third Edition, Prentice-Hall, Engle
wood Cliffs, N.J., 1991 (Chapter 13). A discussion of string pointers can be found in R.
Traister, Mastering C Pointers, Academic Press, San Diego, Calif., 1990. The Knuth,
Morris, Pratt pattern matching algorithm is found in "Fast pattern matching in strings,"
SIAM Journal on Computing, vol. 6, no. 2, 1977.
2.8 ADDITIONAL EXERCISES
I. Given an array a[n] produce the array z[n] such that ^[0] = a [n—l],z[l] =
a[n~2], ••• ,z[n-2] =a[l],z[«-13 = <7[0]. Use a minimal amount of storage.
2. An m X n matrix is said to have a saddle point if some entry a [Z Jlj ] is the smallest
value in row i and the largest value in column j. Write a C function that deter
mines the location of a saddle point if one exists. What is the computing time of
your method?
Exercises 3 through 8 explore the representation of various types of matrices that

are frequently used in the solution of problems in the natural sciences.
Additional Exercises 93
3. A triangular matrix is one in which either all the elements above the main diago
nal or all the elements below the main diagonal of a square matrix are zero. Figure
2.11 shows a lower and an upper triangular matrix. In a lower triangular matrix,
a, with n rows, the maximum number of nonzero terms in row i is i +1. Thus, the
total number of nonzero terms is
n-l
^(Z+ l)=n (n-i-])/2.

i=Q
Since storing a triangular matrix as a two dimensional array wastes space, we

would like to find a way to store only the nonzero terms in the triangular matrix.
Find an addressing formula for the elements ajj so that they can be stored by rows
in an array b [«(n •+• 1 )/2-1 ], with a [0] [0] being stored in b [0].
X XXX X X XXX X X
X X X X
X X X X
X X X non X
X X zero X zero X
X non X X X
X zero X zero X X
X X X X
X X X X
X XXX X X X XXX X
lower triangular upper triangular
Figure 2.11 : Lower and upper triangular matrices
4. Let a and b be two lower triangular matrices, each with n rows. The total number
of elements in the lower triangles is «(zi -h 1). Devise a scheme to represent both
triangles in an array ). [Hint: Represent the triangle of a in the lower tri
angle of d and the transpose b in the upper triangle of d.] Write algorithms to
determine the values of a [i ][/ ], b [i ][/ ], 0 < i, J < n.
5. A tridiagonal matrix is a square matrix in which all elements that are not on the
major diagonal and the two diagonals adjacent to it are zero (Figure 2.12). The
elements in the band formed by these three diagonals are represented by rows in
an array, b, with a [0]f0] being stored in Z?[0]. Obtain an algorithm to determine
the value of a [Z ][7 ], 0 < i. j < n from the array b.
X X
XXX
XXX
. X
zero
zero X X
XXX
XXX
XXX
Figure 2.12 : Tridiagonal matrix
6. A square band matrix is an n x n matrix in which all the nonzero terms lie in
a band centered around the main diagonal. The band includes the main diagonal
and <3-1 diagonals below and above the main diagonal (Figure 2.13).
a diagonals
upper band
lower
band n
rows
0
^4,3
n columns
main diagonal
Figure 2.13 : Square band matrix

(a) How many elements are there in the band £),In,a 7•

(b) What is the relationship between i and j for elements d/y in the band
(c) Assume that the band of is stored sequentially in an array b by diago
nals, starting with the lowermost diagonal. For example, the band matrix,
D4 3 of Figure 2.13 would have the following representation.
b[0] b[l] b[2] b[3] b[4] b[5] b[6] b(7] b[8] b[9] b[l0] bill] b[12] b[13]
9 8 3 6 6 0 2 8 4 9 8 4
<^31 10 d2i ^32 <^00 dll ^22 9^33 <^01 dn ^23 ^02 ^13
Obtain an addressing formula for the location of an element, d/j, in the lower band of
(location(d lo) = 2 in the example above).
7. A generalized band matrix D^ a^b is an az x n matrix in which all the nonzero terms
lie in a band made up of <3-1 diagonals below the main diagonal, the main diago
nal, and b-i bands above the main diagonal (Figure 2.14).
n
rows
n columns
main diagonal
^n.a,h
Figure 2.14 : Generalized band matrix

(a) How many elements are there in the band of

(b) What is the relationship between i and j for the elements dij in the band of
(c) Obtain a sequential representation of the band D^â^b in the one dimensional
array e. For this representation, write a C function value (n, a, b, i, j, e)
that determines the value of element da in the matrix D,'n,a.b. The band of
^n.a,.7, is represented in the array e.
8. A complex-valued matrix X is represented by a pair of matrices <a, b>, where a
and b contain real values. Write a function that computes the product of two
complex-valued matrices <a, b > and <d, e >, where <a, /? > * <J, e > = (a + ib)
* (d + ie) = (ad - be) + i (ae + bd). Determine the number of additions and mul
tiplications if the matrices are all nxn.
9. § [Programming project] There are a number of problems, known collectively as
"random walk" problems, that have been of longstanding interest to the mathemati
cal community. All but the most simple of these are extremely difficult to solve,
and, for the most part, they remain largely unsolved. One such problem may be
stated as:
A (drunken) cockroach is placed on a given square in the middle of a tile floor in a

rectangular room of size n x m tiles. The bug wanders (possibly in search of an
aspirin) randomly from tile to tile throughout the room. Assuming that he may
move from his present tile to any of the eight tiles surrounding him (unless he is
against a wall) with equal probability, how long will it take him to touch every tile
on the floor at least once?
Hard as this problem may be to solve by pure probability techniques, it is quite

easy to solve using a computer. The technique for doing so is called "simulation."
This technique is widely used in industry to predict traffic flow, inventory control,
and so forth. The problem may be simulated using the following method:
An n X m array count is used to represent the number of times our cockroach has
reached each tile on the floor. All the cells of this array are initialized to zero.
The position of the bug on the floor is represented by the coordinates (ibug, jbug).
The eight possible moves of the bug are represented by the tiles located at
(ibug + imove [k ], jbug + jmove [k j), where 0 < k < 7, and
zwove[0) = -1 7m<?ve[0] = 1
= 0 /move[l] = 1
zm6)v^[2] = 1 jmove[2] = 1
imove[3] = 1 jmovel3] = 0
zm(9v^[4] = 1 7move’[4] = -1
zm(9v^[5] = 0 ym<7ve[5] = -1
imove[6] = -1 jmovel6] = -1
zm<?v^[7] = -1 7m€>v^[7] = 0
A random walk to any one of the eight neighbor squares is simulated by generat
ing a random value for k, lying between 0 and 7. Of course, the bug cannot move
outside the room, so that coordinates that lead up a wall must be ignored, and a
new random combination formed. Each time a square is entered, the count for that
square is incremented so that a nonzero entry shows the number of times the bug
has landed on that square. When every square has been entered at least once, the
experiment is complete.
Write a program to perform the specified simulation experiment. Your program

MUST:
(a) handle all values of n and m, 2 < n< 40, 2 < m < 20;
(b) perform the experiment for (1) n = 15, m = 15, starting point (10, 10), and
(2) n = 39, m = 19, starting point (1, 1);
(c) have an iteration limit, that is, a maximum number of squares that the bug
may enter during the experiment. This ensures that your program will ter
minate. A maximum of 50,000 is appropriate for this exercise.
For each experiment, print (1) the total number of legal moves that the cockroach
makes and (2) the final count array. This will show the "density" of the walk, that
is, the number of times each tile on the floor was touched during the experiment.
This exercise was contributed by Olson.
10. § [Programming project] Chess provides the setting for many fascinating diver
sions that are quite independent of the game itself. Many of these are based on the
strange "L-shaped" move of the knight. A classic example is the problem of the
"knight’s tour," which has captured the attention of mathematicians and puzzle
enthusiasts since the beginning of the eighteenth century. Briefly stated, the prob
lem requires us to move the knight, beginning from any given square on the chess
board, successively to all 64 squares, touching each square once and only once.
Usually we represent a solution by placing the numbers 0, 1, • • •, 63 in the
squares of the chess board to indicate the order in which the squares are reached.
One of the more ingenious methods for solving the problem of the knight’s tour
was given by J. C. Warnsdorffin 1823. His rule stated that the knight must always
move to one of the squares from which there are the fewest exits to squares not
already traversed.
The goal of this programming project is to implement Warnsdorff s rule. The

ensuing discussion will be easier to follow, however, if you try to construct a solu
tion to the problem by hand, before reading any further.
The crucial decision in solving this problem concerns the data representation. Fig
ure 2.15 shows the chess board represented as a two-dimensional array.
0 1 2 3 4 5 6 7
2 7 0
3 6 1
4 K
5 5 2
4 3
Figure 2.15: Legal moves for a knight
The eight possible moves of a knight on square (4, 2) are also shown in this figure.
In general, a knight may move to one of the squares (i - 2, 7 4- 1), (/ -1,74- 2),
(/ + 1,7 + 2), {i + 2,7 + 1), (z + 2,7 - 1), (z + 1,7 - 2), (z - 1,7 - 2), (z -2J- 1).
However, notice that if (z, j) is located near one of the board’s edges, some of
these possibilities could move the knight off the board, and, of course, this is not
permitted. We can represent easily the eight possible knight moves by two arrays
ktmove 1 and ktmove 2 as:
ktmove 1 ktmove 2
-2 1
-1 2
1 2
2 1
2 -I
1 -2
-1 -2
-2 -1
Then a knight at (/, 7) may move to (i + ktmove [/:], 7 + ktrnovellk]), where Z: is

some value between 0 and 7, provided that the new square lies on the chess board.
Below is a description of an algorithm for solving the knight’s tour problem using
Wamsdorffs rule. The data representation discussed in the previous section is
assumed.
(a) [Initialize chessboard] For 0 < i, j < 7 set board [/ ][7 ] to 0.
(b) [Set starting position] Read and print (/, j) and then set board [z ][7 ] to 0.
(c) [Loop] For 1 < m < 63, do steps (d) through (g).
(d) [Form a set of possible next squares] Test each of the eight squares one
knight’s move away from (/, 7) and form a list of the possibilities for the
next square (nexti[l], nextj [I]). Let npos be the number of possibilities.
(That is, after performing this step we have nexti [/] = / + ktmove 1 [k ] and
nexlj [/ ] = j + ktmove ^[k ], for certain values of k between 0 and 7. Some of
the squares (z + ktmove 1[^], j + /cZznove 2[/:]) may be impossible because
they lie off the chessboard or because they have been occupied previously
by the knight, that is, they contain a nonzero number. In every case we will
have 0 < npos < 8.)
(e) [Test special cases] If npos = 0, the knight’s tour has come to a premature
end; report failure and go to step (h). If npos = 1, there is only one next
move; set min to 1 and go to step (g).
(0 [Find next square with minimum number of exits] For 1 < I < npos, set
exits [Z] to the number of exits from square (nexti [/], nextj[l ]). That is, for
each of the values of Z, examine each of the next squares
(nexti [Z] + ktmove 1[^], nexzy [Z ] + 2[A: ]) to see if it is an exit from
(nexti [I ], nextj [I ]), and count the number of such exits in exits [I ]. (Recall
that a square is an exit if it lies on the chessboard and has not been occupied
previously by the knight.) Finally, set min to the location of the minimum
value of exits. (If there is more than one occurrence of the minimum value,
let min denote the first such occurrence. Although this does not guarantee a
solution, the chances of completing the tour are very good.)
(g) [Move knight] Set i = nexti[mm], j = nextj [min], and [/][/] = m.

Thus, (/, j) denotes the new position of the knight, and board [/][/] records
the move in proper sequence.
(h) [Print] Print out the board showing the solution to the knight’s tour, and
then terminate the algorithm.
Write a C program that corresponds to the algorithm. This exercise was contri
buted by Legenhausen and Rebman.

02-Chap 02-ARRAYS AND STRUCTURES

Uploaded by

Copyright:

Available Formats

02-Chap 02-ARRAYS AND STRUCTURES

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

02-Chap 02-ARRAYS AND STRUCTURES

Uploaded by

Copyright:

Available Formats

CHAPTER 2

ARRAYS AND STRUCTURES

2.1 THE ARRAY AS AN ABSTRACT DATA TYPE

Structure 2.1: Abstract Data Type Array

Now let’s examine arrays in C. We restrict ourselves initially to one-dimensional

int list [5], *plist[5];

Variable Memory Address

In fact, when we write list[i] in a C program, C interprets it as a pointer to an integer

int one[] {0, 1, 2, 3 , 4} ;

#define MAX-SIZE 100

for (i 0; i < MAX-SIZE; i++)

answer sum(input, MAX—SIZE);

Program 2.1: Example array program

void printl(int *ptr, int rows)

Program 2.2: One-dimensional array accessed by address

Figure 2.1: One-dimensional array addressing

2.2 STRUCTURES AND UNIONS

a name that is a character array

typedef struct human—being { or typedef struct {

human—being personl, person2;

We might have a program segment that says:

While structures cannot be directly checked for equality or inequality, we can

int humans—equal(human—being personl,

Program 2.3: Function to check equality of structures

typedef struct human—being {

Continuing with our human-being example, it would be nice if we could distinguish

typedef struct sex—type {

We could assign values to person! and person2 as:

2.2.3 Internal Implementation of Structures

struct {int i,j; float a, b;};

2.2.4 Self-Referential Structures

A self-referential structure is one in which one or more of its components is a pointer to

typedef struct list {

list iteml/ item2, item3;

iteml.link &i tem2;

We will see more of this linking in Chapter 4.

Assign values to the fields for some person of type human-being.

2.3 THE POLYNOMIAL ABSTRACT DATA TYPE

• Days of the week: (Sunday, Monday, Tuesday, Wednesday, Thursday, Friday,

A (x) = + + 4 and B (x) = + lOx^ + 3x^ + 1

A (x) + B (x) = '^(ai + bi)x'

#define MAX—DEGREE 101 Max

Polynomial Zero() return the polynomial,

Structure 2.2: Abstract data type Polynomial

Program 2.4: Initial version of padd function

a . coef[1] = 0 < z <n

In this representation, we store the coefficients in order of decreasing exponents,

MAX—TERMS 100 size

starta finisha startb finishb avail

Figure 2.2: Array representation of two polynomials

void padd(int starta,int finisha,int startb, int finishb,

Program 2.5: Function to add two polynomials

void attach(float coefficient, int exponent)

Program 2.6: Function to add a new term

ttdefine MAX-TERMS 101 / *■ maximum number of terms + 1

2.4 THE SPARSE MATRIX ABSTRACT DATA TYPE

col 0 col 1 col 2 col 0 col 1 col 2 col 3 col 4 col 5

Figure 2.3; Two matrices

Sparse-Matrix Crcate(max-row, max-col) ::=

Structure 2.3: Abstract data type Sparse-Matrix

The internal representation of multidimensional arrays requires more complex address

1. Assume that we have a one-dimensional array, a[MAX-SlZE\. Normally, the sub

void strnins(char s, char t. int i)

int pmatch(char string, char