Module-3 Arrays and Strings RBT Level – 1, 2, 3 8 Hours

Arrays: Introduction to Arrays, Declaration and initialization of 1D and 2D arrays.

Searching and Sorting techniques – Linear Search, Binary Search and Bubble Sort.

Strings: Declaration and Initialization of Strings, String Handling Functions.

Textbook 1: Chapter 8.1 – 8.7, 11.1- 11.5

3.1 Introduction to Arrays

In the pervious module, we discussed the first derived data type, the function. In this module, we
discuss the second derived type, the array. Below figure shows the six derived types and the chapters
in which they are covered. Derived

Concepts
Imagine we have a problem that requires us to read, process, and print 10 integers. We must also keep
the integers in memory for the duration of the program. To begin, we can declare and define 10
variables, each with a different name, as shown in Figure.

Ten Variables Having 10 different names, however, creates a problem: How can we read 10 integers
from the keyboard and store them? To read 10 integers from the keyboard, we need 10 read
statements, each to a different variable. Furthermore, once we have them in memory, how can we
print them? To print them, we need 10 write statements. Although this approach may be acceptable
for 10 variables, it is definitely not acceptable for 100 or 1,000 or 10,000. To process large amounts of
data we need a powerful data structure, the array.
“An array is a collection of elements of the same data type.” Since an array is a sequenced collection,
we can refer to the elements in the array as the first element, the second element, and so forth until
we get to the last element. Thus, when we put the 10 integers of our problem into an array, the
address of the first element is 0 as Scores0, address of second element is Scores1, third is Scores2 and
the last one is Scoresn-1.

What we have seen is that the elements of the array are individually addressed through their
subscripts, a concept shown graphically in Figure. The array as a whole has a name, scores, but each
member can be accessed individually using its subscript. Rather than using subscripts, however, we
will place the subscript value in brackets. This format is known as indexing.

3.2 Using Arrays in C

We will first learn how to declare and define arrays. Following figure shows a typical array, named
scores, and its values.
C provides two different array types, fixed-length array and variable- length array. In a fixed-length
array, the size of the array is known when the program is written. In a variable-length array,
introduced in C99, the size of the array is not known until the program is run.

3.2.1 Declaration and Definition

An array must be declared and defined before it can be used. Array declaration and definition tell the
compiler the name of the array, the type of each element, and the size or number of elements in the
array. In a fixed-length array, the size of the array is a constant and must have a value at compilation
time. The declaration format is shown in the following example.

type arrayName [arraySize]

Below figure shows three different fixed-length array declarations:

one for integers, one for characters, and one for floating-point numbers.
The declaration format for a variable-length array is the same as for a fixed-length array except that
the array size is a variable. When the program is executed, the array size is determined and the array
is defined. Once defined, its size cannot be changed.

Note: Following standard C syntax rules, the array size must be declared and initialized before it is
used in the variable-length array definition.

float salessAry [arySize];

3.2.2 Accessing Elements in Arrays

C uses an index to access individual elements in an array. The index must be an integral value or an
expression that evaluates to an integral value. The simplest form for accessing an element is a numeric
constant.

For example, given the scores array in Figure 8-6, we could access the first element as shown in the
next example: scores [0] The index is an expression, typically the value of a variable. To process all the
elements in scores, a loop similar to the following code is used:

We could access the first element as shown below:

scores[0]

The index could also be an expression, typically the value of a variable. To process all the elements in
scores, a loop similar to the following code is used:

for (i=0; i < 10; i++)

process (scores[i]);

How does C know where an individual element is located in memory?

The answer is simple. The array's name is a symbolic reference for the address to the first byte of the
array. Whenever we use the array's name, therefore, we are actually referring to the first byte of the
array. The index represents an offset from the beginning of the array to the element being referenced.
With these two pieces of data, C can calculate the address of any element in the array using the
following simple formula:
element address =array address + (sizeof (element) index)

For example, assume that scores is stored in memory at location 10,000. If scores is an integer of type
int, the size of one element is the size of int. Assuming the size of an int is 4, the address of the element
at index 3 is element address

3.2.3 Storing Values in Arrays

Declaration and definition only reserve space for the elements in the array. No values are stored. If
we want to store values in the array, we must either initialize the elements, read values from the
keyboard, or assign values to each individual element.

Initialization
Just as with variables, initialization of the elements in a fixed-length array can be done when it is
defined. Variable-length arrays cannot be initialized when they are defined. For each element in the
array, we provide a value. The only difference is that the values must be enclosed in braces and, if
there is more than one, separated by commas.

It is a compile error to specify more values than there are elements in the array. Figure contains four
examples of array initialization.

The first example the below figure is a simple array declaration of five integers and is typical of the
way array initialization is coded. When the array is completely initialized, the programmer does not
need to specify the size of the array.

This case is seen in Figure(b). It is a good idea, however, to define the size explicitly, because it allows
the compiler to do some checking for errors and is also good documentation. If the number of values
provided is fewer than the number of elements in the array, the unassigned elements are filled with
zeros.

This case is seen in Figure (c). We can use this rule to easily initialize an array to all zeros by supplying
just the first zero value, as shown in the last example in Figure(d).
Inputting Values
Another way to fill the array is to read the values from the keyboard or a file. This method of inputting
values can be done using a loop. When the array is to be completely filled, the most appropriate loop
is the for loop because the number of elements is fixed and known.

for (i 0; i<10; i++)

scanf ("%d", &scores [i]);

Several concepts need to be studied in this simple statement.

First, we start the index, i, at 0. Since the array has 9 elements, we must load the values from index
locations 0 through 8.

The limit test, therefore, is set at i < 9, which conveniently is the number of elements in the array.
Then, even though we are dealing with array elements, the address operator (&) is still necessary in
the scanf call.

Assigning Values
We can assign values to individual elements using the assignment operator. A simple assignment
statement for scores is seen below.

