Week 11 Laboratory — BSTs, Files, Random Numbers

You can use dry run as usual:

prompt$ ~cs1921/bin/dryrun lab11

prompt$ ~cs1921/bin/dryrun lab11 2

Exercises

  1. (Binary Search Trees) Write a program called pruneTree.c that:

    Note: You might find this exercise challenging, although pruning requires just a single (recursive) function. You should start by copying data structures and functions from the lectures and last week's lab:

    typedef struct node { ... } Node;
    typedef Node *Tree;
    
    Node *newNode(int v);              // make a new node
    Tree insert(Tree t, int v);        // insert a node 'v' into a BST
    void printTree(Tree t, int level); // pretty-print a BST
    void freeTree(Tree t);             // free the tree
    

    Examples of program execution are:

    prompt$ ./pruneTree 2 1 3
    	1
    2
    	3
    Pruned tree:
    2
    

    prompt$ ./pruneTree 8 4 6 2 7 5 3 1 12 10 9 14 13 11 15
    			1
    		2
    			3
    	4
    			5
    		6
    			7
    8
    			9
    		10
    			11
    	12
    			13
    		14
    			15
    Pruned tree:
    		2
    	4
    		6
    8
    		10
    	12
    		14
    

    prompt$ ./pruneTree 6 5 4 3 2 1
    					1
    				2
    			3
    		4
    	5
    6
    Pruned tree:
    				2
    			3
    		4
    	5
    6
    

    prompt$ ./pruneTree 1 2 3 4 5 6
    1
    	2
    		3
    			4
    				5
    					6
    Pruned tree:
    1
    	2
    		3
    			4
    				5
    

    prompt$ ./pruneTree 5 6 7 1 2 3 4
    	1
    		2
    			3
    				4
    5
    	6
    		7
    Pruned tree:
    	1
    		2
    			3
    5
    	6
    

    prompt$ ./pruneTree 7
    7
    Pruned tree:
    

    If there are no arguments on the command line then the program generates a usage error message, as shown below:

    prompt$ ./pruneTree
    Usage: ./pruneTree integers ...
    

    If there is a non-numeric argument on the command line, a usage error message is also printed.

    prompt$ ./pruneTree 3 10 a
    Usage: ./pruneTree integers ...
    

  2. (Files) A 3-way merge of files involves taking the first line of each file, then adding the second line of each file, then the third line of each file, and so on until all lines in each of the files are exhausted. In this exercise, write a 3-way file merge program called merge3.c, where the 3 files are command-line arguments, and print the result on stdout. Errors should be sent to stderr. You can assume that each line of each file is less than BUFSIZ.

    For example, if the file FileA has contents:

    111
    111
    

    file FileB:

    222222
    222222
    222222
    222222
    222222
    222222
    222222
    

    and file FileC:

    333333333
    333333333
    333333333
    

    then the command:

    ./merge3 FileA FileB FileC
    

    will result in the output:

    111
    222222
    333333333
    111
    222222
    333333333
    222222
    333333333
    222222
    222222
    222222
    222222
    

    If an incorrect number of file arguments is given then the error message should be:

    ./merge3
    Usage: ./merge3 <fname1> <fname2> <fname3>
    

    ./merge3 FileA FileB
    Usage: ./merge3 <fname1> <fname2> <fname3>
    

    If one or more of the files cannot be opened then the error message should be:

    ./merge3 FileA FileB nothing
    Error in opening file
    

  3. (Randum numbers, linked lists) There are two parts to this exercise. In the first part you will generate random strings of letters: in the second part you will insert these letters into a linked list and then reverse the list. The programs from both parts should be submitted.

    1. Write a program called randword.c that generates a random word (consisting of just lower-case letters). When executed, the first command-line argument is the length of the word, and the second argument is the seed used by the random number generator (i.e. by random()). If there are not exactly 2 numerical command-line arguments then a usage message is output. Consider the following testcases:
      • Testcase 1: the execution
        prompt$ ./randword 10 1
        nwlrbbmqbh
        
        seeds the random-number generator with 1 and generates a random word of length 10.

      • Testcase 2: a different seed results in another word
        prompt$ ./randword 10 4334
        hzykhhffgg
        

      • Testcase 3: similarly
        prompt$ ./randword 10 4747
        ephhbtttto
        

      • Testcase 4: here is a testcase for a longer word:
        prompt$ ./randword 50 73861
        vvvvvhpliidmeowljxvmpahskmbhptskophmwxzghdsmroxcos
        

      • Testcase 5: if there are no arguments then we get
        prompt$ ./randword
        Usage: ./randword wordlength randomseed
        

      • Testcase 6: a non-numerical argument results in
        prompt$ ./randword a 123
        Usage: ./randword wordlength randomseed
        

      • Testcase 7: too many arguments result in
        prompt$ ./randword 10 123 1
        Usage: ./randword wordlength randomseed
        

        Note: It is important in this exercise that you call the random number generator as specified in lectures, otherwise the outputs will not match. If you use a different method to generate random numbers, the testcases 1 to 4 will 'fail', but your program could still be perfectly correct.

    2. Modify the random-word program above, calling the new program llrandword.c, to use a linked list to store the random word, one letter in each node in the list. Print the list, then reverse it and print the resulting list. The same testcases as above may be used here, but the output will look different if the command-line arguments are correct:

      • Testcase 1
        prompt$ ./llrandword 10 1
        n->w->l->r->b->b->m->q->b->h
        h->b->q->m->b->b->r->l->w->n
        

      • Testcase 2
        prompt$ ./llrandword 10 4334
        h->z->y->k->h->h->f->f->g->g
        g->g->f->f->h->h->k->y->z->h
        

      • Testcase 3
        prompt$ ./llrandword 10 4747
        e->p->h->h->b->t->t->t->t->o
        o->t->t->t->t->b->h->h->p->e
        

      • Testcase 4
        prompt$ ./llrandword 50 73861
        v->v->v->v->v->h->p->l->i->i->d->m->e->o->w->l->j->x->v->m->p->a->h->s->k->m->b->h->p->t->s->k->o->p->h->m->w->x->z->g->h->d->s->m->r->o->x->c->o->s
        s->o->c->x->o->r->m->s->d->h->g->z->x->w->m->h->p->o->k->s->t->p->h->b->m->k->s->h->a->p->m->v->x->j->l->w->o->e->m->d->i->i->l->p->h->v->v->v->v->v
        

      • Testcase 5, 6 and 7 are similar to the above (with the name of the executable different of course).

Submit your work using:


  give  cs1921  lab11  pruneTree.c  merge3.c  randword.c  llrandword.c