CProjects

C Projects

The following C resources might be helpful.

This is an individual assignment. Feel free to ask questions of your instructor, student assistants and classmates as desired.

Goals

The goals of this exercise are to:

Gain practice coding simple algorithms using the C programming language.
Appreciate the differences between Java and C, including strings, pointers, and parameter passing.

The Exercise

This project consists of a number of small programs you are to write. Each will be described in turn.

Program 1: That's Perfect

Be sure to 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 -1 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.)

Program 2: SelectionSort

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. Create an Eclipse Project called SelectionSort. It must include 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 1000 elements.

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 auxilliary swap function with a prototype like we discussed in class (there is no reason to use the array version required in Java ):

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

Program 3: ArrayList (Pointers and dynamic memory allocation)

You should create a struct with related methods that simulates a simplified Java ArrayList. The struct should have as fields: a dynamically-sized array of integers, the size (current number of elements) of the array, and the capacity of the array (the max size before it must be resized; start with an initial capacity of 5). Write add(ar, element) to add an element to the back of the array, doubling the capacity when the array is filled. Also write getMemoryLocation(ar) to return the address of the internal array, and getSize(ar), and getCapacity(ar) functions.

Create a driver function that will read all the integers from a file and store them in the array. You may assume the file only contains integers. After each integer is read, you should print the memory address of the internal array, its current size, its current capacity, and the integer contents of the array (on a single line). You must display the contents of the array using pointer arithmetic, not array subscripting

For example, a run might look like:

stored at 003D3D80, with size = 1 and capacity = 5, contents = [3]
stored at 003D3D80, with size = 2 and capacity = 5, contents = [3,7]
stored at 003D3D80, with size = 3 and capacity = 5, contents = [3,7,8]
stored at 003D3D80, with size = 4 and capacity = 5, contents = [3,7,8,2]
stored at 003D3D80, with size = 5 and capacity = 5, contents = [3,7,8,2,4]
stored at 003D5DF0, with size = 6 and capacity = 10, contents = [3,7,8,2,4,0]
stored at 003D5DF0, with size = 7 and capacity = 10, contents = [3,7,8,2,4,0,12]
stored at 003D5DF0, with size = 8 and capacity = 10, contents = [3,7,8,2,4,0,12,4]
stored at 003D5DF0, with size = 9 and capacity = 10, contents = [3,7,8,2,4,0,12,4,4]
stored at 003D5DF0, with size = 10 and capacity = 10, contents = [3,7,8,2,4,0,12,4,4,7]
stored at 003D5E20, with size = 11 and capacity = 20, contents = [3,7,8,2,4,0,12,4,4,7,9]

BONUS: Write and make use of char* toString(ar) to print the array contents. As above, this function must be calculated using pointer arithmetic rather than subscripting. (It will produce output separated by commas, and delimited by brackets, just like Java's ArrayList.toString())

Program 4: Pig Latin

In this program, you will demonstrate your understanding of strings (character arrays), string library functions, string manipulation and pointers. Create an Eclipse Project called PigLatin. Your program should encode English language phrases into Pig Latin, using the dialect shown below.

Accept a whole phrase or sentence from the console using gets(char* buffer) (defined in stdio.h).
Tokenize the input phrase/sentence into individual words. Use the strtok function. You might find a description of C in the C resources to be helpful.
Convert each word to its Pig Latin equivalent. Use the following dialect: If the word starts with at least 1 consonant, place the first set of consonants of the English word at the end of the English word, and add the letters ``ay''. If it starts with a vowel, just append the letters, "yay" to the end of the word. For example, ``this is a string manipulation program'' will become ``isthay isyay ayay ingstray anipulationmay ogrampray'' You may consider y's always to be consonants. Store the pig-latinized words in some way so that you can print the pig-latinized sentence all at once later..
When finished processing the phrase/sentence, then print the entire Pig Latin equivalent to the console.
EASIER VERSION: You can print output to the console as you go. If you choose this option, your maximum grade on this problem will be a B.

You may assume that words in a phrase/sentence are delimited by spaces and all lower-case. Also, an input English phrase/sentence may contain no punctuation and all words have at least one vowel.

Program 5: LinkedListBasic

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.

You may not change the header file, since splitting code up into an interface and an implementation 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 driverBasic.c to help test your program. You may add other tests (I will).

Additional note about reverse:

To get full credit (the O(n) version), 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 6: 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:

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 ndoe as you walk through the list.
Include dummy nodes before the first node and after the last node. (These are called "header" and "trailer" nodes.) This will remove special cases that occur when you are inserting into an empty list, or removing the last node from a list.
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 LinkedListEnhanced project (containing the header file and driver) from the public repository and committing it to your personal 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 #5 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).