Week 08 Laboratory Sample Solutions
Objectives
- working with structs and pointers
- introducing linked lists
- using memory allocation
Preparation
Before the lab you should re-read the relevant lecture slides and their accompanying examples.
Getting Started
Exercise — in pairs:
Compare two note structs to find out which is higher
Download note_compare.c here, or copy it to your CSE account using the following command:
cp -n /web/cs1511/20T1/activities/note_compare/note_compare.c .
Your task is to add code to this function in note_compare.c:
//Returns 1 if a is higher than b
// -1 if b is higher than a
// 0 if they are equal
int note_compare(Note a, Note b) {
//TODO: Change this return.
return -42;
}
struct note { int octave; int key; struct note *next; };
It has also been given a typedef, as shown below:
typedef struct note *Note;
Your task in this exercise is first to complete the function int note_compare(Note a, Note b)
so that it returns:
- 1 if the Note contained in a is higher than the Note in b
- -1 if the Note contained in b is higher than the Note in a
- 0 if the two Notes are the same
Comparing Notes
To compare two Notes, you should first compare their octaves. A higher note will have a larger octave number. If the two octave numbers are the same, the higher Note will have a larger key number.
For example, A Note with octave 3, and key 6 is higher than a Note with octave 2 and key 8, and higher than a Note with octave 3 and key 1; but lower than a Note with octave 3 and key 9, and lower than a Note with octave 4 and key 1.
Testing
note_compare.c also contains a main function which allows you to test your note_compare function.Do not change this main function. If you want to change it, you have misread the question.
Your note_compare function will be called directly in marking. The main function is only to let you test your note_compare function
Here is how you use main function allows you to test note_compare:
dcc -o note_compare note_compare.c ./note_compare 3 4 4 4 b is higher than a ./note_compare 3 6 3 4 a is higher than b
Assumptions/Restrictions/Clarifications.
note_compare should return only 1, 0, or -1.note_compare should not change the notes it is given. Your function should not change the octave or key fields of the passed structs.
note_compare should not use arrays.
note_compare should not call malloc.
note_compare should not call scanf (or getchar or fgets).
note_compare should not print anything. It should not call printf.
Do not change the supplied main function. It will not be tested or marked.
1511 style note_compare.c
When you think your program is working,
you can use autotest
to run some simple automated tests:
1511 autotest note_compare
When you are finished working on this exercise,
you and your lab partner must both
submit your work by running give
:
give cs1511 lab08_note_compare note_compare.c
Note, even though this is a pair exercise,
you both must run give
from your own account
before Friday 12 April 20:00
to obtain the marks for this lab exercise.
note_compare.c
//complete note_compare()
//Completed by:
//On:
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//There are 10 octaves (0 to 9) and 12 notes (0 to 11)
struct note {
int octave;
int key;
struct note *next;
};
int note_compare(struct note *a, struct note *b);
struct note *create_note(int octave, int key);
int main(void) {
printf("this should brea\n");
int octave, key;
scanf("%d %d", &octave, &key);
struct note a = {octave, key};
scanf("%d %d", &octave, &key);
struct note b = {octave, key};
int compared = note_compare(&a, &b);
if (compared == 1) {
printf("a is higher than b\n");
} else if (compared == -1) {
printf("b is higher than a\n");
} else {
printf("a and b are equal\n");
}
return 0;
}
//Returns 1 if a is higher than b
// -1 if b is higher than a
// 0 if they are equal
int note_compare(struct note *a, struct note *b) {
assert(a != NULL && b != NULL);
if (a->octave < b->octave) {
return -1;
} else if (a->octave > b->octave){
return 1;
} else {
if (a->key < b ->key){
return -1;
} else if (a->key > b->key) {
return 1;
} else {
return 0;
}
}
}
Exercise — in pairs:
Subtract one note struct from another
struct note { int octave; int key; Note next; };
It has also been given a typedef, as shown below:
typedef struct note *Note;
Your task in this exercise is first to complete the functions int note_subtract(Note a, Note b)
and void print_note(Note n)
so that they return a new Note created with malloc, with a value that is the larger note subtracted from the smaller.
Download note_subtract.c here, or copy it to your CSE account using the following command:
cp -n /web/cs1511/20T1/activities/note_subtract/note_subtract.c .
Subtracting Notes
When subtracting notes, the resulting octave is the larger octave minus the smaller octave. The resulting key is the key of the larger Note, minus the other key. If the resulting key is negative, you should subtract one from the octave, and add 12 to the key (that is, if you would have octave 3 and key -1, you should actually have octave 2 and key 11).
Testing
note_subtract.c also contains a main function which allows you to test your note_subtract function.Do not change this main function. If you want to change it, you have misread the question.
Your note_subtract function will be called directly in marking. The main function is only to let you test your note_subtract function
Here is how you use main function allows you to test note_subtract:
dcc -o note_subtract note_subtract.c ./note_subtract 7 4 4 3 3 01 ./note_subtract 7 3 4 3 3 00 ./note_subtract 7 2 4 3 2 11
Assumptions/Restrictions/Clarifications.
note_subtract should return a Note created with malloc
.
note_subtract will be given two arguments, and you are guaranteed that higher
will be larger than or equal to lower
. You do not need to check this.
note_subtract will be given two arguments, and you are guaranteed that higher
and lower
will have octaves between 0 and 9, and keys between 0 and 11. You do not
need to check this.
note_subtract and print_note should not change the notes they are given. Your functions should not change the octave or key fields of the passed structs.
note_subtract and print_note should not use arrays.
note_subtract should call malloc. print_note should not call malloc or free.
note_subtract and print_note should not call scanf (or getchar or fgets).
note_subtract should not print anything. It should not call printf.
Do not change the supplied main function. It will not be tested or marked.
1511 style note_subtract.c
When you think your program is working,
you can use autotest
to run some simple automated tests:
1511 autotest note_subtract
When you are finished working on this exercise,
you and your lab partner must both
submit your work by running give
:
give cs1511 lab08_note_subtract note_subtract.c
Note, even though this is a pair exercise,
you both must run give
from your own account
before Friday 12 April 20:00
to obtain the marks for this lab exercise.
note_subtract.c
//complete note_subtract() and note_print()
//Completed by:
//On:
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//There are 10 octaves (0 to 9) and 12 notes (0 to 11)
struct note {
int octave;
int key;
struct note *next;
};
struct note *note_subtract(struct note *higher, struct note *lower);
struct note *create_note(int octave, int key);
void print_note(struct note *n);
int main(void) {
int octave, key;
scanf("%d %d", &octave, &key);
struct note *a = create_note(octave, key);
scanf("%d %d", &octave, &key);
struct note *b = create_note(octave, key);
struct note *diff = note_subtract(a, b);
print_note(diff);
return 0;
}
//Mallocs a note and creates it given an octave and a key
struct note *create_note(int octave, int key) {
struct note *new_note = malloc(sizeof(struct note));
new_note->octave = octave;
new_note->key = key;
new_note->next = NULL;
return new_note;
}
// For a note with octave 0, and note 9,
// `print_note` should print:
// "0 09\n"
void print_note(struct note *n) {
printf("%d %02d\n", n->octave, n->key);
}
//Returns a pointer to a malloced struct containing the difference between a
//higher and a lower note
struct note *note_subtract(struct note *higher, struct note *lower) {
int key = higher->key - lower->key;
int octave = higher->octave - lower->octave;
if (key < 0) {
octave = octave - 1;
key = 12 + key;
}
return create_note(octave, key);
}
Exercise — in pairs:
Print out the elements of a Linked List
Download list_print.c here, or copy it to your CSE account using the following command:
cp -n /web/cs1511/20T1/activities/list_print/list_print.c .
Your task is to add code to this function in list_print.c:
// print a linked list in this format:
// 17 -> 34 -> 51 -> 68 -> X
void print(struct node *head) {
// PUT YOUR CODE HERE
}
Add code to print so that it prints the elements in the list
For example if the linked list contains these 8 elements:
1, 7, 8, 9, 13, 19, 21, 42
print should print 1 -> 7 -> 8 -> 9 -> 13 -> 19 -> 21 -> 42 -> X
Testing
list_print.c also contains a main function which allows you to test your print function.This main function:
- converts the command-line arguments to a linked list
- assigns a pointer to the first node in the linked list to head
- calls list_print(head)
Do not change this main function. If you want to change it, you have misread the question.
Your list_print function will be called directly in marking. The main function is only to let you test your list_print function
Here is how you use main function allows you to test list_print:
dcc list_print.c -o list_print ./list_print 1 2 4 8 16 32 64 128 256 1 -> 2 -> 4 -> 8 -> 16 -> 32 -> 64 -> 128 -> 256 -> X ./list_print 2 4 6 5 8 9 2 -> 4 -> 6 -> 5 -> 8 -> 9 -> X ./list_print 42 4 42 -> 4 -> X ./list_print 43 43 -> X ./list_print X
Assumptions/Restrictions/Clarifications.
print should not change the linked list it is given. Your function should not change the next or data fields of list nodes.print should not use arrays.
print should not call malloc.
print should not call scanf (or getchar or fgets).
Do not change the supplied main function. It will not be tested or marked.
1511 style list_print.c
When you think your program is working,
you can use autotest
to run some simple automated tests:
1511 autotest list_print
When you are finished working on this exercise,
you and your lab partner must both
submit your work by running give
:
give cs1511 lab08_list_print list_print.c
Note, even though this is a pair exercise,
you both must run give
from your own account
before Friday 12 April 20:00
to obtain the marks for this lab exercise.
list_print.c
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
struct node {
struct node *next;
int data;
};
void print(struct node *head);
struct node *strings_to_list(int len, char *strings[]);
int main(int argc, char *argv[]) {
// create linked list from command line arguments
struct node *head = strings_to_list(argc - 1, &argv[1]);
print(head);
return 0;
}
// print a linked list in this format:
// 17 -> 34 -> 51 -> 68 -> X
void print(struct node *head) {
struct node *n = head;
while (n != NULL) {
printf("%d -> ", n->data);
n = n->next;
}
printf("X\n");
}
// create linked list from array of strings
struct node *strings_to_list(int len, char *strings[]) {
struct node *head = NULL;
for (int i = len - 1; i >= 0; i = i - 1) {
struct node *n = malloc(sizeof (struct node));
assert(n != NULL);
n->next = head;
n->data = atoi(strings[i]);
head = n;
}
return head;
}
list_print.c
#include <stdio.h>
#include <assert.h>
struct node {
struct node *next;
int data;
};
// print a linked list in this format:
// 17 -> 34 -> 51 -> 68 -> X
void print(struct node *head) {
if (head == NULL) {
printf("X\n");
}
printf("%d -> ", head->data);
print(head->next);
}
Exercise — in pairs:
Insert an element at the head of a Linked List
Download list_insert_head.c here, or copy it to your CSE account using the following command:
cp -n /web/cs1511/20T1/activities/list_insert_head/list_insert_head.c .
Your task is to add code to this function in list_insert_head.c:
// Insert a new node containing value at the start of the linked list.
// The head of the new list is returned.
struct node *insert_head(int value, struct node *head) {
// PUT YOUR CODE HERE (change the next line!)
return NULL;
}
Add code to insert_head so that it creates a new list node (using malloc) containing value and places it at the start of the list.
insert_head should return a pointer to the new list.
For example if value is 12 and the linked list contains these 3 elements:
16, 7, 8
insert_head should return a pointer to a list with these elements:
12, 16, 7, 8
Testing
list_insert_head.c also contains a main function which allows you to test your insert_head function.This main function:
- converts the command-line arguments to a linked list
- assigns a pointer to the first node in the linked list to head
- reads a single integer from standard input and assigns it to value
- calls insert_head(value, head)
- prints the result.
Do not change this main function. If you want to change it, you have misread the question.
Your insert_head function will be called directly in marking. The main function is only to let you test your insert_head function
dcc list_insert_head.c -o list_insert_head ./list_insert_head 16 7 8 12 [12, 16, 7, 8] ./list_insert_head 16 42 [42, 16] ./list_insert_head 2 [2]
Assumptions/Restrictions/Clarifications.
insert_head should not use arrays.insert_head should not call scanf (or getchar or fgets).
insert_head should not print anything. It should not call printf.
Do not change the supplied main function. It will not be tested or marked.
1511 style list_insert_head.c
When you think your program is working,
you can use autotest
to run some simple automated tests:
1511 autotest list_insert_head
When you are finished working on this exercise,
you and your lab partner must both
submit your work by running give
:
give cs1511 lab08_list_insert_head list_insert_head.c
Note, even though this is a pair exercise,
you both must run give
from your own account
before Friday 12 April 20:00
to obtain the marks for this lab exercise.
list_insert_head.c
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
struct node {
struct node *next;
int data;
};
struct node *insert_head(int value, struct node *head);
struct node *create_node(int data, struct node *next);
struct node *strings_to_list(int len, char *strings[]);
void print_list(struct node *head);
int main(int argc, char *argv[]) {
int value;
scanf("%d", &value);
// create linked list from command line arguments
struct node *head = NULL;
if (argc > 1) {
// list has elements
head = strings_to_list(argc - 1, &argv[1]);
}
struct node *new_head = insert_head(value, head);
print_list(new_head);
return 0;
}
// Insert a new node containing value at the start of the linked list.
// The head of the new list is returned.
struct node *insert_head(int value, struct node *head) {
struct node *new_node = malloc(sizeof (struct node));
if (new_node == NULL) {
fprintf(stderr, "out of memory\n");
exit(1);
}
new_node->data = value;
new_node->next = head;
return new_node;
}
// create linked list from array of strings
struct node *strings_to_list(int len, char *strings[]) {
struct node *head = NULL;
int i = len - 1;
while (i >= 0) {
struct node *n = malloc(sizeof (struct node));
assert(n != NULL);
n->next = head;
n->data = atoi(strings[i]);
head = n;
i -= 1;
}
return head;
}
// print linked list
void print_list(struct node *head) {
printf("[");
struct node *n = head;
while (n != NULL) {
// If you're getting an error here,
// you have returned an invalid list
printf("%d", n->data);
if (n->next != NULL) {
printf(", ");
}
n = n->next;
}
printf("]\n");
}
Exercise — in pairs:
Find an element in a Linked List
Download list_contains.c here, or copy it to your CSE account using the following command:
cp -n /web/cs1511/20T1/activities/list_contains/list_contains.c .
Your task is to add code to this function in list_contains.c:
// Return 1 if value occurs in linked list, 0 otherwise
int contains(int value, struct node *head) {
// PUT YOUR CODE HERE (change the next line!)
return 42;
}
Add code to contains so that its returns 1 if value occurs in the linked and otherwise it returns 0.
For example if the linked list contains these 8 elements:
1, 7, 8, 9, 13, 19, 21, 42
and contains is called with value of 9,
contains should return 1.
Testing
list_contains.c also contains a main function which allows you to test your contains function.This main function:
- converts the command-line arguments to a linked list
- assigns a pointer to the first node in the linked list to head
- reads a single integer from standard input and assigns it to value
- calls list_contains(value, head)
- prints the result.
Do not change this main function. If you want to change it, you have misread the question.
Your list_contains function will be called directly in marking. The main function is only to let you test your list_contains function
Here is how you use main function allows you to test list_contains:
dcc list_contains.c -o list_contains ./list_contains 1 2 3 4 3 1 ./list_contains 1 2 3 4 42 0 ./list_contains 15 17 17 18 17 1 ./list_contains 15 17 17 18 21 0 ./list_contains 42 0
Assumptions/Restrictions/Clarifications.
contains should return a single integer.contains should not change the linked list it is given. Your function should not change the next or data fields of list nodes.
contains should not use arrays.
contains should not call malloc.
contains should not call scanf (or getchar or fgets).
contains should not print anything. It should not call printf.
Do not change the supplied main function. It will not be tested or marked.
1511 style list_contains.c
When you think your program is working,
you can use autotest
to run some simple automated tests:
1511 autotest list_contains
When you are finished working on this exercise,
you and your lab partner must both
submit your work by running give
:
give cs1511 lab08_list_contains list_contains.c
Note, even though this is a pair exercise,
you both must run give
from your own account
before Friday 12 April 20:00
to obtain the marks for this lab exercise.
list_contains.c
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
struct node {
struct node *next;
int data;
};
int contains(int value, struct node *head);
struct node *strings_to_list(int len, char *strings[]);
int main(int argc, char *argv[]) {
int value;
scanf("%d", &value);
// create linked list from command line arguments
struct node *head = NULL;
if (argc > 1) {
// list has elements
head = strings_to_list(argc - 1, &argv[1]);
}
int result = contains(value, head);
printf("%d\n", result);
return 0;
}
// Return 1 if value occurs in linked list, 0 otherwise
int contains(int value, struct node *head) {
struct node *n = head;
while (n != NULL) {
if (n->data == value) {
return 1;
}
n = n->next;
}
return 0;
}
// create linked list from array of strings
struct node *strings_to_list(int len, char *strings[]) {
struct node *head = NULL;
int i = len - 1;
while (i >= 0) {
struct node *n = malloc(sizeof (struct node));
assert(n != NULL);
n->next = head;
n->data = atoi(strings[i]);
head = n;
i -= 1;
}
return head;
}
list_contains.c
#include <stdio.h>
#include <assert.h>
struct node {
struct node *next;
int data;
};
// Return 1 if value occurs in linked list, 0 otherwise
int contains(int value, struct node *head) {
if (head == NULL) {
return 0;
}
return (head->data == value) || contains(value, head->next);
}
Challenge Exercise — individual:
Insert into the nth position in a Linked List
Download list_insert_nth.c here, or copy it to your CSE account using the following command:
cp -n /web/cs1511/20T1/activities/list_insert_nth/list_insert_nth.c .
Your task is to add code to this function in list_insert_nth.c:
// Insert a new node containing value at position n of the linked list.
// if n == 0, node is inserted at start of list
// if n >= length of list, node is appended at end of list
// The head of the new list is returned.
struct node *insert_nth(int n, int value, struct node *head) {
// PUT YOUR CODE HERE (change the next line!)
return NULL;
}
Add code to insert_nth so that it creates a new list node (using malloc) containing value and places it before position n of the list.
The elements are counted in the same manner as array elements (zero-based), so the first element in the list is regarded as at position 0, the second element position 1 and so on.
If there are less than n
elements in the list, the new list node should
be appended to the end of the list.
insert_nth should return a pointer to the new list.
For example if n is 1 and value is 12 and the linked list contains these 3 elements:
16, 7, 8
insert_nth should return a pointer to a list with these elements:
16, 12, 7, 8
Testing
list_insert_nth.c also contains a main function which allows you to test your insert_nth function.This main function:
- converts the command-line arguments to a linked list
- assigns a pointer to the first node in the linked list to head
- reads an integer from standard input and assigns it to n
- reads a second integer from standard input and assigns it to value
- calls insert_nth(n, value, head)
- prints the result.
Do not change this main function. If you want to change it, you have misread the question.
Your insert_nth function will be called directly in marking. The main function is only to let you test your insert_nth function
dcc list_insert_nth.c -o list_insert_nth ./list_insert_nth 16 7 8 0 12 [12, 16, 7, 8] ./list_insert_nth 16 7 8 1 12 [16, 12, 7, 8] ./list_insert_nth 16 7 8 2 12 [16, 7, 12, 8] ./list_insert_nth 16 7 8 3 12 [16, 7, 8, 12] ./list_insert_nth 16 7 8 42 12 [16, 7, 8, 12] ./list_insert_nth 42 0 16 [16, 42] ./list_insert_nth 0 2 [2] ./list_insert_nth 10 2 [2]
Assumptions/Restrictions/Clarifications.
insert_nth should not use arrays.insert_nth should not call scanf (or getchar or fgets).
insert_nth should not print anything. It should not call printf.
Do not change the supplied main function. It will not be tested or marked.
1511 style list_insert_nth.c
When you think your program is working,
you can use autotest
to run some simple automated tests:
1511 autotest list_insert_nth
When you are finished working on this exercise,
you must
submit your work by running give
:
give cs1511 lab08_list_insert_nth list_insert_nth.c
You must run give
before Friday 12 April 20:00
to obtain the marks for this lab exercise.
Note that this is an individual exercise,
the work you submit with give
must be entirely your own.
list_insert_nth.c
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
struct node {
struct node *next;
int data;
};
struct node *insert_nth(int n, int value, struct node *head);
struct node *create_node(int data, struct node *next);
struct node *strings_to_list(int len, char *strings[]);
void print_list(struct node *head);
int main(int argc, char *argv[]) {
int n;
scanf("%d", &n);
int value;
scanf("%d", &value);
// create linked list from command line arguments
struct node *head = NULL;
if (argc > 1) {
// list has elements
head = strings_to_list(argc - 1, &argv[1]);
}
struct node *new_head = insert_nth(n, value, head);
print_list(new_head);
return 0;
}
// Insert a new node containing value at position n of the linked list.
// if n == 0, node is inserted at start of list
// if n >= length of list, node is appended at end of list
// The head of the new list is returned.
struct node *insert_nth(int n, int value, struct node *head) {
struct node *new_node = malloc(sizeof (struct node));
if (new_node == NULL) {
fprintf(stderr, "out of memory\n");
exit(1);
}
new_node->data = value;
// new node is head of list
if (head == NULL || n == 0) {
new_node->next = head;
return new_node;
}
int i = n - 1;
struct node *p = head;
while (p->next != NULL && i > 0) {
p = p->next;
i = i - 1;
}
new_node->next = p->next;
p->next = new_node;
return head;
}
// create linked list from array of strings
struct node *strings_to_list(int len, char *strings[]) {
struct node *head = NULL;
int i = len - 1;
while (i >= 0) {
struct node *n = malloc(sizeof (struct node));
assert(n != NULL);
n->next = head;
n->data = atoi(strings[i]);
head = n;
i -= 1;
}
return head;
}
// print linked list
void print_list(struct node *head) {
printf("[");
struct node *n = head;
while (n != NULL) {
// If you're getting an error here,
// you have returned an invalid list
printf("%d", n->data);
if (n->next != NULL) {
printf(", ");
}
n = n->next;
}
printf("]\n");
}
list_insert_nth.c
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
struct node {
struct node *next;
int data;
};
// Insert a new node containing value at position n of the linked list.
// if n == 0, node is inserted at start of list
// if n >= length of list, node is appended at end of list
// The head of the new list is returned.
// recursive version
struct node *insert_nth(int n, int value, struct node *head) {
if (n > 0 && head != NULL) {
head->next = insert_nth(n - 1, value, head->next);
return head;
}
struct node *new_node = malloc(sizeof (struct node));
if (new_node == NULL) {
fprintf(stderr, "out of memory\n");
exit(1);
}
new_node->data = value;
new_node->next = head;
return new_node;
}
Challenge Exercise — individual:
Insert an element at the tail of a Linked List
Download list_insert_tail.c here, or copy it to your CSE account using the following command:
cp -n /web/cs1511/20T1/activities/list_insert_tail/list_insert_tail.c .
Your task is to add code to this function in list_insert_tail.c:
// Insert a new node containing value at the end of the linked list.
// The head of the new list is returned.
struct node *insert_tail(int value, struct node *head) {
// PUT YOUR CODE HERE (change the next line!)
return NULL;
}
Add code to insert_tail so that it creates a new list node (using malloc) containing value and places it at the end of the list.
insert_tail should return a pointer to the new list.
For example if value is 12 and the linked list contains these 3 elements:
16, 7, 8
insert_tail should return a pointer to a list with these elements:
16, 7, 8, 12
Testing
list_insert_tail.c also contains a main function which allows you to test your insert_tail function.This main function:
- converts the command-line arguments to a linked list
- assigns a pointer to the first node in the linked list to head
- reads a single integer from standard input and assigns it to value
- calls insert_tail(value, head)
- prints the result.
Do not change this main function. If you want to change it, you have misread the question.
Your insert_tail function will be called directly in marking. The main function is only to let you test your insert_tail function
dcc list_insert_tail.c -o list_insert_tail ./list_insert_tail 16 7 8 12 [16, 7, 8, 12] ./list_insert_tail 16 42 [16, 42] ./list_insert_tail 2 [2]
Assumptions/Restrictions/Clarifications.
insert_tail should not use arrays.insert_tail should not call scanf (or getchar or fgets).
insert_tail should not print anything. It should not call printf.
Do not change the supplied main function. It will not be tested or marked.
1511 style list_insert_tail.c
When you think your program is working,
you can use autotest
to run some simple automated tests:
1511 autotest list_insert_tail
When you are finished working on this exercise,
you must
submit your work by running give
:
give cs1511 lab08_list_insert_tail list_insert_tail.c
You must run give
before Friday 12 April 20:00
to obtain the marks for this lab exercise.
Note that this is an individual exercise,
the work you submit with give
must be entirely your own.
list_insert_tail.c
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
struct node {
struct node *next;
int data;
};
struct node *insert_tail(int value, struct node *head);
struct node *last(struct node *head);
struct node *create_node(int data, struct node *next);
struct node *strings_to_list(int len, char *strings[]);
void print_list(struct node *head);
int main(int argc, char *argv[]) {
int value;
scanf("%d", &value);
// create linked list from command line arguments
struct node *head = NULL;
if (argc > 1) {
// list has elements
head = strings_to_list(argc - 1, &argv[1]);
}
struct node *new_head = insert_tail(value, head);
print_list(new_head);
return 0;
}
// Add a new node containing value at the end of the linked list.
// The head of the new list is returned.
struct node *insert_tail(int value, struct node *head) {
struct node *new_node = malloc(sizeof (struct node));
if (new_node == NULL) {
fprintf(stderr, "out of memory\n");
exit(1);
}
new_node->data = value;
new_node->next = NULL;
// empty list is a special case
// new node is now the head of the now 1 element list
if (head == NULL) {
return new_node;
}
struct node *l = last(head);
l->next = new_node;
return head;
}
// return pointer to last node in list
// NULL is returned if list is empty
struct node *last(struct node *head) {
if (head == NULL) {
return NULL;
}
struct node *n = head;
while (n->next != NULL) {
n = n->next;
}
return n;
}
// create linked list from array of strings
struct node *strings_to_list(int len, char *strings[]) {
struct node *head = NULL;
int i = len - 1;
while (i >= 0) {
struct node *n = malloc(sizeof (struct node));
assert(n != NULL);
n->next = head;
n->data = atoi(strings[i]);
head = n;
i -= 1;
}
return head;
}
// print linked list
void print_list(struct node *head) {
printf("[");
struct node *n = head;
while (n != NULL) {
// If you're getting an error here,
// you have returned an invalid list
printf("%d", n->data);
if (n->next != NULL) {
printf(", ");
}
n = n->next;
}
printf("]\n");
}
Submission
give
.
You can run give
multiple times.
Only your last submission will be marked.
Don't submit any exercises you haven't attempted.
If you are working at home, you may find it more convenient to upload your work via give's web interface.
Remember you have until Week 8 Sunday 20:00 to submit your work.
You cannot obtain marks by e-mailing lab work to tutors or lecturers.
You check the files you have submitted here
Automarking will be run by the lecturer several days after the submission deadline
for the test, using test cases that you haven't seen:
different to the test cases autotest
runs for
you.
(Hint: do your own testing as well as running
autotest
)
After automarking is run by the lecturer you can view it here the resulting mark will also be available via via give's web interface
Lab Marks
When all components of a lab are automarked you should be able to view the the marks via give's web interface or by running this command on a CSE machine:
1511 classrun -sturec