scores [4]= 23;

Note: we cannot assign one array to another array, even if they match fully in type and size.

We have to copy arrays at the individual element level. For example, to copy an array of 25 integers
to a second array of 25 integers, we could use a loop, as shown below.

for ( i = 0 ; i < 25 i++)

second[i] = first[i];

If the values of an array follow a pattern, we can use a loop to assign values. For example, the following
loop assigns a value that is twice the index number to array scores:

for ( i = 0 i < 10 ;i++)

scores [i] = i * 2i

For another example, the following code assigns the odd numbers 1 through 17 to the elements of an
array named value:

for (i=0; i < 9; i++)

value [i]= (i * 2) +1

Printing Values
Another common application is printing the contents of an array. This is easily done with a for loop,
as shown below.

for (i 0; 19; i++)

printf ("%d", scores [i]);

printf ("\n");

In this example, all the data are printed on one line. After the for loop completes, a final printf
statement advances to the next line. But what if we had 100 values to be printed? In that case, we
couldn't put them all on one line. Given a relatively small number width, however, we could put 10 on
a line. We would then need 10 lines to print all the data. This rather common situation is easily handled
by adding a counter to track the number of elements we have printed on one line. This logic is shown
in the following program.

3.3 Inter-function Communication

To process arrays in a large program, we have to be able to pass them to functions. We can pass arrays
in two ways: pass individual elements or pass the whole array.

3.3.1 Passing Individual Elements

We can pass individual elements by either passing their data values or by passing their addresses.

Passing Data Values

We pass data values, that is individual array elements, just like we pass any data value. As long as the
array element type matches the function parameter type, it can be passed. The called function cannot
tell whether the value it receives comes from an array, a variable, or an expression. Following figure
demonstrates how an array value and a variable value can be passed to the same function.
Passing Addresses
We can pass the address of an individual element in an array just like we can pass the address of any
variable. To pass an array element's address, we prefix the address operator to the element's indexed
reference. Thus, to pass the address of ary [3], we use the code shown in the following example.

&ary [3]

Passing an address of an array element requires two changes in the called function. First, it must
declare that it is receiving an address. Second, it must use the indirection operator (->) to refer to the
elements value. These concepts are shown in figure. Note that when we pass an address, it is two-
way communication.

3.3.2 Passing the Whole Array

Here we see the first situation in which C does not pass values to a function. The reason for this change
is that a lot of memory and time would be used in passing large arrays every time we wanted to use
one in a function. For example, if an array containing 20,000 elements were passed by value to a
function, another 20,000 elements would have to be allocated in the called function and each element
would have to be copied from one array to the other. So, instead of passing the whole array, C passes
the address of the array. In C, the name of an array is a primary expression whose value is the address
of the first element in the array. Since indexed references are simply calculated addresses, all we need
to refer to any of the elements in the array is the address of the array. Because the name of the array
is in fact its address, passing the array name, as opposed to a single element, allows the called function
to refer to the array back in the calling function. The design for passing the whole array is shown in
following figure.

Fixed-length Arrays
To pass the whole array, we simply use the array name as the actual parameter. In the called function,
we declare that the corresponding formal parameter is an array. We do not need to specify the
number of elements in a fixed- length array. Since the array is actually defined elsewhere, all that is
important is that the compiler knows it's an array.

The function declaration for an array can declare the array in two ways.

First, it can use an array declaration with an empty set of brackets in the parameter list.

Second, it can specify that the array parameter is a pointer.

We prefer the array declaration over the pointer declaration because it is clearer. Both are shown in
the following example, which declares arrays of integers.

// Function Declarations

void fun (int ary(),...);

void fun (int ary, ...);

Variable-length Arrays
When the called function receives a variable-length array, we must declare and define it as variable
length. In a function declaration, we declare an array as variable using an asterisk for the array size or
by using a variable for the array size. In the function definition, we must use the variable name, and
following standard syntax rules, it must be defined before the array. The following example
demonstrates these points.
// Function Declaration

float calcArrayAvg (int size, float avgArray [*]);

……….

// Function Definition

float calcArrayAvg (int size, float avgArray [size])

----------

} // calcArrayAvg

Note, however, that the array passed to a function declaring a variable length array can be either a
fixed-length or variable-length array. As long as the array types are correct and the correct size is
specified, the passed array can be processed.

In summary, we must observe the following rules to pass the whole array to a function:

1. The function must be called passing only the name of the array

2. In the function definition, the formal parameter must be an array type, either fixed length or
variable length.

3. The size of a fixed-length array does not need to be specified.

4. The size of a variable-length array in the function prototype must be an asterisk or a variable.

3.3.3 Passing an Array as a Constant

When a function receives an array and doesn't change it, the array should be received as a constant
array. This prevents the function from accidentally changing the array. To declare an array a constant,
we prefix its type with the type qualifier const, as shown in the following function definition. Once an
array is declared constant, the complier will flag any statement that tries to change it as an error.

double average (const int ary[], int size);

Function Communication Examples

Average Array Elements

We can use a function to calculate the average of the integers in an array. In this case, we pass the
name of the array to the function and it returns the average as a real number. This concept is shown
in Program.
3.4 Two-Dimensional Arrays
The arrays we have discussed so far are known as one-dimensional arrays because the data are
organized linearly in only one direction. Many applications require that data be stored in more than
one dimension. One common example is a table, which is an array that consists of rows and columns.
Figure shows a table, which is commonly called a two- dimensional array.

Although a two-dimensional array is exactly what is shown by above figure, C looks at it in a different
way. It looks at the two-dimensional array as an array of arrays. In other words, a two-dimensional
array in C is an array of one-dimensional arrays. This concept is shown as follows:

