0

So im running into a strange problem. This is on the "Find:More" PSET3 problem. When I run the program such as:

./generate 1000 50 | ./find 127

or

./generate 1000 50 | ./find 128

the program returns the correct "Did or didn't find the needle in the haystack", although it does print off a ton of numbers like so:

haystack[435] = 
haystack[436] = 
haystack[437] = 
haystack[438] = 
haystack[439] = 
haystack[440] = 
haystack[441] = 
haystack[442] = 
haystack[443] = 

However if I try to do it manually ie:

./find 42
3
33
44
42
2

I receive a seg fault. Whats even weirder is when running the "cs50 check test" I receive:

~/workspace/pset3/find/ $ check50 2016.find.less helpers.c
:) helpers.c exists
:( helpers.c compiles
   \ expected an exit code of 0, not standard error of "helpers.c:18:8: error: implicit declara..."

yet my program compiles just fine with make? Any ideas?

helpers.c

/**
 * helpers.c
 *
 * Helper functions for Problem Set 3.
 */
 
#include <cs50.h>
#include "helpers.h"


/**
 * Returns true if value is in array of n values, else false.
 */
bool search(int value, int values[], int n)
{
    int min = 0;
    int max = n-1;
    if(binary(value,values,min,max) == true)
    {
        return true;
    }
    else
    {
    return false;
    }
}

bool binary(int value, int values[], int min, int max)
{
    int current_index = ((min+max)/2);
    if(min > max)
    {
        return false;
    }
    else if(values[current_index] == value)
    {
        return true;
    }
    else if(values[current_index] < value)
    {
        min = current_index + 1;
        return binary(value,values,min,max);
    }
    else if(values[current_index] > value)
    {
        max = current_index - 1;
        return binary(value,values,min,max);
    }
    else
    {
        return false;
    }
   
}

/**
 * Sorts array of n values.
 */
void sort(int values[], int n)
{
    int temp;
    int max_value = 0;
    int s = 0;
    //Find Max Value
    for(int j = 0;j < n;j++)
    {   
        if(values[j] > max_value){
            max_value = values[j];
        }
    }
    //Fill Arrays with proper counts
    int array_holder[max_value];
    for(int c = 0;c < max_value;c++)
    {
        array_holder[c]=0;
    }
    for(int i = 0;i < n;i++)
    {   
        temp = values[i];
        array_holder[temp] = array_holder[temp]+1;
    }
    for(int k = 0; k <= max_value; k++)
    {
        if(array_holder[k] == 0)
        {
            k++;
        }
        while(array_holder[k] > 0)
        {
            values[s] = k;
            array_holder[k] = array_holder[k] - 1;
            s++;
        }
    }
    
    return;
}

helpers.h

/**
 * helpers.h
 *
 * Helper functions for Problem Set 3.
 */
 
#include <cs50.h>
#include <stdio.h>
/**
 * Returns true if value is in array of n values, else false.
 */
bool search(int value, int values[], int n);

/**
 * Sorts array of n values.
 */
void sort(int values[], int n);


//Recursive function
bool binary(int value, int values[], int min, int max);

Code posted here:

helpers.c: http://pastebin.com/gmhXnryz

helpers.h: http://pastebin.com/KTWd8iQ4

2

You have problems with the array that sets your counting array to 0:

int array_holder[max_value];
for(int c = 0;c < max_value;c++)
{
    array_holder[c]=0;
}

Think about implementing a counting sort, you will need to provide enough buckets to store all the numbers from 0 up to a maximum value. A small modification to your code will fix this fault.

Also, concerning the following loop:

for(int k = 0; k <= max_value; k++)
{
    if(array_holder[k] == 0)
    {
        k++;
    }
    while(array_holder[k] > 0)
    {
        values[s] = k;
        array_holder[k] = array_holder[k] - 1;
        s++;
    }
}

Be aware that you may be advancing k by 2 on some passes of this loop. In this case, it will probably still work as expected because the while loop will also catch zero values, but it is not good practice!

Regarding check50, I think that it is not seeing the prototype of your binary function in helpers.h. I found that adding an extra function with the prototype in helpers.h did not work with check50, and required a prototype to be added to helpers.c.

| improve this answer | |
  • Ah I guess in the first I need to be setting it to max_value+1 I would assume. Since Max_value may be....400. it will go to array_holder[399] which won't store 400 but 399 (since array_holder[0] needs to hold 0). Correct? Any suggestions on the second part? I couldn't figure out a good way. – msmith1114 Feb 2 '17 at 14:54
  • I just realized the problem...int array_holder[max_value] needs to be max_value+1, since I need to hold 45 values if 44 is the max value. – msmith1114 Feb 2 '17 at 15:50
  • That's correct, and once you change that, you need to make sure you iterate over all values in the array. – Steve Bunting Feb 2 '17 at 17:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .