Extra Lab Solution

Possible Solution

sorter.c

static void sort(int a[], int n) {
	int i, j, nswaps;
	for (i = 0; i < n; i++) {
		nswaps = 0;
-		for (j = n - 1; j > i; j++) {
+		for (j = n - 1; j > i; j--) {
			if (a[j] < a[j - 1]) {
				int tmp;
				tmp = a[j];
				a[j] = a[j - 1];
				a[j - 1] = tmp;
				nswaps++;
			}
		}
		if (nswaps == 0)
			break;
	}
}

Set.c

Set SetNew(void) {
-	Set s = malloc(sizeof(Set));
+	Set s = malloc(sizeof(struct set));
	if (s == NULL) {
		fprintf(stderr, "couldn't allocate set\n");
		exit(EXIT_FAILURE);
	}
	
+	s->root = NULL;
+	s->size = 0;
	return s;
}

void SetFree(Set s) {
	doSetFree(s->root);
+	free(s);
}

static void doSetFree(Node n) {
+	if (n == NULL) return;

+	doSetFree(n->left);
+	doSetFree(n->right);
	free(n);
-	free(n->left);
-	free(n->right);
}

void SetAdd(Set s, int elem) {
-	s->root = doSetAdd(s->root, elem);
-	s->size++;
+	if (!SetContains(s, elem)) {
+		s->root = doSetAdd(s->root, elem);
+		s->size++;
+	}
}

static Node doSetAdd(Node n, int elem) {
	if (n == NULL) {
		return newNode(elem);
	}
	
	if (elem < n->elem) {
-		doSetAdd(n->left, elem);
+		n->left = doSetAdd(n->left, elem);
	} else if (elem > n->elem) {
-		doSetAdd(n->right, elem);
+		n->right = doSetAdd(n->right, elem);
	}
	return n;
}

bool SetContains(Set s, int elem) {
	Node n = s->root;
	
	// iterative search
	while (n != NULL) {
		if (elem == n->elem) {
			return true;
		}
		if (elem < n->elem) {
			n = n->left;
-		}
-		if (elem > n->elem) {
+		} else {
			n = n->right;
		}
	}
	
	return false; // couldn't find element
}