Arrays and Pointers in C


Your assignment must be submitted electronically by 11:59pm on Wednesday, September 27 Friday, September 29.


In this lab, we will focus on bubble sort of character strings. You are to implement three different versions of the bubble sort algorithm. Please read the descriptions of each carefully, and implement each using the starter files provided.

Relevant readings:


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:

Compile and run your program on inputs of your choice, and also make sure it runs correctly on the sample inputs provided. Refer to the sample inputs and outputs provided on exactly how to format your I/O.


Exercise 2

Repeat the above exercise (copy ex1.c to ex2.c), but this time use C string library functions to simplify the code of the bubble sort. Name the file containing your code ex2.c. Compile and run your program on inputs of your choice, and also make sure it runs correctly on the sample inputs provided.


Exercise 3

For this exercise, you will implement string bubble sort by explicitly using pointers instead of arrays. In particular, you will implement the data structure as a 1-dimensional array of character pointers, char* Strings[NUM]. Thus, the index into the data structure yields a pointer, e.g., Strings[i] gives you the i-th pointer (of type char*). Strings[i][j] will, in turn, give you the j-th character of the i-th string.

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 P&M Ch. 26; and the online C reference for malloc/free in stdlib.h). The C function 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 something 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 */
Note: If you wanted to use a data type that is bigger than a single byte, use the sizeof() operator to determine the size in bytes:

        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:

Name the file containing your code ex3.c. Compile and run your program on inputs of your choice, and also make sure it runs correctly on the sample inputs provided.


Test Inputs, Due Date and Submission Procedure

Reminder: Before beginning work, it is generally a good idea to run the following command so your terminal environment is set up properly:

% /home/montek/comp411/bin/comp411start

Sample inputs and corresponding outputs are provided under /home/montek/comp411/samples/lab4. You should try running your program on the sample input files provided, and make sure the program's output is identical to that in the sample output files.

Your assignment must be submitted electronically by 11:59pm on Wednesday, September 27 Friday, September 29.

You will submit your work on Exercises 1-3, specifically, the files ex1.c, ex2.c and ex3.c.

How to submit: Navigate to the folder where these files are stored (~/comp411lab/lab4), and run the following command for running a self-checking script (which does not submit the files):

% cd ~/comp411lab/lab4
% /home/montek/comp411/bin/selfchecklab4

If the self-check did not report any errors, you can submit your work as follows:

% cd ~/comp411lab/lab4
% /home/montek/comp411/bin/submitlab4

When you invoke the submit script, it submits your files, and once again performs a quick check on your source files (including compiling, running and comparing the output of your program with the expected output, for all sample input/output files), and provides a quick summary of any errors. Your work is submitted regardless of whether errors were found or not, but you are free to fix any errors and submit again before the due date.

In case of any problems, please contact the instructor or the TAs.


Revised: 25 September 2005, f.mokhtarian@surrey.ac.uk
Revised: 1 February 2017 and 21 September 2017, Montek Singh, montek@cs.unc.edu