Thread: array occurences

  1. #1
    Registered User
    Join Date
    Jan 2003
    Posts
    115

    array occurences

    Hi guys, ive tried to implement an array to find out the occurence of a single number, im stuck because i dont know how to display the number and its frequency in the output. Ive searched the board but it only mentions using 2d arrays and stuff.
    Thanks

    Code:
    /* Write a program that reads in some integer values,
     * and counts the frequency of each value in the input
    */
    
    #include <stdio.h>
    #define SIZE 1000
    
    int values_array( int [], int );
    void calc_freq( int [], int );
    void print_array( int [], int );
    
    int main()
    {
    	int numbers[SIZE], values, freq;
    
    	values = values_array( numbers, SIZE );
    	printf( "Numbers Entered: " );
    	print_array( numbers, values );
    	calc_freq( numbers, values );
    	printf( "%4s%17s\n", "Number", "Frequency" );
    	print_array( numbers, values );
    
    	return 0;
    }
    
    int values_array( int A[], int size )
    {
    	int num, n=0;
    	printf( "Enter some numbers, crtl-D to end: " );
    	while ( scanf("%d", &num ) == 1 ) {
    		A[n] = num;
    		n++;
    	}
    	return n;
    }
    
    void calc_freq( int A[], int n )
    {
    	int i, j;
    	for ( i = 0; i<n ; i++ )
    		for ( j =i+1; j< n; j++ ) {
    			if (A[i] == A[j])
    				++A[i];
    			}
    }
    
    void print_array( int A[], int n )
    {
    	int i;
    	for ( i = 0; i < n; i++ ) {
    		printf( "%3d", A[i] );
    	}
    }
    there are only 10 people in the world, those who know binary and those who dont

  2. #2
    Open to suggestions Brighteyes's Avatar
    Join Date
    Mar 2003
    Posts
    204
    /* Write a program that reads in some integer values,
    * and counts the frequency of each value in the input
    */
    A binary tree would be waaaaay better for this problem
    Code:
    /* No error checking done, be sure to add it if you use my code */
    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct node *NODE;
    
    struct node {
        NODE left;
        NODE right;
        int num;
        int count;
    };
    
    NODE add(NODE tree, int num)
    {
        if (tree == NULL)
        {
            tree = malloc(sizeof (*tree));
            tree->num = num;
            tree->count = 1;
            tree->left = NULL;
            tree->right = NULL;
        }
        else if (num < tree->num)
            tree->left = add(tree->left, num);
        else if (num > tree->num)
            tree->right = add(tree->right, num);
        else
            tree->count++;
    
        return tree;
    }
    
    void display(NODE tree)
    {
        if (tree != NULL)
        {
            display(tree->left);
            printf("%-5d%-5d\n", tree->num, tree->count);
            display(tree->right);
        }
    }
    
    int main(void)
    {
        int num;
        NODE tree;
    
        tree = NULL;
    
        printf("Enter a list of numbers (ctrl+z to quit): ");
        fflush(stdout);
    
        while (scanf("%d", &num) == 1)
            tree = add(tree, num);
    
        printf("Num\tCount\n");
        display(tree);
    
        return 0;
    }

  3. #3
    ....
    Join Date
    Aug 2001
    Location
    Groningen (NL)
    Posts
    2,380
    You need to calculate the frequency of each value in the array? Then your algorithm isn't correct.

    > values = values_array( numbers, SIZE );

    Here you fill the array with values.

    > calc_freq( numbers, values );

    Here you want to calculate the frequency of each value in the array. When doing this in your function:

    > ++A[i];

    You change the value of the element in the array. So when comparing, you compare with a changed value, not with the original value in that element. I think that is not how it should be. Better would be to pass a second array to the function and store the frequencies in that array.

    > A binary tree would be waaaaay better for this problem

    Why? In my opinion it would be too much effort.

  4. #4
    Open to suggestions Brighteyes's Avatar
    Join Date
    Mar 2003
    Posts
    204
    Why? In my opinion it would be too much effort.
    The code isn't but a few lines longer, is easier to follow, and the algorithm is considerably more efficient even in the worst case. Seems like a good enough reason to me.

  5. #5
    Registered User
    Join Date
    Jan 2003
    Posts
    115
    is there any other algorithms for number frequency?
    i thought about sorting the list first then find the frequency of a value, have two arrays, one store the values and the other store its frequency.

    what if the list was unsorted?
    i think i will run in to the problem of matching values for frequency and probably ending up outputting the wrong data.

    the binary tree looks like a good idea but i have not covered that material yet.

    if say you have 1000 numbers would a simple bubblesort do its job without too much fuss? im not familiar with qsort but i think bubblesort would do a standard job.
    there are only 10 people in the world, those who know binary and those who dont

  6. #6
    Open to suggestions Brighteyes's Avatar
    Join Date
    Mar 2003
    Posts
    204
    >is there any other algorithms for number frequency?
    Nothing simple that I know of.

    >i thought about sorting the list first then find the frequency of a value, have two arrays, one store the values and the other store its frequency.
    That sounds like a good plan.

    >what if the list was unsorted?
    Working with sorted data is much easier because you can make assumptions in your algorithm, thus making it simpler. Simpler is good.

    >if say you have 1000 numbers would a simple bubblesort do its job without too much fuss?
    Bubblesort is okay for small arrays, really anything less than 5000 would give acceptable performance
    Code:
    #include <stdio.h>
    
    #define LIMIT 1000
    
    static void sort(int list[], int size);
    
    int main(void)
    {
        int i;
        int j;
        int max;
        int list[LIMIT];
        int freq[LIMIT] = {0};
    
        printf("Enter some numbers (Ctrl+D to quit): ");
        fflush(stdout);
    
        max = 0;
    
        while (scanf("%d", &list[max]) == 1)
            max++;
    
        /* Sort the list */
        sort(list, max);
    
        /* Find the frequencies */
        for (i = 0, j = 0; i < max; )
        {
            int num;
    
            num = list[i];
    
            while (num == list[i] && i < max)
            {
                freq[j]++;
    
                i++;
            }
    
            j = i;
        }
    
        for (i = 0; i < max; i++)
        {
            if (freq[i] != 0)
                printf("%d -- %d\n", list[i], freq[i]);
        }
    
        return 0;
    }
    
    static void sort(int list[], int size)
    {
        int i;
        int j;
        int temp;
    
        for (i = size - 1; i > 0; i--)
        {
            for (j = 0; j < i; j++)
            {
                if (list[j] > list[j + 1])
                {
                    temp = list[j];
                    list[j] = list[j + 1];
                    list[j + 1] = temp;
                }
            }
        }
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 16
    Last Post: 05-29-2009, 07:25 PM
  2. from 2D array to 1D array
    By cfdprogrammer in forum C Programming
    Replies: 17
    Last Post: 03-24-2009, 10:33 AM
  3. Class Template Trouble
    By pliang in forum C++ Programming
    Replies: 4
    Last Post: 04-21-2005, 04:15 AM
  4. Unknown Memory Leak in Init() Function
    By CodeHacker in forum Windows Programming
    Replies: 3
    Last Post: 07-09-2004, 09:54 AM
  5. Quick question about SIGSEGV
    By Cikotic in forum C Programming
    Replies: 30
    Last Post: 07-01-2004, 07:48 PM