![\framebox{\includegraphics[width=4in]{linked_list}}](linkedList.png)
|
Work on these exercises with a partner, using pair programming.
|
The goals of this exercise are to:
|
The following C resources might be helpful. |
Reminder: Use pair programming.
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.)
Reminder: Use pair programming.
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 functionvoid 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);
Reminder: Use pair programming.
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). Writeadd(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())
Reminder: Use pair programming.
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.gets(char* buffer) (defined in stdio.h). Reminder: Use pair programming.
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.
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).
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!
Reminder: Use pair programming.
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: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).