3.4.1 Declaration
Two-dimensional arrays, like one-dimensional arrays, must be declared before being used.
Declaration tells the compiler the name of the array, the type of each element, and the size
of each dimension. Two-dimensional arrays can be either fixed length or variable length.
As we saw with the one-dimensional array, the size of a fixed-length array is a constant and
must have a value at compilation time. For example, the array shown in above figure can be
declared and defined as follows:
int table[5][4];
By convention, the first dimension specifies the number of rows in the array. The second
dimension specifies the number of columns in each row. The rules for variable-length arrays
follow the same concepts. To define a variable-length array, we would use the following
statement.
int table5x4 [rows] [cols];
Remember, however, that the dimensions must be set before the declaration or a compiler
error occurs.

3.4.2 Initialization
As we noted before, the definition of a fixed-length array only reserves memory for the
elements in the array. No values will be stored. If we don't initialize the array, the contents
are unpredictable. Generally speaking, fixed-length arrays should be initialized. Initialization
of array elements can be done when the array is defined. As previously noted, variable-length
arrays may not be initialized when they are defined. As with one-dimensional arrays, the
values must be enclosed in braces. This time, however, there is a set of data for each
dimension in the array. So, for table, we will need 20 values. One way to initialize it is shown
below.

Another way is as follows:

When we discussed one-dimensional arrays, we said that if the array is completely initialized
with supplied values, we do not need to specify the size of the array. This concept carries
forward to multidimensional arrays, except that only the first dimension can be omitted. All
others must be specified. The format is shown below.

To initialize the whole array to zeros, we need only specify the first value. as shown below.
int table [5][4] (0);

3.4.3 Inputting Values

Another way to fill up the values is to read them from the keyboard. For a two-dimensional
array, this usually requires nested for loops. If the array is an n by m array, the first loop varies
the row from zero to n-1. The second loop varies the column from zero to m-1. The code to
fill the array in Figure is shown below.
for (row 0; row < 5; row++)
for (column 0; column < 4; column++)
scanf ("id", &table [row][column]);
When the program runs, we enter the 20 values for the elements and they are stored in the
appropriate locations.

3.4.4 Outputting Values

We can also print the value of the elements one by one, using two nested loops. Again, the
first loop controls the printing of the rows and the second loop controls the printing of the
columns. To print the table in its table format, a newline is printed at the end of each row.
The code to print is shown below.
for (row 0; row < 5; row++)
{
for (column 0; column < 4; column++)
printf("%d", table [row] [column]);
printf("\n");
} // for

3.4.5 Accessing Values

Individual elements can be initialized using the assignment operator.
table[2][0] = 23;
table[0][1]=table[3][2] + 15:
Let's assume that we want to initialize our 5 x 4 array as shown below.

One way to do this would be to code the values by hand. However, it is much more interesting
to examine the pattern and then assign values to the elements in the array using an algorithm.
What pattern do you see? One is that the value in each element increases by one from its
predecessor in the row. Another is that the first element in each row is the row index times
10. With these two patterns, we should be able to write nested loops to fill the array. The
code to initialize the patterns for the array is shown in Program.
3.4.6 Memory Layout
As discussed earlier, the indexes in the definition of a two-dimensional array represent rows
and columns. This format maps to the way the data are laid out in memory. If we were to

consider memory as a row of bytes with the lowest address on the left and the highest address
on the right, then an array would be placed in memory with the first element to the left and
the last element to the right. Similarly, if the array is a two-dimensional array, then the first
dimension is a row of elements that are stored to the left. This is known "row-major" storage
and is seen in Figure.

3.4.7 Passing A Two-Dimensional Array to functions

With two-dimensional arrays, we have three choices for passing parts of the array to a
function.
(1) We can pass individual elements.
(2) We can pass a row of the array. This is similar to passing an array, as we saw in "Passing
the Whole Array
(3) Finally, we can pass the whole array.
Passing A Row
Passing a row of the array is rather interesting. We pass a whole row by indexing the array
name with only the row number.
For the above array, when we pass the first row, the receiving function receives a one-
dimensional array of four integers. The for loop in print square prints the square of each of
the four elements. After printing all the values, the function advances to the next line on the
console. and returns. The for loop in main calls print square five times so that the final result
is a table of the values squared shown on the monitor.

Passing the Whole Array

When we pass a two-dimensional array to a function, we use the array name as the actual
parameter just as we did with one-dimensional arrays. The formal parameter in the called
function header, however, must indicate that the array has two dimensions. This is done by
including two sets of brackets, one for each dimension, as shown below.
double average (int table[][MAX_COLS])
Note that again we do not need to specify the number of rows in a fixed- length array. It is
necessary, however, to specify the size of the second dimension. Thus, we specified the
number of columns in the second dimension (MAX COLS).
In summary, to pass two-dimensional arrays to functions:
1. The function must be called by passing only the array name.
2. In the function definition, the formal parameter is a two-dimensional array, with the size
of the second dimension required for a fixed-length array.
3. In the function definition for a variable-length array, the size of all dimensions must be
specified.
For example, we can use a function to calculate the average of the integers in an array. In this
case, we pass the name of the array to the function as seen in Figure.

➢ Write a program that fills the left-to-right diagonal of a square matrix (a two-
dimensional array with an equal number of rows and columns) with zeros, the lower
left triangle with Is, and the upper right triangle with +15. The output of the program,
assuming a six-by-six matrix is shown in following figure.
3.5 Searching and Sorting techniques

Searching and sorting are the two important applications of arrays.

Searching refers to a technique that helps us search a data element out of the given string or
array.
Sorting refers to the technique used for rearranging the data elements present in a string or
an array in any specified order, descending or ascending.

3.5.1 Searching
Searching is the process used to find the location of a target among a list of objects. In the
case of an array, searching means that given a value, we want to find the location (index) of
the first element in the array that contains that value. The search concept is shown in
following figure.

