COMP1511 17s1 Introduction to Programming
1. Your tutor has asked a lab pair to present their week 11 work.

Discuss the good, the bad and the ugly aspects of their code.

Please be gentle in any criticism - we are all learning!

2. Did you blog last week? What is this week's blogging theme?
3. How are you progressing with the assignment?

Do you have any questions? Have you learned anything that would be useful to share with the rest of the tutorial?

4. See list.c and list.h for this weeks linked list tute questions, and testlist.c for autotests. Alternatively download all three files at tut_list_files.zip.

The function member tests if a specified value is a found in a specified list, i.e. the function should return 1 if the value occurs in the list 0 otherwise. It has this prototype:

```int member(int value, struct node *list);
```
Implement this function both iteratively (using a while/for loop) and recursively.
Recursive:
```// return 1 iff value occurs in list, 0 otherwise

int member(int value, struct node *head) {
return 0;
}
return 1;
}
}

```
Very terse recursive:
```// return true iff value occurs in list

int member(int value, struct node *list) {
return list != NULL && (list->data == value || member(value, list->next));
}
```
Iterative:
```/*
* return true iff value occurs in list
*/
int member(int value, struct node *list) {
struct node *n;
for (n = list; n != NULL; n = n->next) {
if (n->data == value) {
return 1;
}
}
return 0;
}
```
5. Implement a function list_append which appends its second argument to its first. It should have this prototype:
```struct node *list_append(struct node *list1, struct node *list2);
```
It should not create (malloc) any new list elements.

It should just change the appropriate next field in the first list.

```struct node *list_append(struct node *list1, struct node *list2) {
struct node *n;
if (list1 == NULL) {
return list2;
}
n = list1;
while (n->next != NULL) {
n = n->next;
}
n->next = list2;
return list1;
}
```
6. The function insert_ordered is used to construct ordered lists. It will insert the supplied value at the appropriate point in the list remains sorted (non-decreasing). It has this prototype:
```struct node *insert_ordered(int item, struct node *list);
```
It should create (malloc) just 1 list element and change the appropriate next field in the list to insert it.

Implement this function.

```struct node *insert_ordered(int item, struct node *list) {
struct node *n;
struct node *new = malloc(sizeof *new);
if (new == NULL) {
fprintf(stderr, "Out of memory");
exit(1);
}
new->data = item;
if (list == NULL || item < list->data) {
new->next = list;
return new;
}
n = list;
while (n->next != NULL && n->next->data < item) {
n = n->next;
}
new->next = n->next;
n->next = new;
return list;
}
```
7. The function merge_sorted is used to merge two ordered lists. It will combine two sorted list into a new sorted list (non-decreasing). It has this prototype:
```struct node *merge_sorted(struct node *list1, struct node *list2);
```

It should not create (malloc) any list elements. It should change the appropriate next fields to combined the lists.

Implement this function both iteratively (using a while/for loop) and recursively.

Iterative version:
```struct node *merge_sorted(struct node *list1, struct node *list2) {
struct node *start;
struct node *n;
if (list1 == NULL) {
return list2;
} else if (list2 == NULL) {
return list1;
} else if (list1->data < list2->data) {
start = list1;
n = list1;
list1 = list1->next;
} else {
start = list2;
n = list2;
list2 = list2->next;
}
while (list1 != NULL && list2 != NULL) {
if (list1->data < list2->data) {
n->next = list1;
n = list1;
list1 = list1->next;
} else {
n->next = list2;
n = list2;
list2 = list2->next;
}
}
if (list1 == NULL) {
n->next = list2;
} else {
n->next = list1;
}
return start;
}
```
Recursive version:
```struct node *merge_sorted(struct node *list1, struct node *list2) {
if (list1 == NULL) {
return list2;
} else if (list2 == NULL) {
return list1;
} else if (list1->data < list2->data) {
list1->next = merge_sorted(list1->next, list2);
return list1;
} else {
list2->next = merge_sorted(list1, list2->next);
return list2;
}
}
```

Revision questions

The remaining tutorial questions are primarily intended for revision - either this week or later in session.

Your tutor may still choose to cover some of the questions time permitting.

8. Consider:

```double ff[] = {1.1, 2.2, 3.3, 4.4, 5.5, 6.6};
double *fp = &ff[0];
```

What are the similarities between `ff` and `fp`? What are the differences?

They are both pointers to double. They both point to the beginning of the double array `ff`. They can both be used to access the array.
The difference is that ff always point to the beginning of the array, while fp is variable and can be made to point somewhere else. Also sizeof ff will return the size of the array (probably 48 bytes) but sizeof fp will return the size of the pointer (probably 4 or 8 bytes).
9. Consider:

```char s[] = "Hello World!";
char *cp = s;
char *cp2 = &s[8];
```

What is the output when the following statements are executed?

```printf("%s\n", cp);
printf("%c\n", *cp);
printf("%c\n", cp[6]);
printf("%s\n",cp2);
printf("%c\n",*cp2);
```

