CS136 Assignment 9

Due Wednesday, Nov. 21 at 11:59 am sharp. Late submissions will receive half marks if submitted before Dec. 3 at 11:59 AM sharp.

Note: 10 marks on this assignment will be from hand-marking for style and possibly efficiency.

Assignment 9 Problem 1 [10 marks]. File: readint.c

In this question, the goal is to write a function readint with the signature:

int readint(void);

It does not consume any arguments but produces an integer read from standard input using the function getchar. The first character read will be part of a valid integer and reading should terminate when the first character not part of the integer is detected - your function should consume the maximal number of characters to compose the integer.

Assignment 9 Problem 2 [30 marks]. File: arraystuff.c

Implement the interface given in arraystuff.h.

Assignment 9 Problem 3 [31 marks]. File: mystring.c

Implement the interface given in mystring.h. You may not use any function defined in <string.h> or <strings.h>.

Assignment 9 Problem 4 [30 marks]. File: mystring.c

Augment your solution for problem 3 to include an implementation of 
   char *mystrstr(char *haystack, char *needle);
   // find the first occurrence of string needle
   // in string haystack
   // identical to strstr in <string.h>
   // running time O(mystrlen(needle)*mystrlen(haystack))
You may not use any function defined in <string.h> or <strings.h>.

Sample Test Program

#include <stdio.h>
#include "mystring.h"

int main(){
   char *a = "wxyz";
   char *b = "xy";
   char *c = mystrstr(a,b);
   printf("%p %p %p\n",a,b,c);
}

Diagram of Test Program Result


  c ----------
              |
              |
              v
        +---+---+---+---+----+
  a --> | w | x | y | z | \0 |
        +---+---+---+---+----+
        107a0

        +---+---+----+
  b --> | x | y | \0 |
        +---+---+----+ 
        107a8

Possible Output for Test Program

107a0 107a8 107a1
The test program searches for the needle "xy" in the haystack "wxyz". The result is a pointer into the haystack where "xy" (without the null terminator) is found. The possible output illustrates the situation where the haystack happens to be at address 107a0 and the needle happens to be at address 107a8. The needle is found within the haystack at address 107a1.

Assignment 9 Bonus [5 marks]. File: mystring.c

Modify your mystrstr function from problem 4 to have running time O(mystrlen(needle)2+mystrlen(haystack)).

Hint: This problem is hard, but you have all the basic tools you need to solve it. Pay attention to the running time constraint. You can find methods for string searching on the web, but you'll learn more if you work it out for yourself, as opposed to trying to reproduce a method you don't understand. String searching is considered in cs240 and cs241, and at great length in cs462 and cs482.

Assignment 9 Bonus 2 [5 marks]. File readstring.c

In this question, the goal is to write a function readstring with the signature:

char* readstring(void);

It does not consume any arguments but produces a pointer to a string read from standard input. There is no limit on the length of the string (aside from the physical limitations of memory). The string terminates when either a space or newline character is read. The function should have runtime of O(n) where n is the number of characters read and the string produced should only allocated the exact amount of memory required to store the string (i.e. no extra space). Failure to meet these requirements will forfeit the marks on this question even if you pass the tests for correctness.