COMP1511 Week 13 Tutorial Sample Answers

Your tutor has asked a lab pair to present their week 12 work.
Discuss the good, the bad and the ugly aspects of their code.
Please be gentle in any criticism - we are all learning!
Did you blog last week? What is this week's blogging theme?
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?
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 testList.c for autotests. Alternatively download all three files at tut_list_files.zip.

See list.c for a version with the functions implemented.

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 containg the same data.

An iterative solution:

struct node *copy(struct node *head) {
    if (head == NULL) {
        return NULL;
    }
    struct node *new_head = malloc(sizeof (struct node));
    assert(new_head);
    new_head->data = head->data;

    struct node *last_new_node = new_head;
    struct node *p = head->next;

    while (p != NULL) {
        last_new_node->next = malloc(sizeof (struct node));
        last_new_node = last_new_node->next;
        assert(last_new_node != NULL);
        last_new_node->data = p->data;
        p = p->next;
    }
    last_new_node->next = NULL;

    return new_head;
}

A recursive solution:

struct node *copy(struct node *head) {
    if (head == NULL) {
        return NULL;
    }
    struct node *new_head = malloc(sizeof (struct node));
    assert(new_head);
    new_head->data = head->data;
    new_head->next = copy(head->next);
    return new_head;
}

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

An iterative solution:

int identical(struct node *head1, struct node *head2) {
    struct node *p1 = head1;
    struct node *p2 = head2;

    while (p1 != NULL && p2 != NULL) {
        if (p1->data != p2->data) {
            return 0;
        }
        p1 = p1->next;
        p2 = p2->next;
    }

    return p1 == p2;
}

A recursive solution:

int identical(struct node *head1, struct node *head2) {
    if (head1 == NULL && head2 == NULL) {
        return 1;
    }
    if (head1 == NULL || head2 == NULL || head1->data != head2->data) {
        return 0;
    }
    return identical(head1->next, head2->next);
}

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

An iterative solution:

int ordered(struct node *head) {
    if (head == NULL || head->next == NULL) {
        return 1;
    }
    struct node *p = head;
    while (p->next->next != NULL) {
        if (p->data >= p->next->data) {
            return 0;
        }
    }
    return 1;
}

A recursive solution:

int ordered(struct node *head) {
    if (head == NULL || head->next == NULL) {
        return 1;
    }
    if (head->data >= head->next->data) {
        return 0;
    }
    return ordered(head->next);
}

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

A recursive solution:

struct node *set_intersection(struct node *set1, struct node *set2) {
    if (set1 == NULL || set2 == NULL) {
        return NULL;
    }
    if (set1->data == set2->data) {
        struct node *new_head = malloc(sizeof (struct node));
        assert(new_head != NULL);
        new_head->data = set1->data;
        new_head->next = set_intersection(set1->next, set2->next);
        return new_head;
    } else if (set1->data < set2->data) {
        return set_intersection(set1->next, set2);
    } else {
        return set_intersection(set1, set2->next);
    }
}

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

A recursive solution:

struct node *set_union(struct node *set1, struct node *set2) {
    if (set1 == NULL && set2 == NULL) {
        return NULL;
    }
    struct node *new_head = malloc(sizeof (struct node));
    assert(new_head != NULL);
    if (set1 != NULL && set2 != NULL && set1->data == set2->data) {
        new_head->data = set1->data;
        new_head->next = set_union(set1->next, set2->next);
    } else if (set2 == NULL || (set1 != NULL && set1->data < set2->data)) {
        new_head->data = set1->data;
        new_head->next = set_union(set1->next, set2);
    } else {
        new_head->data = set2->data;
        new_head->next = set_union(set1, set2->next);
    }
    return new_head;
}

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.

Write a C program thirteen_stdin.c which reads 2 integers from standard input and then prints all integers divisble by 13 between those numbers.

Your program should behave like this:

./a.out 
Enter start: 10
Enter finish: 42
13
26
39

Sample solution thirteen_stdin.c

#include <stdio.h>

int main(void) {
    int i, lower, upper;

    printf("Enter start: ");
    scanf("%d", &lower);
    printf("Enter finish: ");
    scanf("%d", &upper);

    i = lower + 1;
    while (i < upper) {
        if (i % 13 == 0) {
            printf("%d\n", i);
        }
        i = i + 1;
    }
    return 0;
}

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