The algorithm used to search a list depends to a large extent on the structure of the list.
Since our structure is currently limited to arrays, we will study searches that work with
arrays.
There are two basic searches for arrays:
➢ Sequential search
➢ Binary search
[Link] Sequential Search
The sequential search is used whenever the list is not ordered. Generally, we use the technique only
for small lists or lists that are not searched often.

We start searching for the target from the beginning of the list, and we continue until we find the
target or until we are sure that it is not in the list. This gives us two possibilities; either we find it or
we reach the end of the list.

Following figure traces the steps to find the value 62.

We first check the data at index 0, then 1, 2, and 3 before finding the 62 in the fifth element (index 4).
But what if the target is not in the list? Then we have to examine each element until we reach the end
of the list. Following figure traces the search for a target of 72. When we detect the end of the list, we
know that the target does not exist.

Let's write the sequential search function. A search function needs to tell the calling function two
things: Did it find the data was looking for? If it did, what is the index at which the data were found?
But a function can return only one value. For search functions, we use the return value to designate
whether we found the target or not. To "return" the index location where the data were found, we
will use call-by-address. The search function requires four parameters: the list we are searching, the
index to the last element in the list, the target, and the address where the found element's index
location will be stored. Although we could write it without passing the index to the last element, that
would mean the search would have to know how many elements are in the list. To make the function
as flexible as possible, therefore, we pass the index of the last data value in the array. This is also a

good structured design technique. With this information, we are now ready to create the design. It is
shown in Figure.
Function for linear/sequential search is as follows:

[Link] Binary Search

The sequential search algorithm is very slow. If we have an array of 1 million elements, we
must do 1 million comparisons in the worst case.
If the array is not sorted, this is the only solution. But if the array is sorted, we can use a more
efficient algorithm called the binary search. Generally speaking, we should use a binary search
whenever the list starts to become large. The definition of large is vague. We suggest that you
consider binary searches when- ever the list contains more than 50 elements. The binary
search starts by testing the data in the element at the middle of the array. This determines if
the target is in the first half or the second half of the list. If it is in the first half, we do not need
to check the second half. If it is in the second half, we don't need to test the first half. In other
words, either way we eliminate half the list from further consideration. We repeat this
process until we find the target or satisfy ourselves that it is not in the list. To find the middle
of the list, we need three variables, one to identify the beginning of the list, one to identify
the middle of the list, and one to identify the end of the list.
We will analyze two cases:
the target is in the list, and
the target is not in the list.
Target Found
Following figure shows how we find 22 in a sorted array. We descriptively call our three
indexes first, mid, and last. Given first as 0 and last as 11, we can calculate mid as follows:
mid (first last) / 2;
Since the index mid is an integer, the result will be the integral value of the quotient; that is,
it truncates rather than rounds the calculation.
Given the data in figure, mid becomes 5 as a result of the first calculation
At index location 5, we discover that the target is greater than the list value (22>21).
We can therefore eliminate the array locations 0 through 5. (Note that mid is automatically
eliminated.)
To narrow our search, we assign mid+1 to first and repeat the search.
The next loop calculates mid with the new value for first and determines that the midpoint is
now 8.
mid (6+11)/2 = 17/2 = 8
Again we test the target to the value at mid, and this time we discover that the target is less
than the list value (22<62). This time we adjust the ends of the list by setting last to mid -1
and recalculate mid. This eliminates elements 8 through 11 from consideration. We have now
arrived at index location 6, whose value matches our target. This stops the search. Figure
traces the logic we have just described.
Target Not Found
A more interesting case occurs when the target is not in the list. We must construct our search
algorithm so that it stops when we have checked all possible locations. This is done in the
binary search by testing for first and last crossing, that is, we are done when first becomes
greater than last.
Thus, only two conditions terminate the binary search algorithm:
1. Either the target is found or
2. first becomes larger than last.
For example, imagine we want to find 11 in our binary search array. This situation is shown
in figure. In this example, the loop continues to narrow the range as we saw in the
successful search, until we are examining the data at index locations 3 and 4. These
settings of first and last set the mid index to 3.

The test at index location 3 indicates that the target is greater than the list value, so we set
first to mid + 1 or 4. We now test the data at location 4 and discover that 11 < 14.
At this point, we have discovered that the target should be between two adjacent values; in
other words, it is not in the list. We see this algorithmically because last is set to mid1, which
makes first greater than last, the signal that the value we are looking for is not in the list.

Once we fully understand the logic, we can design the program. Figure contains the design in
the form of a flowchart.
Following program contains the implementation of the binary search algorithm we have been
describing. It is constructed along the same design we saw for the sequential search. The first
three parameters describe the list and the target we are looking for, and the last parameter
contains the address into which we place the located index. One point worth noting: When
we terminate the loop with a not-found condition, the index returned is unpredictable it may
indicate the node greater than or less than the value in target.
3.5.2 Sorting
Sorting is a process in which items are arranged systematically.
Sorting refers to ordering data in an increasing or decreasing manner according to some linear
relationship among the data items.
One of the most common applications in computer science is sorting---the process through
which data are arranged according to their values. We are surrounded by data. If the data are
not ordered, we would spend hours trying to find a single piece of information.
Imagine the difficulty of finding some one's telephone number in a telephone book that is
not ordered in name sequence!
Many sorting algorithms are available like bubble sort, insertion sort, selection sort, quick
sort, merge sort so on.
Let us learn about the bubble sort which is a basic sorting technique.
[Link] Bubble Sort
In the bubble sort, the list is divided into two sublists, sorted and unsorted. The smallest
element is bubbled from the unsorted sublist and moved to the sorted sublist. After moving
the smallest element to the sorted list, the wall moves one element ahead, increasing the
number of sorted elements and decreasing the number of unsorted ones. Each time an
element moves from the unsorted sublist to the sorted sublist, one sort pass is completed.
Given a list of n elements, the bubble sort requires up to n-1 passes to sort the data. The
bubble concept is seen in Figure which shows how the wall moves one element in each pass.

