Файл: Programming Microcontrollers in C, 2-nd edit (Ted Van Sickle, 2001).pdf

76 Chapter 2 Advanced C Topics

The corresponding elements in each subarray are compared, and if they are out of order, they are swapped. At the close of this opera­ tion, a new set of subarrays are created, and the process is repeated over these subarrays. Eventually, the gap between elements in the subarrays will be reduced to one, and the array contents will be sorted.

The outer for loop above controls the splitting of the arrays into the subarrays. The second loop steps along the array pairs. The in­ nermost loop successively compares the elements that are separated by gaps in the subarrays. If elements are found that are out of order, they are reversed or swapped in the array.

EXERCISES

1.Restate the shell sort above to use arrays rather than pointers to arrays.

2.Write a program that reads in characters from the input stream and record the number of occurrences of each character. Calculate the percentage occurrence of each character, and print out the result in ascending order of percentage of occurrence.

Functions can return pointers. For example, prototype to a func­ tion that returns a pointer is:

int *able(char* );

Here able returns a pointer to an integer.

In C, a NULL pointer is never used. A NULL pointer implies that something is to be stored at the address zero. This address is never avail­ able for data storage, so no function can return a valid NULL pointer. The NULL pointer can be used as a flag or an error return. The pro­ grammer should never allow a NULL pointer to be dereferenced, which implies that data are read or stored at 0.

If C will support a pointer to a variable, it requires but little imagi­ nation to reason that C will support pointers to pointers. In fact, there is no practical limit in the language to the depth of dereference C will support. C will also allow arrays of pointers, and pointers to functions. (We discussed pointers to arrays in the preceding section.) An array of pointers can be very useful when needed. A most obvi­ ous use for an array of pointers is to read the contents of a command line to a program. So far in our discussion of programs, there have been no provisions for reading the content of a command line that is

Pointers 77

written to the screen when the program is executed. A command line can be read by the program. The definition of the program name main when extended to read in a command line is as follows

void main ( int argc, char *argv[])

The integer variable argc is the number of entries on the command line. The array of pointers to the type char argv[] contains pointers to strings. When entering arguments onto the command line, they must be separated by spaces. The first string pointed to by argv[0] is the name of the program from the command line. The successive pointer values point to additional character strings. These strings are each 0 terminated, and they point to the successive entries on the command line. The value of argc is the total number of command line entries including the program name. It must be remembered that each entry in argv[] is a pointer to a string. Therefore, if a number is entered on the command line, it must be converted from a string to an integer, or floating point number, prior to its use in the program. Let us see how this concept can be used. Earlier, we wrote a function to calculate a Fibonacci number. Let’s use this function in a program in which the argument for the Fibonacci calculation is read in from the command line:

#include <stdio.h> #include <stdlib.h>

long fib( int ); /* Fibonacci number function prototype */

int main( int argc, char* argv[] )

{

int i;

i = atoi(argv[1]);

printf(“The Fibonacci number of %d = %ld\n”, i, fib(i));

return 0;

}

We will not repeat the code for fib(i). A new header file, stdlib.h, is included with this program. The function prototype for atoi() is contained within this header file. The standard com­ mand line arguments are used in the call to main(). The line

78 Chapter 2 Advanced C Topics

i = atoi(argv[1]);

causes the function atoi—ASCII to integer conversion—to be ex­ ecuted with a pointer as an argument. This pointer points to the first argument following the program name on the command line. In this case, it will be pointing to an ASCII string that contains the number to be used as an argument for the fib() call. This string must be converted to an integer before fib() can operate on it, which is exactly what the atoi() function accomplishes. The final line in this program prints out the result of the calculation.

Another example of use of the command line arguments is to print out the command line. The following program will accomplish this task.

#include <stdio.h>

int main( int argc, char* argv[] )

{

int i;

for(i=0; argc--; i++) printf(“%s “,argv[i]); printf(“\n”);

return 0;

}

The arguments to main() are the same as before. This program enters a for loop that initializes i to zero. It decrements argc each time it tests its value, and executes until the loop in which argc is decremented to 0. The printf call

printf(“%s “,argv[i]);

prints out the string to which argv[i] points. Notice the space in the string “%s “. This space will force a space between each argument as it is printed. The program is written so that there are no new line charac­ ters printed. Arguments will all be on one line, and they will each be separated by a space. The printf() statement after execution of the for() loop will print out a single new line so that the cursor will return to the next line after the program is executed.

Command line entry is but a simple example of use of arrays of pointers. Another area in which arrays to pointers are needed is in order­ ing strings of data. For example, it is possible to collect a large number of words in memory, say from an input stream. Suppose that it is needed to alphabetize these words. We saw earlier, that the shell sort will order

Pointers 79

the contents of an array, so it might be possible to simply modify the shell sort to do this job.

First, a comparison is needed that will determine if the lexical value of a one word is smaller, equal, or larger than that of another word. Such a compare routine was outlined above. Second, a swap routine that will swap the words that are in the wrong order. Here is a case where an array of pointers can be quite useful. Assume that the program that reads in the data will put each word into a separate memory location and keep an array of pointers to the beginning of each word rather than just the array of the words themselves. Then in the shell sort, when a swap is required, rather than swapping the words, swap the pointers in the array. Swap routines that swap pointers in the array are very easy to implement. On the other hand, swap routines to swap two strings in memory are diffi­ cult and slow. Therefore, we can create a sort routine that is much more efficient if we use an array of pointers rather than an array of strings.

