Due Wednesday, May 18th, 11:59pm

Goals for this homework

  • Practice with data representation
  • Practice using linked structs

You are expected to complete this assignment individually. If you need help, you are invited to come to office hours and/or ask questions on piazza. Clarification questions about the assignments may be asked publicly. Once you have specific bugs related to your code, make the posts private.

You should submit several files for this assignment ( hw7.h, hw7.c, test_hw7.c, llist.h, llist.c, and Makefile) in your subversion repository as directed below.

Set Up

You should already have your hw7 from lab. Make sure you copy over the files from your duet programming folder, if applicable. Also, copy over your llist.c and llist.h files from week 5.

You need to add the skeleton code so that your program will minimally execute. You must do this in case you do not complete your assignment. Our testing infrastructure needs to compile and execute even if you did not complete the entire assignment. Refer to past assignments on how to make skeleton code.

Problem 1: digit list

As we have seen in class, the integer data types in C are only able to represent numbers up to certain maximum values. We may wish to represent larger numbers; if so, it is incumbent upon us to create the data types and algorithms to work with them ourselves.

One way to accomplish this is to use a linked list of digits that stores a number in some base. For instance, the number 163 has the digits 1, 6, and 3 in base 10; or the digits 10 and 3 in base 16. (Note that when we use hexadecimal, the convention is to use the character "A" for the digit 10, but we will use numerical representations for all digits in this problem.)

It is more convenient to store the digits backwards, that is, with the lowest place value (the "ones place") first in our list. So, the base-10 linked list would have the entries 3, then 6, then 1; the base-16 version would have the digits 3, and then 10.

Use the following struct for your digitlist: 


typedef struct {
	llist *digits;
	unsigned int base;
} digitlist;

Using your llist implementation from week 5, write the following functions. In all cases, you may assume that you are given a "well-formed" list. By well-formed, we mean that no digit is greater than the base, and there are no "leading" zeros (zeros in the highest place values that do not affect the mathematical value of the number). You should work on numbers digit-by-digit, never converting an entire number into a C numerical value; in other words, you cannot simply convert the entire number into an int and then perform a mathematical operation. But, you can use standard C mathematical operations as you work with digits. You may assume that the base you are given is small enough to avoid issues of overflow. You may not assume the two values have the same number of digits.

digitlist* create_digitlist(int base, int num); - creates a linked list representing the given integer.

void multiply_digitlist(digitlist *dl, int num); - multiply dl by num. You will modify the contents of dl, and possibly even the length, depending on the problem.

digitlist* add_digitlists(digitlist *dl1, digitlist *dl2); - The function takes two backwards-ordered lists of digits in the same base and adds them together into a single, well-formed digit list in the same base. If they are different bases, return NULL.

int digitlist_tostring(digitlist *dl, char *str); - Like your warmup, write a function that prints the digitlist to a string. Output the number of digits used. Do not print leading 0's. If a base larger than base 10 is used, use letters as in hex for numbers larger than 9. We will not use a base larger than 36. It is assumed that str will point to an already-allocated string of sufficient length.

Add a few lines to the makefile that will compile your homework. Name the executable digits. Make sure you put all of the necessary .c files in the compile line!

Submit

At this point, you should have done the following:
  • Created four files and filled in the proper information: hw7.h, hw7.c, test_hw7.c inside your hw7 directory. You should also have llist.h and llist.c copied from week5. Finally, you have the warmup files. Don't forget to add and commit everything. 
  • $ svn add *hw7* llist.* warmup7* Makefile
  • Implemented all of your functions. If not, you at least need skeletons of your functions so that our automated tests will compile for the functions you did write.
  • Compiled your executable manually and with the Makefile
  • Implemented your test cases
  • Executed your code
  • Debugged your code 
  • $ svn commit -m "hw7 complete"