Create a new directory for this lab called labB2 by typing:
mkdir labB2Change to this directory by typing:
cd labB2
As you know, every time we use malloc, we need to use a corresponding free when we are finished with the memory.
If we don't we will use more and more memory as our program runs.
It is given back to the system as soon as the program terminates, so for our short toy programs it has not been an issue.
However, users do not want memory leaks in their ADTs.
So in this lab and the next lab we want to make sure you correctly implement your destroy functions.
And use them correctly in your client program so we know that you can manage your memory accurately.
In the labs and the exam we will be testing your programs with the additional --leak-check option for dcc. For example:
dcc --leak-check prog.c -o progSo your program will need to generate the correct output AND free all malloced memory to pass the autotests.
To get all of the provided files for this lab you can run the following command:
cp /web/cs1911/current/tlb/B2/code/*.[ch] .
For multi-file projects you must give all required C files to the compiler at the same time.
You don't need to include H files, but they must be in the current directory.
$ dcc ADT-file.c main-file.c -o executable $ ./executable
Create a file hofstadter.c which implements the Hofstadter Male + Female sequences.
The pair of sequences defined by
Female(0) = 1 Male(0) = 0 and Female(n) = n - Male(Female(n - 1)) Male(n) = n - Female(Male(n - 1))
$ dcc hofstadter.c -o hofstadter $ ./hofstadter 1 1 $ ./hofstadter 7 5 $ ./hofstadter 33 21 $ ./hofstadter 52 32 $ ./hofstadter 101 63 $ ./hofstadter 177 110
Create a file array_count_positive.c which uses a recursive function to count the number of positive integers in an array of integers.
$ dcc array_count_positive.c -o array_count_positive $ ./array_count_positive 1 2 3 4 5 5 $ ./array_count_positive 1 2 3 4 5 0 -1 -2 -3 5 $ ./array_count_positive 1 2 3 4 5 0 -1 -2 -3 6 7 8 9 9
The file list.c and the interface list.h is the starting point for this lab exercise.
It contains two structs, List and Node,
which can be used to represent a sequence of strings.
It should, when you have finished your implementation, uses a doubly-linked-list as its data representation.
It is one of the same structs you have seen in lectures.
You will remember that each element in the list is represented by a Node struct.
You have to implement these functions:
list list_create(void);
void list_destroy(list);
void list_insert_first(list, string);
void list_insert_last(list, string);
void list_insert(list, int, string);
string list_get_first(list);
string list_get_last(list);
string list_get(list, int);
void list_delete_first(list);
void list_delete_last(list);
void list_delete(list, int);
list list_copy(list);
list list_reversed(list);
void list_show(list);
int list_size(list);
int list_count_occurrences(list, string);
Each function in list.c has a comment describing what it should do.
And any limitations on how it should be implemented.
many of these functions can be copied from the lectures with only minor changes.
main function in runList.c contains code which allows you to test your functions.
Note: you do not need to understand how this code works.
The examples below demonstrate how to use the testing code.
These examples also indicate how your functions should behave.
$ dcc --leak-check list.c runList.c -o list $ ./list list (0) = NULL > insert_last Hello World list (1) = "Hello World" -> NULL > insert_last How are you list (2) = "Hello World" -> "How are you" -> NULL > insert_first COMP1911 list (3) = "COMP1911" -> "Hello World" -> "How are you" -> NULL > insert 1 23T2 list (4) = "COMP1911" -> "23T2" -> "Hello World" -> "How are you" -> NULL > delete 2 list (3) = "COMP1911" -> "23T2" -> "How are you" -> NULL > reverse list (3) = "How are you" -> "23T2" -> "COMP1911" -> NULL > get 1 < 23T2 list (3) = "How are you" -> "23T2" -> "COMP1911" -> NULL > quit
labB2 directory):
give cs1911 labB2 hofstadter.c array_count_positive.c list.c