Practial 3 Flashcards
1
Q
mylib.c
A
#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;
}
2
Q
mylib.h
A
include
#ifndef MYLIB_H_ #define MYLIB_H_
extern void *emalloc(size_t);
extern int getword(char *s, int limit, FILE *stream);
3
Q
htable_new
A
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;
}
4
Q
htable_insert (Part 1)
A
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;
}
5
Q
htable_insert (Part 2)
A
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;
}
6
Q
htable_print
A
void htable_print(htable h, FILE *stream){
/* GIVEN PRINT CODE */
}
7
Q
htable_free
A
void htable_free(htable h){
int i;
for (i=0;i< h->capacity; i++){
free(h->keys[i]);
}
free(h->keys);
free(h);
}
8
Q
bst housekeeping
A
#include stdio.h #include stdlib.h #include "mylib.h" #include "bst.h" #include string.h
struct bst_node {
char *key;
bst left;
bst right;
};
9
Q
bst_new() (SIMPLE!!)
A
bst bst_new(){
return NULL;
}
10
Q
bst_insert
A
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;
}
11
Q
bst_inorder
A
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);
}
12
Q
bst_preorder
A
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);
}
13
Q
bst_search
A
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;
}
14
Q
bst_free
A
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;
}
15
Q
ARRAY queue_new
A
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;
}
16
Q
ARRAY dequeue
A
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;
}
17
Q
ARRAY queue_print
A
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);
}
18
Q
ARRAY queue_size and queue_free
A
int queue_size(queue q){
return q->num_items;
}
queue queue_free(queue q){
free(q->items);
free(q);
return q;
}
19
Q
ARRAY queue housekeeping
A
define DEFAULT_SIZE 7
struct queue {
double *items;
int head;
int capacity;
int num_items;
};
20
Q
LIST queue housekeeping
A
struct q_item{
double item;
q_item next;
};
struct queue {
q_item first;
q_item last;
int length;
};
21
Q
LIST queue_new
A
queue queue_new(){
queue q = emalloc(sizeof *q);
q->first = NULL;
q->last = NULL;
q->length = 0;
return q;
}
22
Q
LIST dequeue
A
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;
}
23
Q
LIST queue_print
A
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;
}
} .
24
Q
LIST queue_size
A
int queue_size(queue q){
return q->length;
}
25
Q
List queue_free_aux
A
void queue_free_aux(q_item i){
q_item temp = i;
while(i != NULL){
i = i->next;
free(temp);
temp = i;
}
}
26
Q
LIST queue_free
A
queue queue_free(queue q){
queue_free_aux(q->first);
free(q);
return q;
}
