Goals

After completing this lab, you should feel comfortable using pointers, structures, and arrays in C, along with some basic number representation.

Reading

• K&R 4, 5

Notes

It is strongly encouraged for you to work with a partner on this lab!

Setup

Copy the contents of ~cs61c/labs/02 to a suitable location in your home directory.

            $ mkdir ~/lab
            $ cp -R ~cs61c/labs/01b/ ~/lab
          

Exercise 1: Out of Bounds

A student is experimenting with strings and arrays in C and writes the following code:

            #include <stdlib.h>
            #include <stdio.h>
            #include <string.h>

            int main(void)
            {
              char hello[] = "hello ", world[] = "world!\n", *s;
              s = strcat(hello,world);
              printf(s);
              return 0;
            }
          

Answer the following questions in a text file:

1. When our student runs her code, it fails to give her the expected result (try it!). Why? What's one way to fix this bug?

   (note: not all C compilers emit code that crashes. But the Macs in 200SD crash, and the program is not correct. Side note: you won't crash every time you write a bug in C, and sometimes it will do just what you expect; it's kind of like how you don't always get a ticket when you break the speed limit on the freeway, but it's still illegal).

2. Why doesn't C provide the same kind of bounds-checking on arrays that Java does?
3. What is a pro and a con for implementing strings as dumb arrays rather than smart objects like in Java?

Exercise 2: Pointers and Structures in C

Here's one to help you in your interviews. In cyclic_ll.c, complete the function has_cycle to implement the following algorithm for checking if a singly-linked list has a cycle. Recall that if p is a pointer to a struct, p->member refers to a member variable in the struct, and is equivalent to (*p).member.

1. Start with two pointers at the head of the list
2. On each iteration, increment the first pointer by one node and the second pointer by two nodes. If it is not possible to do one or both of these because of a null pointer, we know there is an end to the list and there is therefore no cycle.
3. If the second pointer is the same as the first pointer or the node after the one pointd to by the second pointer is pointed to by the first pointer, the second pointer has come up from behind the first and we know there is a cycle.

After you have correctly implemented has_cycle, the program you get when you compile cyclic_ll.c will tell you that has_cycle agrees with what the program expected it to output.

Exercise 3: The Biggest Integer

Wednesday's class, we discussed number representation. In particular, we discussed two's complement, the ubiquitous format for signed integers. Look at biggestInt.c. You may wish to read through the comments but at this point it is not critical that you understand exactly how the program works. Basically, it is a C program that will tell you some useful information about certain C data types. It does this by exploiting the fact that C does not check for overflow and wrap around conditions. Compile and run the program and answer the following questions:

1. The first piece of information output by the program tells you the value of the most significant bit (MSB) of an unsigned int on your terminal. Based on this information, How many bits does the C data type unsigned int have?
2. The second piece of information tells you the value of the largest positive signed long on your terminal. Based on this information, how many bits does the C data type long have?
3. The third piece of information tells you the value of the most negative signed int on your machine. Based on this information, do the unsigned int and signed int have the same number of bits?
4. 2's Complement number representations have one more negative number than they do positive numbers. That is, the most negative number does not have a positive counter-part. The final piece of information printed is the signed value of what you get when you try to negate the most negative value. Can you explain why this happens?