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

94Chapter 2 Advanced C Topics

typedef struct

{

int x; int y;

}Point;

typedef struct

{

Point center; int radius;

}Circle;

typedef struct

{

Point p1; Point p2;

}Rect;

Circle make_circle( Point ct, int rad )

{

Circle temp; temp.center=ct; temp.radius = rad; return temp;

}

/* some useful macros */

#define min(a,b) (((a)<(b)) ? (a) : (b)) #define abs(a) ((a)<0 ? -(a) : (a))

/* function prototypes */ void draw_rectangle(Rect); void draw_circle(Circle);

int main ( void )

{

Circle cir; Point center;

Rect window = { {80,80},{600,400} };

Structures 95

int radius,xc,yc;

center.x = (window.p1.x+window.p2.x)/2; center.y = (window.p1.y+window.p2.y)/2; xc = abs(window.p1.x - window.p2.x)/2; yc = abs(window.p1.y - window.p2.y)/2; radius=min(xc,yc);

cir=make_circle(center,radius); draw_rectangle(window); draw_circle(cir);

return 0;

}

The function make_circle() returns a type Circle and re­ quires arguments Point and int. Circle is used to declare the variable temp in make_circle(). Within the main program Circle, Point, and Rect are used as types in the definition of the several structure type variables used in the program. With the typedef declarations, there is no basic change to the program, but it is easier to read and follow.

The two functions draw_rectangle() and draw_circle() are not standard C functions. These functions are programmed and the listing of the final program is shown in Appendix B.

Self Referential Structures

A structure cannot contain itself as a member. Structure defini­ tions are not recursive. However, a structure can contain a pointer to a structure of the same type. This capability has proven quite useful in dealing with complicated sort or listing problems. One sort prob­ lem that can be easily treated is the binary tree sort. A tree sort receives data, such as a word. Within the tree there is a root node that contains a word. The node also contains a count of the number of times the word has been seen and two pointers to additional nodes. These nodes are called child or descendent nodes. Traditionally, the node to the left contains a word that is less than the root word, and the node to the right contains a word that is greater than the root node. As data are read into the tree, the new word is compared with the root word. If it is equal to the root word, the count in the node is incremented,

96 Chapter 2 Advanced C Topics

and a new word is received. If the word is not the same and is less than the root word, the node to the left is accessed and the compari­ son is repeated. This process is repeated until a match is found or a node with no descendants is found. If a match is found, the count of that node is incremented. If no match is found a new node is created and placed at the bottom location, and the word is inserted into the new node. This process is repeated with the smaller words always going to the left and the larger words always going to the right.

Eventually a tree that contains all of the different words entered into the program will have been created. The tree has several properties. Since each node has two child nodes, the tree builds in a binary manner. The root level has exactly one entry, the second level has two entries, the third level has four entries, and so forth. If the tree is balanced, each level will have a power of two entries. However, if word data are taken in randomly, it is possible that some tree branches will terminate early and others will extend to a depth or level that exceeds some.

Once the data are placed into the tree, it is possible to sort it or to arrange the words in alphabetical order. If we traverse the tree from the root node to the extreme left, we will find the word that is small­ est. Immediately above that word will be the next larger word. To the right of the second word will be words larger than itself but smaller than the word in the next node above. Therefore, the right path must be traversed to the left to find the next larger words. All of this— right and left, larger and smaller—sounds complicated. It is not.

Here is a case where a little thought and recursive code will help things along easily. The code that follows is a complete function to alphabetize and count the number of times that each word is used in a document. Several new concepts will be shown in this program, so it will be broken into short blocks and described in these small pieces of code rather than trying to bite into the whole program at one time. The structure tnode is listed below.

typedef struct tnode { /* the tree node */

char *word; /* points to text */ int count; /* occurrences */

struct tnode *left;/* pointer to left child */ struct tnode *right; /* pointer to right child*/

}Tnode;

Structures 97

The first two elements to this structure are a pointer to the word contained in the node, and the number of times that the word has been seen. The last two elements are pointers to structures of the type struct tnode. Note that in the typedef of the struct tnode, the structure tag was used. It is necessary to use the tag in this case because the self-referential pointers inside of the structure needs the tag to find the correct type. For the remainder of the pro­ gram, the typedef Tnode is used.

Some new files are included in the include files. These files will be discussed in a following section. The first is ctype.h. This pro­ gram uses several character tests that are identified in ctype.h. There are string operations found in string.h , and there are stan­ dard functions defined in stdlib.h.

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

The list of function prototypes for the functions written in this program follow:

Tnode *addtree(TNODE *, char *); Tnode *talloc(void);

void treeprint( TNODE *); int getword(char *, int); char *strsave(char *);

The first function is the function that is used to add a tree to the program. *talloc() is a function that allocates memory for a Tnode. The function treeprint() prints out the tree, and getword() reads in a word from the input stream. There are two function prototypes defined within the program getword(). These functions are used by getword() only. The final function above saves the string pointed to by the argument in a safe place and re­ turns a pointer to the word location in memory.

