黑白点匹配问题代码

#include <stdio.h> #include <stdlib.h> #include "myfunction.h" //小根堆的结构 //堆是从0——(n-1) //i--2i+1,2i+2 //i--(i-1)/2 //小根堆 //下移数字 //i--2i+1,2i+2 void Sift_Down_MinHeap(point *a, int i, int n) { if ((2 * i + 1) >= n) return; //叶子节点直接返回 int tmp = 0; while (2 * i + 1 < n) { tmp = i; //父节点 i = 2 * i + 1; //i指向的是孩子节点 if (i + 1 < n && (a[i + 1].x < a[i].x || (a[i + 1].x == a[i].x && a[i + 1].y < a[i].y))) //存在右孩子 i++; if (a[tmp].x > a[i].x || (a[tmp].x == a[i].x&&a[tmp].y > a[i].y)) { switch_point(&a[tmp], &a[i]); } else { break; } } } //上移数字 //i--(i-1)/2 void Sift_Up_MinHeap(point *a, int i, int n) { if ((i - 1) / 2 < 0) return; int tmp = 0; while ((i - 1) / 2 >= 0) { tmp = (i - 1) / 2; //指向当前节点的父节点 if (a[tmp].x > a[i].x || (a[tmp].x == a[i].x&&a[tmp].y > a[i].y)) { switch_point(&a[tmp], &a[i]); } else { break; } i = tmp; } } //n个节点，最后一个非叶子节点是(n-1)/2 void Create_MinHeap(point *a, int n) { int i = 0; for (i = (n - 1) / 2; i >= 0; i--) { Sift_Down_MinHeap(a, i, n); } } //delete void DeleteMax_MinHeap(point *a, int *n) { //point tmp = a[0]; DeleteMinHeap(a, 0, n); } void DeleteMinHeap(point *a, int i, int *n) { int num = *n; point tmp = a[i]; point y = a[num-1]; num--; if (i == num + 1) { *n = num; return; } a[i] = y; if (a[i].x < tmp.x || (a[i].x == tmp.x&&a[i].x < tmp.y)) Sift_Up_MinHeap(a, i, num); else Sift_Down_MinHeap(a, i, num); *n = num; } //堆排序，降序输出 void MinHeap_Sort(point *a, int n) { Create_MinHeap(a, n); int i = 0; for (i = n - 1; i >= 1; i++) { switch_point(&a[0], &a[i]); Sift_Down_MinHeap(a, 0, i); } } int select(point *a, int m, int b, int c) { int tmp = -1; if (m != -1) //m = 1 { tmp = m; if (b != -1) //m = 1 b = 1 { tmp = (a[m].y >a[b].y)? m: b; if (c != -1) { tmp = (a[tmp].y > a[c].y)? tmp: c; } } else { if (c != -1) { tmp = (a[tmp].y > a[c].y) ? tmp : c; } } } else { if (b != -1) //m = -1 b = 1 { tmp = b; if (c != -1) { tmp = (a[tmp].y > a[c].y) ? tmp : c; } } else //m = -1 b = -1 { tmp = c; } } return tmp; } //堆查找 int Find_MinHeap(point *a, point src, int i, int n) { if (i >= n) { return -1; } int p0 =-1, p1 = -1, p2 = -1; if (a[i].x <= src.x) //X匹配成功 { if (a[i].y <= src.y) //Y匹配成功 { p0 = i; } p1 = Find_MinHeap(a, src, 2 * i + 1, n); p2 = Find_MinHeap(a, src, 2 * i + 2, n); p0 = select(a, p0, p1, p2); return p0; } else { return -1; } }