CProjects   

You may work solo or with a partner. If you pair-program:

Goals and Resources

The goals of this exercise are to:

The following C resources might complement the videos well.

Program 1: Nested Loops (expressions, logic, functions)

(15 pts) Be sure to check out the CNestedLoops project into your Eclipse C workspace, not your Java workspace. This will require connecting to your repository again in the new workspace, using the SVN Repository Exploring perspective. Recall that your individual SVN repository is at the URL:

http://svn.csse.rose-hulman.edu/repos/csse221-201110-username

If you are working with a partner, your pair repository name is listed here instead.

  1. Edit the initial comment to include your name and today's date. Look at the function rectangleOfStars. Make sure you understand how it works. Ask for help if you're confused.

    Note: You may assume that the functions that print numbers will only be given one-digit numbers as their "highest number to print" actual parameters. Otherwise, some of the output formatting would be very tricky.
  2. (5 points) Write the function, triangleAllNumsEachRow For example: 
    triangleAllNumsEachRow(6);
    should produce the output: 
    1
12
123
1234
12345
123456
  3. (10 points) The next function, triangleNumsCentered, prints a triangle that is centered and includes spaces. For example: 
    triangleNumsCentered(9);
    should produce the output: 
            1 
       2 2 
      3 3 3 
     4 4 4 4 
    5 5 5 5 5 
   6 6 6 6 6 6 
  7 7 7 7 7 7 7 
 8 8 8 8 8 8 8 8 
9 9 9 9 9 9 9 9 9

    4. Commit your work.

Program 2: PerfectNumbers (expressions, statements, functions)

(20 points) Check out the ThatsPerfect project into your Eclipse C workspace, not your Java workspace. In the source file perfect.c, edit the initial comment to include your name and today's date. A perfect number is one that is the sum of its factors that are smaller than itself (including 1). For example, 6 and 28 are perfect because 1+2+3=6 and 1+2+4+7+14=28. But 24 is not perfect because 1+2+3+4+6+8+12 is not 24. Define a function: 

    int isPerfect(int n)
that returns 1 if n is perfect and 0 if it is not perfect. Do not attempt to find a closed-form solution. Instead, actually compute the factors of n and add them together. Create a while loop in main() that will keep asking the user for numbers to check for perfection, and prints an appropriate response, until they enter a negative number to quit. A sample run of the program might be: 
	Enter an integer (negative to quit): 6
	6 is perfect.

	Enter an integer (negative to quit): 24
	24 is not perfect.

	Enter an integer (negative to quit): 28
	28 is perfect.

	Enter an integer (negative to quit): -1
	Goodbye!
The first two perfect numbers are 6 and 28. Modify your program so that after the interactive part, but before exiting, it calculates and prints out the fourth perfect number.

Note: In case you are wondering about the doublingInt() and doublingDouble() functions, they demonstrate overflow of ints and doubles. The curious among us may want to investigate these questions: (1) What's the largest int produced by doublingInt() before it overflows? (2) How many times can the value 1.0 be doubled before exceeding the maximum expressible double value? (You can edit the doublingDouble() function to count. These will not be graded.)
 

