This assignment focuses on pointer and array aspects of the C language. Although you will use the C++ compiler to compile your solutions, your code should not include any class definitions or constructors, but you will have C structures. Use malloc and free for heap memory allocation and de-allocation (we will get to new and delete in the next assignment).

1. Write a program that implements a simple singly linked list of integer values. Do this as a C program where all functions are global functions and without using C++ classes. (But you should still use the C++ compiler g++ to compile your code.) Write functions to initialize, add and remove values, and display the list of values. Provide a header file named ilist.h with the definition of the IntNode structure and declarations (not definitions) of the functions that manipulate the structure. The definitions of the functions should be provided in a source file named ilist.c.

   Your code should work with driver ilistTest.c, so you can use it as a guide for what functions to provide. This driver can also be used to test your implementation. For example, this driver would work as follows:

   % listTest 3 -4 5 19 1982 5 99 3 7 29 -2 5 28 4 5 3              
   3 -4 5 19 1982 5 99 3 7 29 -2 5 28 4
   After deleting the value 5, the list is
   3 -4 19 1982 99 3 7 29 -2 28 4
   Inserted 99 at position 0
   Inserted 999 at position 4
   Inserted 999 at position 13
   99 3 -4 19 999 1982 99 3 7 29 -2 28 4 9999
   After deleting the value 3, the list is
   99 -4 19 999 1982 99 7 29 -2 28 4 9999
   

   Note that the function to insert a value puts it at a position, where positions are counted beginning with zero.
   Make sure your clean up function recovers all memory that is allocated.

   ---

2. Implement functions to dynamically allocate and release two dimensional arrays of doubles that behave syntactically just like compile time declared two dimensional arrays. The interfaces to the functions should be as given in the following array2d.h:

   /*
    * Dynamic allocation of two dimensional arrays. The allocated
    * entity is typed as a pointer to pointer, and can be treated
    * just like a variable declared as a regular two dimensional array.
    */
   
   #ifndef _ARRAY_2D_H_
   #define _ARRAY_2D_H_
   
   #include <stdio.h>
   #include <stdlib.h>
   
   // Allocate a two dimensional array
   double ** array2dAlloc(int rows, int cols);
   
   // De-allocate a two dimensional array
   void array2dFree(double ** array);
   
   // Display a two dimensional array
   void array2dDisplay(double ** array, int rows, int cols);
   
   // Transpose a two dimensional array
   double ** array2dTranspose(double ** array, int rows, int cols);
   
   #endif
   

   Use the driver code array2dTest.c to test your implementation. Executing this program with values 3 and 7 should produce:

    0.5  1.5  2.5  3.5  4.5  5.5  6.5 
    7.5  8.5  9.5 10.5 11.5 12.5 13.5 
   14.5 15.5 16.5 17.5 18.5 19.5 20.5 
   
    0.1  1.1  2.1 
    3.1  4.1  5.1 
    6.1  7.1  8.1 
   
   

   Formatting hint: you can use printf("%5.1lf", x) to print a double value x with one digit after the decimal point, and padded to be at least 5 characters wide.

   ---

3. Add the array2dTranspose function to your solution of the previous problem. This function should return a new array (don't forget to release the existing one) with the dimensions reversed and the elements transposed. That is, the value in the i'th row and j'th column should appear in the j'th row and i'th column of the transposed result.

   You only need to turn in the code for your transpose function - the rest of your array2d functions should be the same.

   You can test by adding this code after the first call to array2dDisplay:

   array = array2dTranspose(array, rows, cols);
   array2dDisplay(array, cols, rows);
   

   and it will produce the following results for the 3 by 7 array:

    0.5  7.5 14.5 
    1.5  8.5 15.5 
    2.5  9.5 16.5 
    3.5 10.5 17.5 
    4.5 11.5 18.5 
    5.5 12.5 19.5 
    6.5 13.5 20.5 
   

   ---

4. Implement functions to dynamically allocate and release three dimensional arrays of doubles that behave syntactically just like compile time declared three dimensional arrays. Turn in the header file array3d.h with declarations of the functions and array3d.c with their implementations. The driver code array3dTest.c shows how these functions are used. Executing this program with values 2, 3 and 4 should produce:

     0.0  1.0  2.0  3.0
     4.0  5.0  6.0  7.0
     8.0  9.0 10.0 11.0
   
    12.0 13.0 14.0 15.0
    16.0 17.0 18.0 19.0
    20.0 21.0 22.0 23.0
   
   

   Hint: you can save yourself some work by using the two dimensional array implemented above.

   ---

5. Quicksort is a well known general sorting algorithm. It works by partitioning an array into big and little elements. That is, the elements are divided into two groups as they compare to a chosen "pivot" element, and this process is applied recursively until the array is completely sorted. An implementation of quicksort can be found in many texts. In their book, The Practice of Programming, Kernighan and Pike provide this simple quicksort implementation for an array of integer values.

   In this problem you are to generalize the quicksort code above in two ways:

   • Your generalization should have an additional argument passed to quicksort that is a function to compare values that are being sorted.
   • The dependence on the value type integer should be factored out and a symbolic type name VALTYPE should be used instead. This will allow the code to be easily adapted to other data types. Make sure you use VALTYPE in your implementation of the swap function as well as quicksort.

   The driver code quicksortTest.c gives examples of how to test your generalized implementation with C strings. Three different comparison functions on C strings are used in this test code. Note that VALTYPE is defined as a preprocessor symbol before quicksort.c is included. Note that to keep things simple, we are not using a separate header file for a prototype for quicksort. The complete implementation is contained in quicksort.c, and this file is directly included by the driver code. Thus, your implementation should be entirely in the file quicksort.c, which is the only code you will submit as your solution. Also note that this file will not compile by itself since a definition for VALTYPE is required.

   Here's how the code would work on some sample data:

   % quicksortTest abc dEf Ghi abd dab
   abc dEf Ghi abd dab 
   sorted by compare1: abc abd dab dEf Ghi 
   sorted by compare2: Ghi dEf dab abd abc 
   sorted by compare3: Ghi abc abd dEf dab 
   
   

   You can also test your implementation for integers. The driver quicksortTest2.c uses two comparison functions (regular comparison of ints and absolute value comparison). It will produce results:

   % quicksortTest2 19 -3 12 10 17 1 0 -5 11 -8
   19 -3 12 10 17 1 0 -5 11 -8 
   sorted by compare1: -8 -5 -3 0 1 10 11 12 17 19 
   sorted by compare2: 0 1 -3 -5 -8 10 11 12 17 19