Source Code - Koreng

Vb, Delphi, .net, framework, C++, Java, Pascal,Visual Studio, Asm, Ruby, C#, j#, Cs, Html, Php, Perl, Asp, xHtml Get Free Souce Code Here...



Other Preprocessor Commands

The C Preprocessor

  Recall that preprocessing is the first step in the C program compilation stage -- this feature is unique to C compilers. The preprocessor more or less provides its own language which can be a very powerful tool to the programmer. Recall that all preprocessor directives or commands begin with a #.
Use of the preprocessor is advantageous since it makes:
  • programs easier to develop,
  • easier to read,
  • easier to modify
  • C code more transportable between different machine architectures.
The preprocessor also lets us customise the language. For example to replace { ... } block statements delimiters by PASCAL like begin ... end we can do:


    #define begin {
   #define end  }


During compilation all occurrences of begin and end get replaced by corresponding { or } and so the subsequent C compilation stage does not know any difference!!!.

Lets look at #define in more detail

#define

Use this to define constants or any macro substitution. Use as follows:



    #define   
 
For Example
 
   #define FALSE  0
   #define TRUE  !FALSE 

We can also define small ``functions'' using #define. For example max. of two variables:

   #define max(A,B) ( (A) > (B) ? (A):(B))

? is the ternary operator in C.

Note: that this does not define a proper function max.

All it means that wherever we place max(C$\dagger$,D$\dagger$) the text gets replaced by the appropriate definition. [$\dagger$ = any variable names - not necessarily C and D]

So if in our C code we typed something like:

   x = max(q+r,s+t);
after preprocessing, if we were able to look at the code it would appear like this:

   x = ( (q+r) > (r+s) ? (q+r) : (s+t));

Other examples of #define could be:


#define Deg_to_Rad(X) (X*M_PI/180.0) 
/* converts degrees to radians, M_PI is the value  
of pi and is defined in math.h library */
 
#define LEFT_SHIFT_8 <<8


NOTE: The last macro LEFT_SHIFT_8 is only
valid so long as replacement context is valid i.e.
x = y LEFT_SHIFT_8.

#undef

This commands undefined a macro. A macro must be undefined before being redefined to a different value.

#include

This directive includes a file into code.

It has two possible forms:


   #include 
 
or
 
   #include ``file''


tells the compiler to look where system include files are held. Usually UNIX systems store files in $\backslash$usr$\backslash$include$\backslash$ directory.

``file'' looks for a file in the current directory (where program was run from)

Included files usually contain C prototypes and declarations from header files and not (algorithmic) C code (SEE next Chapter for reasons)

#if -- Conditional inclusion

#if evaluates a constant integer expression. You always need a #endif to delimit end of statement.

We can have else etc. as well by using #else and #elif -- else if.

Another common use of #if is with:
#ifdef
-- if defined and
#ifndef
-- if not defined
These are useful for checking if macros are set -- perhaps from different program modules and header files.

For example, to set integer size for a portable C program between TurboC (on MSDOS) and Unix (or other) Operating systems. Recall that TurboC uses 16 bits/integer and UNIX 32 bits/integer.

Assume that if TurboC is running a macro TURBOC will be defined. So we just need to check for this:


  #ifdef TURBOC
     #define INT_SIZE 16
   #else
      #define INT_SIZE  32
   #endif


As another example if running program on MSDOS machine we want to include file msdos.h otherwise a default.h file. A macro SYSTEM is set (by OS) to type of system so check for this:


  #if SYSTEM == MSDOS
     #include 
   #else
      #include ``default.h''
  #endif

Preprocessor Compiler Control

You can use the cc compiler to control what values are set or defined from the command line. This gives some flexibility in setting customised values and has some other useful functions. The -D compiler option is used. For example:
   cc -DLINELENGTH=80 prog.c -o prog
has the same effect as:
   #define LINELENGTH 80
Note that any #define or #undef within the program (prog.c above) override command line settings.
You can also set a symbol without a value, for example:
   cc -DDEBUG prog.c -o prog
