我是一个编程初学者（这不是我的学科），这是我在这里的第一个问题，如果我没有正确地发布它，请原谅。
我正在尝试一个问题（在C语言中），必须为一个点定义一个结构，从一个文件中获取点的输入到一个动态数组中，其中第一行包含点的数量，其余行包含点的坐标，中间有空格。然后我要写一个函数来确定哪些点是不占优势的，定义给定 。
- 一个点P1 = ( x1 , y1 )被一个点P2 = ( x2 , y2 )支配，如果y2 > y1和x2 > x1
- 一个点在一组点中不占优势，如果在该组中没有任何点占优势，则该点为非优势点
而另一个函数是用来确定和打印存储在形成的数组中的每个点的优势水平。我需要打印所有非优势点，然后打印所有点的优势水平。
这是我编写的代码。
#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.....读取符号，完成 usrsharegdbgdbinit： 没有这样的文件或目录. (gdb)运行 启动程序：homea.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)&&(Array_of_Points[i].ycord <= Array_of_Points[j].ycord)){ (gdb)
非主导点的坐标在这里也没有被打印出来.如果我问的问题很愚蠢，我很抱歉，但我希望有人能帮我了解出了什么问题。先谢谢你了。
P.S 如果我应该编辑我的问题，请告诉我。
EDIT: 我在代码的第105行犯了一个严重的错误，正如@JGroven所指出的那样，我在那里用j--代替了j++。我已经纠正了上面的错误，但我的代码并没有做它应该做的事情。这就是调试器显示的情况。
从a. out中读取符号... 完毕 usrsharegdbgdbinit: No such file or directory. (gdb)运行 启动程序：homea.out 输入文件名......inp.dat 非主导点是。 (0.000000，0.000000)(2.500000，7.200000)(4.700000，5.000000)(5.600000，9.500000)(9 .0000，5.900000)被0点支配。 (5.600000，9.500000)以0分为主。 (4.700000，5.000000)以0分为主。 (2.500000, 7.200000)以0分为主。 (0.000000，0.000000)被0分支配。 程序结束... 在`homea.out'中出错：free()：无效的下一个大小(fast)：0x00000000006034c0 * **。
程序收到信号 SIGABRT，中止。 在 __GI_raise (sig=sig@entry=6) 中，0x00007ffff7a47c37。
at ../nptl/sysdeps/unix/sysv/linux/raise.c:56 56 ../nptl/sysdeps/unix/sysv/linux/raise.c: No such file or目录。 (gdb)
EDIT 2：正如@Hitokiri进一步指出的那样，如果初始化为i - 1，j将变成-1，因此我将其改为i，并且还将查找支配级别的函数类型改为void。
在朋友的帮助下，我想明白了自己的错误。支配函数没有完全正确，我已经在那里做了修改。而且我写的合并排序函数也有一些不正确的地方，我将在不久后试着去解决这个问题。同时，我已经用插入排序代替了它。我把我改好的代码贴在下面。
谢谢大家的帮助。
#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结束
欢迎大家对我的程序和调试技术提出任何改进建议和技巧。