The Questions

1. You will need these files:

   • printArray.o
   • insert.o
   • delete.o
   • input00
   • output00

   The printArray.o file holds a function called printArray. Here is its prototype:

   /*
   A - the "partially filled" array of ints.
   capacity - the declared capacity of the array
   count - the number of ints stored in the array
   
   Prints the array, showing the first count elements as ints
   and showing the "unfilled" elements as X.  For example,
   for an array with capacity 10 holding the 4 ints shown it would print this:
   [ -2 2 5 7 X X X X X X ]
   */
   void printArray(int *A, int capacity, int count);
   

   
   
   The insert.o file holds a function to insert into a partially filled array, while keeping it sorted and, where necessary, updating a count of the number of items stored in the array. Here is the function prototype:

   /*
   n - the integer to be inserted
   A - the array
   capacity - the declared capacity of the array.
   countPtr - pointer to an int holding the current number of
              elements stored in the array.  On insertion, this count is incremented.
   
   Inserts int n into "partially filled" array A.
   A is assumed to be sorted in non-decreasing order.
   n is inserted in such a way that A remains sorted.
   This may require shifting elements in A to make a space for n.
   If insertion would overflow the array, then no insertion is made,
   i.e. nothing happens.
   */
   void insert(int n, int *A, int capacity, int *countPtr);
   
   
   
   
   
   The delete.o file holds a function to delete an integer from a partially filled
   array, while keeping it sorted and, where necessary, updating a count of the number  
   of items stored in the array.  Here is the function prototype:
   /*
   n - the integer to be deleted from the array
   A - the array
   countPtr - pointer to an int holding the current number of
              elements stored in the array. On deletion, this count is decremented.
   
   Deletes the first occurrence of int n in the array,
   i.e. the first occurrence in the first *countPtr array elements.
   If n is not stored in the array, nothing happens.
   A is assumed to be sorted in non-decreasing order.
   n is deleted in such a way that A remains sorted.
   This may require shifting elements in A to fill the space formerly
   occupied by n.
   */
   void delete(int n, int *A, int *countPtr);
   

   
   
   

   Write a C program called q1.c. It should have a main() method, which starts like this:

   int main(void)
   {
       int arrayCapacity = 10;
       int maxCmdLength = 20;
   
       int A[arrayCapacity];
       int count = 0; /* how many ints stored in array A */
   
       char command[maxCmdLength + 1]; 
       int n;
       ...
   

   It will read from standard input and write to standard output. The input it reads will consist of
   <command> <integer>
   pairs like the following (see the file input00):

   insert  5
   insert 7
   insert 2
   sillyCommand 34
   insert 5
   insert -1
   insert 5
   insert 9
   insert 11
   insert 0
   insert 6
   insert 8
   insert 12
   
   delete    5
   delete 99
   hello   5
   delete     11
   delete 0
   delete 6
   

   Although this example doesn't show it, the insert and delete commands may be in any order; i.e. not all the delete commands need to come after the insert commands. They can be mixed.
   
   If the command is "insert", it attempts to insert the integer into array A, keeping A sorted.
   If the command is "delete", it attempts to delete the integer from array A, keeping A sorted
   Otherwise, the command and interger are just ignored.
   It does its inserts and deletes using the insert() and delete() functions in insert.o and delete.o. And it should print the array using the printArray function in printArray.o.
   
   More precisely, your program should
   • print the array before inserting anything (using printArray)
   then repeatedly
   • read the command and integer
   • if the command is insert or delete, call the appropriate function
   • print out the array (even for a bad command)
   For the input shown, your program should produce the following output (see the file output00):

   [ X X X X X X X X X X ]
   [ 5 X X X X X X X X X ]
   [ 5 7 X X X X X X X X ]
   [ 2 5 7 X X X X X X X ]
   [ 2 5 7 X X X X X X X ]
   [ 2 5 5 7 X X X X X X ]
   [ -1 2 5 5 7 X X X X X ]
   [ -1 2 5 5 5 7 X X X X ]
   [ -1 2 5 5 5 7 9 X X X ]
   [ -1 2 5 5 5 7 9 11 X X ]
   [ -1 0 2 5 5 5 7 9 11 X ]
   [ -1 0 2 5 5 5 6 7 9 11 ]
   [ -1 0 2 5 5 5 6 7 9 11 ]
   [ -1 0 2 5 5 5 6 7 9 11 ]
   [ -1 0 2 5 5 6 7 9 11 X ]
   [ -1 0 2 5 5 6 7 9 11 X ]
   [ -1 0 2 5 5 6 7 9 11 X ]
   [ -1 0 2 5 5 6 7 9 X X ]
   [ -1 2 5 5 6 7 9 X X X ]
   [ -1 2 5 5 7 9 X X X X ]
   

   Note: To use the insert(), delete() and printArray() functions you must compile your program like this:

   $ cc -Wall insert.o delete.o printArray.o q1.c
   

   You can test your program (a bit) as follows:

   $ a.out < input00 > temp
   $ diff temp output00
   $
   

   diff should return silently, if your program produced the correct output.

   Notes

   • You can assume that no command is longer than the maxCmdLength you have chosen (see start of main()) and that no input integer is too large to be stored in an int.
   • Do not call any sorting routine; the insert() and delete() functions should keep the arry sorted.
   • Try to use pointer notation only. The only array declarations should be the ones given above at the start of main() to declare the array called A and the one called command. To be clear: except for that, your code should not contain the [ ] operator.
   
   
   
2. Write a C program called q2.c. It should be used to replace insert.o. q2.c should not have a main() function, just the functions insert() as described above. You can copy and paste in the function header and comment. Then complete the function body.

   To compile q2.c by itself, you need to stop when the q2.o file is produced. You do this by using the -c flag, as in

   $ cc -Wall -c q2.c
   

   Or you can compile it together with q1.c, delete.o and printArray.o. Just replace insert.o in the old compile line with q2.c, as in

   $ cc -Wall q2.c delete.o printArray.o q1.c
   

   Or, if you've already compiled q2.c to get q2.o, you can use

   $ cc -Wall q2.o delete.o printArray.o q1.c
   

   Then, when you run the command

   $ a.out < input00
   

   you should get exactly the same results as before.

   Notes

   • You can assume that no command is longer than the maxCmdLength you have chosen (see start of main()) and that no input integer is too large to be stored in an int.
   • Do not call any sorting routine; the insert() and delete() functions should keep the arry sorted.
   • Try to use pointer notation only. The only array declarations should be the ones given above at the start of main() to declare the array called A and the one called command. To be clear: except for that, your code should not contain the [ ] operator.



3. Write a C program called q3.c. It should be used to replace delete.o. q3.c should not have a main() function, just the functions delete() as described above. You can copy and paste in the function header and comment. Then complete the function body.

   To compile q3.c by itself, you need to stop when the q3.o file is produced. You do this by using the -c flag, as in

   $ cc -Wall -c q3.c
   

   Or you can compile it together with q1.c, delete.o/q2.o and printArray.o. Just replace delete.o in the old compile line with q3.c, as in

   $ cc -Wall insert.o q3.c printArray.o q1.c
   

   Or, if you've already compiled q3.c to get q3.o, you can use

   $ cc -Wall insert.o q3.o printArray.o q1.c
   

   Then, when you run the command

   $ a.out < input00
   

   you should get exactly the same results as before.

   Notes

   • You can assume that no command is longer than the maxCmdLength you have chosen (see start of main()) and that no input integer is too large to be stored in an int.
   • Do not call any sorting routine; the insert() and delete() functions should keep the arry sorted.
   • Try to use pointer notation only. The only array declarations should be the ones given above at the start of main() to declare the array called A and the one called command. To be clear: except for that, your code should not contain the [ ] operator.