c - 查找非支配点的代码无法正常工作
问题描述
我是编程初学者（这不是我的学科主题），这是我在这里的第一个问题，如果我没有正确发布它，我深表歉意。
我正在尝试一个问题（在 C 中），其中必须为一个点定义一个结构，将点的输入从一个文件输入到一个动态数组，其中第一行包含点数，其余行包含之间有空格的点的坐标。然后我必须编写一个函数来确定非支配点，给出的定义：
• 如果 y2 > y1 且 x2 > x1，则点 P1 = ( x1 , y1 ) 由点 P2 = ( x2 , y2 ) 支配
• 一个点在一组点中是非支配的，如果在该集合中没有点支配它
另一个函数确定并打印存储在所形成的数组中的每个点的优势级别。我需要打印所有非支配点，然后打印所有点的支配级别。
这是我写的代码：
#include <stdio.h>
#include <stdlib.h>
#define MAX 20
#define TRUE 1
#define FALSE 0
typedef struct Coordinates{
float xcord;
float ycord;
}POINT;
//globally declaring dynamic array of points
POINT *Array_of_Points;
//globally declaring dynamic array of non-dominated points
POINT *Non_dominated;
//declaring some functions
int dominance(int n);
int Read_File(char filename[]);
void Xmerge(int head, int middle, int tail);
void XmergeSort(int head, int tail);
void level_of_dominance(int a);
int main(){
char Arr[MAX];
int n, i, d;
printf("Enter file name...");
scanf("%s", Arr);
n = Read_File(Arr);
if(!Read_File(Arr)){ //if error occurs
printf("Terminating program with exit code -1\n");
return -1; //terminate program with return value -1
}
//finds non-dominated points and prints them
d = dominance(n);
printf("The non dominated points are:\n");
for(i = 0; i < d; i++){
printf("(%f, %f)", Non_dominated[i].xcord, Non_dominated[i].ycord);
}
//print all points with levels of dominance
level_of_dominance(n);
printf("End of program... Terminating with exit code 0\n");
free(Array_of_Points);
free(Non_dominated);
return 0;
}
//function reads file in required manner
int Read_File(char filename[]){
int n; //to store number of points present in file
int count = 0;
float x, y;
FILE *fptr = fopen(filename, "r"); //opening given file in readable format
if(!fptr) //file handling if pointer returns null
{
printf("The file %s can't be opened.\n", filename);
return FALSE;
}
fscanf(fptr, "%d", &n); //reading first line consisting of number of points
Array_of_Points = (POINT*)malloc(n * sizeof(POINT)); //allocating memory for npoints
//reading points from file and storing them in globally created dynamic array
while((count < n) && (fscanf(fptr, "%f", &x) == TRUE && fscanf(fptr, "%f", &y) == TRUE)){
Array_of_Points[count].xcord = x;
Array_of_Points[count].ycord = y;
++count;
}
return n; //returns number of points
}
int dominance(int n){ //returns number of non-dominated points
/*METHOD TO FIND DOMINANCE:
* First, arranging points in array by sorting, say, x co-ordinates in DESCENDING ORDER...
* using merge sort algorithm for the same
* The first point in this sorted array is automatically a non dominated point,
* as no other point has x coordinate greater than it
* Then, traverse sorted array and keep track of largest y value, initializing first one to max
* While traversing, the point with y value grater than y max is also non dominated,
* and contributes to new y max and so on...
**/
int foo = 0; //keeps track of number of non-dominated points found so far, initialized to zero
int i = 0;
XmergeSort(0, n);
int ymax = Array_of_Points[0].ycord;
//add first element of the array to Non_dominated array and increase foo count
Non_dominated = (POINT*)malloc(sizeof(POINT));
Non_dominated[0] = Array_of_Points[0];
++foo;
for(; foo < n; foo++){
if(Array_of_Points[foo].ycord > ymax){
++i;
Non_dominated = (POINT*)realloc(Non_dominated, (i + 1) * sizeof(POINT));
Non_dominated[i] = Array_of_Points[foo];
}
}
//all non dominated points stored in array
return i;
}
void level_of_dominance(int a){ //returns number of points dominating a point
int i, j, flag = 0;
for(i = a - 1; i >= 0; i--){
for(j = i; j >= 0; j--){
if((Array_of_Points[i].xcord <= Array_of_Points[j].xcord)&&(Array_of_Points[i].ycord <= Array_of_Points[j].ycord)){
++flag;
}
}
printf("(%f, %f) is dominated by %d points.\n", Array_of_Points[i].xcord, Array_of_Points[i].ycord, flag);
flag = 0; //resetting number of points for next point
}
}
void XmergeSort(int head, int tail){
int mid;
if(head < tail){
mid = (head +tail)/2;
XmergeSort(head, mid);
XmergeSort(mid + 1, tail);
Xmerge(head, mid, tail);
}
}
//function to merge 2 halves of array
void Xmerge(int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
/* create temp arrays */
POINT *T1, *T2;
T1 = (POINT*)malloc(n1 * sizeof(POINT));
T2 = (POINT*)malloc(n2 * sizeof(POINT));
/* Copy data to temp arrays L[] and R[] */
for (i = 0; i < n1; i++)
T1[i] = Array_of_Points[l + i];
for (j = 0; j < n2; j++)
T2[j] = Array_of_Points[m + 1+ j];
/* Merge the temp arrays back into arr[l..r]*/
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2)
{
Array_of_Points[k] = ((T1[i].xcord <= T2[j].xcord)?T1[i]:T2[j]);
((T1[i].xcord <= T2[j].xcord)?i++:j++);
k++;
}
/* Copy the remaining elements of L[], if there are any */
while (i < n1)
{
Array_of_Points[k] = T1[i];
i++;
k++;
}
/* Copy the remaining elements of R[], if there are any */
while (j < n2)
{
Array_of_Points[k] = T2[j];
j++;
k++;
}
}
在在线 gdb 上运行此代码时，我遇到了分段错误，如下所示：
从 a.out...读取符号完成。
/usr/share/gdb/gdbinit：没有这样的文件或目录。
(gdb) 运行
启动程序：/home/a.out
输入文件名...inp.dat
测试...否。非支配点数 = 4
非支配点是：
节目接收信号 SIGSEGV，分段错误。
0x0000000000400b82 in level_of_dominance (a=5) at main.c:107
107 if((Array_of_Points[i].xcord <= Array_of_Points[j].xcord)&&(Ar ray_of_Points[i].ycord <= Array_of_Points[j].ycord )){
(gdb)
这里也没有打印非支配点的坐标。如果我问的是愚蠢的，我很抱歉，但我希望有人能帮助我理解出了什么问题。提前致谢。
PS如果我应该编辑我的问题，请告诉我。
编辑：我在代码的第 105 行犯了一个严重错误，正如@JGroven 所指出的那样，我写了 j++ 来代替 j--。我已经更正了上面的相同内容，但我的代码没有做它应该做的事情。这是调试器显示的内容：
从 a.out...读取符号完成。
/usr/share/gdb/gdbinit：没有这样的文件或目录。
(gdb) run
启动程序：/home/a.out
输入文件名...inp.dat
非支配点为：
(0.000000, 0.000000)(2.500000, 7.200000)(4.700000, 5.000000)(5.600000, 9.500000)(9 .000000, 5.900000) 以 0 分为主。
(5.600000, 9.500000) 以 0 分为主。
(4.700000, 5.000000) 以 0 分为主。
(2.500000, 7.200000) 以 0 分为主。
(0.000000, 0.000000) 以 0 分为主。
程序结束...以退出代码 0 终止
*** `/home/a.out' 中的错误：free()：下一个大小无效（快速）：0x00000000006034c0 * **程序收到信号 SIGABRT，已中止。
__GI_raise (sig=sig@entry=6) 中的 0x00007ffff7a47c37at ../nptl/sysdeps/unix/sysv/linux/raise.c:56 56 ../nptl/sysdeps/unix/sysv/linux/raise.c: No such file or目录。(gdb)
编辑2：正如@Hitokiri 进一步指出的那样，如果初始化为i - 1，j 将变为-1，因此我已将其更改为i。并且还更改了函数的类型以找到无效级别。
解决方案
在朋友的帮助下，我发现了自己的错误。支配功能并不完全正确，我在那里进行了更改。我写的合并排序函数有些东西不能正常工作，我很快就会弄清楚。与此同时，我已将其替换为插入排序。我在下面发布我更正的代码。
感谢大家的帮助。
#include <stdio.h>
#include <stdlib.h>
#define MAX 20
#define TRUE 1
#define FALSE 0
//segmentation fault...
typedef struct Coordinates{
float xcord;
float ycord;
}POINT;
//globally declaring dynamic array of points
POINT *Array_of_Points;
//globally declaring dynamic array of non-dominated points
POINT *Non_dominated;
//declaring some functions
int dominance(int n);
int Read_File(char filename[]);
/*void Xmerge(int head, int middle, int tail);
void XmergeSort(int);*/
void XInsertion(int n);
int level_of_dominance(int a);
int main(){
char Arr[MAX];
int n, i, d;
printf("Enter file name...");
scanf("%s", Arr);
n = Read_File(Arr);
if(!Read_File(Arr)){ //if error occurs
printf("Terminating program with exit code -1\n");
return -1; //terminate program with return value -1
}
//finds non-dominated points and prints them
d = dominance(n);
printf("The non dominated points are:\n");
for(i = 0; i < d; i++){
printf("(%f, %f)", Non_dominated[i].xcord, Non_dominated[i].ycord);
}
printf("\n");
//print all points with levels of dominance
level_of_dominance(n);
printf("End of program... Terminating with exit code 0\n");
free(Array_of_Points);
free(Non_dominated);
return 0;
}
//function reads file in required manner
int Read_File(char filename[]){
int n; //to store number of points present in file
int count = 0;
float x, y;
FILE *fptr = fopen(filename, "r"); //opening given file in readable format
if(!fptr) //file handling if pointer returns null
{
printf("The file %s can't be opened.\n", filename);
return FALSE;
}
fscanf(fptr, "%d", &n); //reading first line consisting of number of points
Array_of_Points = (POINT*)malloc(n * sizeof(POINT)); //allocating memory to store data of n points
//reading points from file and storing them in globally created dynamic array
while((count < n) && (fscanf(fptr, "%f", &x) == TRUE && fscanf(fptr, "%f", &y) == TRUE)){
Array_of_Points[count].xcord = x;
Array_of_Points[count].ycord = y;
++count;
}
return n; //returns number of points
}
int dominance(int n){ //returns number of non-dominated points
/*METHOD TO FIND DOMINANCE:
* First, arranging points in array by sorting, say, x co-ordinates in DESCENDING ORDER...
* using merge sort algorithm for the same
* The first point in this sorted array is automatically a non dominated point,
* as no other point has x coordinate greater than it
* Then, traverse sorted array and keep track of largest y value, initializing first one to max
* While traversing, the point with y value grater than y max is also non dominated,
* and contributes to new y max and so on...
**/
int foo = 0; //keeps track of number of non-dominated points found so far, initialized to zero
int i;
XInsertion(n);
int ymax = Array_of_Points[0].ycord;
//add first element of the array to Non_dominated array and increase foo count
Non_dominated = (POINT*)malloc(sizeof(POINT));
Non_dominated[0] = Array_of_Points[0];
++foo;
for(i=1 ; i < n; i++){ //note change
if(Array_of_Points[i].ycord > ymax){
ymax=Array_of_Points[i].ycord; /*changes made*/
Non_dominated = (POINT*)realloc(Non_dominated, (foo+1) * sizeof(POINT));
Non_dominated[foo] = Array_of_Points[i];
foo++;
}
}
//all non dominated points stored in array
return foo;
}
int level_of_dominance(int a){ //returns number of points dominating a point
int i, j, flag = 0;
for(i = a - 1; i >= 0; i--){
for(j = i - 1; j >= 0; j--){
if((Array_of_Points[i].xcord <= Array_of_Points[j].xcord)&&(Array_of_Points[i].ycord <= Array_of_Points[j].ycord)){
++flag;
}
}
printf("(%f, %f) is dominated by %d points.\n", Array_of_Points[i].xcord, Array_of_Points[i].ycord, flag);
flag = 0; //resetting number of points for next point
}
}
/*
void XmergeSort(int head, int tail){
int mid;
if(head < tail){
mid = (head +tail)/2;
XmergeSort(head, mid);
XmergeSort(mid + 1, tail);
Xmerge(head, mid, tail);
}
}
//function to merge 2 halves of array
void Xmerge(int l, int m, int r)
{
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
// create temp arrays
POINT *T1, *T2;
T1 = (POINT*)malloc(n1 * sizeof(POINT));
T2 = (POINT*)malloc(n2 * sizeof(POINT));
// Copy data to temp arrays L[] and R[]
for (i = 0; i < n1; i++)
T1[i] = Array_of_Points[l + i];
for (j = 0; j < n2; j++)
T2[j] = Array_of_Points[m + 1+ j];
// Merge the temp arrays back into arr[l..r]
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2)
{
Array_of_Points[k] = ((T1[i].xcord <= T2[j].xcord)?T1[i]:T2[j]);
((T1[i].xcord <= T2[j].xcord)?i++:j++);
k++;
}
// Copy the remaining elements of L[], if there are any
while (i < n1)
{
Array_of_Points[k] = T1[i];
i++;
k++;
}
// Copy the remaining elements of R[], if there are any
while (j < n2)
{
Array_of_Points[k] = T2[j];
j++;
k++;
}
}*/
void XInsertion(int n)
{
int i,j;
POINT a;
//Applying insertion-sort on x co-ordinates to have them arranged in decreasing order
for(i=0;i<n;i++)
{
j=i-1;
a=Array_of_Points[i];
while((Array_of_Points[j].xcord<=a.xcord)&&(j>=0))
{
if(Array_of_Points[j].xcord==a.xcord && Array_of_Points[j].ycord>a.ycord)
break;//in case of tie, arrange in decreasing order
else
{
Array_of_Points[j+1]=Array_of_Points[j];
j--;
}
}
Array_of_Points[j+1]=a;
}
}
这是输出：
输入文件名...inp.dat
非支配点为：
(12.600000, 2.300000)(9.000000, 5.900000)(5.600000, 9.500000)
(2.500000, 7.200000) 占1点。
(4.700000, 5.000000) 以 2 点为主。
(5.600000, 9.500000) 以 0 分为主。
(9.000000, 5.900000) 以 0 分为主。
(12.600000, 2.300000) 以 0 分为主。
程序结束...以退出代码 0 终止
任何改进我的程序和调试技术的建议和技巧都非常受欢迎。
推荐阅读
- sql - SQL中根据主键更新一列的多行
- javascript - 按数据属性对 HTML 元素进行排序
- c# - WindowsFormsHost 控件未显示在 Prism 区域中
- javascript - 在另一页中单击按钮时更改一页的内容
- python - 为什么当我设置 pos=[50,0] 时，psychopy.visual.TextStim 不呈现文本？
- devops - 如何知道 Flow Drain 是否完成？
- spring - Spring Session JdbcHttpSessionConfiguration 导致 JPA bean 无法启动
- node.js - nodejs循环卷曲，异步或阻塞
- sql-server - 禁止的架构名称：SYS、DBO (MsSQL)
- javascript - Firefox 和 Chromium 之间 Uint8Array 到字符串转换的区别