/* shell_sort(): sort the contents of the array char* v[] into ascending order */

#include <string.h>

void shell_sort(char* v[], int n)

{

int gap, i, j; char* temp;

for( gap = n/2; gap > 0; gap /= 2) for( i=gap; i < n; i++)

for( j=i-gap; j>=0 && strcmp(v[j],v[j+gap]); j -= gap)

{

temp = v[j]; v[j] = v[j+gap]; v[j+gap] = v[j];

}

}

Here the strcmp() routine is used to determine if a swap is needed. strcmp() is identified in the header file string.h. When needed, the contents of the array of pointers to the beginning of the words is swapped rather than swapping the words themselves.

80 Chapter 2 Advanced C Topics

An important point of style: Recall that a few pages back a func­ tion strcomp() was written as an example. It did the exact same operations as strcmp() above. Why should we choose one over the other? Well, library functions have been written, rewritten, de­ bugged, and worked over for years. They work correctly, and you can count on their robust construction. As a general rule, use a li­ brary function if you can find one to do the job that you are attempting. Most of the time, programmers who write duplicates of library func­ tions do it to satisfy their own egos. The reward is poor when a bug is discovered, especially in production code, that could have been avoided by using a standard library function.

Multidimensional Arrays

C supports multidimensional arrays. Programmers often find that much of the need for multidimensional arrays will go away with the availability of pointers. Multidimensional arrays in C are thought of as arrays of arrays. This idea can be extended to more than two di­ mensions. A two-dimensional array is identified as

array[x][y]; /* [row][column] */

The first argument to the right can be thought of as the row dimen­ sion, and the second the column dimension. Elements specified by the rightmost argument are stored in adjacent memory locations.

An array can be initialized at declaration time. For example:

int array [3][4] = { {10,11,12,13}, {14,15,16,17}, {18,19,20,21} };

It is equally valid to initialize the array as follows:

int array [3][4]={10,11,12,13,14,15,16,17,18,19,20,21};

Either form of initialization will place the proper numbers in the proper location in memory, and the two-dimensional indices will work properly in either case.

Frequently, it is needed to know the size of a variable in C. This variable can be a basic type, an array, a multiple dimensional array, or even a structure that will be introduced later. C provides an operator

that has much the appearance of a function called sizeof. To deter­ mine the size of any variable, use the sizeof operator as follows:

a = sizeof array;

which will return the number of bytes contained in array[][] above. There are several important different ways that you can use the sizeof operator. First, the value of the return from sizeof is in characters. The type of the return is called a type size_t. This special type is usually the largest unsigned type that the compiler supports. For the MIX compiler, it is an unsigned long. If you should want the size of a type in your program, you should enclose the parameter in parentheses. If you want the size of any other item, do not use the paren­ theses. One other item. If the sizeof operator is used in a module where an array is defined, it will give you the size of the array as above. If you should pass an array to a function, the array name degenerates to a pointer to the array, and in that case, the return from the sizeof

operator would give you the size of a pointer to the array.

A common example program using two-dimensional arrays is to determine the Julian date. The Julian date is simply the day of the year. The following function is one that allows counting the number of days that have passed in a year.

int month_days[2][13] = { {0,31,28,31,30,31,30,31,31,30,31,30,31}, {0,31,29,31,30,31,30,31,31,30,31,30,31}};

int Julian_data(int month, int date, int year)

{

int i,leap;

leap = year%4==0 && year%100!=0 || year%400==0; for(i=1;i<month;i++)

day += month_days[leap][i]; return day;

}

The declaration

int month_days[2][13] = { {0,31,28,31,30,31,30,31,31,30,31,30,31}, {0,31,29,31,30,31,30,31,31,30,31,30,31}};

array must always be understood as being arrays of arrays of arrays and so forth. For example, the declaration

int ar[3][5];

defines three arrays of five elements each. We have already seen that data stored in this array is column major. The second argument points to a column in the two-dimensional array, and ar[n][0] and ar[n][1] are stored in adjacent memory locations. Following the logic of array names and pointers, the array name ar is a pointer to the first element in the array. The value obtained when using ar as an rvalue is &ar[0][0]. The order of evaluation of the square brackets is from left to right so that *(ar+1) is a pointer to the element ar[1][0] in the array. Think of the two-dimensional ar­ ray as being *(ar+n)[i] where n has a range from 0 to 2 and i has a range from 0 to 4. An increment in n here will increment the absolute value of the pointer by 5*sizeof(int).

These ideas can be carried to the next level. The element *(ar+n) is a pointer to the first element of a five-element array. Therefore, the evaluation of *(*(ar+n)+i) is the value found in the location ar[n][i]. The important item is that the right-most argument in multiple dimensional arrays point to adjacent memory locations, and the increments of the left arguments step the corresponding pointer value from array to array to array.

These ideas can be extended to arrays of more than two dimen­ sions. Had the array been

double br[3][4][5];

then *(*(*(br+1)+2)+3) would be the element br[1][2][3] from the above array, and *(*(br+1)+2)+3 is a pointer to this element.

EXERCISES

1.Write a function that will receive the year and the Julian date of that year, and calculate the month and date.

2.Write a function that will calculate the product of a 4 by 4 matrix and a scalar. The scalar product requires multiplication of each element in the matrix by the scalar value.