Practial 3

Question 1

mylib.c

Answer 1

#include stdlib.h
#include stdio.h
#include "mylib.h"
#include assert.h
#include ctype.h

/* INSERT GETWORD HERE */

void *emalloc(size_t s){
    void *result = malloc(s);
    if (NULL == result){
        fprintf(stderr, "Memory allocation failed!\n");
        exit(EXIT_FAILURE);
    }
    return result;
}

Question 2

mylib.h

Answer 2

include

#ifndef MYLIB_H_
#define MYLIB_H_

extern void *emalloc(size_t);
extern int getword(char *s, int limit, FILE *stream);

Question 3

htable_new

Answer 3

htable htable_new(int capacity){
    int i;
    htable result = emalloc(sizeof *result);
    result->capacity = capacity;
    result->num_keys = 0;
    result->keys = emalloc(result->capacity * sizeof result->keys[0]);

    for (i=0; I less than result->capacity; I++){
            keys[i] = NULL;
    }
    return result;
}

Question 4

htable_insert (Part 1)

Answer 4

int htable_insert(htable h, char *str){
    int collisions = 0;
    unsigned int i = htable_word_to_int(str) % h->capacity;

    if (h->keys[i] == NULL){
        h->keys[i] = emalloc((strlen(str) + 1) * sizeof str[0]);
        strcpy(h->keys[i], str);
        h->num_keys++;
        return 1;
    }

Question 5

htable_insert (Part 2)

Answer 5

while (h->keys[i] != NULL && strcmp(h->keys[i],str) != 0 &&
(collisions-1) != h->capacity){
i = (i+1)% h->capacity;
collisions++;

        if (h->keys[i] == NULL){
            h->keys[i] = emalloc((strlen(str) + 1) * sizeof str[0]);
            strcpy(h->keys[i], str);
            h->num_keys++;
            return 1;
        }
/* IF ++collisions GREATER than capacity */
        if (++collisions > h->capacity) return 0;
    }
    return 0;
}

Question 6

htable_print

Answer 6

void htable_print(htable h, FILE *stream){
/* GIVEN PRINT CODE */
}

Question 7

htable_free

Answer 7

void htable_free(htable h){
    int i;
    for (i=0;i< h->capacity; i++){
        free(h->keys[i]);
    }
    free(h->keys);
    free(h);
}

Question 8

bst housekeeping

Answer 8

#include stdio.h
#include stdlib.h
#include "mylib.h"
#include "bst.h"
#include string.h

struct bst_node {
    char *key;
    bst left;
    bst right;
};

Question 9

bst_new() (SIMPLE!!)

Answer 9

bst bst_new(){
      return NULL;
}

Question 10

bst_insert

Answer 10

bst bst_insert(bst b, char *str){
    if (b == NULL){
        b = emalloc(sizeof *b);
        b->key = emalloc(strlen(str)+ 1);
        strcpy(b->key, str);
        b->left = NULL;
        b->right = NULL;
    } else if (strcmp(b->key, str) < 0){
        b->right = bst_insert(b->right, str);
    } else if (strcmp(b->key, str) > 0){
        b->left = bst_insert(b->left, str);
    }
    return b;
}

Question 11

bst_inorder

Answer 11

void bst_inorder(bst b, void f(char *str)){
    if (b== NULL){
        return;
    }
    bst_inorder(b->left, f);
    f(b->key);
    bst_inorder(b->right, f);
}

Question 12

bst_preorder

Answer 12

void bst_preorder(bst b, void f(char *str)){
    if (NULL == b){
        return;
    }
    f(b->key);
    bst_preorder(b->left, f);
    bst_preorder(b->right, f);
}

Question 13

bst_search

Answer 13

int bst_search(bst b, char *str){
    if (NULL == b){
        return 0;
    } else {
        int compare = strcmp(b->key, str);
        if (compare == 0){
            return 1 ;
        } else if (compare < 0){
            return bst_search(b->right, str);
        } else {
            return bst_search(b->left, str);
        }
    }
    return 0;
}

Question 14

bst_free

Answer 14

bst bst_free(bst b){
    if (b == NULL){
        return b;
    }
    bst_free(b->right);
    bst_free(b->left);
    free(b->key);
    free(b);
    return b;
}

Question 15

ARRAY queue_new

Answer 15

queue queue_new(){
    int i;
    queue result = emalloc(sizeof *result);
    result->head = 0;
    int default_size = 7;
    result->capacity = DEFAULT_SIZE;
    result->num_items = 0;
    result->items = emalloc(result->capacity * sizeof result->items[0]);
    for (i=0; i < result->capacity; i++){
        result->items[i] = 0.0;
    }
    return result;
}

Question 16

ARRAY dequeue

Answer 16

double dequeue(queue q){
    double target;
    if (q->num_items == 0){
        fprintf(stderr, "Queue is empty.\n");
        return EXIT_FAILURE;
    }
    target = q->items[q->head];
    q->head++;
    q->num_items--;
    return target;
}

Question 17

ARRAY queue_print

Answer 17

void queue_print(queue q){
    int i = q->head;
    do {
        printf("%.2f\n", q->items[i]);
        i = (i+1)%q->capacity;
    } while (i != (q->head + q->num_items)%q->capacity);
}

Question 18

ARRAY queue_size and queue_free

Answer 18

int queue_size(queue q){
    return q->num_items;
}

queue queue_free(queue q){
    free(q->items);
    free(q);
    return q;
}

Question 19

ARRAY queue housekeeping

Answer 19

define DEFAULT_SIZE 7

struct queue {
    double *items;
    int head;
    int capacity;
    int num_items;
};

Question 20

LIST queue housekeeping

Answer 20

struct q_item{
double item;
q_item next;
};

struct queue {
    q_item first;
    q_item last;
    int length;
};

Question 21

LIST queue_new

Answer 21

queue queue_new(){
    queue q = emalloc(sizeof *q);
    q->first = NULL;
    q->last = NULL;
    q->length = 0;
    return q;
}

Question 22

LIST dequeue

Answer 22

double dequeue(queue q){
    q_item head = q->first;
    double result;
    if (NULL == head){
        return 0.0;
    }
    q->first = q->first->next;
    result = head->item;
    free(head);
    q->length--;
    return result;
}

Question 23

LIST queue_print

Answer 23

void queue_print(queue q){
    q_item temp = q->first;
    int i;
    for (i=0; i < q->length;i++){
        printf("%.2f\n", temp->item);
        temp = temp->next;
    }
} .

Question 24

LIST queue_size

Answer 24

int queue_size(queue q){
    return q->length;
}

Question 25

List queue_free_aux

Answer 25

``` void queue_free_aux(q_item i){ q_item temp = i; while(i != NULL){ i = i->next; free(temp); temp = i; } } ```

Question 26

LIST queue_free

Answer 26

``` queue queue_free(queue q){ queue_free_aux(q->first); free(q); return q; } ```