The main program is relatively simple. The constant MAXWORD is the maximum number of characters that can be allowed in a word. Within main() a pointer to a structure Tnode named root is de­ clared along with a character array named word and an integer i.

98Chapter 2 Advanced C Topics

/* word frequency count */

#define MAXWORD 100

int main(void)

{

Tnode *root;

char word[MAXWORD]; int i;

root=NULL; while(getword(word,MAXWORD) != EOF)

if(isalpha(word[0]))

root=addtree(root,word);

treeprint(root); return 0;

}

A NULL value is assigned to root, and the program enters a loop that reads words from the input stream. It is assumed that if the first character of the word is a letter, that a word has been read in. The function isaplha() returns a TRUE if its argument is a letter, and a FALSE if it is not. If the input is a letter, the routine addtree is executed with the arguments root and word. The first time that this function is executed, root is a NULL. This loop is repeatedly executed until getword() receives an EOF character from the input stream. At that time the input loop terminates, and the function treeprint() is executed. When treeprint() is completed, main() returns a 0 to the calling pro­ gram or the operating system. This signal can be used to notify the operating system that the program has executed correctly.

Here is a good point to introduce the concept of a NULL pointer. Often people use the term NULL to mean zero or a character contain­ ing a zero. This idea is incorrect. In this text, the word NULL means a NULL pointer to a type void. Such a pointer can be defined in a header file and the definition will look like

#define NULL ((* void) 0)

Any place you see the name NULL in this text, it has the above meaning. The function addtree() is the most complicated function in

Structures 99

this program. This function receives a pointer to a Tnode and a pointer to a character string as arguments. It returns a pointer to a Tnode. If the Tnode pointer argument is a NULL on entry to the function, the first if loop is executed. Within that loop, talloc() returns a pointer to a new Tnode. The function strsave() copies the string into a safe place and returns a pointer to this location. This pointer is put into the word pointer location in the new Tnode. A value of 1 is put into the count location, and the pointers to the left and right child Tnodes are set to NULL. At this time, the word has been put into the Tnode , and the pointer to this Tnode is returned to the calling program.

/* addtree: add a node with w, at or below p */

Tnode *addtree(Tnode *p, char *w)

{

int cond;

if(p == NULL) /* new word has arrived */

{

p=talloc(); /* make a new node */ p->word=strsave(w);

p->count=1; p->left=p->right=NULL;

}

else if((cond = strcmp(w,p->word)) == 0 ) p->count++; /* repeated word */

else if(cond <0) /* less than into left subtree*/ p->left = addtree(p->left,w);

else /* greater than into right subtree */ p->right = addtree(p->right,w);

return p;

}

Suppose now that at a later time addtree() is called and this time p is no longer a NULL. In this case, a string compare test will be executed to determine if the word that has been passed is equal to that in the Tnode pointed to by p. If it is equal, it is a repeated word for that node, so the word count is incremented and control is returned to the calling program. If it is not equal (say, it is lexically less than the

100 Chapter 2 Advanced C Topics

word of the node), it is necessary to either traverse to the node on the left or add a new node on the left if there is none there. The code

p->left = addtree(p->left,w);

does exactly what is needed in this case. This recursive call to addtree() will descend to the left Tnode if one exists. If one does not exist, the pointer to the left Tnode will be NULL, so addtree() will create a new node for this location. addtree() returns a pointer to the new node, so it will be placed in the left pointer of this node.

Had the lexical value of the word been greater than that of the word stored in the node, the addtree() call would work on the pointer to the right child node. Therefore, the function addtree() will start at the root node and traverse down the tree to the right or left child nodes depending on the size of the word relative to the sizes of the words in the tree. If the word is found in the tree, its count is incremented. If control proceeds down the tree, and the word is not found, eventually, a Tnode with a NULL pointer to the direc­ tion that the path must move. A that time a new Tnode is created and the word is assigned to that Tnode.

When all of the data to be input into the tree are read in, control is passed to the function treeprint(). The argument of treeprint() is a pointer to the root node and treeprint() returns nothing to the calling program. Efficient printing out of the data requires another recursive routine. The function treeprint() shown below shows this routine. treeprint() is called with the root pointer as an argument. The root pointer will not be a NULL, so the code following the if statement will be executed. The first

/* treeprint: in-order print of tree p */

void treeprint(TNODE *p)

{

if(p !=NULL)

{

treeprint(p->left); printf(“%4d%15s\n”,p->count,p->word); treeprint(p->right);

}

}

Structures 101

statement of this code is a recursive call to treeprint() with the pointer to the left child pointer as an argument. This recursive call will cause control to propagate to the lowest and leftmost level of the tree. At this time treeprint() will return normally, and the word pointed to in the Tnode will be printed out by the printf() call. The program will then start a recursive treeprint() to the right of this node. Control will immediately go to the left side of the right branch and will descend the lowest level and print out the word “found.” This routine will repeat up and down until the whole tree content has been printed.

The function strsave() copies the word passed to it as an argument into a save place and returns a pointer to this memory loca­ tion to the calling program. C provides for dynamic allocation of memory.

