COMP1511 Week 09 Tutorial Questions

Your tutor has asked a lab pair to present their week 8 work.
Discuss the good, the bad and the ugly aspects of their code.

Please be gentle in any criticism - we are all learning!
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?
What does malloc() do?
What are its inputs and output and what do they mean?

Describe a function that will allocate memory for a struct and assign a pointer to the result.
What does free() do?
What is the input to free and how does it help it do what it needs to do?
What is a use after free error? Give an example.
Discuss why these are extremely dangerous, one of the worst causes of bugs in C programs and a major source of security vulnerabilities.
What is a memory leak?
What does dcc --leak-check do?
Implement a function list_append which appends its second argument to its first. Treat both inputs as if they are lists and may have more than one node. It should have this prototype:
```
struct node *list_append(struct node *list1, struct node *list2);
```
As usual, struct node has this definition:
```
struct node {
    int          data;
    struct node *next;
};
```
It should not create (malloc) any new list elements.
It should just change the appropriate next field in the first list.
This and following questions use this datatype from lectures:
```
struct node {
    int data;
    struct node *next;
};
```
See list_empty.c and list.h for this weeks linked list tute questions, and test_list.c for autotests. Alternatively download all three files as tut_list_files.zip.
Implement a function copy which returns a copy of a linked list. It should have this prototype.
```
struct node *copy(struct node *head);
```
It should call malloc to create a new linked list of the same length and which contains the same data.
Implement a function identical that returns 1 if the contents of the two linked lists are identical (same length, same values in data fields) and otherwise returns 0. It should have this prototype:
```
int identical(struct node *head1, struct node *head2);
```
Implement a function ordered which returns 1 if a linked list is in (strictly) increasing order; 0 otherwise. It should have this prototype:
```
int ordered(struct node *head);
```
Implement a function set_intersection which given two linked lists in strictly increasing order returns a new linked list containing a copy of the elements found in both lists.
The new linked list should also be in strictly increasing order. It should include only elements found in both lists.

set_intersection should call malloc to create the nodes of the new linked list.

set_intersection should have this prototype:
```
struct node *set_intersection(struct node *set1, struct node *set2);
```
Implement a function set_union which given two linked lists in strictly increasing order returns a new linked list containing a copy of the elements found in either list.
The new linked list should also be in strictly increasing order. Elements found in both lists should only occur once in the new linked list.

set_union should call malloc to create the nodes of the new linked list.

set_union should have this prototype:
```
struct node *set_union(struct node *set1, struct node *set2);
```
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.
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.
1. Write a function strings_to_list which takes an array of pointers to strings and converts it to a linked list. It should have this prototype:
```
struct node *strings_to_list(int len, char *strings[]);
```
  Assume the strings contain only digit characters,
  It might be called like this:
```
    char *powers[] = {"2", "4", "8", 16"};
    struct node *head = strings_to_list(4, powers);
```
2. How would you use strings_to_list to convert a program's command line arguments to a linked list?
3. How would you use strings_to_list to convert a program's command line arguments to two linked lists?
  Assume, a command line argument of "-" separates the arguments to be converted.
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.
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?

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);

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.
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).
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)
```
Write a function to calculate the Manhattan distance between two points.
Use this function from the math.h library:
```
double fabs(double x);
```
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.
Write a C program thirteen_stdin.c which reads 2 integers from standard input and then prints all integers divisible by 13 between those numbers.
Your program should behave like this:
```
./a.out 
Enter start: 10
Enter finish: 42
13
26
39
```
Modify the previous C program so that it instead takes 2 integers as command line arguments
Your program should behave like this:
```
./a.out 10 42
13
26
39
```
Exam questions typically specify no error checking required.
If error checking was required - what checking would you add to the programs from the previous 2 questions?
Write a program median.c which reads integers until end-of-input is reached. It should then print the median (middle) of the integers. If there are an even number of integer you can print either of the two middle integers.
Assume the numbers of integer is > 0 and < 1000.

Assume the integer are entered in sorted (non-decreasing) order.

Your program should behave like this:
```
./a.out
1
2
4
8
16
5 numbers read. Median was 4
```
Modify the program from the previous question to check that the numbers of integers supplied is > 0 and < 1000, and to check they are in sorted (non-decreasing) order.
Modify the program from the previous question to handle integers entered in any order, e.g.
```
./a.out
16
8
2
1
4
5 numbers read. Median was 4
```
Write a function that takes an array of integers and the array length as arguments and performs the following:
- Determines the number, say n (n <= len) of distinct integers in the array.
- Modifies the array such that the first n elements are the distinct integers in the array - it does not matter what is in the rest of the array
Since the length of the array is variable you should not create additional arrays, nor assume a maximum array length. You may write extra functions in answering this question. Your function should have the following prototype:
```
int distinct_nums(int size, int nums[size]);
```
Running the function with the following input:
```
int nums[] = {7,3,1,4,7,3,6,5,3};
int num_distinct = distinct_nums(9, nums);
```
Should return the value 6 and the first six elements of the array should be changed to: {7,3,1,4,6,5}
Write a function that takes in a 2d array of ints and multiplies every value in the array by a given int.
Write a function, prototype below, that takes a string, and a character and removes the first occurrence of that character from the string. It should return 1 if the letter was found and removed, 0 otherwise. Write a main function that could test this function.
```
int remove_char(char str[], char c)
```
Write a function that takes 2 strings as arguments and returns the length of their common prefix.
For example "carpark" and "carpet" have a common prefix length of 4.

Write a function that takes an array of pointers to strings and prints out all the strings with more than a given number of characters. The prototype should be

// text - the array of strings
// array_size - the number of strings in the array
// num_chars - print out any strings in the array with more than this number
// of characters
void print_if_longer(int array_size, char text[array_size][MAX_LEN], int num_chars);

What would be the output of the following code?

int x = -9;
int *p1 = &x;
int *p2;

p2 = p1;
printf("%d\n", *p2);
*p2 = 10;
printf("%d\n",x);

What would be the output of the following code?

int x = -9;
int y = 0;

while (x != 0){
    y = y - 1;
    x = x + 1;
}

printf("%d\n", x);
printf("%d\n",y);

What would be the output of the following code?

int i = -7;
int j = 0;

while (i != 0){
    j = j - i;
    i = i + 1;
}

printf("%d\n", i);
printf("%d\n",j);

Given the following code fragment:
```
char goals[] = "All your goals belong to us.";
char *a, *b, *c;

a = goals + 5;
b = &goals[10];
c = goals + (b - goals) + (b - a);
```
The fragment is valid C. It executes without error. Indicate clearly and exactly what the following expressions evaluate to:
1. a == goals
2. a > goals
3. goals > c
4. c - b
5. goals - a
6. a[0] != b[0]
7. *c
8. goals[a - goals] == *a
9. c[a - b]
Given the following code fragment:
```
int i = 0;
int j = 0;
char *s = "ceded";

while (s[i] != '\0') {
  j = j + s[i] - 'a';
  i = i + 1;
}
printf("%d %d\n", i, j);
```
The fragment is valid C. It executes without error. Indicate clearly and exactly what output will be printed.
Write a function with the prototype below that calculates the sum and the product of all the integers in the given array.
```
void sum_prod(int len, int nums[len], int *sum, int *product);
```
Write a function,that takes a string along with a character and returns 1 if the character is found in the string and 0 otherwise. You must implement this function recursively. You may not use loops or C library functions. Write a main function that could test this function.

Revision questions