qsort() 라이브러리 함수에서 compareX 작업을 설명하십시오.

Question

가장 가까운 쌍 코드를 찾고 있었는데 qsort() 라이브러리 함수를 사용하고있는 것을 발견했습니다. 나는 기본적으로 그것이 매개 변수 작업을 비교하는 방법에 대한 개념을 이해하지 못했습니다. 이 특정 코드와 관련된 설명을 더 잘 이해할 수 있습니다. 감사.

#include <iostream> 
#include <float.h> 
#include <stdlib.h> 
#include <math.h> 
using namespace std; 

// A structure to represent a Point in 2D plane 
struct Point 
{ 
int x, y; 
}; 


/* Following two functions are needed for library function qsort(). 
Refer: http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/ */ 

// Needed to sort array of points according to X coordinate 
int compareX(const void* a, const void* b) 
{ 
Point *p1 = (Point *)a, *p2 = (Point *)b; 
return (p1->x - p2->x); 
} 
// Needed to sort array of points according to Y coordinate 
int compareY(const void* a, const void* b) 
{ 
Point *p1 = (Point *)a, *p2 = (Point *)b; 
return (p1->y - p2->y); 
} 

// A utility function to find the distance between two points 
float dist(Point p1, Point p2) 
{ 
return sqrt((p1.x - p2.x)*(p1.x - p2.x) + 
      (p1.y - p2.y)*(p1.y - p2.y) 
      ); 
} 

// A Brute Force method to return the smallest distance between two points 
// in P[] of size n 
float bruteForce(Point P[], int n) 
{ 
float min = FLT_MAX; 
for (int i = 0; i < n; ++i) 
    for (int j = i+1; j < n; ++j) 
     if (dist(P[i], P[j]) < min) 
      min = dist(P[i], P[j]); 
return min; 
} 

// A utility function to find minimum of two float values 
float min(float x, float y) 
{ 
return (x < y)? x : y; 
} 


// A utility function to find the distance beween the closest points of 
// strip of given size. All points in strip[] are sorted accordint to 
// y coordinate. They all have an upper bound on minimum distance as d. 
// Note that this method seems to be a O(n^2) method, but it's a O(n) 
// method as the inner loop runs at most 6 times 
float stripClosest(Point strip[], int size, float d) 
{ 
float min = d; // Initialize the minimum distance as d 

// Pick all points one by one and try the next points till the difference 
// between y coordinates is smaller than d. 
// This is a proven fact that this loop runs at most 6 times 
for (int i = 0; i < size; ++i) 
    for (int j = i+1; j < size && (strip[j].y - strip[i].y) < min; ++j) 
     if (dist(strip[i],strip[j]) < min) 
      min = dist(strip[i], strip[j]); 

return min; 
} 

// A recursive function to find the smallest distance. The array Px contains 
// all points sorted according to x coordinates and Py contains all points 
// sorted according to y coordinates 
float closestUtil(Point Px[], Point Py[], int n) 
{ 
// If there are 2 or 3 points, then use brute force 
if (n <= 3) 
    return bruteForce(Px, n); 

// Find the middle point 
int mid = n/2; 
Point midPoint = Px[mid]; 


// Divide points in y sorted array around the vertical line. 
// Assumption: All x coordinates are distinct. 
Point Pyl[mid+1]; // y sorted points on left of vertical line 
Point Pyr[n-mid-1]; // y sorted points on right of vertical line 
int li = 0, ri = 0; // indexes of left and right subarrays 
for (int i = 0; i < n; i++) 
{ 
    if (Py[i].x <= midPoint.x) 
    Pyl[li++] = Py[i]; 
    else 
    Pyr[ri++] = Py[i]; 
} 

// Consider the vertical line passing through the middle point 
// calculate the smallest distance dl on left of middle point and 
// dr on right side 
float dl = closestUtil(Px, Pyl, mid); 
float dr = closestUtil(Px + mid, Pyr, n-mid); 

// Find the smaller of two distances 
float d = min(dl, dr); 

// Build an array strip[] that contains points close (closer than d) 
// to the line passing through the middle point 
Point strip[n]; 
int j = 0; 
for (int i = 0; i < n; i++) 
    if (abs(Py[i].x - midPoint.x) < d) 
     strip[j] = Py[i], j++; 

// Find the closest points in strip. Return the minimum of d and closest 
// distance is strip[] 
return min(d, stripClosest(strip, j, d)); 
} 

// The main functin that finds the smallest distance 
// This method mainly uses closestUtil() 
float closest(Point P[], int n) 
{ 
Point Px[n]; 
Point Py[n]; 
for (int i = 0; i < n; i++) 
{ 
    Px[i] = P[i]; 
    Py[i] = P[i]; 
} 

qsort(Px, n, sizeof(Point), compareX); 
qsort(Py, n, sizeof(Point), compareY); 

// Use recursive function closestUtil() to find the smallest distance 
return closestUtil(Px, Py, n); 
} 

// Driver program to test above functions 
int main() 
{ 
Point P[] = {{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}}; 
int n = sizeof(P)/sizeof(P[0]); 
cout << "The smallest distance is " << closest(P, n); 
return 0; 
} 

Answer 1

qsort의 마지막 매개 변수는 특정 서명 함수에 대한 포인터는 다음 두 항목이있는 경우는 두 void* 포인터를 가지고 가고, 작은 두 통과 항목 중 어느 나타내는 int을 반환하거나해야한다 똑같다. 세부 사항은 here이지만 일반적으로 긍정적 인 결과는 두 번째 항목이 더 작음을 나타내며 음수는 첫 번째 항목이 더 작음을 나타내며 0은 일치도를 나타냅니다.

compareX

int compareX(const void* a, const void* b) 
{ 
    Point *p1 = (Point *)a, *p2 = (Point *)b; 
    return (p1->x - p2->x); 
} 

의 구현은 비교 함수에 대한 일반적인 패턴을 따른다. 먼저 Point 구조의 배열과 함께 사용된다는 것을 "알고"있기 때문에 void* 포인터를 Point 형식으로 변환합니다. 두 번째 점의 x가 클 때 두 번째 점의 x가 음수 작은 경우, 감산의 결과가 긍정적 인 것 것을

p1->x - p2->x 

주 및 0 : 그런 다음 x 두 지점의 좌표를 감산 두 개의 x은 같습니다. 이것은 정확히 qsort이 cmp 함수가 수행하기를 원하므로 감산 연산이 비교 함수의 계약을 수행합니다.