CS 61C (Fall 2007) |
Lab Assignment 2 |
These exercises are intended to expose you to bugs involving storage allocation that newcomers to C commonly encounter.
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.
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
.
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.
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.
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.
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.
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.
#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"); }
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);
#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; }