通过CS50, Pset3和迫切需要帮助/耐心。我正试图实现helpers.c，以便find.c有正确的函数调用…然而，它没有连接…
我做了一个单独的作品，我命名为testBinSearch，这确实工作。用同样的代码…谁能告诉我为什么?
/**
* helpers.c
*
* Computer Science 50
* Problem Set 3
*
* Helper functions for Problem Set 3.
*/
#include <stdio.h>
#include <cs50.h>
#include "helpers.h"
/**
* Returns true if value is in array of n values, else false.
*/
//search(needle, haystack, size)
bool search(int value, int values[], int n)
{
// TODO: implement a Binary searching algorithm (You are welcome to take an iterative approach (as with a loop) or a recursive approach (wherein a function calls itself).)
//define startPoint. numberOfArrayElements(aka size) - (numberOfArrayElements(aka size) - 1) or Element[0]
//define endPoint. numberOfArrayElements(aka size)
int endPoint = n - 1; //element! we -1 because array start from 0th element. last element of array that is 5 elements big will thus be (total number of Elements - 1)th element.
//define midPoint. numberOfArrayElements(aka size)/2
int midPoint = endPoint/2; //element!
//while loop?
while(n > 0)
{
//if midPoint == needle, return 0
if(values[midPoint] == value)
{
return 0;
}
//////////(if midPoint is smaller(to the left) or larger(to the right) than needle)
//ELSE IF midPoint > than needle(look left), keep startPoint, change endPoint element to values[midPoint - 1], define midPoint again.
else if(values[midPoint] > value)
{
endPoint = midPoint - 1;
midPoint = endPoint/2;
n = endPoint;
printf("mid point is more than needlen");
}
//ELSE midPoint < than needle(look right), keep endPoint, change Startpoint element to values[midPoint + 1], define mindPoint again.
else if(values[midPoint] < value)
{
int startPoint = midPoint + 1;
//define midpoint again
midPoint = (endPoint + startPoint)/2;
n = endPoint - startPoint + 1;
printf("mid point is less than needlen");
}
}
printf("cued the while loop return 1n");
return 1;
}
/**
* Sorts array of n values. Done with Insertion sort*
*/
void sort(int values[], int n)
{
//declare variable
int element;
//number of iterations (or passes?). Skip first because first array is already sorted
for (int i = 1; i < n; i++)
{
//value of element moving into sorted portion
element = values[i];
//declare variable
int j = 0;
//index into the unsorted portion
j = i;
//iterate sorted portion from right to left while sorted portion is greater than 'Element' being compared in this iteration of i.
//basically, it stops this loop once the 'Element' is placed to the left of all greater&&sorted numbers.
while(j > 0 && values[j - 1] > element)
{
//shift all sorted positions to the right
values[j] = values[j - 1];
// this enables the loop to move left through the sorted portion
j = j - 1;
}
//insert temp holder value into the position which is now empty because all sorted&&greater number are to the right of 'Element'
values[j] = element;
}
for(int k = 0; k < n; k++)
//print to check
{
printf("{%i}<-- number in %i-th array (sorted)n", values[k], k);
}
}
以下是find.c代码:
/**
* find.c
*
* Computer Science 50
* Problem Set 3
*
* Prompts user for as many as MAX values until EOF is reached,
* then proceeds to search that "haystack" of values for given needle.
*
* Usage: ./find needle
*
* where needle is the value to find in a haystack of values
*/
#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>
#include "helpers.h"
// maximum amount of hay
const int MAX = 65536;
int main(int argc, string argv[])
{
// ensure proper usage
if (argc != 2)
{
printf("Usage: ./find needlen");
return -1;
}
// remember needle
int needle = atoi(argv[1]);
// fill haystack
int size;
int haystack[MAX];
for (size = 0; size < MAX; size++)
{
// wait for hay until EOF
printf("nhaystack[%i] = ", size);
int straw = GetInt();
if (straw == INT_MAX)
{
break;
}
// add hay to stack
haystack[size] = straw;
}
printf("n");
// sort the haystack
sort(haystack, size);
// try to find needle in haystack
if (search(needle, haystack, size))
{
printf("nFound needle in haystack!nn");
return 0;
}
else
{
printf("nDidn't find needle in haystack.nn");
return 1;
}
}
最后，当我把它们都放在一个文件中时，这里的代码分别工作(或者至少看起来是工作的)…
标题<testBinSearch>#include <stdio.h>
#include <cs50.h>
void sort(int array[], int NumberOfElements);
bool search(int value, int values[], int n);
int main(void)
{
//decalre variable
int NumberOfElements;
printf("how many Element would you like in this array?n");
NumberOfElements = GetInt();
//declare variable for array
int array[NumberOfElements];
for(int i = 0; i < NumberOfElements; i++)
{
printf("alright, please key in value of each elementn");
array[i] = GetInt();
}
sort(array, NumberOfElements);
for (int i = 0; i < NumberOfElements; i++)
{
printf("alright, here is your array sorted, element %i is %in", i, array[i]);
}
printf("value ot search for?n");
int value = GetInt();
search(value, array, NumberOfElements);
}
//----------
void sort(int array[], int NumberOfElements)
{
//declare variable
int element;
//number of iterations (or passes?). Skip first because first array is already sorted
for (int i = 1; i < NumberOfElements; i++)
{
//value of element moving into sorted portion
element = array[i];
//declare variable
int j = 0;
//index into the unsorted portion
j = i;
//iterate sorted portion from right to left while sorted portion is greater than 'Element' being compared in this iteration of i.
//basically, it stops this loop once the 'Element' is placed to the left of all greater&&sorted numbers.
while(j > 0 && array[j - 1] > element)
{
//shift all sorted positions to the right
array[j] = array [j - 1];
// this enables the loop to move left through the sorted portion
j = j - 1;
}
//insert temp holder value into the position which is now empty because all sorted&&greater number are to the right of 'Element'
array[j] = element;
}
}
//--------------
bool search(int value, int values[], int n)
{
// TODO: implement a Binary searching algorithm (You are welcome to take an iterative approach (as with a loop) or a recursive approach (wherein a function calls itself).)
//variables declaration
//int startPoint;
//int endPoint;
//int midPoint;
//define startPoint. numberOfArrayElements(aka size) - (numberOfArrayElements(aka size) - 1) or Element[0]
//define endPoint. numberOfArrayElements(aka size)
int endPoint = n - 1; //element!
//define midPoint. numberOfArrayElements(aka size)/2
int midPoint = endPoint/2; //element!
//while loop?
while(n > 0)
{
//if midPoint == needle, return 0
if(values[midPoint] == value)
{
printf("found it!n");
return 0;
}
//////////(if midPoint is smaller(to the left) or larger(to the right) than needle)
//ELSE IF midPoint > than needle(look left), keep startPoint, change endPoint element to values[midPoint - 1], define midPoint again.
else if(values[midPoint] > value)
{
endPoint = midPoint - 1;
midPoint = endPoint/2;
n = endPoint;
}
//ELSE midPoint < than needle(look right), keep endPoint, change Startpoint element to values[midPoint + 1], define mindPoint again.
else if(values[midPoint] < value)
{
int startPoint = midPoint + 1;
//define midpoint again
midPoint = (endPoint + startPoint)/2;
n = endPoint - startPoint + 1;
}
}
printf("could not find itn");
return 1;
}
testBinSearch)，一个没有(helpers.c)。div ? 我不确定这是否涵盖了整个问题，但无论如何…
这个计算
midPoint = endPoint/2;
是错误的。
假设您有一个包含100个元素的数组。代码可能会让您看到索引75到99之间的中点(例如87)，即您已经采取了smaller than路径几次。
现在，如果你取greater than部分，你计算一个中点(例如43)在感兴趣的范围之外
此外，在smaller than情况下，startpoint变量不能是一个变量。它必须与端点处于同一级别。在每个循环中，您必须更改起点或端点。中点的计算必须同时依赖于起点和终点