```Hello World!
H
W
rld!
r
```
10. We have student fines in a file named `fines.txt` this format:
```Linus Torvalds fined \$98 for not attending lectures.
Denis Ritchie fined \$50 for eating in labs.
Ken Thompson fined \$150 for attending lecture in his underpants.
```
Write a program `student_fine.c` which reads this file and prints the student with bigesst fine including the amount and reason in this format.
```a.out
Biggest fine was \$150 given to Ken Thompson for 'attending lecture in his underpants'.
```
Sample solution for `student_fine.c`
```#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_LINE 1024

int main(int argc, char *argv[]) {
FILE *f;
char line[MAX_LINE];
int fine;
int biggestFine = 0;
char biggestFineStudentName[MAX_LINE];
char biggestFineReason[MAX_LINE];
int nStudents;
char *p, *q;

f = fopen("fines.txt", "r");
if (f == NULL) {
perror(argv[0]);
return 1;
}
nStudents = 0;
while (fgets(line, MAX_LINE, f) != NULL) {

// look for '\$' to find the fine amount
p = strchr(line, '\$');
if (p == NULL) {
fprintf(stderr, "No \$ on line %d\n", nStudents + 1);
exit(1);
}
fine = atoi(p + 1);

// if it's the first student or fine is bigger than current maximum,
// then we need to update our 'biggestFine'
if (nStudents == 0 || fine > biggestFine) {
biggestFine = fine;

// put '\0' after the name, so that we can use strcpy
p = p - 7; // move the pointer back so that it's immediately after the name
if (p < line) {
fprintf(stderr, "No name for fine on line %d\n", nStudents + 1);
}
p[0] = '\0';
strcpy(biggestFineStudentName, line);

// move forward 3 words
int i;

i = 0;
while (i < 3) {
p = strchr(p + 1, ' ');
if (p == NULL) {
fprintf(stderr, "No reason for fine on line %d\n", nStudents + 1);
exit(1);
}
i = i + 1;
}

// put '\0' after the reason, so that we can use strcpy
q = strchr(p + 1, '.');
if (q == NULL) {
fprintf(stderr, "Line %d too long\n", nStudents + 1);
exit(1);
}
q[0] = '\0';
strcpy(biggestFineReason, p + 1);
}
nStudents = nStudents + 1;
}
if (nStudents > 0) {
printf("Biggest fine was \$%d given to %s for '%s'.\n", biggestFine, biggestFineStudentName, biggestFineReason);
}
fclose(f);
return 0;
}

```

11. Write a function
```int non_decreasing(int n, int a[n])
```
which checks whether items in an array are sorted in non-decreasing order. (i.e. a[i] ≥ a[i-1], for 0<i<N). Your function should returns 1 if the items are in non-decreasing order, 0 otherwise.
```int non_decreasing(int a[], int n) {
int no_decrease = 1;

for (int i = 0; i < n-1 && no_decrease; i = i + 1) {
if (a[i] > a[i + 1]) {
noDecrease = 0;
}
}

return no_decrease;
}
```
12. Write a function
```int find_index(int x, int n, int a[n])
```
which takes two integers x and n together with an array a[] of n integers and searches for the specified value within the array. Your function should return the smallest index k such that a[k] is equal to x (or -1 if x does not occur in the array).
```int find_index(int x, int n, int a[n]) {
int k = -1;

for (int i = 0; i < n && k == -1; i = i + 1) {
if (a[i] == x) {
k = i;
}
}
return k;
}
```
13. Write a function, prototype below, that mirrors the behaviour of the library function strrchr. This function takes a string and a character as arguments, and returns a pointer to the last occurrence of the character `c` in the string s. It returns NULL if the character cannot be found.
```char *strrchr(char s[], char c)
```
```char *strrchr(char s[], char c) {
char *ptr = NULL;
int i;

for (i = 0; i < strlen(s); i = i + 1) {
if (s[i] == c) {
ptr = &s[i];
}
}
return ptr;
}
```
14. Write a function to calculate the Manhattan distance between two points.

Use this function from the math.h library:

```double fabs(double x);
```
```#include <math.h>

double manhattanDistance(double x1, double y1, double x2, double y2) {
return fabs(x1 - x2) + fabs(y1 - y2);
}

```
15. Write a program `multiply.c` that performs addition or multiplication of integers, as follows. Your program should continually read integers from the user until end-of-input is encountered. Then it should print either the sum or the product of the input numbers. The program behaviour is controlled by either of the following command-line arguments:
`-add, -multiply`. If the wrong command-line argument(s) are supplied your program should do nothing.
Sample solution for `multiply.c`
```#include <stdio.h>
#include <string.h>

int main(int argc, char *argv[]) {
int val, result;

if (argc != 2) {
return 0; // should print a message here
}

if (strcmp(argv[1], "-add") != 0 && strcmp(argv[1], "-multiply") != 0) {
return 0; // should print a message here
}

result = 0;

//If we are multiplying we need to initialise result to 1
//Since we have already checked argv[1] contains either
//"-multiply" or "-add" we only need to check the second char

if (argv[1][1] == 'm') {
result = 1;
}
while (scanf("%d", &val) == 1) {
if (argv[1][1] == 'a') {
result = result + val;
} else {
result = result * val;
}
}
if (argv[1][1] == 'a') {
printf("Sum: %d\n", result);
} else {
printf("Product: %d\n", result);
}

return 0;
}

```