Program 3: Pointers (Day 26 in-class)

  1. Please complete the PointerPitfalls assignment
  2. Using Eclipse, checkout the PointersHomework project from your individual SVN repository into your Eclipse C workspace. You  will need to do more analysis than coding. As such, you will type out short answers to many questions in homework.txt and save your answers in your repository, and will draw two box-and-pointer diagrams to hand in next class. (5 pts for diagrams and 20 pointers total for code and typed answers)
    1. Open homework.txt and add your name to it.
    2. Pointers and Output
      1. Look at main.c's basicPointers() function, but don't run it yet.
      2. (2 pts) On paper, draw a box-and-pointer diagram, like we did in class on an early slide, for the code in the basicPointers() function. Make sure you diagram everything in the function.
      3. (2 pts) Predict the output of basicPointers() BEFORE RUNNING IT and write it in homework.txt.
      4. We will give you full credit for any reasonable guess, so don't go back and change your answer after you run it!
      5. (2 pts) Now uncomment the call to basicPointers() and run it to see the actual output. Were you right? If not, explain what you learned from this.
      6. If you think your original box-and-pointer diagram was incorrect, please correct it.
      7. Look at main.c's everybodyUp() function, but don't run it yet.
      8. (3 pts) On paper, draw a box-and-pointer diagram, like we did in class on an early slide, for the call to the everybodyUp() function and the code in it.
      9. (2 pts) Predict the output of everybodyUp() BEFORE RUNNING IT.
      10. We will give you full credit for any reasonable guess, so don't go back and change your answer after you run it!
      11. (2 pts) Now uncomment the call to everybodyUpTest() and run it to see the actual output. Were you right? If not, explain what you learned from this.
      12. If you think your original box-and-pointer diagram was incorrect, please correct it.
      13. Have an instructor or assistant check the two box-and-pointer diagrams you created above.
    3. Writing Functions
      1. (5 pts) In main.c, write and test a function called doubleMe that doubles the integer value passed to it. The doubleMe function had been called using doubleMe(num); you'll need to change it to pass the address instead to make it work correctly with your function.
    4. Scanf
      1. (2 pts) Now that you have worked with pointers, you can understand scanf better. Recall that we need to pass to scanf the addresses of the variables we are getting from the user. Why do we need to do this? (Hint: what would happen if scanf didn't use pointers?)
      2. (2 pts) Try omitting the & when you call scanf. What happens?
    5. Pointer Pitfalls
      1. (3 pts) Explain what's wrong with this code. (You may run it to check after you think about it.) 
        float *ptr = 0;
printf("%4.2f\n", *ptr);
    6. Commit your modified versions of main.c and homework.txt to the repository. Bring the paper with your two box-and-pointer diagrams to your next class.

    Program 4: SelectionSort (pointers and arrays)

    (15 pts) I presented the selection sort algorithm in class. Here, I would like you to create an array filled with random integers between 0 and RAND_MAX (defined in stdlib.h), and sort them using selection sort. Check out the SelectionSort project. Do this by writing the function 
    void selectionSort(int ar[], int size)

    The size of the array should be defined (using #define) in your file, and should be set to 100 elements.

    Print the array before being sorted (all 100 numbers on one line) and after being sorted (all 100 numbers on a second line) to test your function.

    You can get random numbers between 0 and RAND_MAX by calling rand() (in stdlib.h). This will produce the same results every time, which is good for debugging. However, if you want them to be different every time, you need to seed the random number generator once at the start of your program by calling srand(time(NULL));  (time() is defined in time.h, surprise, surprise).

    You should make use of an auxiliary swap function with a prototype like you saw in the video (there is no reason to use the array version required in Java): 

    void swap(int* x, int* y);

    Program 5: String Functions (strings and C libraries)

    1. You must do this assignment using Eclipse and the StringFunctions project that you checked out from your individual SVN repository in class.

    2. In the source file string-functions.c, edit the initial comment to include your name and today's date.

    3. (30 pts) Stubs for the 6 functions below have been provided for you in string-functions.c. The file also contains short specifications of each function as comments. For each, write thorough tests and complete the function definitions. You might want to use the functions declared in the ctype.h and string.h headers in your solution. Be sure to commit to your repository as you finish each function; that will help us to award credit for each function that you finish.

      • stringLength (you should have done this in a video)
      • firstWord (do this if you didn't watch the optional video; but you don't need to do CamelCase)
      • capitalize
      • capWords
      • reverse
      • strip 

      When your code is working, commit it to your repository.

    Program 6: LinkedListBasic (structures, pointers and memory allocation)

    A linked list consists of a sequence of nodes. Each node in a singly-linked list has two parts: (a) data, and (b) a "next node'' pointer (see Figure 1). The last node in the list (if such a node exists, i.e. if the list is not empty) has no node following it, hence its next node pointer is null. Using the next node pointers, it is possible to traverse the entire linked list and thereby access each node.

    Figure 1: Structure of a linked list.
    \framebox{\includegraphics[width=4in]{linked_list}}

    A basic linked list consists of a "first" pointer ("head" in the diagram) that points to the first node if it exists, and is null otherwise; and a "last" pointer (not shown) that points to the last node in the list.

    Start by checking out the LinkedListBasic Project (containing the header file and driver) from the public repository and committing it to your personal repository.

    For this assignment, you are to implement all of the functions given in LinkedListBasic.h. There are many functions of varying difficulty. Some require recursion. Some have special cases that you must handle. For any requiring deletion, you must practice good memory management and free the deleted nodes.

    You may not change the header file, since splitting code up into an interface and an implementation ("separate compilation") occurs in real life. To enforce this, I will copy in a new version of the header file when I test your code.

    You may use the code in LinkedListBasic.c to help test your program. You may add other tests as well. I reserve the right to add more tests.

    Additional note about reverse:

    To get full credit, you must not create nor destroy any nodes. The addresses of each node must not change. All you are doing is reversing the direction of the pointers. Have fun!

    Program 7: LinkedListEnhanced

    There are a number of enhancements we can make to our linked list class to cause it to work more efficiently or to remove special cases:
    1. Doubly-link it. Each node in a doubly-linked list also contains a "previous node'' pointer (not shown). If there is a first node, then its previous node pointer is null. This will make removing nodes easier, since you won't have to keep track of the previous node as you walk through the list.
    2. Include dummy nodes before the first node and after the last node. (These are called "head" and "tail" nodes.) This will remove special cases that occur when you are inserting into an empty list, or removing the last node from a list.
    3. Include and maintain a size field in the list structure, so that you don't need to recompute the size every time you need it. This will also make your life easier when catching out-of-bounds exceptions with setAt(), insertAt(), and removeAt().

    Start by checking out the LinkedListEnhancedUseThis project from your repository.

    Again, you must implement all the functions in the header. You will probably need to make minor changes to most of the functions you wrote for the basic version to get them to work. Note that some functions will be substantially easier than they were with the basic version, because of fewer special cases. Finally, you don't need to write both an iterative and a recursive version of reverse; just do one (your choice).

    Make sure all your projects are committed to your repository!