View Single Post
Old 03-24-12, 08:44 AM   #6
wnd
Nerd, Geek, Freak
 
wnd's Avatar
 
Join Date: Sep 2005
Location: Finland
Posts: 703
Default Re: C programming issue

Nice signature. ;-)

Quote:
Originally Posted by smithdavid View Post
"write a program that reads n integers into an array, then prints on a separate line the value of each distinct element along with the number of times it occurs. the values should be printed in descending order."

and the program prints:

5 occurs 1 times
3 occurs 2 times
-7 occurs 3 times

it also asks that I use dynamic memory allocation and pointer arithmetic
Allocating memory dynamically is obvious, but what's the thing with pointer arithmetics here? Fine, I'll throw something in.

Using binary tree for storage and sorting:
Code:
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#define POINTER_ARITHMETICS


struct tree;

struct tree {
	struct tree *left;
	struct tree *right;
	int val;
	int count;
};



static struct tree *
tree_new_node(int val)
{
	struct tree *node = malloc(sizeof(struct tree));
	assert(node);
	node->val = val;
	node->count = 1;
	node->left = node->right = NULL;
	return node;
}



static struct tree *
tree_insert(struct tree *node, int val)
{
	if (node) {
		if (val == node->val) {
			node->count++;
		} else if (val < node->val) {
			if (node->left) {
				tree_insert(node->left, val);
			} else {
				node->left = tree_new_node(val);
			}
		} else {
			if (node->right) {
				tree_insert(node->right, val);
			} else {
				node->right = tree_new_node(val);
			}
		}
		return node;
	} else {
		return tree_new_node(val);
	}
}



static void
tree_print(struct tree *tree)
{
	if (tree->right) {
		tree_print(tree->right);
	}
	printf("%d occured %d time%s\n",
			tree->val,
			tree->count,
			tree->count == 1 ? "" : "s");
	if (tree->left) {
		tree_print(tree->left);
	}
}



static void
tree_free(struct tree *tree)
{
	if (tree->left) {
		tree_free(tree->left);
	}
	if (tree->right) {
		tree_free(tree->right);
	}
	free(tree);
}



int
main(int argc, char **argv)
{
	struct tree *tree = NULL;
#ifdef POINTER_ARITHMETICS
	int *arr = NULL;
	int *arr_ptr;
	int i;
	int an = 0;

	while (1) {
		int val;
		int r;
		int *new_arr;

		r = scanf("%d", &val);
		if (r != 1 || r == EOF) {
			break;
		}

		new_arr = realloc(arr, (an + 1) * sizeof(int));
		assert(new_arr);
		arr = new_arr;
		arr[an] = val;
		an++;
	}

	/* arr_ptr++ is your obligatory pointer arithmetics part ;-) */
	for (arr_ptr = arr, i = 0; i < an; arr_ptr++, i++) {
		int val = *arr_ptr;
		tree = tree_insert(tree, val);
	}
	free(arr);
#else
	while (1) {
		int val, r;

		r = scanf("%d", &val);
		if (r != 1 || r == EOF) {
			break;
		}
		tree = tree_insert(tree, val);
	}
#endif

	tree_print(tree);
	tree_free(tree);

	return EXIT_SUCCESS;
}
Using flat arrays for storage and qsort for sorting:
Code:
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>


struct instance {
	int	val;
	int	count;
};



static int
instance_cmp(const void *ap, const void *bp)
{
	const struct instance *a = ap;
	const struct instance *b = bp;

	return (a->val < b->val) ? 1 : ((a->val > b->val) ? -1 : 0);
}



int
main(int argc, char **argv)
{
	int *arr = NULL;
	int *arr_ptr;
	struct instance *instance = NULL;
	int an = 0;
	int n = 0;
	int i, j;

	while (1) {
		int val;
		int r;
		int *new_arr;

		r = scanf("%d", &val);
		if (r != 1 || r == EOF) {
			break;
		}

		new_arr = realloc(arr, (an + 1) * sizeof(int));
		assert(new_arr);
		arr = new_arr;
		arr[an] = val;
		an++;
	}

	for (arr_ptr = arr, i = 0; i < an; arr_ptr++, i++) {
		int val = *arr_ptr;
		int seen = 0;
		int *new_instance;

		for (j = 0; j < n; j++) {
			if (instance[j].val == val) {
				instance[j].count++;
				seen = 1;
				break;
			}
		}
		if (seen) {
			continue;
		}

		new_instance = realloc(instance,
				(n + 1) * sizeof(struct instance));
		assert(new_instance);

		instance = new_instance;
		instance[n].val = val;
		instance[n].count = 1;
		n++;
	}
	free(arr);

	qsort(instance, n, sizeof(struct instance), instance_cmp);

	for (i = 0; i < n; i++) {
		printf("%d occurs %d time%s\n", instance[i].val,
				instance[i].count,
				instance[i].count == 1 ? "" : "s");
	}

	free(instance);

	return EXIT_SUCCESS;
}

At first I was just looking at sample I/O and I wrote a version that inverts the tree (that is, allows ordering by count, not value). Then I reread the assignment...
__________________
web | cat

Christianity, noun: The belief that a cosmic Jewish Zombie who was his own father can make you live forever if you symbolically eat his flesh and telepathically tell him you accept him as your master, so he can remove an evil force from your soul that is present in humanity because a rib-woman was convinced by a talking snake to eat from a magical tree. [mad.frog]
wnd is offline   Reply With Quote