char *strsave(char *s) /* make a duplicate of s */

{

char *p;

p = (char *)malloc(strlen(s)+1); if(p != NULL)

strcpy(p,s); return p;

}

Up to this point, all memory access was to memory allocated by declaration statements. With dynamic allocation, the program can go to the operating system and request memory at any time. This memory is from a memory area called the program heap. The first call to allocate memory is malloc() shown above. The function prototype for this function is found in stdlib.h , and the func­ tion requires an argument that is the length of the memory space needed. The program returns a pointer to the base type of the system, chars, to the required block of memory. If there is not enough memory available, the function returns a NULL pointer. C will never return a valid NULL pointer. Therefore, if you have a C program call that returns a pointer, the program can always test for a NULL pointer to determine if the call succeeded. In the above code, it is assumed that the calling program will check for the NULL pointer and deter­ mine what to do.

102 Chapter 2 Advanced C Topics

The function prototype of the function malloc() is contained in stdlib.h. This function returns a pointer to a type void. If you will recall the rules of arithmetic for pointers, a pointer to a type void can be assigned to any other pointer type, and vice versa. There­ fore, it is not necessary to cast the return from the malloc call to the type char* as was done above. In fact, there are people that say that you should not perform this cast. If you make a mistake and do not include the header stdlib.h, then the compiler would as­ sume that the return from the malloc function call is an int. The cast operation would introduce a bug into your code if the header were not included. The error of the missing header file would be identified by the compiler if there is no cast because the program would be loathe to assign an integer to a pointer. Therefore, the code without the cast is more robust.

I personally object to this logic. The current trend is to insist that all operands in expressions that are not of the correct type be cast to the correct type prior to execution of any operators. This trend largely ignores the automatic type promotion that takes place when there are mixed types within a single expression. In fact, many pro­ gramming standards insist that all mixed types be cast explicitly. In such an environment, it seems rather silly that one case be singled out and done differently.

The function talloc() also makes use of the malloc() function. In this case, the argument of the malloc() call is the sizeof operator. sizeof is a C operator that returns the size of the argument. sizeof is an operator in C and requires no prototype.

/* talloc : make a tnode */ TNODE *talloc(void)

{

return (TNODE *) malloc(sizeof(TNODE));

}

The memory allocation function malloc() returns a pointer to the basic memory size of the system. It is always necessary to cast the return from malloc() onto the type of variable that the return must point to. In this case, the cast is to the type pointer to TNODE. In strsave(), the cast was to the type pointer to char. There­ fore, the statement

Structures 103

return (TNODE *) malloc(sizeof(TNODE);

will return to the calling function a pointer of the type TNODE to a free memory space the size of a TNODE. This function is called by the function addtree(). You will note that addtree() does not test the return from talloc() to determine if the return is a NULL pointer. Good programming practice would dictate that the return from talloc() should be tested to make certain that malloc() did not return a NULL pointer.

The next function that must be incorporated into the program is getword(). getword() returns the first character of the word or an EOF in the case that an EOF is detected. It requires two argu­ ments. The first is a pointer to a character array into which the input data are to be stored. The second argument is the length of the array and hence the maximum length of any word that can be read into the program by getword(). Two functions are accessed by getword(). The first is getch() which returns a character from the input stream. The second is ungetch() which restores a char­ acter back onto the input stream. We will see later that for getword() to work correctly, it must pull one more character than the length of the word in some cases. When that happens, the extra character must be put back onto the input stream so that it will be available for the next getch() call.

/* getword: get next word or character from input */ int c, getch(void);

void ungetch(int);

int getword(char *word, int lim)

{

char *w=word; while(isspace(c=tolower(getch()))); if(c!=EOF)

*w++=c;

if(!isalpha(c))

{

*w=‘\0’; return c;

}

for( ; —lim >0 ; w++)

104 Chapter 2 Advanced C Topics

if(!isalnum(*w=tolower(getch())))

{

ungetch(*w);

break;

}

*w=‘\0’; return word[0];

}

The first executable statement

while(isspace(c=tolower(getch())));

includes two standard C functions. The function isspace() has its prototype in the header file ctype.h. This function returns a TRUE if its argument is a space and FALSE otherwise. The second function, tolower(), is also prototyped in ctype.h. It tests the argument and returns a lower case letter if the argument is upper case. Therefore, this operation will loop until it receives a nonspace input, and the lower case version of the letter input will be stored in c.

If c is not an EOF, it is put into the next open location of the word array and the pointer into this array is incremented. If the return is an EOF, the second if statement will execute. The if statement

if(!isalpha(c))

{

*w=‘\0’; return c;

}

tests to determine if the character from the input stream is a letter. isalpha() returns a TRUE if its argument is a letter and a FALSE otherwise. If the character taken from the input stream is an EOF, isalpha() will return a FALSE and the statement following the if will be executed. In this case, a zero character is written to the word, and the EOF is returned to the calling function.

If the return is a letter, the following sequence will be executed:

for( ; —lim >0 ; w++) if(!isalnum(*w=tolower(getch())))

{

ungetch(*w);