我在作业中结合这两个规定的逻辑上遇到了问题。如何更改下面的二进制搜索函数以获取compareTo坐标结构。我第一次写错了，因为我使用了原始的字符串位置。我也不明白compareTo函数是如何跟踪距离目标的长度的。这让我很困惑，因为下面compareTo函数的读取方式与我相反，并要求我比较各个x和y坐标。如果我只是使用指针，我该怎么做？我只是在二进制搜索中传递坐标*ptrPt1吗？数字3是最令人困惑的单词。
函数关系的上下文：
- 您必须编写一个函数
compareTo，该函数接受两个指针ptrPt1和ptrPt2如果ptrPt1指向的点离您更近，则坐标结构化并返回负整数如果ptrPt2所指向的两个位置都是相同的位置，如果ptrPt1指向的点比指向的点离您更远，则为正整数通过ptrPt2。例外情况是当两个指针指向相同的点时距离你很远，但都是不同的点。在这些情况下，如果ptrPt1的x坐标低于ptrPt2的x坐标，必须返回一个负整数。或者，如果ptrPt1的x坐标为大于ptrPt2的x坐标时，必须返回一个正整数。最后，如果x坐标如果ptrPt1的y坐标低于ptrPt2的y坐标，则两个点的必须返回整数。如果ptrPt1的y坐标大于ptrPt2的y坐标，则正必须返回整数 - 由于您的位置必须用于排序，请创建存储您的x和y的变量坐标全局。您的程序不应该有其他全局变量
- 回答查询时必须使用二进制搜索功能
int binarysearch(int searchval, int* array, int length) {
int low = 0, high = length-1;
// Search while there is a valid search space.
while (low <= high) {
int mid = (low+high)/2;
// Value is too small.
if (searchval < array[mid])
high = mid-1;
// too big.
else if (searchval > array[mid])
low = mid+1;
// found it!
else
return 1;
}
// Never found it.
return 0;
}
int
compareTo(coordinates *ptrPt1, coordinates *ptrPt2) {
if (ptrPt1 > ptrPt2)
return -1;
if(ptrPt1 == ptrPt2)
return 0;
if(ptrPt1 < ptrPt2)
return 1;
}
您的compareTo需要重构。
比较结构的地址[与其中的X/Y坐标]是不正确的。
对于compareTo，它必须首先为作为自变量传递的两个点中的每一个计算与任意参考点(例如)self的距离。根据问题定义，self可以[并且应该]是[唯一]全局。
它为两个[自变量]点中的每一个获取到self的距离。它选择这两个点中比较接近的一个(如果它们不同的话)。
如果这两个点与self点的距离相同，则它首先选择X坐标值较低的点。如果两个点的X坐标相同，则会选择两个Y值中较低的一个。
因此，这是一个三步走的过程。
您的binarysearch需要重构。一旦不匹配/失败，它将返回0。但是，零是匹配的有效索引/值。因此，它需要在失败时返回-1。
问题定义存在一些问题。
问题(1)：
(我)不清楚"；等级；唯一有意义的是；等级；是按compareTo排序的列表的索引。
问题(2)：
目前尚不清楚"；距离"；方法它可以是(例如)：
sqrt((p1->x - p2->x)**2 + (p1->y - p2->y)**2)
但是，这使用了浮点，对于这个问题来说可能有些过头了。
另一个"；距离"；是曼哈顿距离，它只是两个坐标的X和Y值的绝对差的总和：
abs(p1->x - p2->x) + abs(p1->y - p2->y)
问题(3)：
我认为需要两个排序列表。
一个按compareTo排序。另一个仅按X/Y坐标排序。
这是因为在匹配搜索坐标时需要使用二进制搜索。因为搜索坐标不知道秩，所以不能使用compareTo列表，必须用X/Y列表。
有两种可能的方法。
这可以通过使用作为个人列表的指针或索引的两个列表来实现。binarysearch应该被修改为接受一个索引/指针数组。
或，可以通过compareTo对人员列表进行排序，在坐标结构中记录排名，然后按X/Y坐标对列表进行调用来实现。应修改binarysearch以接受坐标数组。
我选择使用后一种方法。
而且，如果需要的话，我添加了一些测试代码来生成一个随机化的输入文件。
我刚刚实现了一个简单的插入排序[算法是从维基百科条目中截取插入排序]。因此，您仍然需要对合并/插入排序逻辑进行组合编码。
剧透警报：以下是完整/重构的代码：
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <math.h>
#include <time.h>
typedef struct {
int x;
int y;
int rank;
} coord_t;
// maximum coordinate
#ifndef COORDMAX
#define COORDMAX 10000
#endif
// max # of [infected] people
#ifndef PERSONMAX
#define PERSONMAX 106
#endif
#define SEARCHMAX (2 * (PERSONMAX - 1)) // max # of search coordinates
#define THRESHMAX 30 // maximum threshold
coord_t self; // coordinates of tracer
typedef int (*cmpfnc_p)(const coord_t *,const coord_t *);
int opt_d; // 1=debug
int opt_f; // distance mode (0=manhattan, 1=sqrt)
unsigned int opt_R; // random fill
void gentest(FILE *fi);
// disti -- get distance from given coordinate to self (manhattan distance)
int
disti(const coord_t *pt)
{
int dif;
int tot = 0;
dif = pt->x - self.x;
if (dif < 0)
dif = -dif;
tot += dif;
dif = pt->y - self.y;
if (dif < 0)
dif = -dif;
tot += dif;
return tot;
}
// distf -- get distance from given coordinate to self (floating pt distance)
int
distf(const coord_t *pt)
{
double dif;
double tot = 0;
int rtn;
dif = pt->x - self.x;
dif *= dif;
tot += dif;
dif = pt->y - self.y;
dif *= dif;
tot += dif;
tot = sqrt(tot);
// scale result
// FIXME -- this is untested and may not be necessary
tot *= INT_MAX;
tot /= COORDMAX;
rtn = round(tot);
return rtn;
}
// dist -- get distance from given coordinate to self
int
dist(const coord_t *pt)
{
int tot;
if (opt_f)
tot = distf(pt);
else
tot = disti(pt);
return tot;
}
// compareAbs -- compare two coordinates for lowest X/Y values
int
compareAbs(const coord_t *p1,const coord_t *p2)
{
int cmp;
do {
// use lower X coordinate
cmp = p1->x - p2->x;
if (cmp)
break;
// use lower Y coordinate
cmp = p1->y - p2->y;
if (cmp)
break;
} while (0);
return cmp;
}
// compareTo -- compare two coordinates for distance from self and then position
int
compareTo(const coord_t *p1,const coord_t *p2)
{
int cmp;
do {
// compare distance to self
cmp = dist(p1) - dist(p2);
if (cmp)
break;
// compare against absolute coordinates
cmp = compareAbs(p1,p2);
} while (0);
return cmp;
}
// sortswap -- swap array elements
void
sortswap(coord_t *p1,coord_t *p2)
{
coord_t tmp;
tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
// sortinsert -- insertion sort
void
sortinsert(coord_t *list,int count,cmpfnc_p cmp)
{
for (int i = 1; i < count; ++i) {
for (int j = i; j > 0; --j) {
if (cmp(&list[j - 1],&list[j]) <= 0)
break;
sortswap(&list[j - 1],&list[j]);
}
}
}
// sortany -- outer sort routine
void
sortany(coord_t *list,int count,int threshold,cmpfnc_p cmp)
{
// TODO: do mergesort
if (count < threshold) {
}
// finish with insertion sort
sortinsert(list,count,cmp);
}
// binarysearch -- perform binary search on coordinate list
int
binarysearch(const coord_t *search,const coord_t *array,int length,
cmpfnc_p cmpfnc)
{
int low = 0;
int high = length - 1;
int match = -1;
// Search while there is a valid search space.
while (low <= high) {
int mid = (low + high) / 2;
int cmp = cmpfnc(search,&array[mid]);
// found it
if (cmp == 0) {
match = mid;
break;
}
// Value is too small.
if (cmp < 0)
high = mid - 1;
// too big.
else
low = mid + 1;
}
return match;
}
// main -- main program
int
main(int argc,char **argv)
{
const char *file = NULL;
char *cp;
FILE *fi;
int person_count;
int search_count;
int threshold;
coord_t *pt;
coord_t *person_list;
coord_t *search_list;
--argc;
++argv;
for (; argc > 0; --argc, ++argv) {
cp = *argv;
if (*cp != '-')
break;
switch (cp[1]) {
case 'd':
opt_d = ! opt_d;
break;
case 'f':
opt_f = ! opt_f;
break;
case 'R':
cp += 2;
opt_R = (*cp != 0) ? atoi(cp) : time(NULL);
printf("R=%un",opt_R);
srand(opt_R);
break;
}
}
// get/open input file
do {
fi = stdin;
if (argc <= 0) {
if (opt_R)
fi = stdout;
else
fi = stdin;
break;
}
file = *argv;
fi = fopen(file,opt_R ? "w" : "r");
if (fi == NULL) {
perror(file);
exit(1);
}
} while (0);
// generate test data
if (opt_R) {
gentest(fi);
fclose(fi);
exit(0);
}
fscanf(fi,"%d %d %d %d %d",
&self.x,&self.y,&person_count,&search_count,&threshold);
person_list = calloc(person_count,sizeof(*person_list));
if (person_list == NULL) {
perror("person_list");
exit(1);
}
search_list = calloc(search_count,sizeof(*search_list));
if (search_list == NULL) {
perror("search_list");
exit(1);
}
// read in coordinates of all people
for (int idx = 0; idx < person_count; ++idx) {
pt = &person_list[idx];
fscanf(fi,"%d %d",&pt->x,&pt->y);
}
// read in all search coordinates
for (int idx = 0; idx < search_count; ++idx) {
pt = &search_list[idx];
fscanf(fi,"%d %d",&pt->x,&pt->y);
}
// get the ranking
sortany(person_list,person_count,threshold,compareTo);
// remember the ranking and print the ranked list
for (int idx = 0; idx < person_count; ++idx) {
pt = &person_list[idx];
pt->rank = idx;
if (opt_d)
printf("%d %d dist=%d rank=%dn",pt->x,pt->y,dist(pt),idx);
else
printf("%d %dn",pt->x,pt->y);
}
// reorder list for search points
sortany(person_list,person_count,threshold,compareAbs);
// perform all queries
for (int idx = 0; idx < search_count; ++idx) {
pt = &search_list[idx];
int match = binarysearch(pt,person_list,person_count,compareAbs);
if (match < 0) {
printf("%d %d not foundn",pt->x,pt->y);
continue;
}
pt = &person_list[match];
printf("%d %d found at rank %dn",pt->x,pt->y,pt->rank);
}
if (file != NULL)
fclose(fi);
free(person_list);
free(search_list);
return 0;
}
// gencoord -- generate a random coordinate
void
gencoord(coord_t *pt)
{
int val;
int neg;
for (int mode = 0; mode <= 1; ++mode) {
val = rand();
neg = (val & 1);
val >>= 1;
val %= (COORDMAX + 1);
if (neg)
val = -val;
if (mode == 0)
pt->x = val;
else
pt->y = val;
}
}
// genrand -- genrate a random number in the inclusive range
int
genrand(int lo,int hi)
{
int val;
val = rand();
val %= (hi + 1);
if (val < lo)
val = lo;
return val;
}
// gensame -- decide if coordinate already in use
int
gensame(coord_t *pt,coord_t *list,int length)
{
int match;
do {
// coordinate may _not_ be the starting/self point
match = (compareAbs(pt,&self) == 0);
if (match)
break;
// coordinate may not match any previous point in the list
for (int idx = 0; idx < length; ++idx) {
match = (compareAbs(pt,&list[idx]) == 0);
if (match)
break;
}
} while (0);
return match;
}
// gentest -- generate a random test file
void
gentest(FILE *fi)
{
int val;
int threshold;
int person_count;
int search_count;
int same;
coord_t *person_list;
coord_t *pt;
coord_t tmp;
gencoord(&self);
person_count = genrand(2,PERSONMAX);
search_count = genrand(1,SEARCHMAX);
threshold = genrand(1,THRESHMAX);
fprintf(fi,"%d %d %d %d %dn",
self.x,self.y,person_count,search_count,threshold);
person_list = calloc(person_count,sizeof(*person_list));
if (person_list == NULL) {
perror("person_list");
exit(1);
}
// generate coordinates of all people
fprintf(fi,"n");
for (int idx = 0; idx < person_count; ++idx) {
pt = &person_list[idx];
pt->rank = 0;
// ensure [proposed] coordinate is unique
same = 1;
while (same) {
gencoord(pt);
same = gensame(pt,person_list,idx);
}
fprintf(fi,"%d %dn",pt->x,pt->y);
}
// generate search coordinates
fprintf(fi,"n");
for (int idx = 0; idx < search_count; ++idx) {
pt = &tmp;
val = rand();
val %= 100;
// generate a random point that is _not_ a person or self (10% of the
// time)
if (val < 10) {
same = 1;
while (same) {
gencoord(pt);
same = gensame(pt,person_list,person_count);
}
}
// randomly select an infected person
else {
val = genrand(0,person_count - 1);
pt = &person_list[val];
}
fprintf(fi,"%d %dn",pt->x,pt->y);
}
free(person_list);
}