Here the value is assumed to be 1.
The setting of such flags is useful, especially for debugging. You can put commands like:
#ifdef DEBUG
     print("Debugging: Program Version 1\");
#else
     print("Program Version 1 (Production)\");
#endif
Also since preprocessor command can be written anywhere in a C program you can filter out variables etc for printing etc. when debugging:
x = y *3;

#ifdef DEBUG
     print("Debugging: Variables (x,y) = \",x,y);
#endif
The -E command line is worth mentioning just for academic reasons. It is not that practical a command. The -E command will force the compiler to stop after the preprocessing stage and output the current state of your program. Apart from being debugging aid for preprocessor commands and also as a useful initial learning tool (try this option out with some of the examples above) it is not that commonly used.

There are few other preprocessor directives available:
#error
text of error message -- generates an appropriate compiler error message. e.g

  #ifdef OS_MSDOS
     #include 
   #elifdef OS_UNIX
      #include ``default.h''
  #else
     #error Wrong OS!!
  #endif
# line
number "string" -- informs the preprocessor that the number is the next number of line of input. "string" is optional and names the next line of input. This is most often used with programs that translate other languages to C. For example, error messages produced by the C compiler can reference the file name and line numbers of the original source files instead of the intermediate C (translated) source files.

Exercises

Exercise 12529
Define a preprocessor macro swap(t, x, y) that will swap two arguments x and y of a given type t.

Exercise 12531
Define a preprocessor macro to select:
  • the least significant bit from an unsigned char
  • the nth (assuming least significant is 0) bit from an unsigned char.

Low Level Operators and Bit Fields

  We have seen how pointers give us control over low level memory operations. Many programs (e.g. systems type applications) must actually operate at a low level where individual bytes must be operated on.
NOTE: The combination of pointers and bit-level operators makes C useful for many low level applications and can almost replace assembly code. (Only about 10 % of UNIX is assembly code the rest is C!!.)

Bitwise Operators

The bitwise operators of C a summarised in the following table:


 
Table: Bitwise operators
& AND
$\mid$ OR
$\wedge$ XOR
$\sim$ One's Compliment
  $0 \rightarrow 1$
  $1 \rightarrow 0$
<< Left shift
>> Right Shift

DO NOT confuse & with &&: & is bitwise AND, && logical AND. Similarly for $\mid$ and $\mid\mid$.

$\sim$ is a unary operator -- it only operates on one argument to right of the operator.

The shift operators perform appropriate shift by operator on the right to the operator on the left. The right operator must be positive. The vacated bits are filled with zero (i.e. There is NO wrap around).
For example: x << 2 shifts the bits in x by 2 places to the left.

So:

if x = 00000010 (binary) or 2 (decimal)

then:

$x \gt\gt= 2 \Rightarrow x = 00000000$ or 0 (decimal)

Also: if x = 00000010 (binary) or 2 (decimal)

$x <<= 2 \Rightarrow x = 00001000$ or 8 (decimal)

Therefore a shift left is equivalent to a multiplication by 2.

Similarly a shift right is equal to division by 2

NOTE: Shifting is much faster than actual multiplication (*) or division (/) by 2. So if you want fast multiplications or division by 2 use shifts.

To illustrate many points of bitwise operators let us write a function, Bitcount, that counts bits set to 1 in an 8 bit number (unsigned char) passed as an argument to the function.


int bitcount(unsigned char x) 
 
   { int count;
 
     for (count=0; x != 0; x>>=1);
       if ( x & 01)
         count++;
     return count;
   }



This function illustrates many C program points:
  • for loop not used for simple counting operation
  • x$\gt\gt=1 \Rightarrow$ x = x >> 1
  • for loop will repeatedly shift right x until x becomes 0
  • use expression evaluation of x & 01 to control if
  • x & 01 masks of 1st bit of x if this is 1 then count++

Bit Fields

Bit Fields allow the packing of data in a structure. This is especially useful when memory or data storage is at a premium. Typical examples:
  • Packing several objects into a machine word. e.g. 1 bit flags can be compacted -- Symbol tables in compilers.
  • Reading external file formats -- non-standard file formats could be read in. E.g. 9 bit integers.
C lets us do this in a structure definition by putting :bit length after the variable. i.e.


struct packed_struct {
   unsigned int f1:1;
   unsigned int f2:1;
   unsigned int f3:1;
   unsigned int f4:1;
   unsigned int type:4;
   unsigned int funny_int:9;
} pack;


Here the packed_struct contains 6 members: Four 1 bit flags f1..f3, a 4 bit type and a 9 bit funny_int.

C automatically packs the above bit fields as compactly as possible, provided that the maximum length of the field is less than or equal to the integer word length of the computer. If this is not the case then some compilers may allow memory overlap for the fields whilst other would store the next field in the next word (see comments on bit fiels portability below).

Access members as usual via:

   pack.type = 7;

NOTE:
  • Only n lower bits will be assigned to an n bit number. So type cannot take values larger than 15 (4 bits long).
  • Bit fields are always converted to integer type for computation.
  • You are allowed to mix ``normal'' types with bit fields.
  • The unsigned definition is important - ensures that no bits are used as a $\pm$ flag.

Bit Fields: Practical Example

Frequently device controllers (e.g. disk drives) and the operating system need to communicate at a low level. Device controllers contain several registers which may be packed together in one integer (Figure 12.1).
 
Fig. 12.1 Example Disk Controller Register We could define this register easily with bit fields:
struct DISK_REGISTER  {
     unsigned ready:1;
     unsigned error_occured:1;
     unsigned disk_spinning:1;
     unsigned write_protect:1;
     unsigned head_loaded:1;
     unsigned error_code:8;
     unsigned track:9;
     unsigned sector:5;
     unsigned command:5;
};
To access values stored at a particular memory address, DISK_REGISTER_MEMORY we can assign a pointer of the above structure to access the memory via:
struct DISK_REGISTER *disk_reg = (struct DISK_REGISTER *) DISK_REGISTER_MEMORY;
The disk driver code to access this is now relatively straightforward:
/* Define sector and track to start read */

disk_reg->sector = new_sector;
disk_reg->track = new_track;
disk_reg->command = READ;

/* wait until operation done, ready will be true */

while ( ! disk_reg->ready ) ;

/* check for errors */

if (disk_reg->error_occured)
  { /* interrogate disk_reg->error_code for error type */
    switch (disk_reg->error_code)
    ......
  }

A note of caution: Portability

Bit fields are a convenient way to express many difficult operations. However, bit fields do suffer from a lack of portability between platforms:
  • integers may be signed or unsigned
  • Many compilers limit the maximum number of bits in the bit field to the size of an integer which may be either 16-bit or 32-bit varieties.
  • Some bit field members are stored left to right others are stored right to left in memory.
  • If bit fields too large, next bit field may be stored consecutively in memory (overlapping the boundary between memory locations) or in the next word of memory.
If portability of code is a premium you can use bit shifting and masking to achieve the same results but not as easy to express or read. For example:
unsigned int  *disk_reg = (unsigned int *) DISK_REGISTER_MEMORY;

/* see if disk error occured */

disk_error_occured = (disk_reg & 0x40000000) >> 31;

Exercises

Exercise 12507
 Write a function that prints out an 8-bit (unsigned char) number in binary format.

Exercise 12514
Write a function setbits(x,p,n,y) that returns x with the n bits that begin at position p set to the rightmost n bits of an unsigned char variable y (leaving other bits unchanged).
E.g. if x = 10101010 (170 decimal) and y = 10100111 (167 decimal) and n = 3 and p = 6 say then you need to strip off 3 bits of y (111) and put them in x at position 10xxx010 to get answer 10111010.
Your answer should print out the result in binary form (see Exercise 12.1 although input can be in decimal form.
Your output should be like this:
x = 10101010 (binary)
   y = 10100111 (binary)
   setbits n = 3, p = 6 gives x = 10111010 (binary)

Exercise 12515
Write a function that inverts the bits of an unsigned char x and stores answer in y.
Your answer should print out the result in binary form (see Exercise 12.1 although input can be in decimal form.
Your output should be like this:
x = 10101010 (binary)
   x inverted = 01010101 (binary)

Exercise 12516
Write a function that rotates (NOT shifts) to the right by n bit positions the bits of an unsigned char x.ie no bits are lost in this process.
Your answer should print out the result in binary form (see Exercise 12.1 although input can be in decimal form.
Your output should be like this:
x = 10100111 (binary)
   x rotated by 3 = 11110100 (binary)

Note: All the functions developed should be as concise as possible

Advanced Pointer Topics

We have introduced many applications and techniques that use pointers. We have introduced some advanced pointer issues already. This chapter brings together some topics we have briefly mentioned and others to complete our study C pointers.
In this chapter we will:
  • Examine pointers to pointers in more detail.
  • See how pointers are used in command line input in C.
  • Study pointers to functions

Pointers to Pointers

We introduced the concept of a pointer to a pointer previously. You can have a pointer to a pointer of any type.
Consider the following:
char ch;  /* a character */
char *pch; /* a pointer to a character */
char **ppch; /* a pointer to a pointer to a character */
We can visualise this in Figure 11.1. Here we can see that **ppch refers to memory address of *pch which refers to the memory address of the variable ch. But what does this mean in practice?
 
Fig. 11.1 Pointers to pointers Recall that char * refers to a (NULL terminated string. So one common and convenient notion is to declare a pointer to a pointer to a string (Figure 11.2)
 
Fig. 11.2 Pointer to String Taking this one stage further we can have several strings being pointed to by the pointer (Figure 11.3)
 
Fig. 11.3 Pointer to Several Strings We can refer to individual strings by ppch[0], ppch[1], ..... Thus this is identical to declaring char *ppch[].
One common occurrence of this type is in C command line argument input which we now consider.

Command line input

C lets read arguments from the command line which can then be used in our programs.

We can type arguments after the program name when we run the program.

We have seen this with the compiler for example

   c89 -o prog prog.c

c89 is the program, -o prog prog.c the arguments.

In order to be able to use such arguments in our code we must define them as follows:

   main(int argc, char **argv)

So our main function now has its own arguments. These are the only arguments main accepts.

  • argc is the number of arguments typed -- including the program name.
  • argv is an array of strings holding each command line argument -- including the program name in the first array element.
A simple program example:


#include
 
main (int argc, char **argv)
    { /* program to print arguments
     from command line */
 
     int i;
 
     printf(``argc = %d$\backslash$n$\backslash$n'',argc);
     for (i=0;i
       printf(``argv[%d]: %s$\backslash$n'',
         i, argv[i]);
   }


Assume it is compiled to run it as args.

So if we type:

   args f1 ``f2'' f3 4 stop!

The output would be:


   argc = 6
 
   argv[0] = args
   argv[1] = f1
   argv[2] = f2
   argv[3] = f3
   argv[4] = 4
   argv[5] = stop!


NOTE: $\bullet$ argv[0] is program name.
   $\bullet$ argc counts program name
   $\bullet$ Embedded `` '' are ignored.
   Blank spaces delimit end of arguments.
   Put blanks in `` '' if needed.

Pointers to a Function

  Pointer to a function are perhaps on of the more confusing uses of pointers in C. Pointers to functions are not as common as other pointer uses. However, one common use is in a passing pointers to a function as a parameter in a function call. (Yes this is getting confusing, hold on to your hats for a moment).
This is especially useful when alternative functions maybe used to perform similar tasks on data. You can pass the data and the function to be used to some control function for instance. As we will see shortly the C standard library provided some basic sorting ( qsort) and searching (bsearch) functions for free. You can easily embed your own functions.
To declare a pointer to a function do:
int (*pf) ();
This simply declares a pointer *pf to function that returns and int. No actual function is pointed to yet.
If we have a function int f() then we may simply (!!) write:
pf = &f;
For compiler prototyping to fully work it is better to have full function prototypes for the function and the pointer to a function:
int f(int);
int (*pf) (int) = &f;
Now f() returns an int and takes one int as a parameter.
You can do things like:
ans = f(5);
ans = pf(5);
which are equivalent.
The qsort standard library function is very useful function that is designed to sort an array by a key value of any type into ascending order, as long as the elements of the array are of fixed type.
qsort is prototyped in (stdlib.h):
void qsort(void *base, size_t num_elements, size_t element_size,
   int (*compare)(void const *, void  const *));
The argument base points to the array to be sorted, num_elements indicates how long the array is, element_size is the size in bytes of each array element and the final argument compare is a pointer to a function.
qsort calls the compare function which is user defined to compare the data when sorting. Note that qsort maintains it's data type independence by giving the comparison responsibility to the user. The compare function must return certain (integer) values according to the comparison result:
less than zero
: if first value is less than the second value
zero
: if first value is equal to the second value
greater than zero
: if first value is greater than the second value
Some quite complicated data structures can be sorted in this manner. For example, to sort the following structure by integer key:
typedef struct {
        int   key;
        struct other_data;
} Record;
We can write a compare function, record_compare:
int record\_compare(void const *a, void  const *a)
  {  return ( ((Record *)a)->key - ((Record *)b)->key );
  }
Assuming that we have an array of array_length Records suitably filled with date we can call qsort like this:
qsort( array, arraylength, sizeof(Record), record_compare);
Further examples of standard library and system calls that use pointers to functions may be found in Chapters 15.4 and 19.1.

Exercises

Exercise 12476
Write a program last that prints the last n lines of its text input. By default n should be 5, but your program should allow an optional argument so that
last -n
prints out the last n lines, where n is any integer. Your program should make the best use of available storage. (Input of text could be by reading a file specified from the command or reading a file from standard input)

Exercise 12477
Write a program that sorts a list of integers in ascending order. However if a -r flag is present on the command line your program should sort the list in descending order. (You may use any sorting routine you wish)
Exercise 12478
Write a program that reads the following structure and sorts the data by keyword using qsort
typedef struct {
        char   keyword[10];
        int    other_data;
} Record;
Exercise 12479
An insertion sort is performed by adding values to an array one by one. The first value is simply stored at the beginning of the array. Each subsequent value is added by finding its ordered position in the array, moving data as needed to accommodate the value and inserting the value in this position.
Write a function called insort that performs this task and behaves in the same manner as qsort, i.e it can sort an array by a key value of any type and it has similar prototyping.

Dynamic Memory Allocation and Dynamic Structures

Dynamic allocation is a pretty unique feature to C (amongst high level languages). It enables us to create data types and structures of any size and length to suit our programs need within the program.

We will look at two common applications of this:
  • dynamic arrays
  • dynamic data structure e.g. linked lists

Malloc, Sizeof, and Free

The Function malloc is most commonly used to attempt to ``grab'' a continuous portion of memory. It is defined by:

   void *malloc(size_t number_of_bytes)

That is to say it returns a pointer of type void * that is the start in memory of the reserved portion of size number_of_bytes. If memory cannot be allocated a NULL pointer is returned.
Since a void * is returned the C standard states that this pointer can be converted to any type. The size_t argument type is defined in stdlib.h and is an unsigned type.
So:


    char *cp;
   cp = malloc(100);


attempts to get 100 bytes and assigns the start address to cp.
Also it is usual to use the sizeof() function to specify the number of bytes:


    int *ip;
   ip = (int *) malloc(100*sizeof(int));
Some C compilers may require to cast the type of conversion. The (int *) means coercion to an integer pointer. Coercion to the correct pointer type is very important to ensure pointer arithmetic is performed correctly. I personally use it as a means of ensuring that I am totally correct in my coding and use cast all the time.
It is good practice to use sizeof() even if you know the actual size you want -- it makes for device independent (portable) code.
sizeof can be used to find the size of any data type, variable or structure. Simply supply one of these as an argument to the function.

SO:


   int i;
   struct COORD {float x,y,z};
   typedef struct COORD PT;
 
   sizeof(int), sizeof(i),
   sizeof(struct COORD) and
   sizeof(PT) are all ACCEPTABLE


In the above we can use the link between pointers and arrays to treat the reserved memory like an array. i.e we can do things like:

   ip[0] = 100;

or

   for(i=0;i<100;++i) scanf("%d",ip++);


When you have finished using a portion of memory you should always free() it. This allows the memory freed to be aavailable again, possibly for further malloc() calls
The function free() takes a pointer as an argument and frees the memory to which the pointer refers.

Calloc and Realloc

There are two additional memory allocation functions, Calloc() and Realloc(). Their prototypes are given below:
void *calloc(size_t num_elements, size_t element_size};

void *realloc( void *ptr, size_t new_size);
Malloc does not initialise memory (to zero) in any way. If you wish to initialise memory then use calloc. Calloc there is slightly more computationally expensive but, occasionally, more convenient than malloc. Also note the different syntax between calloc and malloc in that calloc takes the number of desired elements, num_elements, and element_size, element_size, as two individual arguments.
Thus to assign 100 integer elements that are all initially zero you would do:

    int *ip;
   ip = (int *) calloc(100, sizeof(int));

Realloc is a function which attempts to change the size of a previous allocated block of memory. The new size can be larger or smaller. If the block is made larger then the old contents remain unchanged and memory is added to the end of the block. If the size is made smaller then the remaining contents are unchanged.
If the original block size cannot be resized then realloc will attempt to assign a new block of memory and will copy the old block contents. Note a new pointer (of different value) will consequently be returned. You must use this new value. If new memory cannot be reallocated then realloc returns NULL.
Thus to change the size of memory allocated to the *ip pointer above to an array block of 50 integers instead of 100, simply do:
   ip = (int *) calloc( ip, 50);

Linked Lists

  Let us now return to our linked list example:

  typedef struct {  int value;
        ELEMENT *next;
     } ELEMENT; 


We can now try to grow the list dynamically:

  link = (ELEMENT *) malloc(sizeof(ELEMENT));

This will allocate memory for a new link.

If we want to deassign memory from a pointer use the free() function:

  free(link)

See Example programs (queue.c) below and try exercises for further practice.

Full Program: queue.c

A queue is basically a special case of a linked list where one data element joins the list at the left end and leaves in a ordered fashion at the other end.
The full listing for queue.c is as follows:
/*            */
/* queue.c            */
/* Demo of dynamic data structures in C                      */

#include 

#define FALSE 0
#define NULL 0

typedef struct {
    int     dataitem;
    struct listelement *link;
}               listelement;

void Menu (int *choice);
listelement * AddItem (listelement * listpointer, int data);
listelement * RemoveItem (listelement * listpointer);
void PrintQueue (listelement * listpointer);
void ClearQueue (listelement * listpointer);

main () {
    listelement listmember, *listpointer;
    int     data,
            choice;

    listpointer = NULL;
    do {
 Menu (&choice);
 switch (choice) {
     case 1: 
  printf ("Enter data item value to add  ");
  scanf ("%d", &data);
  listpointer = AddItem (listpointer, data);
  break;
     case 2: 
  if (listpointer == NULL)
      printf ("Queue empty!\n");
  else
      listpointer = RemoveItem (listpointer);
  break;
     case 3: 
  PrintQueue (listpointer);
  break;

     case 4: 
  break;

     default: 
  printf ("Invalid menu choice - try again\n");
  break;
 }
    } while (choice != 4);
    ClearQueue (listpointer);
}    /* main */

void Menu (int *choice) {

    char    local;

    printf ("\nEnter\t1 to add item,\n\t2 to remove item\n\
\t3 to print queue\n\t4 to quit\n");
    do {
 local = getchar ();
 if ((isdigit (local) == FALSE) && (local != '\n')) {
     printf ("\nyou must enter an integer.\n");
     printf ("Enter 1 to add, 2 to remove, 3 to print, 4 to quit\n");
 }
    } while (isdigit ((unsigned char) local) == FALSE);
    *choice = (int) local - '0';
}

listelement * AddItem (listelement * listpointer, int data) {

    listelement * lp = listpointer;

    if (listpointer != NULL) {
 while (listpointer -> link != NULL)
     listpointer = listpointer -> link;
 listpointer -> link = (struct listelement  *) malloc (sizeof (listelement));
 listpointer = listpointer -> link;
 listpointer -> link = NULL;
 listpointer -> dataitem = data;
 return lp;
    }
    else {
 listpointer = (struct listelement  *) malloc (sizeof (listelement));
 listpointer -> link = NULL;
 listpointer -> dataitem = data;
 return listpointer;
    }
}

listelement * RemoveItem (listelement * listpointer) {

    listelement * tempp;
    printf ("Element removed is %d\n", listpointer -> dataitem);
    tempp = listpointer -> link;
    free (listpointer);
    return tempp;
}

void PrintQueue (listelement * listpointer) {

    if (listpointer == NULL)
 printf ("queue is empty!\n");
    else
 while (listpointer != NULL) {
     printf ("%d\t", listpointer -> dataitem);
     listpointer = listpointer -> link;
 }
    printf ("\n");
}

void ClearQueue (listelement * listpointer) {

    while (listpointer != NULL) {
 listpointer = RemoveItem (listpointer);
    }
}

Exercises

Exercise 12456
Write a program that reads a number that says how many integer numbers are to be stored in an array, creates an array to fit the exact size of the data and then reads in that many numbers into the array.
Exercise 12457
Write a program to implement the linked list as described in the notes above.
Exercise 12458
Write a program to sort a sequence of numbers using a binary tree (Using Pointers). A binary tree is a tree structure with only two (possible) branches from each node (Fig. 10.1). Each branch then represents a false or true decision. To sort numbers simply assign the left branch to take numbers less than the node number and the right branch any other number (greater than or equal to). To obtain a sorted list simply search the tree in a depth first fashion.
 
Fig. 10.1 Example of a binary tree sort Your program should: Create a binary tree structure. Create routines for loading the tree appropriately. Read in integer numbers terminated by a zero. Sort numbers into numeric ascending order. Print out the resulting ordered values, printing ten numbers per line as far as possible.
Typical output should be
The sorted values are:
     2  4  6  6  7  9 10 11 11 11
    15 16 17 18 20 20 21 21 23 24
    27 28 29 30

Pointers

  Pointer are a fundamental part of C. If you cannot use pointers properly then you have basically lost all the power and flexibility that C allows. The secret to C is in its use of pointers. C uses pointers a lot. Why?:
  • It is the only way to express some computations.
  • It produces compact and efficient code.
  • It provides a very powerful tool.
C uses pointers explicitly with:
  • Arrays,
  • Structures,
  • Functions.
NOTE: Pointers are perhaps the most difficult part of C to understand. C's implementation is slightly different DIFFERENT from other languages.

What is a Pointer?

A pointer is a variable which contains the address in memory of another variable. We can have a pointer to any variable type.
The unary or monadic operator & gives the ``address of a variable''.
The indirection or dereference operator * gives the ``contents of an object pointed to by a pointer''.
To declare a pointer to a variable do:
   int *pointer;
NOTE: We must associate a pointer to a particular type: You can't assign the address of a short int to a long int, for instance.
Consider the effect of the following code:


   int x = 1, y = 2;
   int *ip;
 
   ip = &x;
 

y = *ip;
 

x = ip;
 

   *ip = 3;
It is worth considering what is going on at the machine level in memory to fully understand how pointer work. Consider Fig. 9.1. Assume for the sake of this discussion that variable x resides at memory location 100, y at 200 and ip at 1000. Note A pointer is a variable and thus its values need to be stored somewhere. It is the nature of the pointers value that is new.
 
Fig. 9.1 Pointer, Variables and Memory Now the assignments x = 1 and y = 2 obviously load these values into the variables. ip is declared to be a pointer to an integer and is assigned to the address of x (&x). So ip gets loaded with the value 100.
Next y gets assigned to the contents of ip. In this example ip currently points to memory location 100 -- the location of x. So y gets assigned to the values of x -- which is 1.
We have already seen that C is not too fussy about assigning values of different type. Thus it is perfectly legal (although not all that common) to assign the current value of ip to x. The value of ip at this instant is 100.
Finally we can assign a value to the contents of a pointer (*ip).
IMPORTANT: When a pointer is declared it does not point anywhere. You must set it to point somewhere before you use it.
So ...

   int *ip;
 
   *ip = 100;

will generate an error (program crash!!).
The correct use is:


   int *ip;
   int x;
 
   ip = &x;
   *ip = 100;
We can do integer arithmetic on a pointer:


   float *flp, *flq;
 
   *flp = *flp + 10;
 
   ++*flp;
 
   (*flp)++;
 
   flq = flp;
NOTE: A pointer to any variable type is an address in memory -- which is an integer address. A pointer is definitely NOT an integer.
The reason we associate a pointer to a data type is so that it knows how many bytes the data is stored in. When we increment a pointer we increase the pointer by one ``block'' memory.
So for a character pointer ++ch_ptr adds 1 byte to the address.
For an integer or float ++ip or ++flp adds 4 bytes to the address.
Consider a float variable (fl) and a pointer to a float (flp) as shown in Fig. 9.2.
 
Fig. 9.2 Pointer Arithmetic Assume that flp points to fl then if we increment the pointer ( ++flp) it moves to the position shown 4 bytes on. If on the other hand we added 2 to the pointer then it moves 2 float positions i.e 8 bytes as shown in the Figure.

Pointer and Functions

Let us now examine the close relationship between pointers and C's other major parts. We will start with functions.
When C passes arguments to functions it passes them by value.
There are many cases when we may want to alter a passed argument in the function and receive the new value back once to function has finished. Other languages do this (e.g. var parameters in PASCAL). C uses pointers explicitly to do this. Other languages mask the fact that pointers also underpin the implementation of this.
The best way to study this is to look at an example where we must be able to receive changed parameters.
Let us try and write a function to swap variables around?
The usual function call:

    swap(a, b)   WON'T WORK.

Pointers provide the solution: Pass the address of the variables to the functions and access address of function.

Thus our function call in our program would look like this:

    swap(&a, &b)

The Code to swap is fairly straightforward:

    void swap(int *px, int *py)
 
      { int temp;
 
     temp = *px;
     /* contents of pointer */ 
 
     *px = *py;
     *py = temp;
   }

We can return pointer from functions. A common example is when passing back structures. e.g.:


typedef struct {float x,y,z;} COORD;
 
   main()
 
    {  COORD p1, *coord_fn();
      /* declare fn to return ptr of
       COORD type */ 
 
       ....
       p1 = *coord_fn(...);
     /* assign contents of address returned */
       ....
     }


   COORD *coord_fn(...)
 
    {  COORD p;
 
       .....
       p = ....;
       /* assign structure values */ 
 
       return &p;
       /* return address of p */
     }
Here we return a pointer whose contents are immediately unwrapped into a variable. We must do this straight away as the variable we pointed to was local to a function that has now finished. This means that the address space is free and can be overwritten. It will not have been overwritten straight after the function ha squit though so this is perfectly safe.

Pointers and Arrays

Pointers and arrays are very closely linked in C.

Hint: think of array elements arranged in consecutive memory locations.

Consider the following:

   int a[10], x;
   int *pa;
 
   pa = &a[0];  /* pa pointer to address of a[0] */
 
   x = *pa;
   /* x = contents of pa (a[0] in this case) */

 
Fig. 9.3 Arrays and Pointers
To get somewhere in the array (Fig. 9.3) using a pointer we could do:

   pa + i $\equiv$ a[i]

WARNING: There is no bound checking of arrays and pointers so you can easily go beyond array memory and overwrite other things.

C however is much more subtle in its link between arrays and pointers.

For example we can just type

   pa = a;

instead of

   pa = &a[0]

and

   a[i] can be written as *(a + i).
i.e. &a[i] $\equiv$ a + i.

We also express pointer addressing like this:

   pa[i] $\equiv$ *(pa + i).

However pointers and arrays are different:
  • A pointer is a variable. We can do
    pa = a and pa++.
  • An Array is not a variable. a = pa and a++ ARE ILLEGAL.
This stuff is very important. Make sure you understand it. We will see a lot more of this.

We can now understand how arrays are passed to functions.

When an array is passed to a function what is actually passed is its initial elements location in memory.

So:

   strlen(s) $\equiv$ strlen(&s[0])

This is why we declare the function:

     int strlen(char s[]);

An equivalent declaration is : int strlen(char *s);
since char s[] $\equiv$ char *s.

strlen() is a standard library function (Chapter 18) that returns the length of a string. Let's look at how we may write a function:

   int strlen(char *s)
     { char *p = s;
 
     while (*p != `${\backslash}0$);
       p++;
     return p-s;
     }

Now lets write a function to copy a string to another string. strcpy() is a standard library function that does this.

   void strcpy(char *s, char *t)
     {  while ( (*s++ = *t++) != `${\backslash}0$);}


This uses pointers and assignment by value.

Very Neat!!

NOTE: Uses of Null statements with while.

Arrays of Pointers

We can have arrays of pointers since pointers are variables.

Example use:

Sort lines of text of different length.

NOTE: Text can't be moved or compared in a single operation.

Arrays of Pointers are a data representation that will cope efficiently and conveniently with variable length text lines.

How can we do this?:
  • Store lines end-to-end in one big char array (Fig. 9.4). $\backslash$n will delimit lines.
  • Store pointers in a different array where each pointer points to 1st char of each new line.
  • Compare two lines using strcmp() standard library function.
  • If 2 lines are out of order -- swap pointer in pointer array (not text).
 
Fig. 9.4 Arrays of Pointers (String Sorting Example)
This eliminates:
  • complicated storage management.
  • high overheads of moving lines.

Multidimensional arrays and pointers

We should think of multidimensional arrays in a different way in C:

A 2D array is really a 1D array, each of whose elements is itself an array

Hence

  a[n][m] notation.

Array elements are stored row by row.

When we pass a 2D array to a function we must specify the number of columns -- the number of rows is irrelevant.

The reason for this is pointers again. C needs to know how many columns in order that it can jump from row to row in memory.

Considerint a[5][35] to be passed in a function:

We can do:

   f(int a[][35]) {.....}

or even:

   f(int (*a)[35]) {.....}

We need parenthesis (*a) since [] have a higher precedence than *

So:

   int (*a)[35]; declares a pointer to an array of 35 ints.

   int *a[35]; declares an array of 35 pointers to ints.

Now lets look at the (subtle) difference between pointers and arrays. Strings are a common application of this.

Consider:
   char *name[10];
   char Aname[10][20];

We can legally do name[3][4] and Aname[3][4] in C.
However
  • Aname is a true 200 element 2D char array.
  • access elements via
       20*row + col + base_address
    in memory.
  • name has 10 pointer elements.
NOTE: If each pointer in name is set to point to a 20 element array then and only then will 200 chars be set aside (+ 10 elements).

The advantage of the latter is that each pointer can point to arrays be of different length.

Consider:


   char *name[] = { ``no month'', ``jan'',
    ``feb'', ... };
   char Aname[][15] = { ``no month'', ``jan'',
    ``feb'', ... };
 
Fig. [*] 2D Arrays and Arrays of Pointers

Static Initialisation of Pointer Arrays

Initialisation of arrays of pointers is an ideal application for an internal static array.

some_fn()
    { static char *months = { ``no month'',
       ``jan'', ``feb'',
       ...};
 
     }

static reserves a private permanent bit of memory.

Pointers and Structures

These are fairly straight forward and are easily defined. Consider the following:


   struct COORD {float x,y,z;} pt;
   struct COORD *pt_ptr;
 

pt_ptr = &pt; /* assigns pointer to pt */
the $-\!\gt$ operator lets us access a member of the structure pointed to by a pointer.i.e.:
   pt_ptr$-\!\gt$x = 1.0;
   pt_ptr$-\!\gt$y = pt_ptr$-\!\gt$y - 3.0;


Example: Linked Lists


  typedef struct {  int value;
       ELEMENT *next;
     } ELEMENT; 
 

ELEMENT n1, n2;
 

n1.next = &n2;
 
Fig. [*] Linking Two Nodes NOTE: We can only declare next as a pointer to ELEMENT. We cannot have a element of the variable type as this would set up a recursive definition which is NOT ALLOWED. We are allowed to set a pointer reference since 4 bytes are set aside for any pointer.
The above code links a node n1 to n2 (Fig. 9.6) we will look at this matter further in the next Chapter.

Common Pointer Pitfalls

Here we will highlight two common mistakes made with pointers.

Not assigning a pointer to memory address before using it


  int *x;
 
   *x = 100;
 
we need a physical location say: int y;
 
   x = &y;
   *x = 100;

This may be hard to spot. NO COMPILER ERROR. Also x could some random address at initialisation.

Illegal indirection

Suppose we have a function malloc() which tries to allocate memory dynamically (at run time) and returns a pointer to block of memory requested if successful or a NULL pointer
otherwise.

  char *malloc() -- a standard library function (see later).

Let us have a pointer: char *p;

Consider:

  *p = (char *) malloc(100);    /* request 100 bytes of memory */

  *p = `y';

There is mistake above. What is it?


No * in
   *p = (char *) malloc(100);

Malloc returns a pointer. Also p does not point to any address.

The correct code should be:

   p = (char *) malloc(100);

If code rectified one problem is if no memory is available and p is NULL. Therefore we can't do:
   *p = `y';.

A good C program would check for this:

  p = (char *) malloc(100);
   if ( p == NULL)
     { printf(``Error: Out of Memory $\backslash$n'');
       exit(1);
     }
   *p = `y';

Exercise

Exercise 12453
Write a C program to read through an array of any type using pointers. Write a C program to scan through this array to find a particular value.
Exercise 12454
Write a program to find the number of times that a given word(i.e. a short string) occurs in a sentence (i.e. a long string!).
Read data from standard input. The first line is a single word, which is followed by general text on the second line. Read both up to a newline character, and insert a terminating null before processing.
Typical output should be:
The word is "the".
        The sentence is "the cat sat on the mat".
       The word occurs 2 times.
Exercise 12455
Write a program that takes three variable (a, b, b) in as separate parameters and rotates the values stored so that value a goes to be, b, to c and c to a.