Sample solution thirteen_atoi.c

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[]) {
    int i, lower, upper;

    lower = atoi(argv[1]);
    upper = atoi(argv[2]);

    i = lower + 1;
    while (i < upper) {
        if (i % 13 == 0) {
            printf("%d\n", i);
        }
        i = i + 1;
    }
    return 0;
}

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?
Check scanf suceeded (returned 1).
Check two arguments present (argv == 3).
In both cases you might check first number is not greater than first.
You might check arguments or input are numeric (more difficult)

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

Sample solution median.c

#include <stdio.h>

#define MAX 1000

int main(void) {
    int x[MAX];
    int number;
    int numbersRead;

    numbersRead = 0;
    while (scanf("%d", &number) == 1) {
        x[numbersRead] = number;
        numbersRead = numbersRead + 1;
    }
    printf("%d numbers read. Median was %d\n", numbersRead, x[numbersRead/2]);
    return 0;
}

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.

Sample solution median.c

#include <stdio.h>

#define MAX 1000

int main(void) {
    int x[MAX];
    int number;
    int numbersRead;

    numbersRead = 0;
    while (scanf("%d", &number) == 1 && numbersRead < MAX) {
        if (numbersRead > 0 && number < x[numbersRead - 1]) {
            printf("Numbers not in order\n");
            return 1;
        }
        x[numbersRead] = number;
        numbersRead = numbersRead + 1;
    }

    if (numbersRead > 1) {
        printf("%d numbers read. Median was %d\n", numbersRead, x[numbersRead/2]);
    }
    return 0;
}

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

Sample solution median.c

#include <stdio.h>

#define MAX 1000

int main(void) {
    int x[MAX];
    int i, number, numbersRead;

    numbersRead = 0;
    while (scanf("%d", &number) == 1 && numbersRead < MAX) {
        i = numbersRead;
        while (i > 0 && x[i - 1] > number) {
            x[i] = x[i - 1];
            i = i - 1;
        }
        x[i] = number;
        numbersRead = numbersRead + 1;
    }

    if (numbersRead > 1) {
        printf("%d numbers read. Median was %d\n", numbersRead, x[numbersRead/2]);
    }
    return 0;
}

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 numDistinct = 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}

Sample solution (whole program)

#include <stdio.h>

int distinct_nums(int size,int nums[size]);
void  print_array(int size, int nums[size]);

int main(int argc, char * argv[]){
    int nums[] = {7,3,1,4,7,3,6,5,3};

    print_array(9, nums);

    int numDistinct = distinct_nums(9, nums);
    print_array(numDistinct, nums);
    return 0;
}

// Moves the distinct numbers down to the front of the array
int distinct_nums(int size, int nums[size]) {
    int distinct = 0;

    // search through the distinct part of the array to see if
    // it is a duplicate.
    for (int i = 0 ; i < size; i++) {
        int seen = 0;
        for (int j = 0; j < distinct; j++) {
            if (nums[i] == nums[j]) {
                 seen = 1;
            }
        }
        // If it is distinct, move down into the next distinct location
        if (seen == 0) {
            nums[distinct] = nums[i];
            distinct++;
        }
    }
    return distinct;
}

void print_array(int size, int nums[size]) {
    for (int i = 0; i < size; i++) {
      printf("%d ",nums[i]);
    }
    printf("\n");
}

Write a function that takes in a 2d array of ints and multiplies every value in the array by a given int.


void scalar_mutliply(int rows, int columns, int matrix[rows][columns],  int scalar){
    int i,j;
    for (i = 0;i < rows; i = i + 1) {
        for (j = 0;j < columns; j = j + 1) {
            matrix[i][j] = matrix[i][j] * scalar;
        }
    }
}

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)

int remove_char(char str[], char c) {
    int i;

    // Find the first occurrence of the character c
    i = 0
    while (str[i] != '\0' && str[i] != c) {
        i = i + 1;
    }
    if (str[i] == '\0') {
        return 0;
    }

    // We found the letter, do shift all the letters
    // after it, down one cell in the array
    while (str[i] != '\0') {
        str[i] = str[i + 1];
        i = i + 1;
    }

    return 1;
}

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.
```
int prefixLen(char s1[], char s2[]) {
   int i = 0;
   while (s1[i] == s2[i] && s1[i] != '\0') {
          i = i + 1
   }
   return i;
}
```

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
// arraySize - the number of strings in the array
// numChars - print out any strings in the array with more than this number
// of characters
void printIfLonger(int arraySize, char text[arraySize][MAX_LEN], int numChars);

