CSC 180
Notes for Tutorial #10

Monday 18  November  

Wednesday 20 November  


SUMMARY OF THE TOPICS
 1. Example using 2d arrays and arrays of pointers
 2. Example program using strings.

1. Example using 2d arrays and arrays of pointers
==================================================

In lectures you have seen that 2-d arrays are stored in memory
in a row-wise fashion, with one row following another, as in the 
following picture:

   int A[5][8];

   A[0][0] A[0][1]  ...  A[0][7] A[1][0] ... A[1][7] ... A[4][0] ... A[4][7]
   ------- ------- ----- ------- ------- --- ------- --- ------- --- ------- 
  |       |       | ... |       |       |   |       |   |       |   |       |
   ------- ------- ----- ------- ------- --- ------- --- ------- --- ------- 
   <---- first row ------------> <-- second row ---> ... <--- fifth row --->

We saw that when we passed 2d arrays to functions, we also had to use the
declared column length of the 2d array in the function declaration.  To
pass the array A to a function f, we would have to declare f as:

   int f( int M[][8], int ... )

This is most annoying, as one would like to be able to write one function
that works for all 2d arrays.

(Some compilers will allow you to write:
   int f( int nr, int nc, int M[nr][nc] )
where the parameters nr and nc represent the declared dimension lengths
for the 2-d parameter -- but this is not legal according to the ANSI standard.
So if you write your program to use this feature, it may not work with
other compilers on other machines.  It is best to not write your program
this way.)

Why does the function f() need to know the declared number of columns
of the matrix?  Because it is only passed a pointer to a pointer to A[0][0].
To determine the location of element A[3][2], say, the function f()
needs to know the length of each row of A.  In the above picture,
where there are 8 columns, the element A[3][2] is 3*8 + 2 integers
away from A[0][0].  And f() knows how to find A[0][0].

In general, then, element A[i][j] is 
    i*<the declared number of columns in a> + j
integers after A[0][0].

This suggests that the function could treat the array as a 1 dimensional
array, and calculate the indices explicitly through pointer arithmetic.  
This is in fact often done in C programs.

The following program prints a 3-by-4 2d array, but processes it 
as if it were a 1-d array:

#include <stdio.h>
void printArray( int M[][], int nr, int nc )
{
    int i, j;
    for ( i=0; i<nr; i++ ) {
        for ( j=0; j<nc; j++ ) {
            printf(" %d ", *(*M + i*nc + j));
        }
        printf("\n");
    }
}

int main()
{
    int A[3][4] = { {11,12,13,14}, {21,22,23,24}, {31,32,33,34} };
    printArray( A, 3, 4 );
    return 0;
}
        

Pay special attention to how the matrix M is accessed in the function.

   M is a pointer to M[0][0]  (which is a pointer to A[0][0] as a result
                               of the function call)

  *M is also a pointer to M[0]

and **M is the value of the element M[0][0] !

(We could have also written
    (*M + i*nc)[j]
in place of 
    *(*M + i*nc + j)
but that may look even more confusing!)
    
--------------------

Note that although the 2-d array  M  is thought of as an array
of arrays, pointers are not kept to the start of each individual
row.  The only pointer is the pointer to the upper-left element,
the [0][0] element.

--------------------

This last comment hints at another approach to accessing 2-d arrays
that have been passed to functions.   We can setup an additional
1d array of pointers, with each element in the array pointing to the
start of a row. 

For example, we could declare

  int A[3][4] = { {11,12,13,14}, {21,22,23,24}, {31,32,33,34} };
and then
  int *Aptr[3] = { A[0], A[1], A[2] };
   /* remember that A[i] is thought of as a pointer to the row i of A[][] */
   /* so we initialize to A[0], etc, not &A[0] . */


A print array function could then be written as:
void printPtrArray( int *M[], int nr, int nc )
{
    int i, j;
    for ( i=0; i<nr; i++ ) {
        for ( j=0; j<nc; j++ ) {
            printf(" %d ", M[i][j]);
        }
        printf("\n");
    }
}