Looking at the first pass, we start with 56 and compare it to 32. Since 56 is not less than 32, it
is not moved and we step down one element. No exchanges take place until we compare 45
to 8. Since 8 is less than 45, the two elements are exchanged and we step down 1 element.
Because 8 was moved down, it is now compared to 78 and these two elements are exchanged.
Finally, 8 is compared to 23 and exchanged. This series of exchanges places 8 in the first
location and the wall is moved up one position.
Program for Bubble sort:
Module 3 - Strings

11.1 String Concepts

In general, a string is a series of characters treated as a unit. Computer sei ence has long recognized
the importance of strings, but it has not adapted a standard for their implementation. We find,
therefore, that a string created in Pascal differs from a string created in C.

Virtually all string implementations treat a string as a variable-length piece of data. Consider, for
example, one of the most common of all strings, a name. Names, by their very nature, vary in length.
It makes no difference if we are looking at the name of a person, a textbook, or an automobile.

Given that we have data that can vary in size, how do we accommodate them in our programs? We
can store them in fixed-length objects, or we can store them in variable-length objects. This
breakdown of strings is seen in Figure 11-1

Fixed-Length Strings

When implementing a fixed-length string format, the first decision is the size of the variable. If we
make it too small, we can't store all the data. If we make it too big, we waste memory.

Another problem associated with storing variable data in a fixed-length data structure is how to tell
the data from the nondata. A common solution is to add nondata characters, such as spaces, at the
end of the data. Of course, this means that the character selected to represent the nondata value
cannot be used as data.
Variable-Length Strings

A much preferred solution is to create a structure that can expand and contract to accommodate the
data. Thus, to store a person's name that consists of only one letter, we would provide only enough
storage for one character

To store a person's name that consists of 30 characters, the structure would be expanded to provide
storage for 30 characters.

This flexibility does not come without a cost, however. There must be some way to tell when we get
to the end of the data. Two common techniques are to use length-controlled strings and delimited
strings.

Length-Controlled Strings

Length-controlled strings add a count that specifies the number of charac- ters in the string. This
count is then used by the string manipulation functions to determine the actual length of the data.

Delimited Strings

Another technique used to identify the end of the string is the delimiter at the ends of delimited
strings. You are already familiar with the concept of delimiters, although you probably don't
recognize them as such. In English, each sentence, which is a variable-length string, ends with a
delimiter, the period. Commas, semicolons, colons, and dashes are other common delimit- ers found
in English.

The major disadvantage of the delimiter is that it eliminates one charac- ter from being used for
data. The most common delimiter is the ASCII null character, which is the first character in the ASCII
character sequence (10). This is the technique used by C.

Figure 11-2 shows length-controlled and delimited strings in memory.

11.2 C Strings

AC string is a variable-length array of characters that is delimited by the null character. Generally,
string characters are selected only from the printable character set. Nothing in C, however, prevents
any character, other than the null delimiter, from being used in a string. In fact, it is quite common
to use formatting characters, such as tabs, in strings.

C uses variable-length, delimited strings

Storing Strings