void printIfLonger(char *text[],int arraySize, int numChars){
    int i;
    for (i = 0; i < arraySize; i = i + 1) {
        if (strlen(text[i]) > numChars) {
            printf("%s",text[i]);
        }
    }
}

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

-9
10

What would be the output of the following code?

int x = -9;
int y = 0;

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

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

0
-9

What would be the output of the following code?

int i = -7;
int j = 0;

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

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

0
-28

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
  0 - this is asking whether a points to the same memory address as goals. It doesn't.
2. a > goals
  1 - a points to a higher memory address than goals
3. goals > c
  0 - goals does not point to a higher memory address than c
4. c - b
  5
5. goals - a
  -5
6. a[0] != b[0]
  0 - a[0] is 'o', so is b[0]
7. *c
  'b' - the letter that c points to
8. goals[a - goals] == *a
  1 as they both have the value 'o'
9. c[a - b]
  'o'
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.
```
5 16
```
Here, s is a char pointer that points to the first letter of the string "str". We can index into it since strings are arrays. The loop terminates when s[i] is '\0', i.e., 0, which happens when i is 5.
Indexing into s gives individual characters; subtracting 'a' from each of those gives the 'distance' between the character and 'a', e.g., s[0] - 'a' => 'c' - 'a' = 2.

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

Sample solution (whole program)

#include <stdio.h>

void sumProd(int len, int nums[len], int *sum, int *product);

int main(int argc, char *argv[]){
   int nums[] = {3,4,1,5,6,1};
   int prod;
   int sum;

   //Pass in the address of the sum and product variables
   sumProd(6, nums, &sum, &prod);

   printf("The sum is %d and prod is %d\n",sum,prod);
   return 0;
}


// Calculates the sum and product of the array nums.
// Actually modifies the  variables that *sum and *product are pointing to
void sumProd(int len, int nums[len], int *sum, int *product) {
    int i;
    *sum = 0;
    *product = 1;
    for (i = 0; i < len; i = i + 1) {
        *sum = *sum + nums[i];
        *product = *product * nums[i];
    }
}

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.
```
int findChar(char str[], char c) {
    if (str[0] == c) {
        return 1;
    } else if (str[0] == '\0') {
        return 0;
    } else {
       return findChar(&str[1], c);
    }
}
```

Write a program that reads a set of integer numbers from a file and writes all numbers to an output file in increasing order.

The name of the input file will be the first command line argument.

The name of the output file will be the second command line argument.

In both files there should be one number per line and there will be a maximum of 1000 numbers.

Sample solution (whole program)

#include <stdio.h>

#define MAX 1000

int readNumbers(char *filename, int nums[], int max);
void bubbleSort(int a[], int size);
void writeNumbers(char *filename, int nums[], int size);

int main(int argc, char *argv[]) {
    int nums[MAX];
    int size = 0;
    if (argc < 3) {
        fprintf(stderr,"Incorrect Usage\n");
    }else{
         size = readNumbers(argv[1], nums, MAX);
         bubbleSort(nums, size);
         writeNumbers(argv[2], nums, size);
    }
    return 0;
}

//Reads in a maximum of max numbers into the array nums, from
//a specified file. Returns the number of lines
//actually read in.
int readNumbers(char *filename, int nums[], int max){
     FILE *fp;
     int counter = 0;
     fp = fopen(filename,"r");
     if (fp == NULL) {
          fprintf(stderr,"Unable to open file %s\n",filename);
     } else {
          while (counter < max && fscanf(fp,"%d",&nums[counter]) == 1) {
                counter = counter + 1;
          }
          fclose(fp);
     }
     return counter;
}

//Sorts the given array using bubble sort
void bubbleSort(int a[], int size) {
    int swapped = 1;
    int tmp,i;

    while (swapped == 1) {
        swapped = 0;
        for (i = 0; i < size - 1; i = i + 1) {
            if (a[i] > a[i + 1]) {
                tmp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = tmp;
                swapped = 1;
            }
        }
        size = size - 1;
    }
}

//Writes one number per line from the array nums
//into the specified file
void writeNumbers(char *filename, int nums[], int size) {
     FILE *fp;
     int i;
     fp = fopen(filename,"w");
     if (fp == NULL) {
          fprintf(stderr, "Unable to open file %s\n", filename);
     } else {
          for (i = 0; i < size; i = i + 1) {
              fprintf(fp, "%d\n", nums[i]);
          }
          fclose(fp);
     }
}