Create a new directory for this lab called lab13 by typing:
mkdir lab13Change to this directory by typing:
cd lab13
These revision exercises are not assessable.
They do not get marked.
There is no need to submit them with give.
The file lab13.c is the starting point for the revision exercises.
It contains struct node, which is used to store a sequence of integers. This is the same data representation you have seen in lectures.
struct node {
struct node *next;
int data;
};
Start by copying lab13.c:
cp /import/adams/A/cs1511/public_html/17s1/tlb/13/lab13.c .lab13.c contains five functions which have not been implemented. Your task is to implement these five functions.
int count(int value, struct node *list)
Implement count.
count should return the number of nodes in the list containing value.
As usual autotest is available to test your code:
~cs1511/bin/autotest lab13 count
struct node *get_nth(int n, struct node *head)
Implement get_nth.
get_nth should return a pointer to the node in position n in the list.
Position 0 is the first node in the list.
get_nth should return NULL if the list has no n-th node.
As usual autotest is available to test your code:
~cs1511/bin/autotest lab13 get_nth
struct node *delete_nth(int n, struct node *head)
Implement delete_nth.
delete_nth should delete the node in position n in the list.
delete_nth should free the deleted node.
delete_nth should make no changes if there is no position n in the list.
delete_nth should return the (possibly changed) head of the list.
As usual autotest is available to test your code:
~cs1511/bin/autotest lab13 delete_nth
struct node *delete_odd(struct node *head)
Implement delete_odd.
delete_odd should delete all nodes in the list containing odd numbers.
delete_odd should free any deleted nodes.
delete_odd should return the (possibly changed) head of the list.
As usual autotest is available to test your code:
~cs1511/bin/autotest lab13 delete_odd
struct node *insert_nth(int n, struct node *new_node, struct node *head)
Implement insert_nth.
insert_nth should insert new_node before position n in the list.
Given a position immediately after the last element in the list (n == length of the list) insert_nth should append new_node to the list.
insert_nth should otherwise make no changes if there is no position n in the list.
insert_nth should return the (possibly changed) head of the list.
As usual autotest is available to test your code:
~cs1511/bin/autotest lab13 insert_nth
create_node.
Your functions must not change the data field of any node.
Your functions may change the next field of nodes.
Memory must be freed for nodes removed from the list.
Positions are numbered like array indices. The first node in the list is regarded as being in position 0. The last node in a list of length n is regarded as being in position n - 1.
main function in lab13.c contains code which allows you to
test your functions.
The examples below demonstrate how to use the testing code.
These examples also indicate how your functions should behave.
dcc lab13.c -o lab13 ./lab13 list = [] > append 4 list = [4] > append 5 list = [4, 5] > append 6 list = [4, 5, 6] > append 7 list = [4, 5, 6, 7] > append 6 list = [4, 5, 6, 7, 6] > count 42 count(42) returns 0 list = [4, 5, 6, 7, 6] > count 5 count(5) returns 1 list = [4, 5, 6, 7, 6] > count 6 count(6) returns 2 list = [4, 5, 6, 7, 6] > get_nth 0 get_nth(0) returned a pointer to a node containing 4 list = [4, 5, 6, 7, 6] > get_nth 42 get_nth(42) returned NULL list = [4, 5, 6, 7, 6] > get_nth -1 get_nth(-1) returned NULL list = [4, 5, 6, 7, 6] > delete_nth 2 list = [4, 5, 7, 6] > delete_nth 0 list = [5, 7, 6] > delete_nth 0 list = [7, 6] > insert_nth 0 list = [42, 7, 6] > insert_nth 2 list = [42, 7, 42, 6] > insert_nth 4 list = [42, 7, 42, 6, 42] > delete_odd list = [42, 42, 6, 42]Note the test of insert_nth always insert a node containing 42.
They do not get marked.
There is no need to submit them with give.