In C, a string is stored in an array of characters. It is terminated by the null character (10'). Figure 11-
3 shows how a string is stored in memory. What precedes the string and what follows it is not
important. What is important is that the string is stored in an array of characters that ends with a
null delimiter. Because a string is stored in an array, the name of the string is a pointer to the
beginning of the string.

Figure 11-4 shows the difference between a character stored in memory and a one-character string
stored in memory. The character requires only one memory location. The one-character string
requires two memory locations one for the data and one for the delimiter. The figure also shows
how an empty string is stored. Empty strings require only the end-of-string market
The String Delimiter

At this point, you may be wondering, "Why do we need a null character at the end of a string?" The
answer is that a string is not a data type but a data structure. This means that its implementation is
logical, not physical. The physical structure is the array in which the string is stored. Since the string,
by its definition, is a variable-length structure, we need to identify the logical end of the data within
the physical structure.

Looking at it another way, if the data are not variable in length, then we don't need the string data
structure to store them. They are easily stored in an array, and the end of the data is always the last
element in the array. But, if the data length is variable, then we need some other way to determine
the end of the data.

The null character is used as an end-of-string marker. It is the sentinel used by the standard string
functions. In other words, the null character at the end lets us treat the string as a sequence of
objects (characters) with a defined object at the end that can be used as a sentinel. Figure 11-5
shows the difference between an array of characters and a string.

Because strings are variable-length structures, we must provide enough room for the maximum-
length string we will have to store, plus one for the delimiter. It is possible that the structure will not
be filled, so we can have an array with the null character in the middle. In this case, we treat the part
of the array from the beginning to the null character as the string and ignore the rest. In other
words, any part of an array of characters can be treated as a string as long as the string ends in a null
characters. This is shown in Figure 11-6.
String Literals

A string literal-or as it is also known, string constant-is a sequence of char- acters enclosed in double
quotes. For example, each of the following is a string literal:

"C is a high-level language."

"Hello"

"abcd"

When string literals are used in a program, C automatically creates an array of characters, initializes
it to a null-delimited string, and stores it. remembering its address. It does all this because we use
the double quotes that immediately identify the data as a string value

Strings and Characters

When all we need to store is a single character, we have two options: We can store the data as a
character literal or as a string literal. To store it as a char acter literal, we use single quote marks. To
store it as a string literal, we use double quote marks. Although the difference when we code the
literal is only a shift-key operation on most keyboards, the difference in memory is great. The
character occupies a single memory location. The data portion of the string also occupies a single
memory location, but there is an extra memory location required for the delimiter.
The differences in the ways we manipulate the data are even greater. For example, moving a
character from one location to another requires only an assignment. Moving a string requires a
function call. It is important, therefore, that you clearly understand the differences. Figure 11-7
shows examples of both character literals and string literals

Another important difference between a string and a character is how we represent the absence of
data. Technically, there is no such thing as an empty character. Logically, we often specify that a
space() or a null character (*\0') represents the absence of data. Since the character exists in all
cases, however, both of these concepts require that we program for the interpreta tion of no data.

A string, on the other hand, can be empty. That is, since it is a variable length structure, a string can
exist with no data in it. A string that contains no data consists of only a delimiter. This concept is
specified in the definition of a string and is programmed into all the string-handling functions. We
can, therefore, move or compare an empty string without knowing that we are dealing with no data.
An example of a null string is also shown in Figure 112

Referencing String Literals

A string literal is stored in memory: Just like any object stored in memory has an address. Thus, we
can refer to a string literal by using pointers. Let's first examine addressing a string literal. The literal,
since it is an array of characters, is itself a pointer constant to the first element of the string
Generally, when we use it, we are referring to the entire steing th possible, however, to refer to only
one of the characters in the string, a

shown in Figure 11-8.

Declaring Strings

As we said, C has no string type. To declare a string, therefore, we must use one of the other
available structures. Since strings are a sequence of characters, it is only natural that the structure
used to store string variables is the character array In defining the array to store a string, we must
provide enough room for the data and the delimiter. The storage structure, therefore, must be one
byte larger than the maximum data size. A string declaration for an eight-character string, including
its delimiter, is shown below.

char str[9];

As we have seen, string declaration defines memory for a string when it is declared as an array in
local memory (the stack). However, we can also declare a string as a pointer. When we declare the
pointer, however, memory is allocated only for the pointer; no memory is allocated for the string
itself. In this case, we must allocate memory for the string either dynamically or using a string literal.
Figure 11-9 demonstrates two different ways to declare and define a string. Let's examine each
carefully. In the first case (Figure 11-9a), memory is allocated for future characters. The name of the
string is a pointer constant. We don't need to worry about allocating memory because the declara-
tion is for an array and memory allocation is automatic. We can read data into the string and change
data in the string as necessary

The second case (Figure 11-96) allocates memory for a pointer varia In this case, however, no
memory is allocated for the string itself. Before we can use the string in any way we need to allocate
memory for it. Any attempt to use the string before memory is allocated is a logic error that may
destroy memory contents and cause our program to fail

Initializing Strings
We can initialize a string the same way that we initialize any storage structure by assigning a value to
it when it is defined. In this case, the value is a string literal. For example, to assign "Good Day" to a
string, we would code

char str[9] = "Good Day";

Since a string is stored in an array of characters, we do not need to indi cate the size of the array if
we initialize it when it is defined. For instance, we could define a string to store the month January,
as shown below.

char month[ ]= "January";

In this case, the compiler will create an array of 8 bytes and initialize it with January and a null
character. We must be careful, however, because month is an array. If we now tried to store
"December" in it, we would overrun the array and destroy whatever came after the array. This
example points out one of the dangers of strings: We must make them large enough to boll the
longest value we will place in the variable.

C provides two more ways to initialize strings. A common method is to assign a string literal to a
character pointer, as shown below. This creates a string for the literal and then stores its address in
the string pointer variable, pStr. To clearly see the structure, refer to Figure 11-10.

char* pStr = "Good Day”;

We can also initialize a string as an array of characters. This method is not used too often because it
is so tedious to code. Note that in this example. we must ensure that the null character is at the end
of the string.

char str[9] = { ‘G’, ‘o’,’o’,’d’, ‘ ‘, ‘D’,’a’,’y’,’\0’};

The structures created by these three examples are shown in Figure 11-10
Strings and the Assignment Operator

Since the string is an array, the name of the string is a pointer constant. As a pointer constant, it is an
rvalue and therefore cannot be used as the left oper and of the assignment operator. This is one of
the most common errors in writing a C program; fortunately, it is a compile error, so it cannot affect
our program

Although we could write a loop to assign characters individually, there is a better way. C provides a
rich library of functions to manipulate strings, including moving one string to another. We discuss
this library in the section "String Manipulation Functions."

Reading and Writing Strings

A string can be read and written. C provides several string functions for input and output. We discuss
them in the following section, "String Input/Output Functions

Formatted String Input/Output

In this section, we cover the string-related portions of the formatted input and output functions.
Formatted String Input: scanf/fscanf

We have already discussed the basic operations of the format input functions (see Chapter 7).
However, two conversion codes pertain uniquely to strings, and we discuss them here.

The String Conversion Specification

We read strings using the read-formatted function (scanf). The conversion code for a string is "s."
The scanf functions then do all the work for us. Fint, they skip any leading whitespace. Once they
find a character, they read until they find whitespace, putting each character in the array in order.
When they find a trailing whitespace character, they end the string with a null character The
whitespace character is left in the input stream. To delete the whitespace from the input stream, we
use a space in the format string before the nest conversion code or FLUSH the input stream,
whichever is more appropriate. The conversion specification strings can use only three options field.
flag, maximum field size, and size

need to worry about is to make sure that the array is large enough to store all the data. If it isn't,
then we destroy whatever follows the array in memory Therefore, we must make sure we don't
exceed the length of the data. Assum- ing that month has been defined as
char month [10];

we can protect against the user entering too much data by using a width in the field specification.
(Recall that the width specifies the maximum number of characters to be read.) The modified scanf
statement is shown below.

scanf("%9s", month);

Note that we set the maximum number of characters at nine while the array size is ten. This is
because scanf will read up to nine characters and then insert the null character. Now, if the user
accidentally enters more than nine characters, the extra characters will be left in the input stream.
But this can cause a problem. Assuming that the data are being entered as a separate line-that is,
that there is only one piece of data on the line-we use the preprocessor-defined statement, PLUSH-
see Chapter 7, to eliminate any extra characters that were entered. This function also flushes the
newline that is left in the input stream by scanf when the user correctly enters data. The complete
block of code to read a month is shown in Program 11-1.

The Scan Set Conversion Code (...)

In addition to the string conversion code, we can also use a scan set conver sion code to read a
string. The scan set conversion specification consists of the open bracket (1), followed by the edit
characters, and terminated by the close bracket (1). The characters in the scan set identify the valid
characters, known as the scan set, that are to be allowed in the string. All characters except the close
bracket can be included in the set.

Edited conversion reads the input stream as a string. Each character read by scanf/fscanf is
compared against the scan set. If the character just read is in the scan set, it is placed in the string
and the scan continues. The first character that does not match the scan set stops the road. The
nonmatching character remains in the input stream for the next read operation. If the fire character
read is not in the scan set, the scanf/fscanf terminates and a nulll string is returned.
A major difference between the scan set and the string conversion codes is that the scan set does
not skip leading whitespace. Leading whitespace is either put into the string being read when the
scan set contains the corresponding whitespace character, or stops the conversion when it is not.

In addition to reading a character that is not in the scan set, there are two other terminating
conditions. First, the read will stop if an end-of-file is detected. Second, the read will stop if a field
width specification is included and the maximum number of characters has been read.

For example, let's assume we have an application that requires we read a string containing only
digits, commas, periods, the minus sign, and a dollar sign; in other words, we want to read a dollar
value as a string. No other characters are allowed. Let's also assume that the maximum number of
characters in the resulting string is 10. The format string for this operation would be

scanf("%10[0123456789.,-$]", str);

Sometimes it is easier to specify what is not to be included in the scan set rather than what is valid.
For instance, suppose that we want to read a whole line. We can do this by stating that all characters
except the newline (\n) are valid. To specify invalid characters, we start the scan set with the caret
(*) symbol. The caret is the negation symbol and in effect says that the following characters are not
allowed in the string. (If you know UNIX, this should sound familiar.) To read a line, we would code
the scanf as shown below.

scanf("%81[^\n]", line);

In this example, scanf reads until it finds the newline and then stops. Note that we have again set
the width of the data to prevent our string, line, from being overrun. We would never use this code,
however. As we see in the next section, an intrinsic string function does it for us.

For the last example, let's read a 15-character string that can have any character except the special
characters on the top of the keyboard. In this case, we again specify what is not valid. This
conversion code is shown in the following example.

scanf("%15[^~!@#$%^&*()_+]", str);
String Input/Output
In addition to the formatted string functions, C has two sets of string fune- tions that read and write
strings without reformatting any data. These func- tions convert text-file lines to strings and strings
to text-file lines. A line consists of a string of characters terminated by a newline character.

C provides two parallel sets of functions, one for characters and one for wide characters. They are
virtually identical except for the type. Because wide characters are not commonly used and because
the functions operate identi- cally, we limit our discussion to the character type. The wide-character
func- tions are listed in Appendix F.

Line to String

The gets and fgets functions take a line (terminated by a newline) from the input stream and make a
null-terminated string out of it. They are therefore sometimes called line-to-string input functions.

The function declarations for get string are shown below.

Figure 11-11 shows the concept. As you can see, gets and fgets do not work the same. The gets
function converts the return (newline character) to the end-of-string character (10), while fgets puts
it in the string and appends an end-of-string delimiter.
String to Line
The puts/fputs functions take a null-terminated string from memory and write it to a file or the
keyboard. Thus, they are sometimes called string-to-line out- put functions.

Figure 11-12 shows how these functions work. All change the string to a line. The null character is
replaced with a newline in puts; it is dropped in fputs. Because puts is writing to the standard output
unit, usually a display, this is entirely logical. On the other hand, fputs is assumed to be writing to a
file where newlines are not necessarily required. It is the programmer's responsibility to make sure
the newline is present at the appropriate place.

Note how the newline is handled in these functions. Then compare their use of the newline to the
gets and fgets functions. While the output functions treat the newline the opposite of the input
functions, they are compatible. As long as we are reading from a file and writing to a file, the
newlines will be handled automatically. Care must be taken, however, when we read from the
keyboard and write to a file.

The declarations for these functions are shown below.

int puts (const char* strPtr);

int fputs (const char* strPtr, FILE* sp);

The string pointed to by strPtr is written to the indicated file as explained above. If the write is
successful, it returns a non-negative integer; if any transmission errors occur, it returns EOF. Note
that the absence of a null character to terminate the string is not an error; however, it will most
likely cause your program to fail.
11.4 Arrays of Strings

When we discussed arrays of pointers in Chapter 10, we introduced the concept of a ragged array.
Ragged arrays are very common with strings. Consider, for example, the need to store the days of
the week in their textual format. We could create a two-dimensional array of seven days by ten
characters (Wednesday requires nine characters), but this wastes space. It is much easier and more
efficient to create a ragged array using an array of string pointers. Each pointer points to a day of the
week. In this way each string is independent, but at the same time, they are grouped together
and that the calculation needs to be done only once, but we can't be sure that such eff cient code
would in fact be generated.) Therefore, we calculate the ending address just ance, before the while
loop, and then we can be sure that the limit test will be efficient.
Study this code carefully. Note first that pWalker is a pointer to a pointer to a character. Then notice
how it is used in the for statement. It is initialized to the first ele ment in pDays, then it is
incremented until it is no longer less than or equal to plast Finally, note how it is used in the printf
statement. The printf syntax requires that the variable list contain the address of the string to be
printed. But pWalker is a pointer to an address that in turn points to the string (a pointer to a
pointer). Therefore, when we dereference pWalker, we get the pointer to the string, which is what
printf requires. This example is diagrammed in Figure 11-13

11.5 String Manipulation Functions

Because a string is not a standard type, we cannot use it directly with mos C operators. For example,
to move one string to another, we must move the individual elements of the sending string to the
receiving string. We cannot simply assign one string to another. If we were to write the move, we
would have to put it in a loop.

C has provided a rich set of string functions. Besides making it easier for us to write programs,
putting the string operations in functions provides the opportunity to make them more efficient
when the operation is supported by hardware instructions. For example, computers often have a
machine instruction that moves characters until a token, such as a null character, is reached. When
this instruction is available, it allows a string to be moved in one instruction rather than in a loop.

In addition to the string character functions, C provides a parallel set of functions for wide
characters. They are virtually identical except for the type Because wide characters are not
commonly used and because the functions operate identically, we limit our discussion to the
character type. The wide character functions are listed in Appendix F. The traditional string functions
have a prefix of str. The basic format is shown in the following:
String Copy

C has two string copy functions. The first, strcpy, copies the contents of one string to another. The
second, strncpy, also copies the contents of one string to another, but it sets a maximum number of
characters that can be moved. Therefore, strncpy, is a safer function.

Basic String Copy

The string copy function, strcpy, copies the contents of the from string including the null character, to
the string. Its function declaration is shown below.

char* strcpy (char* toStr, const char* fromStr);

If fromStr is longer than toStr, the data in memory after toStr are destroyed. It is our responsibility to
ensure that the destination string array is large enough to hold the sending string. This should not be
a problem, since we control the definition of both string variables. The address of toStr is returned,
which allows string functions to be used as arguments inside other string functions. We will
demonstrate the use of these returned pointers later in the chapter.
Figure 11-14 shows two examples of string copy. In the first example, the source string is shorter than
the destination variable. The result is that, after the string has been copied, the contents of the last
three bytes of al are unchanged; s1 is a valid string, however.
moved. If the from string is smaller than size, the entire string is copied and then null characters are
inserted into the destination string until exactly size characters have been copied. Thus, it is more
correct to think of size as the destination characters that must be filled.

If the sending string is longer than size, the copy stops after size bytes have been copied. In this case,
the destination variable may not be a valid string; that is, it may not have a delimiter. The string
number copy functions do not insert a delimiter if the from string is longer than size. On the other
hand, the data following the destination variable will be intact, assuming the size was properly
specified. Figure 11-15 shows the operation of strncpy under these two conditions.

We recommend that you always use strncpy; do not use strcpy. To prevent invalid strings, we also
recommend that you move one fewer character than the maximum and then automatically place a
null character in the last position. The code for this technique is shown below.

strncpy(s1, s2, sizeof(sl) -1);

*(s1 + (sizeof (s1) - 1)) = ‘\0’;

Since the strncpy places null characters in all unfilled characters, guaranteed that the last character
in the string array is a null character. If it is we are not, then the copy was short. By executing the
above statements, we are assured that i will be a valid string, even if it doesn't have the desired
contents. A closing note: If size is zero or negative, nothing is copied. The destination string is
unchanged.
The identifier, pNames, is a pointer to an array of pointers to a character that is dynamically allocated
from the heap. Then, as each name is read, space is allocated from the heap, and its pointer is placed
in the next location in the ptlames orroy. The only way to refer to the names is by dereferencing
pNames. To access an individual element, we use pNames and index it to get to an individual string
pointer in the array This code is shown in statement 36. Since the first parameter in the string copy is
a pointer to a string, only one dereference is required.

To build the pointer array, we use a while loop with two limit tests: end-of-file and a full array. Either
condition will stop the loading of the array. To print the array, however, we only need to test for a null
pointer, since the pointer array is allocated with one extra element. Using an extra element is a
common programming technique that makes pro cessing arrays of pointers easier and more efficient.

String Compare

As with the string copy functions, C has two string compare functions. The first, stremp, compares two
strings until unequal characters are found or until the end of the strings is reached. The second,
strncmp, compares until unequal characters are found, a specified number of characters have been
tested, or until the end of a string is reached.

Both functions return an integer to indicate the results of the compare. Unfortunately, the results
returned do not map well to the true false logical values that we see in the if...else statement (see
Chapter 5), so you will need to memorize a new set of rules:

1. If the two strings are equal, the return value is zero. Two strings are con- sidered equal if they are
the same length and all characters in the same relative positions are equal.

2. If the first parameter is less than the second parameter, the return value is less than zero. A string,
s1, is less than another string, s2, if starting from the first character, we can find a character in s1 that
is less than the character in s2. Note that when the end of either string is reached, the null character
is compared with the corresponding character in the other

string

3. If the first parameter is greater than the second parameter, the return value is greater than zero. A
string, 31, is greater than string, a2, if starting from the first character, we can find a character in a2
that is greater than the corresponding character in a1. Note that when the end of either string is
reached, the null character is compared with the corresponding character in the other string

Note that the not-equal values are specified as a range. If the first parameter is less than the second
parameter, the value can be any negative value. Likewise, if the first parameter is greater than the
second parameter, the value can be any positive number. This differs from other situations, such as
EOF, where we can rely on one given value being returned.
The first parameter is the string that is being parsed; the second parameter is a set of delimiters that
will be used to parse the first string. If the fest parameter contains an address, then strtok starts at
that address, which is assumed to be the beginning of the string. It first skips over all leading delimiter
characters. If all the characters in the string are delimiters, then it terminates and returns a null
pointer. When it finds a nondelimiter character, it changes its search and skips over all characters that
are not in the set; that is, it searches until it finds a delimiter. When a delimiter is found, it is changed
to a null character (10'), which turns the token just parsed into a string.
If the first parameter is not a string, strtok assumes that it has already parsed part of the string and
begins looking at the end of the previous string token for the next delimiter. When a delimiter is
located, it again changes the delimiter to a null character, marking the end of the token, and returns
a pointer to the new token string.

Let's look at a simple example of a string containing words separated by spaces. We begin by calling
string token with the address of the full string. It returns the address of the first character of the first
string that was just parsed. The second execution of the string token function parses the second string
and returns its address, and so on until the complete string has been parsed. This design is shown in
Figure 11-22.