Arrays and Pointers in C

Exercise 1

For the first version, you will implement the primary data structure as a 2-dimensional array Strings[NUM][LEN], where NUM is the number of strings, and LEN is the maximum length allowed for the string: the first index i gives you the i-th string, and the second index j gives you the j-th character within that string. Using the starter file ex1.c, implement bubble sort of strings. Your code must strictly follow these specifications:

• Use fgets() to read each string from the input, one string per line. Use LEN as an argument to fgets() to ensure that an input line that is too long does not exceed the bounds imposed by the string's length. Note that the newline and NULL characters will be included in LEN, so the maximum number of printable characters in the string will actually be LEN-2.
• The comparison of two strings must be done by checking them one character at a time, without using any C string library functions. That is, write your own loop to do this.
• The swap of two strings must be done by copying them (using a temp variable of your choice) one character at a time, without using any C string library functions. That is, write your own loop to do this.

Exercise 2

• Add "#include <string.h>" near the top of the C file to tell the compiler that you will be using the C string library functions.
• Use the C function strcmp() to perform the comparison of two strings. Study this function carefully (see K&R, or the online C reference [under Strings/String Library Functions]). You may choose to use a similar function called strncmp() instead of strcmp() because the former also allows you to specify the maximum number of characters to check (e.g., for extra safety, or if only a first few characters are significant, etc.).
• Use the C function strcpy() to perform the copy of one string to another, in order to perform the swap of two strings (see K&R or the online C reference). Thus, you may use a temporary string variable and three calls to strcpy() to swap two strings. There is also a variant strncpy() which copies only a specified maximum number of characters.

Exercise 3

This behavior is superficially identical to that of Exercises 1 and 2, but the implementation of the data structure is quite different. A benefit of this approach is that it allows the programmer to define the length of strings at runtime, instead of fixing it during coding.

Study the malloc() and free() functions, which are part of the C standard library, and are used to allocate and free up, respectively, space in memory for a variable (see K&R, or the online C reference [under Data Structures/Memory Allocation]). malloc() is quite like the new operator in Java. Here is an example on how to use malloc() to allocate 57 bytes of memory for a string (of max length 56 plus one for the NULL terminating character):

        char* s;
        s = malloc(57);    /* allocate 57 bytes for s */
        puts("Enter a string:");
        fgets(s, 57, stdin);
        printf("You typed:\n%s\n", s);
        free(s);                   /* good practice to free up those 57 bytes so somebody else can use that space */

Observe that the following lines of code in C and Java are equivalent:

        char*  s = malloc(57);    /* in C */
        char[] s = new char[57];  /* in Java */

        float*  s = malloc(57*sizeof(float));  /* in C */
        float[] s = new float[57];             /* in Java */

In C, there is a free() function which frees up the memory allocated for a variable by malloc(). There is no such function in Java (the JVM does automatic garbage collection, and does not require the programmer to keep track of when a data structure is no longer needed). It is good practice to use free() to free up the memory that was used for a variable right before that variable is about to go out of scope, or otherwise lost to the program. Your program will still run correctly if you do not use free(), but it may start hogging memory unnecessarily, a frequent cause of "memory leaks" which often cause programs to bloat up during the course of their execution.

Using the starter file ex3.c, implement bubble sort of strings. Your code must strictly follow these specifications:

• Add "#include <stdlib.h>" near the top of the C file to tell the compiler that you will be using the C standard library (malloc is part of that library).
• Use malloc() to allocate only as much memory space as needed for each string read.
• In the main code fragment that performs the sort, the comparison of two strings must still be done by strcmp() or strncmp().
• The swap of two strings must be done by swapping pointer values. You must not swap two strings using strcpy()/strncpy() or using your own loop to swap them a character at a time.
• Add a loop near the end of the code to free() up space that was allocated for each of the strings.