CS 136 Assignment 8

Due Friday, March 21 at 11:59 AM sharp (noon).

Please read the preamble in Assignment 1.

Only the C language features introduced up to section 10 are allowed.


In your code, you do NOT have to check that the value returned from malloc (or realloc) is invalid (NULL).

You may assume that all C strings are null terminated: you do not have to assert this.

If a PRE-condition is that a structure is "valid", you may assume this, and you do are not required to to assert it.


Note: For Problem 1, you are NOT allowed to use the string.h library (module).


Assignment 8 Problem 0. [10 Marks correctness]

Problem 0 is a "warm-up" question. You are allowed to collaborate with your fellow classmates and discuss the solution on piazza.
  1. [1 mark] Write the C module strdup.c that implements the my_strdup function described in Module 10 slide 21 (you may use strcpy, but you are not allowed to use the strdup function in string.h).

    char *my_strdup(const char *s);

  2. [2 marks] Write the C module posn.c that provides the make_posn function described in posn.h.

  3. [2 marks] In this question you will revisit the manifests from A6. Write the C module reservation.c that provides the functions described in reservation.h.

  4. [5 marks] Write a C module readstr.c that implements a "safe" version of the gets function called readstr (see readstr.h for details).

    Your function must repeatedly call getchar() until a newline or EOF is encountered. The returned string must NOT include the EOF or newline. You may assume that all of the characters you read (except for newline) will be in the visible range (ASCII values 32..126).

    TIP: use a "doubling dynamic array" strategy. You will likely require multiple calls to realloc, including one call to set the final (correct) size. You can choose any initial dynamic array size you'd like (e.g., 1, 16, 64...).

    We have included a large file (alice.txt) that can be used as a ".in file" to test that your implementation can read a very large string.

    Note: Originally, this was not a "warm-up" question, but we believe you will all benefit from collaboration on this problem.


Assignment 8 Problem 1. [10 Marks for correctness.]

Write a C module strappend.c that implements a strappend function (see strappend.h for details).

NOTE: For this question, you cannot use string.h

Public test sample:

strappend("hello","world") returns the new string "helloworld"


Assignment 8 Problem 2. [10 Marks for correctness.]

Write a C module afilter.c that provides the abstract array function afilter. See the interface file afilter.h for more details.

Public test sample:
for a dynamic array da of length 6: (4 8 15 16 23 42)
and the following function:
bool is_even(int n) { return n % 2 == 0; }
then, afilter(da, is_even) would modify da to be of length 4: (4 8 16 42)


Assignment 8 Problem 3. [15 Marks for correctness.]

Write a program skipints.c that reads in a sequence of positive integers using scanf("%d", &i) until a 0 is encountered (you can assume only positive integers will be entered in the sequence, and no EOF is encountered). The program then reads in a final positive integer k. The program then prints every k-th integer from the original sequence of integers. Each integer printed is followed by a newline.

Examples: If k is 1, it prints the full sequence of integers. If k is 2, it prints every other integer, ignoring the first, third, etc. If k is equal to the length of the sequence, it prints out the last integer. If k is larger than the length of the sequence, then no integers are printed out.

Public test sample:
input:
4 8 15 16 23 42 0 2
output:
8
16
42

Assignment 8 Problem 4. [25 Marks for correctness, 10 Marks hand-marking.]

Write a C module aos.c for managing an array of strings. See the interface file aos.h for more details.

An array of strings is really an array of char pointers, where each pointer can then point to a string.

Public test sample:
struct aos *a = create_aos(10);
assert(aos_get(a,5) == NULL);
aos_set(a,"apple",5);
assert(strcmp(aos_get(a,5),"apple") == 0);
assert(aos_add(a,"zebra") == 0);
aos_sort(a);
assert(strcmp(aos_get(a,0),"apple") == 0);
assert(strcmp(aos_get(a,1),"zebra") == 0);
destroy_aos(a);


Assignment 8 Problem 5. [20 Marks for correctness.]

In this question, you will see a technique for storing a Binary Search Tree (BST) in an array. We will use the following rules: Consider the following BST:

It would be stored in the following array (blanks would contain INT_MIN):
index012345678910111213141516...
value5310-671242

Write a C module atree.c for managing a BST in an array. See the interface file atree.h for more details.