At the cost of keeping an extra 1d array of pointers, we are able to
write a print function that is a little easier to understand.

----------------

2. Example program using strings.
=================================

Now that you know about character strings, your interactive
programs can ask your users to enter text responses instead
having them enter numerical codes, which your program 
would have to interpret appropriately.

In this example, you will write a small program that prompts
the user for two words, and determines whether or not the first
word is contained in the second word.  The program will continue
matching first and second words until the first word is "quit".

For example, the function should return TRUE when applied to the 
words  "dog" and "boondoggle", because the second word contains "dog".

What would the basic program look like?

Since it may not be obvious how to determine whether or not
one word contains another, lets start by writing the main part
of the program:

Basically, we want to do:

  read a word,
  repeat as long as the word was not quit
      read another word and see if it contains the first word,
      read a new first word
  end repeat

Let's implement this part.  Since we know about the fgets function now,
(from Ch 22 of the text) we should use it instead of scanf, just in case 
some user gives us a word that is longer than our character string array.
And we can use the sscanf() function to extract the word from the input 
string.

<TAs:  Please work through the following implementation. >

#include <stdio.h>
#include <strings.h>   /* Yes, there are two string libraries! */
#include <string.h>
#define MAX_WORD_LENGTH 512
#define TRUE 1
#define FALSE 0

/* prototype for the as yet unwritten function */
int firstPartofSecond( char w1[], char w2[] );

int main()
{
    char stringOne[MAX_WORD_LENGTH], stringTwo[MAX_WORD_LENGTH];
    char wordOne[MAX_WORD_LENGTH], wordTwo[MAX_WORD_LENGTH];

    printf("Please enter a word (\"quit\" to stop) : ");
    fgets( stringOne, MAX_WORD_LENGTH, stdin );
    /* in case the user entered more than one word, extract
       the first word from the string that was entered.    */
    sscanf( stringOne, "%s", wordOne );
    printf("Your first word is %s\n", wordOne);

    while( strcasecmp(wordOne, "quit") != 0 ) {
      /* the strcasecmp function compares strings independent of case. */
        printf("Please enter a second word : ");
        fgets( stringTwo, MAX_WORD_LENGTH, stdin );
        sscanf( stringTwo, "%s", wordTwo );
        printf("Your second word is %s\n", wordTwo);

        if ( firstPartOfSecond( wordOne, wordTwo ) ) {
            printf("Yes, %s is contained in %s.\n", wordOne, wordTwo );
        } else {
            printf("No, %s is not contained in %s.\n", wordOne, wordTwo );
        }
   
        /* get next words */
        printf("Please enter a new word (\"quit\" to stop) : ");
        fgets( stringOne, MAX_WORD_LENGTH, stdin );
        sscanf( stringOne, "%s", wordOne );
        printf("Your first word is %s\n", wordOne);
    }
    return 0;
}


----------


Now we need to determine whether or not the first word falls in the 
second.   Fortunately, there is a string function called "strstr"
that locates the first occurrence of one string in another.  The 
prototype for strstr is:

  char *strstr(const char *haystack, const char *needle);

The  strstr()  function  finds the first occurrence of the
substring needle in the string haystack.  The  terminating
`\0' characters are not compared.

The  strstr()  function returns a pointer to the beginning
of the substring, or NULL if the substring is not found.

Hence our firstPartOfSecond function can simply return whether 
or not the strstr() function returns a null pointer when asked
to find wordOne in wordTwo.

We can write:

int firstPartOfSecond( char w1[], char w2[] ) {
    return (strstr( w2, w1 ) != NULL );
}


<TAs:  In any remaining time, do more string examples, if you like.
For example, you could show them how the strstr() function could
be implemented.  (Basically, a search for the first character of
needle in haystack, and then a charcter by character comparison of
the remaining letters.) >