CS 61C (Fall 2007)

Lab Assignment 2

Goals

These exercises are intended to expose you to bugs involving storage allocation that newcomers to C commonly encounter.

Reading

K&R: material from chapters 1 through 4 on pointers; sections 5.1 through 5.5; sections 6.1 through 6.6.

The document "Pointers and Memory" accessible from the "Resources" link at the CS 61C web site will also be useful.

Initial preparation

Find a partner, someone different from the person(s) you worked with last week. Introduce yourself to him or her, and tell each other your favorite ice cream flavors.

To compile a program with multiple c files, use gcc foo.c bar.c or gcc foo.c bar.c -o myexecutable.

Exercise 1 (3 points)

All three of these parts of this exercise involve working with incorrect versions of a function that adds an element to the front of a linked list (i.e. acts like Scheme's cons function). Copy the files in ~cs61c/files/lab/2 to your directory. For checkoff, you'll be showing box-and-pointer diagrams to your lab T.A.; save them, together with descriptions of the behavior of each program version, so that your t.a. can check off all parts of this exercise together.

Part a

The cons function in the program list1.c appears below.

	/* return the result of "consing" an element to the front of the given list */
	struct node *cons (char *newCar, struct node *list) {
	    struct node newNode;
	    newNode.data = newCar;
	    newNode.next = list;
	    return &newNode;
	}

Compile list1.c with main.c, trace through the code with gdb, and draw a box-and-pointer diagram of the list structure that results from adding two elements to the list. Explain your diagram to your lab T.A. for checkoff.

Part b

Here is the cons function in list2.c.

	struct node newNode;
	
	/* return the result of "consing" an element to the front of the given list */
	struct node *cons (char *newCar, struct node *list) {
	    newNode.data = newCar;
	    newNode.next = list;
	    return &newNode;
	}

Compile list2.c with main.c, trace through the code with gdb, and draw a box-and-pointer diagram of the list structure that results from adding two elements to the list. Explain your diagram to your lab T.A. for checkoff.

Part c

Finally comes the cons function in list3.c.

	/* return the result of "consing" an element to the front of the given list */
	struct node *cons (char *newCar, struct node *list) {
	    struct node *rtn = (struct node *) malloc (sizeof (struct node));
	    rtn->data = newCar;
	    rtn->next = list;
	    return rtn;
	}

Compile list3.c with main.c, trace through the code with gdb, and draw a box-and-pointer diagram of the list structure that results from adding two elements to the list. Explain your diagram to your lab t.a. for checkoff.

Exercise 2 (1 point)

Supply a correct version of the cons function in a file named list.c. Modify it to #include "ilist.h" instead of list.h. Then edit imain.c, a slightly different version of the main program used in exercise 1, by adding a loop to free all the memory reserved in calls to malloc. Compile your corrected list code with i_memory.c:

    gcc imain.c list.c i_memory.c

Run it, making sure that it prints the message "Mo memory leaks found.". Show your corrected code and the result of running the memory-checking program to your T.A. for checkoff.

Code you'll be working with

main.c

	#include <stdio.h>
	#include <string.h>
	#include "list.h"	// change to ilist.h for exercise 2
	
	#define MAXSTRLEN 80
	
	void print (struct node *);
	
	int main ( ) {
	    char line[80];
	    struct node *list = emptyList ( );
	    printf ("string to add to front of list? (type ^D if finished) ");
	    while (fgets (line, MAXSTRLEN, stdin) != NULL) {
	        line[strlen(line)-1] = '\0'; // get rid of carriage return
		list = cons (line, list);
		print (list);
		printf ("string to add to front of list? (type ^D if finished) ");
	    }
	    return 0;
	}
	
	void print (struct node *list) {
	    printf ("(");
	    while (!isEmpty (list)) {
		printf (" \"%s\"", car (list));
		list = cdr (list);
	    }
	    printf (" )\n");
	}

list.h

	struct node;
	
	/* return the result of "consing" an element to the front of the given list */
	struct node *cons (char *newCar, struct node *list);
	
	/* return an empty list */
	struct node *emptyList ( );
	
	/* determine if a list is empty */
	int isEmpty (struct node *list);
	
	/* return the first element of the given list */
	char *car (struct node *list);
	
	/* return the rest of the given list (all elements after the first) */
	struct node *cdr (struct node *list);

Code common to list1.c, list2.c, and list3.c

	#include <stdio.h>
	#include <stdlib.h>
	#include <string.h>
	
	#include "list.h"	// change to ilist.h for exercise 2
	
	struct node {
	    char *data;
	    struct node *next;
	};
	
	/* return the result of "consing" an element to the front of the given list */
	struct node *cons (char *newCar, struct node *list) {
	    /* code is different in the various versions */
	}
	
	/* return an empty list */
	struct node *emptyList ( ) {
	    return NULL;
	}
	
	/* determine if a list is empty */
	int isEmpty (struct node *list) {
	    return list == NULL;
	}
	
	/* return the first element of the given list */
	char *car (struct node *list) {
	    return list->data;
	}
	
	/* return the rest of the given list (all elements after the first) */
	struct node *cdr (struct node *list) {
	    return list->next;
	}